Введение

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

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

Заявление леммы

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

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

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

Эффективность вычислений

Аспекты вычислимости леммы Кёнига были тщательно исследованы. Для этой цели удобно сформулировать лемму Кёнига в виде утверждения, что любое бесконечное конечно ветвящееся поддерево имеет бесконечный путь. Здесь обозначает множество натуральных чисел (рассматриваемое как порядковое число) и – дерево, узлы которого являются конечными последовательностями натуральных чисел, где родительский узел получается удалением последнего элемента из последовательности. Каждая конечная последовательность может быть отождествлена с частичной функцией из в себя, а каждый бесконечный путь – с полной функцией. Это позволяет провести анализ с использованием методов теории вычислимости. Поддерево, в котором каждая последовательность имеет лишь конечное число непосредственных продолжений (то есть дерево имеет конечную степень, если рассматривать его как граф), называется конечно ветвящимся. Не каждое бесконечное поддерево имеет бесконечный путь, но лемма Кёнига показывает, что любое конечно ветвящееся бесконечное поддерево должно иметь такой путь. Для любого поддерева обозначение обозначает множество узлов , через которые проходит бесконечный путь. Даже если вычислимо, множество может быть не вычислимым. Всякий раз, когда поддерево имеет бесконечный путь, этот путь может быть вычислен из , шаг за шагом, жадно выбирая преемника в на каждом шаге. Ограничение на гарантирует, что этот жадный процесс не зайдёт в тупик. Известно, что существуют не конечно ветвящиеся вычислимые поддеревья , не имеющие арифметического пути, и даже гиперарифметического пути. Однако, каждое вычислимое поддерево с путем должно иметь путь, вычислимый из O Клини, канонического -полного множества. Это связано с тем, что множество всегда (для значения этой нотации см. аналитическую иерархию), когда вычислимо. Более детальный анализ был проведен для вычислимо ограниченных деревьев. Поддерево называется вычислимо ограниченным или рекурсивно ограниченным, если существует вычислимая функция из в такая, что для каждой последовательности в дереве и каждого натурального числа , -й элемент последовательности не превосходит . Таким образом, определяет границу для того, насколько "широко" дерево. Следующие теоремы применимы к бесконечным, вычислимо ограниченным, вычислимым поддеревьям : любое такое дерево имеет путь, вычислимый из , канонического Тьюринг-полного множества, способного решать проблему останова. У любого такого дерева есть низкий путь. Это известно как теорема о низком основании. У любого такого дерева есть путь, свободный от гипериммунных функций. Это означает, что любая функция, вычислимая по этому пути, доминируется вычислимой функцией. Для любого невычислимого подмножества дерево имеет путь, который не вычисляет . Слабая форма леммы Кёнига, утверждающая, что каждое бесконечное бинарное дерево имеет бесконечную ветвь, используется для определения подсистемы WKL0 арифметики второго порядка. Эта подсистема играет важную роль в обратной математике. Здесь бинарное дерево – это дерево, в котором каждый член каждой последовательности в дереве равен 0 или 1, то есть дерево вычислимо ограничено постоянной функцией 2. Полная форма леммы Кёнига не доказуема в WKL0, но эквивалентна более сильной подсистеме ACA0.

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

Доказательство, приведенное выше, обычно не считается конструктивным, поскольку на каждом шаге в нем используется доказательство от противного для установления существования смежной вершины, из которой можно достичь бесконечного числа других вершин, а также из-за зависимости от слабой формы аксиомы выбора. Факты о вычислительных аспектах леммы позволяют предположить, что не существует доказательства, которое было бы признано конструктивным основными школами конструктивной математики. Теорема о вентиляторе, с классической точки зрения, является обратной к форме леммы Кёнига. Подмножество S называется баром, если любая функция из в множество имеет некоторый начальный отрезок в S. Бар называется отделимым, если любая последовательность либо принадлежит бару, либо не принадлежит ему (это предположение необходимо, поскольку теорема обычно рассматривается в ситуациях, где закон исключённого третьего не предполагается). Бар называется равномерным, если существует число такое, что любая функция из в имеет начальный отрезок в баре длиной не более . Теорема Брауэра о вентиляторе утверждает, что любой отделимый бар является равномерным. Это можно доказать в классическом контексте, рассматривая бар как открытое покрытие компактного топологического пространства . Каждая последовательность в баре представляет собой базовое открытое множество этого пространства, и эти базовые открытые множества покрывают пространство по предположению. В силу компактности, это покрытие имеет конечный подпокрывающий набор. N в теореме о вентиляторе можно принять равным длине самой длинной последовательности, базовое открытое множество которой содержится в конечном подпокрытии. Это топологическое доказательство может быть использовано в классической математике для демонстрации справедливости следующей формы леммы Кёнига: для любого натурального числа k, любое бесконечное поддерево дерева имеет бесконечный путь.

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

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

Обобщение

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