Lemma of king

The lemma king or king Unendlichkeitslemma ( English king's infinity lemma ) is a mathematical theorem that both the area of Ramsey and which the graph theory is attributed. The lemma goes back to the Hungarian mathematician Dénes Kőnig and his classic monograph Theory of Finite and Infinite Graphs from 1936. Last but not least, it plays an important role in predictability theory and has therefore also been researched in mathematical logic .

Statement of the lemma

Let be a connected graph with infinitely many nodes, so that each node has finite degree, i.e. is only adjacent to finitely many other nodes. Starting from any starting node, there is then always an infinitely long path in , on which each node is visited at most once. ${\displaystyle G}$ ${\displaystyle G}$

A common special case is that every tree consisting of an infinite number of nodes of finite degree has an infinite path.

It should be noted that the degree of the node must be finite, but not restricted . It is possible to have one node with degree 10, one with degree 100, the third with degree 1000, and so on.

proof

Suppose the graph is connected and has an infinite number of nodes . ${\displaystyle v_{i}}$

Starting with any node , each node can be reached from the node by a path. Such a path must begin at one of the finite number of adjacent nodes. There must be one of the adjacent nodes through which an infinite number of nodes can be reached. If there were no such vertex, then the entire graph would be a union of finitely many finite sets of vertices and would therefore contradict the assumption of the infinite graph. ${\displaystyle v_{1}}$ ${\displaystyle G}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{1}}$

Be one of those knots. This allows an infinite number of nodes of be out achieved by a path that does not contain. Every such path must begin at one of the finite number of nodes that are adjacent. A similar argument to the one above shows us that there must be an adjacent knot through which an infinite number of knots can be reached; this is . ${\displaystyle v_{2}}$ ${\displaystyle G}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{1}}$ ${\displaystyle v_{2}}$ ${\displaystyle v_{3}}$

In this way an infinite path can be inductively constructed. At each step the induction hypothesis says that there are infinitely many nodes that can be reached by means of a path from , whereby this path must not contain a finite set of nodes. The induction step is carried out with the argument that one of the nodes that are adjacent to it satisfies the induction hypothesis, even if it belongs to that finite set. ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$

This proof is not considered constructive because at every step there is a contradiction proof to show that there is an adjacent node from which an infinite number of other nodes can be reached. Computational analyzes suggest that there is no constructive evidence.

Predictability

The predictability of König's lemma has been thoroughly researched. The formulation of the lemma, namely that every infinite, finitely branched subtree of has an infinite path, is very favorable for this purpose. stands for a set of natural numbers, where the canonical enumeration of all finite sequences of natural numbers sorted by intermediate result is. Every finite sequence can be determined by means of a partial function of in itself. Every infinite path can be determined with a total function . Therefore the analysis with the help of the computability theory is possible. ${\displaystyle \omega ^{<\omega }\,}$ ${\displaystyle \omega }$ ${\displaystyle \omega ^{<\omega }\,}$ ${\displaystyle \omega }$

A subtree of in which each sequence only has a finite number of direct successors, i.e. H. the corresponding tree has finite degrees at all nodes, is called finitely branched . Not every infinite subtree of has an infinite path, but the lemma shows that every finitely branched subtree must have an infinite path. ${\displaystyle \omega ^{<\omega }\,}$ ${\displaystyle \omega ^{<\omega }\,}$

For all subtrees of the notation denotes the set of nodes of through which an infinite path leads. Even if is predictable, it is not necessarily predictable. Every subtree of that has an infinite path also has an infinite path that is computable from . ${\displaystyle T}$ ${\displaystyle \omega ^{<\omega }\,}$ ${\displaystyle Ext(T)}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle Ext(T)}$ ${\displaystyle T}$ ${\displaystyle \omega ^{<\omega }\,}$ ${\displaystyle Ext(T)}$

There are finite branched, computable subtrees of that have no arithmetic and no hyperarithmetic path. Every computable subtree of with path must have a path computable by Kleene's O, the complete set. This is because the amount is always and is therefore predictable. ${\displaystyle \omega ^{<\omega }\,}$ ${\displaystyle \omega ^{<\omega }\,}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle Ext(T)}$ ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle T}$

