König's lemma

The lemma of King or Königslemma is a theorem in graph theory by Dénes Kőnig (1936). The predictability of the lemma has been thoroughly researched in mathematical logic. Dénes Kőnig is properly spelled with double acute. The lemma is named after him but is usually written with an umlaut.

Statement of the lemma

Let G be a connected graph with infinitely many nodes so that each node has finite degree, ie only a finite number of other nodes is adjacent. Then, each node of G portion of an infinitely long path on which a node is visited at most once.

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

It should be noted that the node degrees at last, but need not be limited. It is possible for a node with degree 10 to have a degree with 100, with the third degree in 1000, and so on.

Evidence

Assuming that the graph is connected and possesses an infinite number of nodes.

Starting with any node V1, each node of G can be reached from node V1 through a path. Such a path must begin at one of the finitely many are adjacent to v1 node. There has to be one of its incident nodes, an infinite number of nodes can be reached by the. If there were no such node, then the entire graph would be a union of finitely many finite Knotenmegen and therefore in contradiction to the assumption of infinite graphs.

Be v2 one of these nodes. This infinitely many nodes of G can be of v2 obtained by a path that does not contain v1. Any such path must begin at one of the finitely many are adjacent to node v2. A similar argument as above shows us that there must be a node are adjacent, an infinite number of nodes can be achieved by; this is v3.

In this manner can be constructed inductive an endless path. At each step, the induction hypothesis implies that there are infinitely many nodes that can be reached by a path from from, this path must not contain a finite set of nodes. The induction step is carried out with the argument that one of its incident nodes to satisfy the induction hypothesis, even if belongs to the finite set.

This evidence is considered not constructive, because at each step a proof by contradiction is done to show that there is a node are adjacent, an infinite number of other nodes can be reached from where. Computational analysis suggests that there is no constructive proof.

Predictability

The predictability of the lemma by King has been thoroughly researched. The formulation of the lemma, namely that every infinite, finite branched subtree of an infinite path has is very convenient for this purpose. stands for a set of natural numbers, with the canonical enumeration of all finite, sorted by intermediate result sequences of natural numbers. Each finite sequence can be determined in itself by means of a partial function. Each infinite path can be determined with a total function. Therefore, the analysis with the aid of computability theory is possible.

A subtree of where each sequence has only finitely many direct successor, ie the corresponding tree has finite degree of all nodes is, finitely branching. Not every infinite subtree of having an infinite path, but the lemma shows that every finite branched subtree must have an infinite path.

For all subtrees T of the notation Ext ( T ) denotes the set of nodes of T, performs an infinite path. Even if T is calculated, Ext (T) is not necessarily predictable. Each subtree of T, which has an endless path, having also an endless path, which is calculated from Ext ( T).

There are finally branched, predictable part of trees that have no arithmetic and no hyperarithmetischen path. Every computable subtree of with path must have a path that is computable from Kleene's O, the full amount. This is because the amount Abs (T ) is always and t thus calculated.

A more detailed analysis was carried out for predictable limited trees. A subtree of limited means predictable or recursively bounded if there is a computable function f from to, such that for all n there is no sequence in the tree is, the n- th element is greater than f (n). F is thus a barrier for the "width" of the tree. The following basis sets are valid for infinite computable limited, finite branched computable subtrees of.

• Each such tree has a predictable path, the canonical and Turing - complete amount that can decide the halting problem.
• Each such tree has a low path. That of the Turing jump operator of the path has the same Turing degree as the halting problem.
• Each such tree has a path that is hyperimmune free. That each of the path from computable function is dominated by a computable function.
• For all non- computable subsets X of the tree of X has a path, not calculated.

A weaker form of Lemma King is used in the definition of the subsystem of second order arithmetic. This subsystem has a major role in the reverse mathematics.

Relationship for constructive mathematics and compactness

The Fan Theorem of Brouwer is the classical point of view, counter position of the lemma of King. A subset of S is called a bar, where each function in the set having a first segment in S. A bar is called solvable if each episode is in the bar or in the bar either. This premise is necessary. A bar is uniform if there exists a number n such that exists after a first segment of the bar with a maximum length of n. Brouwer's fan theorem states that any detachable bar is uniform.

Relationship with the axiom of choice

The lemma by King includes the principle of selection; the first evidence above shows the relationship between the lemma and the axiom of choice dependent. At each induction step, a node must be chosen with a particular property. Although it is proven that there exists at least a suitable node; but if there are multiple matching nodes, there may be no canonical choice. This case can not arise if the graph is assumed to be countable.

The lemma is mainly a limitation of the dependent choice axiom to the full relations R, so that x finitely many z with xRz for all. The shape of the lemma, which states that every infinite finally branched tree has an infinite path that is equivalent to the principle that every sequence of finite sets has a choice function (see Levy [ 1979 Exercise IX.2.18 ] ). Thus, there are models of Zermelo -Fraenkel set theory without choice, in this form of the lemma of King is not the case.