HOME

TheInfoList



OR:

Kőnig's lemma or Kőnig's infinity lemma is a
theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...
in
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
due to the Hungarian mathematician
Dénes Kőnig Dénes Kőnig (September 21, 1884 – October 19, 1944) was a Hungarian mathematician of Hungarian Jewish heritage who worked in and wrote the first textbook on the field of graph theory. Biography Kőnig was born in Budapest, the son of mathemat ...
who published it in 1927. It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated by researchers in
mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, especially in
computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...
. This theorem also has important roles in
constructive mathematics In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in classical mathematics, one can prove th ...
and
proof theory Proof theory is a major branchAccording to , proof theory is one of four domains mathematical logic, together with model theory, axiomatic set theory, and recursion theory. consists of four corresponding parts, with part D being about "Proof The ...
.


Statement of the lemma

Let G be a
connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
, locally finite,
infinite graph This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B ...
. This means that every two vertices can be connected by a finite path, each vertex is adjacent to only finitely many other vertices, and the graph has infinitely many vertices. Then G contains a ray: a simple path (a path with no repeated vertices) that starts at one vertex and continues from it through infinitely many vertices. Another way of stating the theorem is: "If the human race never dies out, somebody now living has a line of descendants that will never die out". A useful special case of the lemma is that every infinite
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
contains either a vertex of infinite degree or an infinite simple path. If it is locally finite, it meets the conditions of the lemma and has a ray, and if it is not locally finite then it has an infinite-degree vertex.


Construction

The construction of a ray, in a graph G that meets the conditions of the lemma, can be performed step by step, maintaining at each step a finite path that can be extended to reach infinitely many vertices (not necessarily all along the same path as each other). To begin this process, start with any single vertex v_1. This vertex can be thought of as a path of length zero, consisting of one vertex and no edges. By the assumptions of the lemma, each of the infinitely many vertices of G can be reached by a simple path that starts from v_1. Next, as long as the current path ends at some vertex v_i, consider the infinitely many vertices that can be reached by simple paths that extend the current path, and for each of these vertices construct a simple path to it that extends the current path. There are infinitely many of these extended paths, each of which connects from v_i to one of its neighbors, but v_i has only finitely many neighbors. Therefore, it follows by a form of the
pigeonhole principle In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, of three gloves, at least two must be right-handed or at least two must be l ...
that at least one of these neighbors is used as the next step on infinitely many of these extended paths. Let v_ be such a neighbor, and extend the current path by one edge, the edge from v_i to v_. This extension preserves the property that infinitely many vertices can be reached by simple paths that extend the current path. Repeating this process for extending the path produces an infinite sequence of finite simple paths, each extending the previous path in the sequence by one more edge. The union of all of these paths is the ray whose existence was promised by the lemma.


Computability aspects

The computability aspects of Kőnig's lemma have been thoroughly investigated. For this purpose it is convenient to state Kőnig's lemma in the form that any infinite finitely branching subtree of \omega^ has an infinite path. Here \omega denotes the set of natural numbers (thought of as an
ordinal number In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals (first, second, th, etc.) aimed to extend enumeration to infinite sets. A finite set can be enumerated by successively labeling each element with the leas ...
) and \omega^ the tree whose nodes are all finite sequences of natural numbers, where the parent of a node is obtained by removing the last element from a sequence. Each finite sequence can be identified with a partial function from \omega to itself, and each infinite path can be identified with a total function. This allows for an analysis using the techniques of computability theory. A subtree of \omega^ in which each sequence has only finitely many immediate extensions (that is, the tree has finite degree when viewed as a graph) is called finitely branching. Not every infinite subtree of \omega^ has an infinite path, but Kőnig's lemma shows that any finitely branching infinite subtree must have such a path. For any subtree T of \omega^ the notation \operatorname(T) denotes the set of nodes of T through which there is an infinite path. Even when T is computable the set \operatorname(T) may not be computable. Whenever a subtree T of \omega^ has an infinite path, the path is computable from \operatorname(T), step by step, greedily choosing a successor in \operatorname(T) at each step. The restriction to \operatorname(T) ensures that this greedy process cannot get stuck. There exist non-finitely branching computable subtrees of \omega^ that have no arithmetical path, and indeed no hyperarithmetical path. However, every computable subtree of \omega^ with a path must have a path computable from Kleene's O, the canonical \Pi^1_1 complete set. This is because the set \operatorname(T) is always \Sigma^1_1 (for the meaning of this notation, see
analytical hierarchy Analytic or analytical may refer to: Chemistry * Analytical chemistry, the analysis of material samples to learn their chemical composition and structure * Analytical technique, a method that is used to determine the concentration of a chemica ...
) when T is computable. A finer analysis has been conducted for computably bounded trees. A subtree of \omega^ is called computably bounded or recursively bounded if there is a computable function f from \omega to \omega such that for every sequence in the tree and every natural number n, the nth element of the sequence is at most f(n). Thus f gives a bound for how "wide" the tree is. The following basis theorems apply to infinite, computably bounded, computable subtrees of \omega^. * Any such tree has a path computable from 0', the canonical Turing complete set that can decide the
halting problem In computability theory (computer science), computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run for ...
. * Any such tree has a path that is low. This is known as the low basis theorem. * Any such tree has a path that is ''hyperimmune free''. This means that any function computable from the path is dominated by a computable function. * For any noncomputable subset X of \omega the tree has a path that does not compute X. A weak form of Kőnig's lemma which states that every infinite binary tree has an infinite branch is used to define the subsystem WKL0 of
second-order arithmetic In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation of mathematics, foundation for much, but not all, ...
. This subsystem has an important role in
reverse mathematics Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in cont ...
. Here a binary tree is one in which every term of every sequence in the tree is 0 or 1, which is to say the tree is computably bounded via the constant function 2. The full form of Kőnig's lemma is not provable in WKL0, but is equivalent to the stronger subsystem ACA0.


