Неотделимые множества — различия между версиями
Строка 8: | Строка 8: | ||
Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex>\forall n: g(n) \neq \bot </tex>. | Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>. Это значит, что <tex>f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex>\forall n: g(n) \neq \bot </tex>. | ||
− | По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>. Тогда <tex>g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Значит, <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие. | + | По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>. Тогда <tex>g(i) = U(i, i)</tex>. Поскольку <tex>g(n)</tex> всюду определена, то <tex>U(i, i) \neq \bot</tex>. Значит, определено значение <tex>f(i)</tex> и <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие. |
Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения. | Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения. | ||
Строка 34: | Строка 34: | ||
{{Теорема | {{Теорема | ||
|statement= | |statement= | ||
− | Существуют такие перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что <tex>X' \cap Y' = \o</tex> и не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \in X</tex>, <tex>Y' \in Y</tex>, <tex>X \cap Y = \o</tex>, <tex>X \cup Y = \mathbb{N}</tex>. | + | Существуют такие перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что <tex>X' \cap Y' = \o</tex> и не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \in X</tex>, <tex>Y' \in Y</tex>, <tex>X \cap Y = \o</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми'''. |
|proof= | |proof= | ||
− | Рассмотрим множества <tex>X' = \{n \mid f(n) = 0\}</tex> и <tex>Y' = \{n \mid f(n) = 1\}</tex>, где <tex>f(n)</tex> - функция из леммы 2. Пусть существуют <tex>X</tex> и <tex>Y</tex>, удовлетворяющие указанным свойствам. | + | Рассмотрим множества <tex>X' = \{n \mid f(n) = 0\}</tex> и <tex>Y' = \{n \mid f(n) = 1\}</tex>, где <tex>f(n)</tex> - функция из леммы 2. |
+ | |||
+ | Пусть существуют <tex>X</tex> и <tex>Y</tex>, удовлетворяющие указанным свойствам. Тогда вычислима характеристическая функция множества <tex>Y</tex>, то есть функция <tex>g(n) = \begin{cases} | ||
+ | 1 & n \in Y \\ | ||
+ | 0 & n \notin Y (n \in X) | ||
+ | \end{cases}</tex> | ||
+ | |||
+ | Заметим, что <tex>g(n)</tex> всюду определена и является продолжением <tex>f(n)</tex>, что противоречит лемме 2. | ||
}} | }} |
Версия 19:10, 1 декабря 2010
Лемма (1): |
Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения. |
Доказательство: |
Рассмотрим функцию универсальная функция. , где —Предположим, у нее существует всюду определенное продолжение . Это значит, что и .По определению универсальной функции Таким образом, построенная функция для некоторого . Тогда . Поскольку всюду определена, то . Значит, определено значение и . Получили противоречие. не имеет всюду определенного вычислимого продолжения. |
Лемма (2): |
Существует вычислимая функция, значения которой принадлежат множеству , не имеющая всюду определенного вычислимого продолжения. |
Доказательство: |
Рассмотрим функцию Предположим, у нее существует всюду определенное продолжение .для некоторого . . Поскольку всюду определена, то . Но тогда по построению функции видим, что . Получили противоречие. |
Теорема: |
Существуют такие перечислимые множества и , что и не существует таких разрешимых множеств и , что , , , . Такие множества и называют неотделимыми. |
Доказательство: |
Рассмотрим множества и , где - функция из леммы 2.Пусть существуют Заметим, что и , удовлетворяющие указанным свойствам. Тогда вычислима характеристическая функция множества , то есть функция всюду определена и является продолжением , что противоречит лемме 2. |