Лемма Кёнига

Математический результат на бесконечных деревьях

Публикация Кёнига 1927 года

Лемма Кёнига или лемма Кёнига о бесконечности — теорема в теории графов, сформулированная венгерским математиком Денешем Кёнигом в 1927 году. ^[1] Она дает достаточное условие для того, чтобы бесконечный граф имел бесконечно длинный путь. Аспекты вычислимости этой теоремы были тщательно изучены исследователями в области математической логики , особенно в теории вычислимости . Эта теорема также играет важную роль в конструктивной математике и теории доказательств .

Утверждение леммы

Пусть будет связным , локально конечным , бесконечным графом . Это означает, что каждые две вершины могут быть соединены конечным путем, каждая вершина смежна только с конечным числом других вершин, и граф имеет бесконечно много вершин. Тогда содержит луч : простой путь (путь без повторяющихся вершин), который начинается в одной вершине и продолжается от нее через бесконечно много вершин. ${\displaystyle G}$ ${\displaystyle G}$

Полезный частный случай леммы заключается в том, что каждое бесконечное дерево содержит либо вершину бесконечной степени , либо бесконечный простой путь. Если оно локально конечно, то оно удовлетворяет условиям леммы и имеет луч, а если оно локально не конечно, то оно имеет вершину бесконечной степени.

Строительство

Построение луча в графе, удовлетворяющем условиям леммы, можно выполнять шаг за шагом, сохраняя на каждом шаге конечный путь, который может быть расширен до достижения бесконечного числа вершин (не обязательно все по тому же пути, что и друг друга). Чтобы начать этот процесс, начните с любой одной вершины . Эту вершину можно рассматривать как путь нулевой длины, состоящий из одной вершины и ни одного ребра. По предположениям леммы каждая из бесконечного числа вершин может быть достигнута простым путем, который начинается из . ${\displaystyle G}$ ${\displaystyle v_{1}}$ ${\displaystyle G}$ ${\displaystyle v_{1}}$

Далее, пока текущий путь заканчивается в некоторой вершине , рассмотрим бесконечное множество вершин, которых можно достичь простыми путями, расширяющими текущий путь, и для каждой из этих вершин построим простой путь к ней, расширяющий текущий путь. Существует бесконечно много таких расширенных путей, каждый из которых соединяется с одним из своих соседей, но имеет только конечное число соседей. Следовательно, из принципа ящика следует , что по крайней мере один из этих соседей используется в качестве следующего шага на бесконечном множестве этих расширенных путей. Пусть будет таким соседом, и расширим текущий путь одним ребром, ребром от до . Это расширение сохраняет свойство, что бесконечно много вершин можно достичь простыми путями, расширяющими текущий путь. ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i+1}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i+1}}$

Повторение этого процесса для расширения пути производит бесконечную последовательность конечных простых путей, каждый из которых расширяет предыдущий путь в последовательности еще на одно ребро. Объединение всех этих путей является лучом, существование которого было обещано леммой.

Аспекты вычислимости

Аспекты вычислимости леммы Кёнига были тщательно исследованы. Для этой цели удобно сформулировать лемму Кёнига в форме, что любое бесконечное конечно ветвящееся поддерево имеет бесконечный путь. Здесь обозначает множество натуральных чисел (рассматриваемое как порядковое число ) и дерево, все узлы которого являются конечными последовательностями натуральных чисел, где родитель узла получается путем удаления последнего элемента из последовательности. Каждая конечная последовательность может быть идентифицирована с помощью частичной функции от к себе, а каждый бесконечный путь может быть идентифицирован с помощью полной функции. Это позволяет проводить анализ с использованием методов теории вычислимости. ${\displaystyle \omega ^{<\omega }}$ ${\displaystyle \omega }$ ${\displaystyle \omega ^{<\omega }}$ ${\displaystyle \omega }$

Поддерево , в котором каждая последовательность имеет только конечное число непосредственных расширений (то есть дерево имеет конечную степень, если рассматривать его как граф), называется конечно ветвящимся . Не каждое бесконечное поддерево имеет бесконечный путь, но лемма Кёнига показывает, что любое конечно ветвящееся бесконечное поддерево должно иметь такой путь. ${\displaystyle \omega ^{<\omega }}$ ${\displaystyle \omega ^{<\omega }}$

Для любого поддерева нотации обозначает множество узлов из , через которые проходит бесконечный путь. Даже когда является вычислимым, множество может быть невычислимым. Всякий раз, когда поддерево из имеет бесконечный путь, путь вычислим из , шаг за шагом, жадно выбирая преемника в на каждом шаге. Ограничение на гарантирует, что этот жадный процесс не может застрять. ${\displaystyle T}$ ${\displaystyle \omega ^{<\omega }}$ ${\displaystyle \operatorname {Ext} (T)}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle \operatorname {Ext} (T)}$ ${\displaystyle T}$ ${\displaystyle \omega ^{<\omega }}$ ${\displaystyle \operatorname {Ext} (T)}$ ${\displaystyle \operatorname {Ext} (T)}$ ${\displaystyle \operatorname {Ext} (T)}$

