Неотделимые множества — различия между версиями
(→Источники информации) |
(→Источники информации) |
||
(не показаны 2 промежуточные версии этого же участника) | |||
Строка 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>. | |
− | + | == Примечания == | |
− | + | <references /> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
== Источники информации == | == Источники информации == | ||
− | |||
* [http://en.wikipedia.org/wiki/Recursively_inseparable_sets Wikipedia {{---}} Recursively inseparable sets] | * [http://en.wikipedia.org/wiki/Recursively_inseparable_sets 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 | * 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 |
Версия 23:11, 12 января 2015
Лемма (1): |
Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения. |
Доказательство: |
Рассмотрим функцию универсальная функция. , где —Предположим, у нее существует всюду определенное продолжение и .По определению универсальной функции для некоторого .Поскольку Таким образом, построенная функция всюду определена, то . Значит, определено значение и . Получили противоречие. не имеет всюду определенного вычислимого продолжения. |
Лемма (2): |
Существует вычислимая функция, значения которой принадлежат множеству , не имеющая всюду определенного вычислимого продолжения. |
Доказательство: |
Рассмотрим функцию Предположим, у нее существует всюду определенное продолжение Поскольку для некоторого . всюду определена, то и определено значение . Но по построению функции видим, что . Получили противоречие. |
Теорема: |
Существуют такие непересекающиеся перечислимые множества и , что не существует таких разрешимых множеств и , что , , , . Такие множества и называют неотделимыми (англ. inseparable sets). |
Доказательство: |
Рассмотрим множества и , где — функция из леммы 2.Пусть существуют Заметим, что и , удовлетворяющие указанным свойствам, тогда вычислима характеристическая функция множества . всюду определена и является продолжением , что противоречит лемме 2. |
Неотделимые множества используются в доказательстве других фактов[1].
Примечания
Источники информации
- 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