Proof of Equivalence To Infinity, Assuming Axiom of Countable Choice
That every Dedekind-infinite set is infinite can be easily proven in ZF: every finite set has by definition a bijection with some finite ordinal n, and one can prove by induction on n that this is not Dedekind-infinite.
By using the axiom of countable choice one can prove the converse, namely that every infinite set X is Dedekind-infinite, as follows:
First, define a function over the natural numbers (that is, over the finite ordinals) f: N → Power(X), so that for every natural number n, f(n) is the set of finite subsets of X of size n (i.e. that have a bijection with the finite ordinal n). f(n) is never empty, or otherwise X would be finite (as can be proven by induction on n).
The image of f is the countable set {f(n)|n ∈ N}, whose members are themselves infinite (and possibly uncountable) sets. By using the axiom of countable choice we may choose one member from each of these sets, and this member is itself a finite subset of X. More precisely, according to the axiom of countable choice, a (countable) set exists, G = {g(n)|n ∈ N}, so that for every natural number n, g(n) is a member of f(n) and is therefore a finite subset of X of size n.
Now, we define U as the union of the members of G. U is an infinite countable subset of X, and a bijection from the natural numbers to U, h:N→U, can be easily defined. We may now define a bijection B:X→X\h(0) that takes every member not in U to itself, and takes h(n) for every natural number to h(n+1). Hence, X is Dedekind-infinite, and we are done.
Read more about this topic: Dedekind-infinite Set
Famous quotes containing the words proof of, proof, assuming, axiom and/or choice:
“The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (1686–1743)
“If we view our children as stupid, naughty, disturbed, or guilty of their misdeeds, they will learn to behold themselves as foolish, faulty, or shameful specimens of humanity. They will regard us as judges from whom they wish to hide, and they will interpret everything we say as further proof of their unworthiness. If we view them as innocent, or at least merely ignorant, they will gain understanding from their experiences, and they will continue to regard us as wise partners.”
—Polly Berrien Berends (20th century)
“You see how this House of Commons has begun to verify all the ill prophecies that were made of it—low, vulgar, meddling with everything, assuming universal competency, and flattering every base passion—and sneering at everything noble refined and truly national. The direct tyranny will come on by and by, after it shall have gratified the multitude with the spoil and ruin of the old institutions of the land.”
—Samuel Taylor Coleridge (1772–1834)
“It’s an old axiom of mine: marry your enemies and behead your friends.”
—Robert N. Lee. Rowland V. Lee. King Edward IV (Ian Hunter)
“A girl loves most often because she is loved,Mnot from choice on her part. She is won by the flattery of the man’s desire.”
—Anthony Trollope (1815–1882)