Mathematics desk | ||
---|---|---|
< August 31 | << Aug | September | Oct >> | September 2 > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
In the proof of Konig's lemma it is mentioned that:
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 the proof mentioned, it is clear that there are only finitely many such vertices to consider at any given stage.(Cf: "Every one of the infinitely many vertices of G can be reached from v1 with a simple path, and each such path must start with one of the finitely many vertices adjacent to v1."..."We may thus pick one of these vertices and call it v2." That is, the choice is being made among finitely many vertices. Why then do we need the axiom of choice or some weaker version of it to prove the lemma? Thanks-- Shahab ( talk) 13:07, 1 September 2012 (UTC)
Mathematics desk | ||
---|---|---|
< August 31 | << Aug | September | Oct >> | September 2 > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
In the proof of Konig's lemma it is mentioned that:
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 the proof mentioned, it is clear that there are only finitely many such vertices to consider at any given stage.(Cf: "Every one of the infinitely many vertices of G can be reached from v1 with a simple path, and each such path must start with one of the finitely many vertices adjacent to v1."..."We may thus pick one of these vertices and call it v2." That is, the choice is being made among finitely many vertices. Why then do we need the axiom of choice or some weaker version of it to prove the lemma? Thanks-- Shahab ( talk) 13:07, 1 September 2012 (UTC)