BrainDen.com - Brain Teasers

## Question

Two sets have the same size (cardinality) if their elements can be placed

in a 1-1 correspondence. (A bijection exists.)

For finite sets this is a simple concept.

The sets {a b c d e f g} and {days of the week} are the same size;

they both have a 1-1 correspondence with the first 7 counting numbers.

For infinite sets things get dicey.

The counting numbers, the even counting numbers (seemingly half as many)

and the rational numbers (seemingly infinitely more numerous) have equal cardinality.

Bijections among these sets can be easily described in words (or with a simple picture.)

Can you verbally describe a bijection of the counting numbers with all of their subsets (their superset power set)?

Or, remembering that neither set is finite, verbally prove no such bijection exists?

## Recommended Posts

• 0

I think I got this.. pleased as punch Let, N be the set of counting numbers, {1, 2, 3, ..}. Let S(N) be its super set.

The one-to-one mapping from N -> S(N) is easy, for each 'x' in N, we map it to {x} in S(N).

For the mapping S(N) -> N, take any element {x0, x1, .., xn} in set S(N). Map it to: p(x0)*p(x1)*..*p(xn), where p(m) denotes the mth prime number (p(1) = 2, p(2) = 3, etc). This maps each element in S(N) to a unique element in N.

##### Share on other sites

• 0

no you can't

if you could, you could map the counting numbers to the reals, which are uncountably infinite.

to prove this, simply let each subset represent a decimal number, with the decimal point after the first number in the set, and the rest of the number in the set of the remaining numbers.

for example the subset {1, 3, 5, 7, 11, 13...}  would be represented as 1.3571113...

to prove that the real numbers are uncountably infinite, imagine you try to construct a countably infinite number of real numbers.

say the following list. 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.01 ... now i will construct a number not on the list. take the digit in each decimal place, add 1 unless 9, then go back to 0. so for the above sequence, the number 2.21111... will never appear.

Edited by phil1882
##### Share on other sites

• 0

I think I got this.. pleased as punch Let, N be the set of counting numbers, {1, 2, 3, ..}. Let S(N) be its super set.

The one-to-one mapping from N -> S(N) is easy, for each 'x' in N, we map it to {x} in S(N).

For the mapping S(N) -> N, take any element {x0, x1, .., xn} in set S(N). Map it to: p(x0)*p(x1)*..*p(xn), where p(m) denotes the mth prime number (p(1) = 2, p(2) = 3, etc). This maps each element in S(N) to a unique element in N.

karthikgururaj proposes two injections (both of which are far from being surjections also) rather than a single bijection.

So the question is, are two (one each direction) injections equivalent to a bijection?

##### Share on other sites

• 0

no you can't

if you could, you could map the counting numbers to the reals, which are uncountably infinite.

to prove this, simply let each subset represent a decimal number, with the decimal point after the first number in the set, and the rest of the number in the set of the remaining numbers.

for example the subset {1, 3, 5, 7, 11, 13...}  would be represented as 1.3571113...

to prove that the real numbers are uncountably infinite, imagine you try to construct a countably infinite number of real numbers.

say the following list. 1 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.01 ... now i will construct a number not on the list. take the digit in each decimal place, add 1 unless 9, then go back to 0. so for the above sequence, the number 2.21111... will never appear.

Since the subset is unordered, a single subset can map to more than one decimal number. For example, {1, 3, 5, 7, 11, 13} can map to either 1.3571113 or 3.5171113 or 7.1113531 or.. etc. So it is one-to-many mapping, not one-to-one.

Further, a given subset will represent only a rational number. Irrationals will require mapping of subset with infinite number of elements - which is not legal.

##### Share on other sites

• 0

I think I got this.. pleased as punch Let, N be the set of counting numbers, {1, 2, 3, ..}. Let S(N) be its super set.

The one-to-one mapping from N -> S(N) is easy, for each 'x' in N, we map it to {x} in S(N).

For the mapping S(N) -> N, take any element {x0, x1, .., xn} in set S(N). Map it to: p(x0)*p(x1)*..*p(xn), where p(m) denotes the mth prime number (p(1) = 2, p(2) = 3, etc). This maps each element in S(N) to a unique element in N.

karthikgururaj proposes two injections (both of which are far from being surjections also) rather than a single bijection.

So the question is, are two (one each direction) injections equivalent to a bijection?

I thought about this when posting the solution.. In truth, it doesn't appear to be an equivalent to bijection

If an injection can be defined from set A to B, then it implies cardinality of B must be greater than or equal to A. If an injection can be defined both ways, it implies the cardinality of both must be same.. This is trivial for finite sets, I'm not sure for infinite sets.

