Editing Transfinite induction (section)

==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.<ref>In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation ''R'' is set-like: for any ''x'', the collection of all ''y'' such that ''y''&nbsp;''R''&nbsp;''x'' must be a set.</ref> 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 number]]s (this is where the axiom of choice enters via the [[well-ordering theorem]]), giving a sequence <math> \langle r_\alpha \mid \alpha < \beta \rangle </math>, where &beta; is an ordinal with the [[cardinality of the continuum]].  Let ''v''<sub>0</sub> equal ''r''<sub>0</sub>.  Then let ''v''<sub>1</sub> equal ''r''<sub>''α''<sub>1</sub></sub>, where ''α''<sub>1</sub> is least such that ''r''<sub>''α''<sub>1</sub></sub>&nbsp;&minus;&nbsp;''v''<sub>0</sub> 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''<sub>''α''+1</sub>, given the sequence up to ''α'', but will specify only a ''condition'' that ''A''<sub>''α''+1</sub> 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 set|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.