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.

September 1

Konig's lemma

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)[reply]

I am not at all well up on this, but I believe it is because we are making infinitely many such choices. I do know that (because there is no uniform way of telling a left sock from a right sock, unlike for shoes) you need choice to get one sock from each of infinitely many pairs (apart, of course, from the fact that they are in a nice Euclidean space...) Straightontillmorning (talk) 13:39, 1 September 2012 (UTC)[reply]

Yep. You need choice to make infinitely many choices; it doesn't matter whether each of those choices is from finitely or infinitely many possibilities.--121.73.35.181 (talk) 21:02, 1 September 2012 (UTC)[reply]

This is a complete guess: if there's only one suitable vertex, you can identify it by trying out paths of increasing length for every vertex. If only one is suitable, this search will end eventually. If more then one is suitable, it won't. Ssscienccce (talk) 14:59, 1 September 2012 (UTC)[reply]