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:
“From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
—Johan Huizinga (1872–1945)
“The moment a man begins to talk about technique that’s proof that he is fresh out of ideas.”
—Raymond Chandler (1888–1959)
“Contentment even protects against colds. Has any woman who knew herself to be well dressed ever caught a cold?—I am assuming that she was barely dressed.”
—Friedrich Nietzsche (1844–1900)
““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)
“European society has always been divided into classes in a way that American society never has been. A European writer considers himself to be part of an old and honorable tradition—of intellectual activity, of letters—and his choice of a vocation does not cause him any uneasy wonder as to whether or not it will cost him all his friends. But this tradition does not exist in America.”
—James Baldwin (1924–1987)