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 thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
—Lenny Bruce (1925–1966)
“The chief contribution of Protestantism to human thought is its massive proof that God is a bore.”
—H.L. (Henry Lewis)
“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)
“It is an axiom in political science that unless a people are educated and enlightened it is idle to expect the continuance of civil liberty or the capacity for self-government.”
—Texas Declaration of Independence (March 2, 1836)
“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)