Talk:Kőnig's lemma

Claim about hyperarithmetical paths

"It is known that there are finitely branching computable subtrees of w^<w that have no arithmetical path" -- I believe this is false and needs amending.

Suppose T is computable and finitely branching. Then with a Sigma-1 oracle we can answer queries of form, "does node n have a successor node of index > m?"; using this oracle we can enumerate all successors of any given node n and recognize when there are no more. So our tree's branching is Sigma-1-computably bounded, and so by the Sigma-1-relativized version of the result "Any computably-bounded-branching recursive tree has a Sigma-1-computable infinite path", our tree has a Sigma-1^{Sigma-1} = Sigma-2 -computable path.

I believe the correct result is "there are computable subtrees (not locally finite) of w^<w that have infinite paths but no arithmetical infinite path". But I don't have a reference.

---

Andy Drucker —Preceding informally signed comment added by 66.117.149.88 (talk) 04:37, 23 December 2006

Yes, this was a typo, and your argument is sound. Please feel free to fix these things if you find them. I added a reference to one canonical source for a computable tree with paths but no hyperarithmetical ones. — Carl (CBM · talk) 23:29, 2 February 2009 (UTC)

Potential problem with the proof of Konig's lemma presented on this page

The proof shows that for any vertex v1, and for any integer n, there exists a simple path of length n starting at v1. The proof then claims that by induction an infinite path exists. This is FALSE, induction on n shows that a claim is true for arbitrarily large finite values, but does not prove a anything about the infinite case.

The proof thus glosses over the most essential part of the proof of Konig's lemma, showing that arbitrarily long finite simple paths ==> an infinite simple path. Please explain if my analysis is mistaken. Otherwise the Wikipedia proof should be corrected. Thanks —Preceding unsigned comment added by 128.135.199.198 (talk) 07:15, 23 November 2008

The fact the the trees produced by induction form a chain under the partial order of inclusion can possibly be used in the proof.—Preceding unsigned comment added by 128.135.199.198 (talk) 07:18, 23 November 2008

The proof is fine. It shows that any v_i with infinitely many descendants has a child v_i+1 (not equal to any v_j for j <= i) with infinitely many descendants. We assume v_0 has infinitely many descendants. So induction gives a sequence {v_i} that is an infinite path by construction. "This" is FALSE in general of course, but not in the case where each vertex has finitely many neighbors. Previous comment is setting up a standard Zorn type argument. — Preceding unsigned comment added by 173.18.240.48 (talk) 12:10, 5 October 2012 (UTC)

No, the proof is not fine. The note after it about the Axiom of Choice, and the discussion below, explain why it is not fine. It needs to be modified to use the restricted form of dependent choice or the axiom of countable choice for finite sets. --Dfeuer (talk) 18:50, 27 May 2013 (UTC)

I agree that the proof is correct, and that the last paragraph answers the question it is supposed to answer, with one caveat: because the last line of the argument relies the axiom of countable choice, this section should be called "Proof", rather "Construction". Since the argument uses the countable axiom of choice, is already slightly controversial whether it constitutes a proof, but this is the mainstream view. Calling it a "construction", however, is inflammatory: it strongly suggests that the proof is constructive, which (like the original poster) I expected based on the title. Some good mathematicians (though a decided minority) would say that simply means the argument is not valid. That may be what caused the initial confusion: from the title of the section, the reader was (naturally) expects a (computable) construction. — Preceding unsigned comment added by 75.108.232.187 (talk) 13:10, 14 January 2023 (UTC)

WikiProject class rating

This article was automatically assessed because at least one WikiProject had rated the article as start, and the rating on other projects was brought up to start class. BetacommandBot 04:14, 10 November 2007 (UTC)

fan theorem

It would be useful to have a separate page for Brouwer's fan theorem. Tkuvho (talk) 13:18, 20 September 2010 (UTC)

König's lemma vs. countable choice for finite sets

I believe there is something not completely accurate with the assertion in the last section about the equivalence of König's lemma and countable choice for finite sets. The cited exercise in Levy's book only refers to one implication. What about the converse? ,i.e., does really countable choice for finite sets imply König's lemma? I suspect it doesn't.Godelian (talk) 19:25, 27 October 2010 (UTC)

I am sure I can find a reference for this (there are some promising ones on google). Here is the proof I know.

Let T be an infinite, finitely branching tree. Since we're in ZF anyway, we can cut down T in the usual way so that it has no dead ends and is still infinite. This requires no choice. Now given σ in T, let S(σ) be the set of all immediate extensions of σ. Since T is finitely branching and we got rid of all dead ends, each S(σ) is finite and nonempty, so by assumption we can find a choice function c on the collection of all the sets S(σ) for σ ∈ T. Now, working by recursion on ω, we can define a function f from ω to T so that f(0) is the root of T and f(n+1) is c(S(f(n))). This is entirely choice-free after we have made c, so it can be done in ZF. The function f is the desired path in T.

