Relationship To The Axiom of Choice
Proofs or constructions using induction and recursion often use the axiom of choice to produce a well-ordered relation that can be treated by transfinite induction. However, if the relation in question is already well-ordered, one can often use transfinite induction without invoking the axiom of choice. For example, many results about Borel sets are proved by transfinite induction on the ordinal rank of the set; these ranks are already well-ordered, so the axiom of choice is not needed to well-order them.
The following construction of the Vitali set shows one way that the axiom of choice can be used in a proof by transfinite induction:
- First, well-order the real numbers (this is where the axiom of choice enters via the well-ordering theorem), giving a sequence, where β is an ordinal with the cardinality of the continuum. Let v0 equal r0. Then let v1 equal rα1, where α1 is least such that rα1 − v0 is not a rational number. Continue; at each step use the least real from the r sequence that does not have a rational difference with any element thus far constructed in the v sequence. Continue until all the reals in the r sequence are exhausted. The final v sequence will enumerate the Vitali set.
The above argument uses the axiom of choice in an essential way at the very beginning, in order to well-order the reals. After that step, the axiom of choice is not used again.
Other uses of the axiom of choice are more subtle. For example, a construction by transfinite recursion frequently will not specify a unique value for Aα+1, given the sequence up to α, but will specify only a condition that Aα+1 must satisfy, and argue that there is at least one set satisfying this condition. If it is not possible to define a unique example of such a set at each stage, then it may be necessary to invoke (some form of) the axiom of choice to select one such at each step. For inductions and recursions of countable length, the weaker axiom of dependent choice is sufficient. Because there are models of Zermelo–Fraenkel set theory of interest to set theorists that satisfy the axiom of dependent choice but not the full axiom of choice, the knowledge that a particular proof only requires dependent choice can be useful.
Read more about this topic: Transfinite Induction
Famous quotes containing the words relationship to the, relationship to, relationship, axiom and/or choice:
“... the Wall became a magnet for citizens of every generation, class, race, and relationship to the war perhaps because it is the only great public monument that allows the anesthetized holes in the heart to fill with a truly national grief.”
—Adrienne Rich (b. 1929)
“Women, because of their colonial relationship to men, have to fight for their own independence. This fight for our own independence will lead to the growth and development of the revolutionary movement in this country. Only the independent woman can be truly effective in the larger revolutionary struggle.”
—Women’s Liberation Workshop, Students for a Democratic Society, Radical political/social activist organization. “Liberation of Women,” in New Left Notes (July 10, 1967)
“Every man is in a state of conflict, owing to his attempt to reconcile himself and his relationship with life to his conception of harmony. This conflict makes his soul a battlefield, where the forces that wish this reconciliation fight those that do not and reject the alternative solutions they offer. Works of art are attempts to fight out this conflict in the imaginative world.”
—Rebecca West (1892–1983)
“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)
“The question of place and climate is most closely related to the question of nutrition. Nobody is free to live everywhere; and whoever has to solve great problems that challenge all his strength actually has a very restricted choice in this matter. The influence of climate on our metabolism, its retardation, its acceleration, goes so far that a mistaken choice of place and climate can not only estrange a man from his task but can actually keep it from him: he never gets to see it.”
—Friedrich Nietzsche (1844–1900)