Relationship to constructive mathematics and compactness

The proof given above is not generally considered to be constructive, because at each step it uses a
proof by contradiction In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical pr ...
to establish that there exists an adjacent vertex from which infinitely many other vertices can be reached, and because of the reliance on a weak form of the
axiom of choice In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
. Facts about the computational aspects of the lemma suggest that no proof can be given that would be considered constructive by the main schools of
constructive mathematics In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a specific example of a mathematical object in order to prove that an example exists. Contrastingly, in classical mathematics, one can prove th ...
. The fan theorem of is, from a classical point of view, the
contrapositive In logic and mathematics, contraposition, or ''transposition'', refers to the inference of going from a Conditional sentence, conditional statement into its logically equivalent contrapositive, and an associated proof method known as . The contrap ...
of a form of Kőnig's lemma. A subset ''S'' of \^ is called a ''bar'' if any function from \omega to the set \ has some initial segment in ''S''. A bar is ''detachable'' if every sequence is either in the bar or not in the bar (this assumption is required because the theorem is ordinarily considered in situations where the
law of the excluded middle In logic, the law of excluded middle or the principle of excluded middle states that for every proposition, either this proposition or its negation is true. It is one of the three laws of thought, along with the law of noncontradiction and th ...
is not assumed). A bar is ''uniform'' if there is some number N so that any function from \omega to \ has an initial segment in the bar of length no more than N. Brouwer's fan theorem says that any detachable bar is uniform. This can be proven in a classical setting by considering the bar as an open covering of the
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact, a type of agreement used by U.S. states * Blood compact, an ancient ritual of the Philippines * Compact government, a t ...
topological space \^\omega. Each sequence in the bar represents a basic open set of this space, and these basic open sets cover the space by assumption. By compactness, this cover has a finite subcover. The ''N'' of the fan theorem can be taken to be the length of the longest sequence whose basic open set is in the finite subcover. This topological proof can be used in classical mathematics to show that the following form of Kőnig's lemma holds: for any natural number ''k'', any infinite subtree of the tree \^ has an infinite path.


Relationship with the axiom of choice

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 In mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. T ...
. 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 fact, the full strength of the axiom of dependent choice is not needed; as described below, the
axiom of countable choice The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function A with domain \mathbb ( ...
suffices. If the graph is countable, the vertices are well-ordered and one can canonically choose the smallest suitable vertex. In this case, Kőnig's lemma is provable in second-order arithmetic with arithmetical comprehension, and, a fortiori, in ZF set theory (without choice). Kőnig's lemma is essentially the restriction of the axiom of dependent choice to entire relations R such that for each x there are only finitely many z such that xRz. Although the axiom of choice is, in general, stronger than the principle of dependent choice, this restriction of dependent choice is equivalent to a restriction of the axiom of choice. In particular, when the branching at each node is done on a finite subset of an arbitrary set not assumed to be countable, the form of Kőnig's lemma that says "Every infinite finitely branching tree has an infinite path" is equivalent to the principle that every countable set of finite sets has a choice function, that is to say, the axiom of countable choice for finite sets., p. 273; , pp. 20, 243; compare , Exercise IX.2.18. This form of the axiom of choice (and hence of Kőnig's lemma) is not provable in ZF set theory.


Generalization

In the
category of sets In the mathematical field of category theory, the category of sets, denoted by Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the functions from ''A'' to ''B'', and the composition of mor ...
, the
inverse limit In mathematics, the inverse limit (also called the projective limit) is a construction that allows one to "glue together" several related objects, the precise gluing process being specified by morphisms between the objects. Thus, inverse limits ca ...
of any inverse system of non-empty finite sets is non-empty. This may be seen as a generalization of Kőnig's lemma and can be proved with
Tychonoff's theorem In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact with respect to the product topology. The theorem is named after Andrey Nikolayevich Tikhonov (whose surname sometimes is tra ...
, viewing the finite sets as compact discrete spaces, and then using the
finite intersection property In general topology, a branch of mathematics, a non-empty family A of subsets of a set X is said to have the finite intersection property (FIP) if the intersection over any finite subcollection of A is non-empty. It has the strong finite intersect ...
characterization of compactness.


See also

*
Aronszajn tree In set theory, an Aronszajn tree is a tree of uncountable height with no uncountable branches and no uncountable levels. For example, every Suslin tree is an Aronszajn tree. More generally, for a cardinal ''κ'', a ''κ''-Aronszajn tree is a tree o ...
, for the possible existence of counterexamples when generalizing the lemma to higher cardinalities. * PA degree


Notes


References

*. published in * * * *; reprint, Dover, 2002, . * * *


Further reading

* * * * *


External links


Stanford Encyclopedia of Philosophy: Constructive Mathematics
* The Mizar project has completely formalized and automatically checked the proof of a version of Kőnig's lemma in the fil
TREES_2
{{DEFAULTSORT:Koenigs Lemma Lemmas in graph theory Articles containing proofs Computability theory Wellfoundedness Axiom of choice Infinite graphs Constructivism (mathematics)