Set Theory 101

[bonanova]

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?

[karthickgururaj]

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 {x₀, x₁, .., x_n} in set S(N). Map it to: p(x₀)*p(x₁)*..*p(x_n), where p(m) denotes the m^th prime number (p(1) = 2, p(2) = 3, etc). This maps each element in S(N) to a unique element in N.

 

[phil1882]

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 November 24, 2014 by phil1882

[bonanova]

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 {x₀, x₁, .., x_n} in set S(N). Map it to: p(x₀)*p(x₁)*..*p(x_n), where p(m) denotes the m^th 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?

[karthickgururaj]

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.

 

[karthickgururaj]

 

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 {x₀, x₁, .., x_n} in set S(N). Map it to: p(x₀)*p(x₁)*..*p(x_n), where p(m) denotes the m^th 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.

[bonanova]

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

[karthickgururaj]

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.

[bonanova]

@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}.

[witzar]

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.

[karthickgururaj]

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.

[karthickgururaj]

@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: {x₀, x₁, .., x_n}. This can be mapped to a unique number in N: : p(x₀)*p(x₁)*..*p(x_n), where p(m) denotes the m^th 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.

 

[bonanova]

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.

[bonanova]

I decided to post a separate thread to show how Russell's paradox relates to the powerset proof.

[gavinksong]

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

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

[gavinksong]

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.

[bonanova]

What fun?

 

The succinct proof says 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.