Topics Logic

Question Is it possible to prove within ZF(C) that the set of all proper infinite subsets of set N has cardinality that is strictly greater than |N|?

Accepted:
December 12, 2015

Comments

I assume that N here denotes

I assume that N here denotes the set of natural numbers: N = {0, 1, 2, 3, ...}.

Yes, it is possible to prove this. And the axiom of choice isn't needed, so you can prove it in ZF. Here's one way to do it: Let E = {2, 4, 6, ...} and O = {1, 3, 5, ...}. Thus, E and O are the sets of even and odd positive integers. (Notice that I have left out 0). Now consider the collection of all sets of the form E U X, where X is a subset of O. Every set in this collection is infinite, since it includes all even integers. And every set is a proper subset of N, since it doesn't include 0. There is one such set for each subset X of O, so the cardinality of this collection of sets is the same as the cardinality of the set of all subsets of O (the power set of O). And since O can be put into one-to-one correspondence with N, the cardinality of the power set of O is the same as the cardinality of the power set of N, which, as Cantor showed, is strictly greater than |N|.

Note: When I say that the cardinality of a set A is strictly greater than the cardinality of a set B, what I mean is: There is a one-to-one correspondence between B and a subset of A, but no one-to-one correspondence between B and A.

Question Is it possible to prove within ZF(C) that the set of all proper infinite subsets of set N has cardinality that is strictly greater than |N|? Accepted:December 12, 2015

Question Is it possible to prove within ZF(C) that the set of all proper infinite subsets of set N has cardinality that is strictly greater than |N|?

Accepted:
December 12, 2015