Лемма Кенига или бесконечность лемма Кёниги является теоремой в теории графов в связи с венгерским математиком Dénes Konig , который опубликовал его в 1927 году [1] Это дает достаточное условие для бесконечного графа иметь бесконечно длинный путь. Аспекты вычислимости этой теоремы были тщательно исследованы исследователями математической логики , особенно теории вычислимости . Эта теорема также играет важную роль в конструктивной математике и теории доказательств .
Утверждение леммы
Пусть G - связный , локально конечный , бесконечный граф (это означает: любые две вершины могут быть соединены путем, у графа бесконечно много вершин, и каждая вершина смежна только с конечным числом других вершин). Тогда G содержит луч : простой путь (путь без повторяющихся вершин), который начинается в одной вершине и продолжается от нее через бесконечное количество вершин.
Частным частным случаем этого является то, что каждое бесконечное дерево содержит либо вершину бесконечной степени, либо бесконечный простой путь.
Доказательство
Начнем с любой вершины v 1 . Каждая из бесконечного числа вершин графа G может быть достигнута из v 1 простым путем, и каждый такой путь должен начинаться с одной из конечного числа вершин, смежных с v 1 . Должна быть одна из тех смежных вершин, через которые можно пройти бесконечно много вершин, не проходя через v 1 . Если бы не было, то весь граф был бы объединением конечного числа конечных множеств и, следовательно, конечным, что противоречит предположению, что граф бесконечен. Таким образом, мы можем выбрать одну из этих вершин и назвать ее v 2 .
Теперь бесконечно много вершин G может быть достигнуто из v 2 простым путем, не включающим вершину v 1 . Каждый такой путь должен начинаться с одной из конечного числа вершин, смежных с v 2 . Таким образом, рассуждение, аналогичное приведенному выше, показывает, что должна быть одна из тех смежных вершин, через которые может быть достигнуто бесконечно много вершин; выберите один и назовите его v 3 .
Продолжая таким образом, можно построить бесконечный простой путь, используя математическую индукцию и слабую версию аксиомы зависимого выбора . На каждом шаге гипотеза индукции утверждает, что существует бесконечно много узлов, достижимых простым путем от конкретного узла v i , который не проходит через одну из конечного набора вершин. Аргумент индукции состоит в том, что одна из вершин, смежных с v i, удовлетворяет предположению индукции, даже когда v i добавляется к конечному множеству.
Результатом этого аргумента индукции является то, что для всех n можно выбрать вершину v n, как описывает конструкция. Набор вершин, выбранных в конструкции, является цепочкой в графе, потому что каждая из них была выбрана смежной с предыдущей, и конструкция гарантирует, что одна и та же вершина никогда не будет выбрана дважды.
Аспекты вычислимости
Аспекты вычислимости леммы Кёнига тщательно исследованы. Наиболее удобная для этой цели форма леммы Кёнига гласит, что любое бесконечное конечно ветвящееся поддеревоимеет бесконечный путь. Здесьобозначает набор натуральных чисел (рассматриваемых как порядковое число ) идерево, узлы которого представляют собой все конечные последовательности натуральных чисел, где родитель узла получается удалением последнего элемента из последовательности. Каждую конечную последовательность можно отождествить с частичной функцией изсамому себе, и каждый бесконечный путь можно отождествить с общей функцией. Это позволяет проводить анализ с использованием методов теории вычислимости.
Поддерево в котором каждая последовательность имеет только конечное число непосредственных расширений (то есть дерево имеет конечную степень, если рассматривать его как граф), называется конечным ветвлением . Не каждое бесконечное поддерево имеет бесконечный путь, но лемма Кёнига показывает, что любое конечно ветвящееся поддерево должно иметь такой путь.
Для любого поддерева T изобозначение Ext ( T ) обозначает множество узлов T, через которые проходит бесконечный путь. Даже если T вычислимо, множество Ext ( T ) может быть невычислимым. Каждое поддерево T изу которого есть путь, есть путь, вычислимый из Ext ( T ).
Известно, что существуют неконечно ветвящиеся вычислимые поддеревья у которых нет арифметического пути и даже гиперарифметического пути. [2] Однако каждое вычислимое поддеревос путем должен иметь путь, вычисляемый из O Клини , каноническийполный комплект. Это потому, что множество Ext ( T ) всегда(см. аналитическую иерархию ), когда T вычислим.
Более тонкий анализ был проведен для вычислимо ограниченных деревьев. Поддеревоназывается вычислимо ограниченной или рекурсивно ограниченной, если существует вычислимая функция f из к таким образом, что для каждой последовательности в дереве , и каждый п , тот п - й элемент последовательности не превосходит F ( п ). Таким образом, f дает оценку «ширины» дерева. Следующие базисные теоремы применяются к бесконечным вычислимо ограниченным вычислимым поддеревьям.
- У любого такого дерева есть путь, вычисляемый из , канонический полный набор Тьюринга, который может решить проблему остановки .
- У любого такого дерева есть низкий путь . Это известно как теорема о низком базисе .
- У любого такого дерева есть путь, свободный от гипериммун . Это означает, что в любой функции, вычисляемой по пути, преобладает вычислимая функция.
- Для любого невычислимого подмножества X вдерево имеет путь , который не вычисляет X .
Слабая форма леммы Кёнига , которая гласит , что каждое бесконечное бинарное дерево имеет бесконечную ветвь используется для определения подсистемы WKl 0 из арифметики второго порядка . Эта подсистема играет важную роль в обратной математике . Здесь двоичное дерево - это дерево, в котором каждый член каждой последовательности в дереве равен 0 или 1, то есть дерево вычислимо ограничено через постоянную функцию 2. Полная форма леммы Кёнига не доказуема в WKL 0 , но эквивалентна более сильной подсистеме ACA 0 .
Отношение к конструктивной математике и компактности
Приведенное выше доказательство обычно не считается конструктивным , потому что на каждом шаге оно использует доказательство от противного, чтобы установить, что существует смежная вершина, из которой может быть достигнуто бесконечно много других вершин, и из-за зависимости от слабой формы аксиома выбора . Факты о вычислительных аспектах леммы предполагают, что не может быть дано никакого доказательства, которое могло бы быть сочтено конструктивным в основных школах конструктивной математики .
Теорема о веере Л. Дж. Брауэра ( 1927 ) с классической точки зрения является противоположностью одной из форм леммы Кёнига. Подмножество S изназывается баром, если какая-либо функция из к набору имеет некоторый начальный сегмент в S . Штанга является съемной, если каждая последовательность находится либо в полосе, либо не в полосе (это предположение требуется, потому что теорема обычно рассматривается в ситуациях, когда не предполагается закон исключенной середины ). Полоса является однородной, если существует некоторое число N, так что любая функция из к имеет начальный отрезок в полосе длиной не более . Теорема Брауэра о веере гласит, что любой съемный стержень однороден.
Это можно доказать в классической ситуации, рассматривая стержень как открытое покрытие компактного топологического пространства. Каждая последовательность в полосе представляет собой базовый открытый набор этого пространства, и эти базовые открытые наборы покрывают пространство по предположению. По компактности это покрытие имеет конечное подпокрытие. Н теорема вентилятора может быть выбрана длиной самой длинной последовательности , чьими основные открытого множества в конечном подпокрытии. Это топологическое доказательство можно использовать в классической математике, чтобы показать, что имеет место следующая форма леммы Кёнига: для любого натурального числа k любое бесконечное поддерево дерева имеет бесконечный путь.
Связь с аксиомой выбора
Лемму Кёнига можно рассматривать как принцип выбора; Первое доказательство, приведенное выше, иллюстрирует связь между леммой и аксиомой зависимого выбора . На каждом шаге индукции должна быть выбрана вершина с определенным свойством. Хотя доказано, что существует хотя бы одна подходящая вершина, при наличии более одной подходящей вершины канонического выбора может не быть. Фактически, полная сила аксиомы зависимого выбора не нужна; как описано ниже, достаточно аксиомы счетного выбора .
Если граф счетный, вершины упорядочены, и можно канонически выбрать наименьшую подходящую вершину. В этом случае лемма Кёнига доказуема в арифметике второго порядка с арифметическим пониманием и, тем более, в теории множеств ZF (без выбора).
Лемма Кёнига по сути является ограничением аксиомы зависимого выбора на целые отношения R, такие, что для каждого x существует только конечное число z таких, что xRz . Хотя аксиома выбора в целом сильнее принципа зависимого выбора, это ограничение зависимого выбора эквивалентно ограничению аксиомы выбора. В частности, когда ветвление в каждом узле осуществляется на конечном подмножестве произвольного множества, которое не считается счетным, форма леммы Кёнига, которая гласит: «Каждое бесконечное конечно ветвящееся дерево имеет бесконечный путь» эквивалентна принципу, согласно которому каждое счетное множество конечных множеств имеет функцию выбора, то есть аксиому счетного выбора для конечных множеств. [3] Эта форма аксиомы выбора (и, следовательно, леммы Кёнига) не доказуема в теории множеств ZF.
Обобщение
В категории множеств , то обратный предел любой обратной системы непустых конечных непусто. Это можно рассматривать как обобщение леммы Кёнига и можно доказать с помощью теоремы Тихонова , рассматривая конечные множества как компактные дискретные пространства, а затем используя характеристику компактности с помощью свойства конечного пересечения .
Смотрите также
- Дерево Ароншайна за возможное существование контрпримеров при обобщении леммы на более высокие мощности.
- Степень PA
Заметки
- ^ Kőnig (1927), как объяснено в Franchella (1997)
- ^ Роджерс (1967) , стр. 418ff.
- ^ Трасс (1976) , стр. 273; Ховард и Рубин (1998) [ необходима страница ] ; сравните Леви (1979) , упражнение IX.2.18.
Рекомендации
- Брауэр, LEJ (1927), Об областях определения функций. опубликовано в ван Хейеноорт, Жан, изд. (1967), От Фреге до Гёделя
- Franchella, Мириам (1997), " К вопросу о происхождении бесконечности леммы Dénes Кениг", Архив для истории точных наук (51 (1) 3: 2-3): 3-27, DOI : 10.1007 / BF00376449
- Говард, Пол; Рубин, Жан (1998), Последствия аксиомы выбора , Математические обзоры и монографии, 59 , Провиденс, Род-Айленд: Американское математическое общество
- Kőnig, D. (1927), "Uber eine Schlussweise aus dem Endlichen ins Unendliche" , Acta Sci. Математика. (Szeged) (на немецком языке) (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
- Трасс, Дж. (1976), «Некоторые случаи леммы Кенига», у Марек, В. Виктор; Сребрный, Мариан; Zarach, Анджей (ред.), Теория множеств и теория иерархии: мемориал дань Анджей Мостовского , Lecture Notes в математике, 537 ., Springer, стр 273-284, DOI : 10.1007 / BFb0096907 , МР 0429557
дальнейшее чтение
- Кензер, Дуглас (1999), "классы теории вычислимости », Справочник по теории вычислимости , Elsevier, стр. 37–85 , DOI : 10.1016 / S0049-237X (99) 80018-4 , ISBN 0-444-89882-4, MR 1720779
- Knig, D. (1926), "Sur les correances multivoques des ensembles" (PDF) , Fundamenta Mathematicae (на французском языке) (8): 114–134
- Knig, D. (1936), Theorie der Endlichen und Unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe (на немецком языке), Лейпциг: Акад. Verlag
- Симпсон, Стивен Г. (1999), Подсистемы арифметики второго порядка , перспективы в математической логике, Springer, ISBN 3-540-64882-8, MR 1723993
- Соар, Роберт И. (1987), Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимых порожденных множеств , Перспективы в математической логике, Springer, ISBN 3-540-15299-7, MR 0882921
Внешние ссылки
- Стэнфордская энциклопедия философии: конструктивная математика
- Проект Mizar полностью формализовал и автоматически проверил доказательство версии леммы Кенига в файле TREES_2 .