##### Share on other sites

• 0

See if there's a similar case (of oppositely directed injections) that applies to finite sets.

For finite sets it is easy to see that a bijection exists, if there are two injections, one from A to B, and other from B to A.

If f: A -> B is an injection from A to B and g: B -> A is an other injection from B to A, then the number of elements in A and B are both same. So, a bijection can be defined from A to B.

I googled a bit on this and read about Schröder–Bernstein theorem, which essentially asserts that if there are two injections in reverse directions, then a bijection exists.

##### Share on other sites

• 0

@karthickgururaj,

S-B theorem seems to be exactly what we're looking for.

The part that seems difficult, but I can't yet say it's impossible, is the injection from the superset into the original set.

In your solution, can you identify (or give examples of) sets A and B? That would complete the proof.

Or, apply it to say A = {1, 2, 3}.

##### Share on other sites

• 0

The set of all subsets of a set S is called a power set (powerset) of S.

According to Cantor's theorem, cardinality of the power set of any set S
is strictly greater then cardinality of S.

PS The Schröder–Bernstein theorem was called Cantor–Bernstein theorem at my set theory classes.

##### Share on other sites

• 0

The set of all subsets of a set S is called a power set (powerset) of S.

According to Cantor's theorem, cardinality of the power set of any set S

is strictly greater then cardinality of S.

PS The Schröder–Bernstein theorem was called Cantor–Bernstein theorem at my set theory classes.

Interesting! Thanks for the link. Reading the wiki article exposes one assumption in my solution. I assumed that, while the super set has infinite number of elements, each individual element of the super set has a finite number of elements. In other words, I assumed that (for example), "the set of all even numbers" is NOT a member of super set.

If that assumption is removed, my solution won't work.

##### Share on other sites

• 0

@karthickgururaj,

S-B theorem seems to be exactly what we're looking for.

The part that seems difficult, but I can't yet say it's impossible, is the injection from the superset into the original set.

In your solution, can you identify (or give examples of) sets A and B? That would complete the proof.

Or, apply it to say A = {1, 2, 3}.

For a finite set, like A = {1, 2, 3}, clearly the super set has higher number of elements (in this case 8), so we can't define an injection from the superset to the original set.

For an infinite set, like N = {1, 2, 3, .. }, it is not immediately clear whether we can (or not) define the injection from the superset of N (lets call it S(N)) to N.

(So, I have just restated part of the OP!)

S(N) will be like, { {1}, {2}, {1, 2, 3, 100}, {4, 5, 6}, {10^9, 10^8, 10^7}, ... }. Specifically, the assumption here is that the super set does NOT have an element like: {2, 4, 6, 8, ...}.

Then, any specific element of S(N) will have a finite set of elements: {x0, x1, .., xn}. This can be mapped to a unique number in N: : p(x0)*p(x1)*..*p(xn), where p(m) denotes the mth prime number (p(1) = 2, p(2) = 3, etc).

However, I do not know if the assumption is valid. After reading about Cantor's theorem, it appears not.

##### Share on other sites

• 0

Post 12 clears up the suggested injection from a powerset to its set.

Which leaves us just with the need for a simple word proof.

The one I have in mind refers closely to Russell's paradox.

I used the wrong term (superset) for powerset in my above posts.

Brain fart.

##### Share on other sites

• 0

Well, what are the chances: I just wrote about this in my blog.

http://en.m.wikipedia.org/wiki/Cantor%27s_theorem

##### Share on other sites

• 0

Sorry for spoiling the fun, but here's a modified excerpt that explains the theorem for the case of natural numbers:

A mapping between the set of all natural numbers and its power set might look something like this:

| 1 2 3 4 5 ...

1 | O X X X O ...

2 | X X X X X ...

3 | X O O O O ...

4 | O X O X O ...

5 | X O O X X ...

... ......

To the left are the natural numbers, and to the right are sets of natural numbers. In each row, a column is marked with an O if the corresponding set contains the corresponding natural number or an X if it doesn't. For example, the number 1 is mapped to a set containing 1 and 5 but not 2, 3, or 4.

If we take the diagonal and switch all the O's to X's and vice versa, we will end up with a set that is different from all the sets in the list, which proves that any given mapping is non-surjective.

##### Share on other sites

• 0

What fun? is a subset of A that does not map to an element.

It uses symbols, and the diagonal proof uses symbols.

The narrative is words-only: B comprises A's red elements.

I'm given to understand there are serious mathematicians who reject these proofs, and reject Cantor's orders of infinity. ## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account. ×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.