Неотделимые множества — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (tex fix)
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
{{Лемма
 
{{Лемма
 
|author=1
 
|author=1

Версия 06:34, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.
Лемма (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 = \varnothing[/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].

Примечания

Источники информации

  • 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