Лемма Кенигса - Kőnigs lemma

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

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

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

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

Частным частным случаем этого является то, что каждый бесконечный дерево содержит либо вершину бесконечного степень или бесконечный простой путь.

Доказательство

Начать с любой вершины v₁. Каждая из бесконечного множества вершин грамм можно добраться из v₁ с простым путем, и каждый такой путь должен начинаться с одной из конечного числа вершин, смежных с v₁. Должна быть одна из тех смежных вершин, через которые можно пройти бесконечно много вершин, не проходя через них. v₁. Если бы не было, то весь граф был бы объединением конечного числа конечных множеств и, следовательно, конечным, что противоречит предположению, что граф бесконечен. Таким образом, мы можем выбрать одну из этих вершин и назвать ее v₂.

Теперь бесконечно много вершин грамм можно добраться из v₂ с простым путем, не включающим вершину v₁. Каждый такой путь должен начинаться с одной из конечного числа вершин, смежных с v₂. Таким образом, рассуждение, аналогичное приведенному выше, показывает, что должна быть одна из тех смежных вершин, через которые может быть достигнуто бесконечно много вершин; выберите один и назовите его v₃.

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

Результатом этого индукционного аргумента является то, что для всех п можно выбрать вершину v_п как описывает конструкция. Набор вершин, выбранных в конструкции, является цепочкой в графе, потому что каждая из них была выбрана смежной с предыдущей, и конструкция гарантирует, что одна и та же вершина никогда не будет выбрана дважды.

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

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

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

Для любого поддерева Т из ${ displaystyle omega ^ {< omega}}$ обозначение Ext (Т) обозначает множество узлов Т через который есть бесконечный путь. Даже когда Т вычислимо множество Ext (Т) не может быть вычислимым. Каждое поддерево Т из ${ displaystyle omega ^ {< omega}}$ у которого есть путь, есть путь, вычисляемый из Ext (Т).

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

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

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

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

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

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

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

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

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

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

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

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

Обобщение

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

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

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

Примечания

^ Кениг (1927) как объяснено в Франчелла (1997)
^ Роджерс (1967), п. 418ff.
^ Ферма (1976), п. 273; сравнивать Леви (1979), Упражнение IX.2.18.
^ Ховард, Пол; Рубин, Жан (1998). Последствия аксиомы выбора. Математические обзоры и монографии. 59. Провиденс, Род-Айленд: Американское математическое общество.

внешняя ссылка

Стэнфордская энциклопедия философии: конструктивная математика
В Проект Мицар полностью формализовал и автоматически проверил доказательство версии леммы Кёнига в файле ДЕРЕВЬЯ_2.

[1] Кениг (1927) как объяснено в Франчелла (1997)

[2] Роджерс (1967), п. 418ff.

[3] Ферма (1976), п. 273; сравнивать Леви (1979), Упражнение IX.2.18.

[4] Ховард, Пол; Рубин, Жан (1998). Последствия аксиомы выбора. Математические обзоры и монографии. 59. Провиденс, Род-Айленд: Американское математическое общество.

[1]

[2]

[3]

[4]