# Infinite Set has greater or equal cardinality that of N

For any infinite set, we can find a 1-1 function (not necessary onto) from N (set of natural no.) to that set. The proof of this theorem I know using axiom of choice.

Can we prove it without using Axiom of choice (not using axiom of replacement and GCH). If not this means this statement is consistent with intial axiom of ZFC (without AC). But is this statement prove somehow Axiom of choice?

Note: A finite set is a set which can be put in 1:1 correspondence with a subset of N that has an upper bound. And infinite set is set which is not finite.

• Just to be sure, you aren't claiming there is a 1-1 correspondence between all infinite sets right? – graydad Sep 2 '14 at 23:49
• @user166967 Yes not 1-1 correspondence just a 1-1 function from N to infinte set – Sushil Sep 2 '14 at 23:50
• Wait a minute, is there a problem with your definition of finite set? The set of all integers greater than 2 is easily shown to be 1:1 with the set of all integers greater than 1, which is a proper subset of $\Bbb{N}$ is it not? But we know that The set of all integers greater than 2 is not finite. – Mark Fischler Sep 3 '14 at 0:33
• The correct definition is that a finite set is a set which can be put in 1:1 correspondence with a subset of $\Bbb{N}$ that has an upper bound. – Mark Fischler Sep 3 '14 at 0:39
• Your question is very unclear. If you are asking whether or not the statement "Every infinite set has a countably infinite subset" is provable without the axiom of choice, the answer is no; if you ask whether it proves the axiom of choice, the answer is again no. In fact this statement is provable from the axiom of choice for countable families, but does not prove the axiom of choice for countable families itself. – Asaf Karagila Sep 3 '14 at 4:25

Does $\sf ZF$ proves that "Every infinite set has a countably infinite subset"? If not, then does $\sf ZF$ with "Every infinite set has a countably infinite subset" prove the axiom of choice?

The answer to both is negative.

Both proofs are non-trivial, and require substantial knowledge of independence proofs and models of $\sf ZF$. But just minor bits of history:

1. Fraenkel proved that if it consistent that the answer of the first question is false, and the axiom of choice fails, but only if we weaken set theory to allow objects which are not sets (called atoms, or urelements).

Cohen proved this in $\sf ZF$ some 40 years afterwards in his original papers about forcing. He took the ideas from Fraenkel's work (after it was polished and corrected by Mostowski and Specker in the meantime) and applied them together with his new method of forcing.

You can find both these in the book "The Axiom of Choice" by Jech.

2. In the other direction, Jech's historical notes from his "Axiom of Choice" book say that Pincus proved this in 1969 (see p.132 in the book). I also know that Monro also proved this in 1975 directly using forcing and relative constructibility arguments.

All proofs mentioned here are not trivial at all, and without further knowledge about forcing, relative constructibility, permutation models and symmetric models, it's hard to explain how these proofs go. But if you want to study these topics, the book mentioned by Jech is a good start, as well his "Set Theory" book, and Halbeisen's book "Combinatorial Set Theory".

• Thanks a lot about this detail. And the suggested list of books – Sushil Sep 3 '14 at 15:10