Существуют не конечно ветвящиеся вычислимые поддеревья , которые не имеют арифметического пути, и, конечно, не имеют гиперарифметического пути. ^[2] Однако, каждое вычислимое поддерево с путем должно иметь путь, вычислимый из O Клини , канонического полного множества. Это потому, что множество всегда (для понимания смысла этой нотации см. аналитическую иерархию ), когда вычислимо. ${\displaystyle \omega ^{<\omega }}$ ${\displaystyle \omega ^{<\omega }}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \operatorname {Ext} (T)}$ ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle T}$

Более тонкий анализ был проведен для вычислимо ограниченных деревьев. Поддерево из называется вычислимо ограниченным или рекурсивно ограниченным, если существует вычислимая функция от до такая, что для каждой последовательности в дереве и каждого натурального числа , th-й элемент последовательности не превышает . Таким образом, дается граница того, насколько «широким» является дерево. Следующие базисные теоремы применимы к бесконечным, вычислимо ограниченным, вычислимым поддеревьям из . ${\displaystyle \omega ^{<\omega }}$ ${\displaystyle f}$ ${\displaystyle \omega }$ ${\displaystyle \omega }$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle f(n)}$ ${\displaystyle f}$ ${\displaystyle \omega ^{<\omega }}$

• Любое такое дерево имеет путь , вычислимый из канонического полного множества Тьюринга, которое может решить проблему остановки . ${\displaystyle 0'}$
• Любое такое дерево имеет путь, который является низким . Это известно как теорема о низком базисе .
• Любое такое дерево имеет путь, который является гипериммунным свободным . Это означает, что любая функция, вычислимая из пути, доминируется вычислимой функцией.
• Для любого невычислимого подмножества дерева существует путь, который невычислим  . ${\displaystyle X}$ ${\displaystyle \omega }$ ${\displaystyle X}$

Слабая форма леммы Кёнига, утверждающая, что каждое бесконечное бинарное дерево имеет бесконечную ветвь, используется для определения подсистемы WKL ₀ арифметики второго порядка . Эта подсистема играет важную роль в обратной математике . Здесь бинарное дерево — это дерево, в котором каждый член каждой последовательности в дереве равен 0 или 1, то есть дерево вычислимо ограничено посредством постоянной функции 2. Полная форма леммы Кёнига не доказуема в WKL ₀ , но эквивалентна более сильной подсистеме ACA ₀ .

Связь с конструктивной математикой и компактностью

Приведенное выше доказательство обычно не считается конструктивным , поскольку на каждом шаге оно использует доказательство от противного, чтобы установить, что существует смежная вершина, из которой можно достичь бесконечно много других вершин, и из-за опоры на слабую форму аксиомы выбора . Факты о вычислительных аспектах леммы предполагают, что не может быть приведено доказательство, которое считалось бы конструктивным основными школами конструктивной математики .

Теорема веера LEJ Brouwer  (1927) является, с классической точки зрения, контрапозицией формы леммы Кёнига. Подмножество S из называется брусом, если любая функция из в множество имеет некоторый начальный сегмент в S . Бар является отсоединяемым, если каждая последовательность либо находится в брусе, либо нет в брусе (это предположение требуется, поскольку теорема обычно рассматривается в ситуациях, когда закон исключенного третьего не предполагается). Бар является однородным, если существует некоторое число такое, что любая функция из в имеет начальный сегмент в брусе длиной не более . Теорема веера Брауэра утверждает, что любой отсоединяемый брус является однородным. ${\displaystyle \{0,1\}^{<\omega }}$ ${\displaystyle \omega }$ ${\displaystyle \{0,1\}}$ ${\displaystyle N}$ ${\displaystyle \omega }$ ${\displaystyle \{0,1\}}$ ${\displaystyle N}$

Это можно доказать в классической постановке, рассматривая брус как открытое покрытие компактного топологического пространства . Каждая последовательность в брусе представляет собой базовое открытое множество этого пространства, и эти базовые открытые множества покрывают пространство по предположению. По компактности это покрытие имеет конечное подпокрытие. N теоремы о веере можно принять равным длине самой длинной последовательности, базовое открытое множество которой находится в конечном подпокрытии. Это топологическое доказательство можно использовать в классической математике, чтобы показать, что справедлива следующая форма леммы Кёнига: для любого натурального числа k любое бесконечное поддерево дерева имеет бесконечный путь. ${\displaystyle \{0,1\}^{\omega }}$ ${\displaystyle \{0,\ldots ,k\}^{<\omega }}$

Связь с аксиомой выбора

Лемму Кёнига можно считать принципом выбора; первое доказательство выше иллюстрирует связь между леммой и аксиомой зависимого выбора . На каждом шаге индукции должна быть выбрана вершина с определенным свойством. Хотя доказано, что существует по крайней мере одна подходящая вершина, если подходящих вершин больше одной, канонического выбора может и не быть. Фактически, полная сила аксиомы зависимого выбора не нужна; как описано ниже, аксиомы счетного выбора достаточно.

Если граф счетный, вершины хорошо упорядочены и можно канонически выбрать наименьшую подходящую вершину. В этом случае лемма Кёнига доказуема в арифметике второго порядка с арифметическим пониманием и, тем более, в теории множеств ZF (без выбора).

Лемма Кёнига по сути является ограничением аксиомы зависимого выбора на целые отношения, такие, что для каждого существует только конечное число таких, что . Хотя аксиома выбора, в общем случае, сильнее принципа зависимого выбора, это ограничение зависимого выбора эквивалентно ограничению аксиомы выбора. В частности, когда ветвление в каждом узле выполняется на конечном подмножестве произвольного множества, не предполагаемого счетным, форма леммы Кёнига, которая гласит «Каждое бесконечное конечно ветвящееся дерево имеет бесконечный путь», эквивалентна принципу, что каждое счетное множество конечных множеств имеет функцию выбора, то есть аксиоме счетного выбора для конечных множеств. ^[3] Эта форма аксиомы выбора (и, следовательно, леммы Кёнига) не доказуема в теории множеств ZF. ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle z}$ ${\displaystyle xRz}$

