Материал из Викиконспекты
|
|
| Строка 46: |
Строка 46: |
| | }} | | }} |
| | | | |
| − | == Примеры неотделимых множеств ==
| + | Неотделимые множества используются для доказательства разных других <ref>[http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 39, с. 63, c. 100. ISBN 5-900916-36-7]</ref>фактов. |
| | | | |
| − | * Пусть <tex>\phi</tex> вычислимая функция, тогда <tex>A = \{e : \phi_e(0) = 0 \}</tex> и <tex>B = \{e : \phi_e(0) = 1\}</tex> {{---}} неотделимые множества (Gasarch 1998, p. 1047).
| + | == Примечания == |
| | | | |
| − | * Пусть <tex>\phi</tex> Гёделева нумерация для формул в арифметики Пьяно, тогда <tex>A = \{\phi(\psi) : PA \vdash \psi \}</tex> и <tex>B = \{\phi(\psi) : PA \vdash \neg\psi \}</tex> {{---}} неотделимые множества (Smullyan 1958).
| + | <references /> |
| − | | |
| − | == Решаемые задачи ==
| |
| − | | |
| − | | |
| − | {{Определение
| |
| − | |definition = '''Полное двоичное дерево''' {{---}} множество всех двоичных слов (конечных последовательностей нулей и единиц); его элементы называют вершинами дерева; пустое слово является корнем этого дерева, а слова <tex>x_0</tex> и <tex>x_1</tex> являются сыновьями вершины <tex>x</tex>, которая является отцом своих сыновей. Поддеревом полного двоичного дерева называют множество вершин, которое вместе с каждой вершиной содержит её отца.
| |
| − | }}
| |
| − | | |
| − | {{Лемма
| |
| − | |author=Кёниг
| |
| − | |statement=Бесконечное поддерево всегда имеет бесконечную ветвь (последовательность вершин, в которой каждая следующая является сыном предыдущей).
| |
| − | }}
| |
| − | | |
| − | | |
| − | Можно показать, что эффективный вариант леммы Кёнига неверен: существует бесконечное разрешимое поддерево полного двоичного дерева, не имеющее вычислимой бесконечной ветви. (Взяв пару перечислимых неотделимых множеств, можно построить дерево, в котором любая бесконечная ветвь поворачивает направо в точках первого множества и налево в точках второго. При этом поддерево можно сделать разрешимым, так как запрет поворота можно наложить на произвольно высоком уровне, когда выяснится принадлежность одному из множеств).
| |
| | | | |
| | == Источники информации == | | == Источники информации == |
Версия 23:07, 12 января 2015
| Лемма (1): |
|
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим функцию [math]f(n) = U(n, n) + 1[/math], где [math]U(n, n)[/math] — универсальная функция.
Предположим, у нее существует всюду определенное продолжение [math]g(n) \Rightarrow f(n) \neq \bot \Rightarrow g(n) = f(n)[/math] и [math] \forall n \in \mathbb{N} \ g(n) \neq \bot[/math].
По определению универсальной функции [math]g(n) = U(i, n)[/math] для некоторого [math]i \Rightarrow g(i) = U(i, i)[/math].
Поскольку [math]g(n)[/math] всюду определена, то [math]U(i, i) \neq \bot[/math]. Значит, определено значение [math]f(i)[/math] и [math]g(i) = f(i) = U(i, i) + 1[/math]. Получили противоречие.
Таким образом, построенная функция [math]f(n)[/math] не имеет всюду определенного вычислимого продолжения. |
| [math]\triangleleft[/math] |
| Лемма (2): |
Существует вычислимая функция, значения которой принадлежат множеству [math]\{0, 1, \bot\}[/math], не имеющая всюду определенного вычислимого продолжения. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим функцию
[math]f(n) = \begin{cases}
0 & U(n, n) \neq 0 \text{, }U(n, n) \neq \bot \\
1 & U(n, n) = 0 \\
\bot & U(n, n) = \bot
\end{cases}[/math]
Предположим, у нее существует всюду определенное продолжение [math]g(n) = U(i, n)[/math] для некоторого [math]i[/math].
Поскольку [math]g(n)[/math] всюду определена, то [math]g(i) = U(i, i) \neq \bot[/math] и определено значение [math]f(i)[/math]. Но по построению функции [math]f(n)[/math] видим, что [math]f(i) \neq U(i, i)[/math]. Получили противоречие. |
| [math]\triangleleft[/math] |
| Теорема: |
Существуют такие непересекающиеся перечислимые множества [math]X'[/math] и [math]Y'[/math], что не существует таких разрешимых множеств [math]X[/math] и [math]Y[/math], что [math]X' \subset X[/math], [math]Y' \subset Y[/math], [math]X \cap Y = \O[/math], [math]X \cup Y = \mathbb{N}[/math]. Такие множества [math]X'[/math] и [math]Y'[/math] называют неотделимыми (англ. inseparable sets). |
| Доказательство: |
| [math]\triangleright[/math] |
|
Рассмотрим множества [math]X' = \{n \mid f(n) = 0\}[/math] и [math]Y' = \{n \mid f(n) = 1\}[/math], где [math]f(n)[/math] — функция из леммы 2.
Пусть существуют [math]X[/math] и [math]Y[/math], удовлетворяющие указанным свойствам, тогда вычислима характеристическая функция [math]g(n) = \begin{cases}
1, & n \in Y \\
0, & n \notin Y (n \in X)
\end{cases}[/math] множества [math]Y[/math].
Заметим, что [math]g(n)[/math] всюду определена и является продолжением [math]f(n)[/math], что противоречит лемме 2. |
| [math]\triangleleft[/math] |
Неотделимые множества используются для доказательства разных других [1]фактов.
Примечания
Источники информации
- Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 20, с. 68. ISBN 5-900916-36-7
- Wikipedia — Recursively inseparable sets
- Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math. 139, Amsterdam: North-Holland, pp. 1041–1176, MR 1673598
- Smullyan, Raymond M. (1958), "Undecidability and recursive inseparability", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 4: 143–147
