Set theory and Infinite cardinals?

Favorite Answer

Let Z be the integers
O be the odd integers
E be the even integers

Then |E| = |O| = |Z \ E|

I have a proof, but it's not a constructive proof.

If X is an infinite set, then |X| = |X × {0, 1}|

This means that there exist a bijective function f:X → X × {0, 1}

So let A be the inverse image, under f, of all points of the form (x, 0).
It follows that X \ A is the inverse image, under f, of all points of the form (x, 1).

We define g:A → X \ A as follows. Let a be an element of A. then f(a) = (x, 0) for
some x in X. Let g(a) = b where b is the unique member of X for which f(b) = (x, 1).
It's easy to show that g is bijective.

Hence |A| = |X \ A|....Show more

It is obviously true if the set X is countably infinite (Pauley Morph gives an explicit example). Here is a simple argument that shows it is true if the set X is a power set of some other non-empty set Z:

Suppose X = 2^Z (being the set of all subsets of Z). Take any element z of Z. Divide X into two sets:
A = elements of 2^Z that contain z.
B = elements of 2^Z that do not contain z.

Then A and B are disjoint and satisfy A U B = X. Further, A and B have the same cardinality (just form the bijection that maps A to B by removing the element z).

***

Thus, it is also true for any set that has the same cardinality as a power set of something. So it is true if your set has the same cardinality as one of the following:

N = {natural numbers}
2^N = {power set of naturals} (same cardinality as reals)
2^2^N
2^2^2^N
2^2^2^2^N

and so on.

***
EDIT: If you believe that any uncountably infinite set is the same cardinality as the power set of something, then the above proves it for all infinite sets. =) Has anyone seen an example of an uncountably infinite set that does NOT have the same cardinality as the power set of something? If not, then at least I have proved the result for all sets you have ever seen, which is pretty good I guess...
***
@Pauley: The crux of your argument is in your first line that you assumed away with no proof. =) How do you know |X| = |X x {0,1}|? I agree that if we can double the set and put it into one-to-one correspondence with its doubling, then we can also "halve" the set. But the hard part is showing we can put the doubling into one-to-one correspondence with itself. I'm wondering if more structure is needed to prove this...

@Pauley: PS: I don't know why someone gave you a thumbs down...that was not me. =) But I still don't agree that you can just assert |X| = |X x {0,1}|...

***
EDIT: Also for unions: Say that set E has the "halving property" if it can be decomposed into disjoint sets E = A U B where |A| = |B|. Then it is easy to show that if E_n is a countable sequence of distinct sets (indexed by n), such that each E_n has the halving property, then the union U E_n also has the halving property (Just write U E_n = U [A_n U B_n] = (U A_n) U (U B_n), and note that U A_n and U B_n both have the same cardinality).

Thus the halving property works for:
1) any set that has the same cardinality as a set that is a power set of something,
2) any set that has the same cardinality as a set that can be written as the countable union of sets that have the the halving property.

I don't think I have used the "axiom of choice" anywhere.

By induction, this proves for all "aleph" type sets that are unions of all sets of the form N, 2^N, 2^2^N, and so on, or unions of aleph sets, and so on. I _think_ the generalized continuum hypothesis says that these are the only possible sets, but I'm not sure. The web is not very clear on these points. I am pretty sure these are the only sets people know about.

***
Pauley's wiki link says the "axiom of choice" implies |A x B| = max[|A|, |B|], and the doubling property is a special case of this. But this is not a satisfying answer because nothing is said about how to prove such a thing, even if we allow the axiom of choice (and proving such a thing was the reason this question was interesting in the first place). Of course, my answer is also unsatisfying because, although it does not seem to use the axiom of choice, it only proves it for all sets we know about, which begs the question "are these the only possible sets?"

***
EDIT: From the web, it seems that the only known way to prove this is to use "Zorn's lemma," which the web says is equivalent to the axiom of choice. In this case Zorn's lemma says the following:

If we take the set X and consider collections of disjoint subsets of X that each contain 2 elements, then Zorn says there is a "maximal" collection, being a collection which cannot be trivially expanded by forming any more subsets of size 2 from unused elements. Then take any such maximal collection of disjoint pairs of elements in X. Then this maximal collection either contains all points in X, or at most leaves out one point p. Thus, Zorn says:

X = U_{z in Z} {a_z, b_z} U p

where Z is an infinite index set, (a_z, b_z) is the pair of points in X associated with index z, and p is just one point (or possibly no point). Then define:

A = U_{z in Z} a_z
B = p U U_{z in Z} b_z

It is easy to see that A and B are disjoint, A U B = X, and |A| = |B| (note that possibly adding one point p to the infinite set B does not change its cardinality).

Note that I am getting the use of Zorn's lemma in this result from Prop 5 of the following notes:
http://math.uga.edu/~pete/settheorypart2.pdf...Show more