A more detailed analysis was performed for computable bounded trees. A subtree of is called computable restricted or recursively restricted if there is a computable function from to , so that for all of them there is no sequence in the tree whose -th element is greater than . Thus, there is a limit to the "width" of the tree. The following basic theorems apply to infinite computable restricted, finitely branched computable subtrees of . ${\displaystyle \omega ^{<\omega }\,}$ ${\displaystyle f}$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f(n)}$ ${\displaystyle f}$ ${\displaystyle \omega ^{<\omega }\,}$

• Each such tree has a computable path of , the canonical and Turing-complete set that can solve the holding problem . ${\displaystyle 0'}$
• Every such tree has a low path. I.e. the Turing jump operator of the path has the same degree of Turing as the stopping problem.
• Each such tree has a path that is hyperimmune free . I.e. every function that can be calculated from the path is dominated by a calculable function.
• For all non-computable subsets of the tree has a path that is not computed. ${\displaystyle X}$ ${\displaystyle \omega }$ ${\displaystyle X}$

A weaker form of König's lemma is used in defining the subsystem of second order arithmetic. This subsystem has an important role in reverse mathematics . ${\displaystyle \operatorname {WKL} _{0}}$

Relationship to constructive mathematics and compactness

The fan theorem of Brouwer is from the classical point of view opposite position of the lemma of King. A subset of is called bar if every function of in has a first segment in . A bar is called solvable if every episode is either in the bar or not in the bar . This premise is necessary. A bar is uniform if there is a number such that from to there is a first segment in the bar with a maximum length . Brouwer's Fan Theorem states that every detachable bar is uniform . ${\displaystyle S}$ ${\displaystyle \{0,1\}^{<\omega }\,}$ ${\displaystyle \omega }$ ${\displaystyle \{0,1\}}$ ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle \omega }$ ${\displaystyle \{0,1\}}$ ${\displaystyle n}$

Relation to the axiom of choice

König's lemma includes the principle of selection; the first proof above shows the relationship between the lemma and the axiom of dependent choice . For each induction step, a node with a specific property must be selected. It is proven that at least one suitable node exists; but if there are multiple matching nodes, there may not be canonical selection. This case cannot arise if the graph is assumed to be countable.

The lemma is mainly a restriction of the axiom of dependent choice to the complete relations , so that for all there are finitely many with . The form of the lemma, which states that every infinite finitely branching tree has an infinite path , is equivalent to the principle that every sequence of finite sets has a selection function (cf. Levy [1979, Exercise IX.2.18]). Thus there are models of the Zermelo-Fraenkel set theory without selection, in which this form of König's lemma does not apply. ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle xRz}$

literature

• Reinhard Diestel : graph theory . 2nd Edition. Springer Verlag, Berlin / Heidelberg / New York (and others) 2000, ISBN 3-540-67656-2 .
• Reinhard Diestel: Graph Theory (=  Graduate Texts in Mathematics . Volume 173 ). 3. Edition. Springer Verlag, Berlin / Heidelberg / New York 2005, ISBN 3-540-26182-6 .
• Dénes König: Theory of finite and infinite graphs . With a treatise by L. Euler. Ed .: H. Sachs (=  Teubner Archive for Mathematics . Volume 6 ). BSB BG Teubner Verlagsgesellschaft, Leipzig 1986, ISBN 3-211-95830-4 .
• A. Levy: Basic Set Theory . Springer, 1979 (reprint: Dover 2002, ISBN 0-486-42079-5 ).
• S. Simpson: Subsystems of Second Order Arithmetic . Springer, 1999, ISBN 3-540-64882-8 .
• R. Soare: Recursively Enumerable Sets and Degrees . Springer, 1987, ISBN 0-387-15299-7 .

Web links

• Constructive Mathematics Stanford Encyclopedia of Philosophy
• The Mizar project has completely formalized and automatically verified the proof of a modification of König's lemma. mizar.org (English)

Individual evidence

1. ↑ King's name is correctly spelled with a double acute . In the designation of the lemma named after him, however, his name is written with an umlaut - as is usual in specialist literature.