Editing Kőnig's lemma (section)

==Relationship with the axiom of choice==
Kőnig's lemma may be considered to be a choice principle; the first proof above illustrates the relationship between the lemma and the [[axiom of dependent choice]]. At each step of the induction, a vertex with a particular property must be selected. Although it is proved that at least one appropriate vertex exists, if there is more than one suitable vertex there may be no canonical choice. In fact, the full strength of the axiom of dependent choice is not needed; as described below, the [[axiom of countable choice]] suffices.

If the graph is countable, the vertices are well-ordered and one can canonically choose the smallest suitable vertex. In this case, Kőnig's lemma is provable in second-order arithmetic with [[arithmetical comprehension]], and, a fortiori, in [[Zermelo–Fraenkel set theory|ZF set theory]] (without choice).

Kőnig's lemma is essentially the restriction of the axiom of dependent choice to entire relations <math>R</math> such that for each <math>x</math> there are only finitely many <math>z</math> such that <math>xRz</math>. Although the axiom of choice is, in general, stronger than the principle of dependent choice, this restriction of dependent choice is equivalent to a restriction of the axiom of choice.
In particular, when the branching at each node is done on a finite subset of an arbitrary set not assumed to be countable, the form of Kőnig's lemma that says "Every infinite finitely branching tree has an infinite path" is equivalent to the principle that every countable set of finite sets has a choice function, that is to say, the axiom of countable choice for finite sets.<ref>{{harvtxt|Truss|1976}}, p.&nbsp;273; {{harvtxt|Howard|Rubin|1998}}, pp. 20, 243; compare {{harvtxt|Lévy|1979}}, Exercise IX.2.18.</ref> This form of the axiom of choice (and hence of Kőnig's lemma) is not provable in ZF set theory.