Неотделимые множества - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:41:31Z

rollbackEdits.php mass rollback

185.244.195.157 в 03:34, 1 сентября 2022

2022-09-01T03:34:11Z

VictorMinsky: tex fix

2022-05-04T01:28:08Z

tex fix

88.201.136.78: /* Источники информации */

2015-01-12T20:11:19Z

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

88.201.136.78 в 20:09, 12 января 2015

2015-01-12T20:09:00Z

88.201.136.78 в 20:07, 12 января 2015

2015-01-12T20:07:56Z

88.201.136.78: /* Источники информации */

2015-01-12T19:57:51Z

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

88.201.136.78 в 19:50, 12 января 2015

2015-01-12T19:50:06Z

88.201.136.78 в 19:00, 12 января 2015

2015-01-12T19:00:30Z

88.201.136.78 в 16:55, 12 января 2015

2015-01-12T16:55:35Z

← Предыдущая		Версия 16:41, 4 сентября 2022
Строка 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

← Предыдущая		Версия 03:34, 1 сентября 2022
Строка 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

@@ Строка 34: / Строка 34: @@
 {{Теорема
 |statement=
-Существуют такие непересекающиеся перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \subset X</tex>, <tex>Y' \subset Y</tex>, <tex>X \cap Y = \O</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми''' (англ. ''inseparable sets'').
+Существуют такие непересекающиеся перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \subset X</tex>, <tex>Y' \subset Y</tex>, <tex>X \cap Y = \varnothing</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми''' (англ. ''inseparable sets'').
 |proof=
 Рассмотрим множества <tex>X' = \{n \mid f(n) = 0\}</tex> и <tex>Y' = \{n \mid f(n) = 1\}</tex>, где <tex>f(n)</tex> {{---}} функция из леммы 2.

@@ Строка 54: / Строка 54: @@
 == Источники информации ==
 * [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

@@ Строка 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>фактов.
+Неотделимые множества используются в доказательстве других фактов<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>.
 == Примечания ==

@@ Строка 70: / Строка 70: @@
 * Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 20, с. 68. ISBN 5-900916-36-7
-* [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
 * Smullyan, Raymond M. (1958), "Undecidability and recursive inseparability", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 4: 143–147

@@ Строка 45: / Строка 45: @@
 Заметим, что <tex>g(n)</tex> всюду определена и является продолжением <tex>f(n)</tex>, что противоречит лемме 2.
 }}
 == Источники информации ==
@@ Строка 50: / Строка 71: @@
 * Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 20, с. 68. ISBN 5-900916-36-7
 * [http://en.wikipedia.org/wiki/Recursively_inseparable_sets Wikipedia - Recursively inseparable sets]
 [[Категория: Теория формальных языков]]
 [[Категория: Теория вычислимости]]

@@ Строка 6: / Строка 6: @@
 Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</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) \Rightarrow f(n) \neq \bot \Rightarrow g(n) = f(n)</tex> и <tex> \forall n \in \mathbb{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>f(i)</tex> и <tex>g(i) = f(i) = U(i, i) + 1</tex>. Получили противоречие.
+По определению универсальной функции <tex>g(n) = U(i, n)</tex> для некоторого <tex>i \Rightarrow g(i) = U(i, i)</tex>.
 Таким образом, построенная функция <tex>f(n)</tex> не имеет всюду определенного вычислимого продолжения.
@@ Строка 25: / Строка 27: @@
 \end{cases}</tex>
-Предположим, у нее существует всюду определенное продолжение <tex>g(n)</tex>.
+Предположим, у нее существует всюду определенное продолжение <tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>.
-<tex>g(n) = U(i, n)</tex> для некоторого <tex>i</tex>.
+Поскольку <tex>g(n)</tex> всюду определена, то <tex>g(i) = U(i, i) \neq \bot</tex> и определено значение <tex>f(i)</tex>. Но по построению функции <tex>f(n)</tex> видим, что <tex>f(i) \neq U(i, i)</tex>. Получили противоречие.
 }}
 {{Теорема
 |statement=
-Существуют такие непересекающиеся перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \subset X</tex>, <tex>Y' \subset Y</tex>, <tex>X \cap Y = \O</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми'''.
+Существуют такие непересекающиеся перечислимые множества <tex>X'</tex> и <tex>Y'</tex>, что не существует таких разрешимых множеств <tex>X</tex> и <tex>Y</tex>, что <tex>X' \subset X</tex>, <tex>Y' \subset Y</tex>, <tex>X \cap Y = \O</tex>, <tex>X \cup Y = \mathbb{N}</tex>. Такие множества <tex>X'</tex> и <tex>Y'</tex> называют '''неотделимыми''' (англ. ''inseparable sets'').
 |proof=
-Рассмотрим множества <tex>X' = \{n \mid f(n) = 0\}</tex> и <tex>Y' = \{n \mid f(n) = 1\}</tex>, где <tex>f(n)</tex> - функция из леммы 2.
+Рассмотрим множества <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}
+Пусть существуют <tex>X</tex> и <tex>Y</tex>, удовлетворяющие указанным свойствам, тогда вычислима характеристическая функция <tex>g(n) = \begin{cases}
-& n \in Y \\
+, & n \in Y \\
-& n \notin Y (n \in X)
+, & n \notin Y (n \in X)
-\end{cases}</tex>
+\end{cases}</tex>   множества <tex>Y</tex>.
 Заметим, что <tex>g(n)</tex> всюду определена и является продолжением <tex>f(n)</tex>, что противоречит лемме 2.
@@ Строка 49: / Строка 49: @@
 * Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 20, с. 68. ISBN 5-900916-36-7
 [[Категория: Теория формальных языков]]
 [[Категория: Теория вычислимости]]

@@ Строка 2: / Строка 2: @@
 |author=1
 |statement=
-Существует вычислимая функция, не имеющая всюду определенного вычислимого продолжения.
+Существует [[Вычислимые функции#Основные определения | вычислимая функция]], не имеющая всюду определенного вычислимого продолжения.
 |proof=
 Рассмотрим функцию <tex>f(n) = U(n, n) + 1</tex>, где <tex>U(n, n)</tex> {{---}} [[Диагональный метод|универсальная функция]].
@@ Строка 16: / Строка 16: @@
 |author=2
 |statement=
-Существует вычислимая функция, значения которой принадлежат множеству <tex>\{0, 1, \bot\}</tex>, не имеющая всюду определенного вычислимого продолжения.
+Существует [[Вычислимые функции#Основные определения | вычислимая функция]], значения которой принадлежат множеству <tex>\{0, 1, \bot\}</tex>, не имеющая всюду определенного вычислимого продолжения.
 |proof=
 Рассмотрим функцию
@@ Строка 46: / Строка 46: @@
 }}
-== Литература ==
+== Источники информации ==
-*Верещагин, Шень. Вычислимые функции.
+* Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999. с. 20, с. 68. ISBN 5-900916-36-7