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:
“In the reproof of chance
Lies the true proof of men.”
—William Shakespeare (1564–1616)
“If any proof were needed of the progress of the cause for which I have worked, it is here tonight. The presence on the stage of these college women, and in the audience of all those college girls who will some day be the nation’s greatest strength, will tell their own story to the world.”
—Susan B. Anthony (1820–1906)
“Quite generally, the familiar, just because it is familiar, is not cognitively understood. The commonest way in which we deceive either ourselves or others about understanding is by assuming something as familiar, and accepting it on that account; with all its pros and cons, such knowing never gets anywhere, and it knows not why.... The analysis of an idea, as it used to be carried out, was, in fact, nothing else than ridding it of the form in which it had become familiar.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
““You are bothered, I suppose, by the idea that you can’t possibly believe in miracles and mysteries, and therefore can’t make a good wife for Hazard. You might just as well make yourself unhappy by doubting whether you would make a good wife to me because you can’t believe the first axiom in Euclid. There is no science which does not begin by requiring you to believe the incredible.””
—Henry Brooks Adams (1838–1918)
“I am a good horse to travel, but not from choice a roadster. The landscape-painter uses the figures of men to mark a road. He would not make that use of my figure.”
—Henry David Thoreau (1817–1862)