Talk:König's lemma

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	Mid Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. --Cronholm144 03:32, 16 June 2007 (UTC)

"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

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