This is not essentially different than the proof in ZF that any infinite, finitely branching tree on a well-ordered set has an infinite path. Also, the proof given by Levy, though slightly different than mine, can also be edited pretty minimally so that it only uses ZF and the choice principle in question. — Carl (CBM · talk) 01:40, 28 October 2010 (UTC)

Thanks for the details, but I'm not sure I follow the prove above. For example, how can one assure that the family {σ/ σ ∈ T} is countable? Don't we just know it is infinite?. Its countability would make the appeal to a choice principle unnecessary, since we can just take the minimal element in each selection step in Levy's proof of König's lemma (the one exposed in the article). Also, perhaps I'm not familiar with the terminology, but what does it mean to remove a dead end? Removing a point with no successors?

On the other hand, the book cited in the last paragraph contains an exercise about how König's lemma implies countable choice for finite sets. Is there another book by Levy that contains the proof of the converse you're referring to? Godelian (talk) 19:19, 28 October 2010 (UTC)

Yes, I see what you mean; I used choice for arbitrary families of finite sets. I'm going to get a copy of MR0429557. If you can't see the actual review on the page, it starts off

"König's infinity lemma states that any infinite tree with only finite branching has an infinite branch. It is easily seen to be equivalent to the axiom of choice for countable families of finite sets. This paper investigates what happens when further restrictions are imposed on the type of branching allowed in König's lemma. ..."

Once I have the actual paper, I'll see if it doesn't have the actual proof or a better reference in it. — Carl (CBM · talk) 21:29, 28 October 2010 (UTC)

P.S. after a little more thought, it seems that we can prove by induction that for each n the nth level of the tree is finite, and so with a little more work we can actually get the choice function in my proof as a choice function on a countable sequence of finite sets. But looking up a print reference for the article is certainly worthwhile, and your point about the article not being clear about all this is valid. — Carl (CBM · talk) 21:32, 28 October 2010 (UTC)

I'm still suspicious on whether having a countable collection of finite sets makes the whole union countable, in the same way we know that countable families of countable sets is not necessarily countable. What I find odd is that dependent choice is strictly stronger than countable choice in the general case, and the restriction to countable families of finite sets appears to make them equivalent in strength. But let us see if the paper above has the answer; I will try to get it. Godelian (talk) 16:23, 29 October 2010 (UTC)

I requested it as well (there isn't a local copy here) and I expect to have it in a few days. You're certainly right that in ZF we cannot prove that a countable union of finite sets is countable, because in ZF it is consistent to have a sequence of pairs with no choice function. — Carl (CBM · talk) 17:26, 29 October 2010 (UTC)

I didn't get the paper but found instead another reference in the book "Combinatorics and graph theory - 2nd edition" by J. Harris, J. Hirst and M. Mossinghorff. It is theorem 3.17 on page 302 there. The implication I was doubting about is left as well as an exercise, but the hint refers exactly to the same proof you mentioned, making the remark that it is easy to slip up and use full AC when finding the enumeration.

Now after thinking for a while I just realized that the answer was there all the time (though I could be wrong). Under countable choice for finite sets a countable family of finite sets is necessarily countable, for we can use that axiom to select a fixed bijection of each finite set with a finite ordinal and then use these countable bijections to get a bijection for their union. So they are indeed equivalent. Perhaps the last paragraph could be edited accordingly to highlight this equivalence; as it is now, mentioning the axiom of dependent choices could be somewhat misleading, unless one clearly specifies that the restriction to the finite case implies the equivalence. Godelian (talk) 03:46, 7 November 2010 (UTC)

I agree with that. I did get the book I requested. The author states the result in question without proof in the introduction. I added this as a reference, and added a sentence about the DC/AC issue that you mentioned. — Carl (CBM · talk) 18:12, 9 November 2010 (UTC)

Use "Kőnig" instead of "König" throughout?

Copied/edited from here; please respond there.

Since this lemma was by a Hungarian named Kőnig, shouldn't the article properly use the double acute accent instead of the umlaut on his name? Just checking here. If nobody objects, I think I'll make the change. Oliphaunt (talk) 13:41, 9 May 2011 (UTC)

Are there may English language sources that use the alternate diacritic? In the ones I am familiar with, texts in mathematical logic, they use the umlaut mark. — Carl (CBM · talk) 13:46, 9 May 2011 (UTC)

The linked-to discussion no longer really covers this case as, referring to the father of the person in question here, it has been resolved with reference to the fact that that author chose to identify himself using the umlaut in mathematical publications. Unless a similar fact is known with reference to the author in question here, that discussion is no longer useful. I personally am presently on the side of spelling the author's name correctly (i.e. with double acute accent) unless an alternative preference on the author's part becomes known. The fact that sources are too lazy to spell an author's name correctly doesn't seem sufficient to me to warrant asserting the name of a lemma named for a specific individual should have a name different to that of the individual concerned, which would strike me as quite a bizarre precedent. 130.88.174.147 (talk) 19:19, 30 May 2011 (UTC)