Обобщение

В категории множеств обратный предел любой обратной системы непустых конечных множеств непуст. Это можно рассматривать как обобщение леммы Кёнига и можно доказать с помощью теоремы Тихонова , рассматривая конечные множества как компактные дискретные пространства, а затем используя свойство конечного пересечения, характеризующее компактность.

Смотрите также

• Дерево Ароншайна , для возможного существования контрпримеров при обобщении леммы на более высокие мощности.
• степень ПА

Примечания

1. Кёниг (1927), как объяснено в Franchella (1997)
2. Роджерс (1967), стр. 418 и далее.
3. Truss (1976), стр. 273; Howard & Rubin (1998), стр. 20, 243; сравните Lévy (1979), Exercise IX.2.18.

Ссылки

• Брауэр, Л.Э.Дж. (1927), Об областях определения функций. опубликовано в Van Heijenoort, Jean, изд. (1967), От Фреге до Гёделя
• Franchella, Miriam (1997), «О происхождении леммы Денеша Кёнига о бесконечности», Архив истории точных наук , 51 (51(1)3:2-3): 3–27, doi :10.1007/BF00376449, S2CID  117198918
• Ховард, Пол; Рубин, Джин (1998), Последствия аксиомы выбора , Математические обзоры и монографии, т. 59, Провиденс, Род-Айленд: Американское математическое общество
• Кёниг, Д. (1927), «Über eine Schlussweise aus dem Endlichen ins Unendliche», Acta Sci. Математика. (Сегед) (на немецком языке), 3 (2–3): 121–130, заархивировано из оригинала 23 декабря 2014 г. , получено 23 декабря 2014 г.
• Леви, Азриэль (1979), Базовая теория множеств , Springer, ISBN 3-540-08417-7, МР  0533962; переиздание, Довер, 2002, ISBN 0-486-42079-5 . 
• Роджерс, Хартли-младший (1967), Теория рекурсивных функций и эффективная вычислимость , McGraw-Hill, MR  0224462
• Truss, J. (1976), "Некоторые случаи леммы Кёнига", в Marek, V. Wiktor; Srebrny, Marian; Zarach, Andrzej (ред.), Set Theory and Hierarchy Theory a Memorial Tribute to Andrzej Mostowski , Lecture Notes in Mathematics, т. 537, Springer, стр. 273–284, doi :10.1007/BFb0096907, ISBN 978-3-540-07856-2, МР  0429557

Дальнейшее чтение

• Cenzer, Douglas (1999), « Классы в теории вычислимости», Handbook of Computability Theory, Elsevier, стр. 37–85, doi :10.1016/S0049-237X(99)80018-4, ISBN ${\displaystyle \Pi _{1}^{0}}$ 0-444-89882-4, МР  1720779
• Кениг, Д. (1926), «Sur les соответствия multivoques des ансамблей» (PDF) , Fundamenta Mathematicae (на французском языке), 8 (8): 114–134, doi : 10.4064/fm-8-1-114-134
• Кёниг, Д. (1936), Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckunkomplexe (на немецком языке), Лейпциг: Акад. Верлаг
• Симпсон, Стивен Г. (1999), Подсистемы арифметики второго порядка , Перспективы математической логики, Springer, ISBN 3-540-64882-8, г-н  1723993
• Соаре, Роберт И. (1987), Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо генерируемых множеств , Перспективы математической логики, Springer, ISBN 3-540-15299-7, МР  0882921

Внешние ссылки

• Стэнфордская энциклопедия философии: Конструктивная математика
• Проект Mizar полностью формализовал и автоматически проверил доказательство версии леммы Кёнига в файле TREES_2.