Задача по перечислимым множествам

[Until_Go_Pause]

Здравствуйте!

Есть такая задача: "Множество $U \subset \mathbb{N}\times\mathbb{N}$ - разрешимо. Определим множество нижних точек множества $U$ как: $V = \{(x,y) | (x,y) \in U, \forall z < y: (x,z) \notin U\}$.
а) Можно ли утверждать, что $V$ - разрешимо?
б) Можно ли утверждать, что если $U$ - перечислимо, то $V$ - перечислимо."

Подскажите, пожалуйста, верно ли я решил пункт а):
а) Докажем, что $V$ - разрешимо. Пусть $\overline U$ - алгоритм вычисления характеристической функции множества $U$. Тогда алгоритм вычисления характеристической функции множества $V$ будет следующим: для некоторой входной пары $(x,y)$ запускаем алгоритм $\overline U$. Если он выдал 0, то выдаем 0 (входная пара не принадлежит множеству $U$, а, значит, и множеству $V$). Если же он выдал 1, то запускаем алгоритм $\overline U$ на паре $(x, y-1)$. Если он выдал 1, то выдаем 0, иначе запускаем алгоритм $\overline U$ на паре $(x, y-2)$. Поступаем таким образом до тех пор, пока не дойдем до вычисления $\overline U$ на паре $(x, 0)$. Если на этом шаге алгоритм выдал 1, то выдаем 0, иначе выдаем 1.

Подскажите, пожалуйста, как можно подступиться к пункту б).

[Null]

А если алгоритм зацикливается это нормально?

[Until_Go_Pause]

Null в сообщении #414793 писал(а):

А если алгоритм зацикливается это нормально?

Не могли бы Вы уточнить, какой алгоритм имеется в виду?

[Профессор Снэйп]

a) Да. С предложенным решением согласен.

б) Нет. Выберем перечислимое, но не вычислимое $X \subseteq \mathbb{N}$ и пусть $X = \{ f(0), f(1), \ldots \}$ для всюду определённой вычислимой инъективной функции $f$. Положим $U = \{ (x, f(y)) : y > x \}$. Пусть $g(x)$ равно (очевидно, единственному) $y$, такому что $(x,y) \in V$. Ясно, что $g(0) \leqslant g(1) \leqslant \ldots$ и $\lim_{t \to \infty} g(t) = +\infty$. Если $V$ перечислимо, то функция $g$ вычислима. Но тогда и $X$ тоже вычислимо: для проверки $x \in X$ нужно найти $t_x$, для которого $g(t_x) > x$ и проверить $x \in \{ f(0), f(1), \ldots, f(t_x) \}$.

[Профессор Снэйп]

Вообще, конечно, пункт б --- это классика.

Я напомню, что функция называется частично рекурсивной, если она получается из базисных применением конечного числа операторов суперпозиции, примитивной рекурсии и минимизации. Частично рекурсивные функции --- это, в точности, вычислимые числовые функции.

А в определении минимизации есть одна тонкость. Если $g$ --- частичная функция,то $f(x) = \mu y(g(x,y)=0)$ тогда и только тогда, когда при всех $x$ выполняется $g(x,f(x)) = 0$ и $g(x,z)$ определено и не равно нулю при любом $z < f(x)$. Определённость $g(x,z)$ при $z < f(x)$ часто забывают упомянуть, но она важна. В частности, $f(x)$ не всегда равно минимальному $y$, для которого $g(x,y) = 0$; например, $g(0,0)$ не определено, $g(0,1) = 0$ и $f(0)$ не определено, хотя минимальный $y$ со свойством $g(0,y)=0$ существует и равен $1$. Однако если $g$ всюду определена, то $f(x)$ всё же равно минимальному $y$ для любого $x$...

Ну и теперь для любого перечислимого $U \subseteq \mathbb{N}^2$ существует частично рекурсивная $g$, для которой $U = \{ (x,y) : g(x,y)=0 \}$. Можно заметить, что $V$ перечислимо тогда и только тогда, когда $f'(x) = \min \{ y : g(x,y) = 0 \}$ --- частично рекурсивная функция. $f'$ получается из $g$ похожим на минимизацию оператором, но это --- не минимизация!!!

Если же $U$ вычислимо, то $g$ можно выбрать всюду определённой. В этом случае взятие минимума совпадает с минимизацией, и как прямое следствие этого $V$ перечислимо. Впрочем, как было отмечено, верно даже более сильное утверждение о вычислимости $V$.

[Until_Go_Pause]

Профессор Снэйп в сообщении #414858 писал(а):

a) Да. С предложенным решением согласен.

б) Нет. Выберем перечислимое, но не вычислимое $X \subseteq \mathbb{N}$ и пусть $X = \{ f(0), f(1), \ldots \}$ для всюду определённой вычислимой инъективной функции $f$. Положим $U = \{ (x, f(y)) : y > x \}$. Пусть $g(x)$ равно (очевидно, единственному) $y$, такому что $(x,y) \in V$. Ясно, что $g(0) \leqslant g(1) \leqslant \ldots$ и $\lim_{t \to \infty} g(t) = +\infty$. Если $V$ перечислимо, то функция $g$ вычислима. Но тогда и $X$ тоже вычислимо: для проверки $x \in X$ нужно найти $t_x$, для которого $g(t_x) > x$ и проверить $x \in \{ f(0), f(1), \ldots, f(t_x) \}$.

Спасибо за ответ! К сожалению, доказательство мне не очень понятно. Скажите, пожалуйста, связаны ли $x$ и $y$ в определении функции $g(x) = y$ с теми $x$ и $y$, что фигурируют в определении множества $U$? Если это одни и те же переменные, то, как я понимаю, должно быть так: $g(x) = y$, такому, что $(x,f(y)) \in V$?

[Профессор Снэйп]

Until_Go_Pause в сообщении #415095 писал(а):

Спасибо за ответ! К сожалению, доказательство мне не очень понятно. Скажите, пожалуйста, связаны ли $x$ и $y$ в определении функции $g(x) = y$ с теми $x$ и $y$, что фигурируют в определении множества $U$?

Да вроде всё очень понятно написано. А вот вопрос непонятен

Функция $f$ у нас перечисляет $X$, причём $f$ разнозначна. Определяем $U$ так:

$$ U = \{ (0,f(1)), (0, f(2)), (0, f(3)), \ldots; (1, f(2)), (1, f(3)), \ldots; (2, f(3)), (2, f(4)), \ldots; \ldots \} $$

1) $U$ вычислимо перечислимо. Надеюсь, не вызывает сомнений.

2) Как устроено $V$? Для каждого $x \in \mathbb{N}$ образуем множество $U_x = \{ y \in \mathbb{N} : (x,y) \in U \}$, затем, если $U_x$ не пусто, выбираем наименьший $y_x \in U_x$ и помещаем пару $(x, y_x)$ в $V$.

3) Так как в нашем случае $U_x \neq \varnothing$ для любого $x \in \mathbb{N}$, то $g(x) = y_x$ --- всюду определённая функция из $\mathbb{N}$ в $\mathbb{N}$.

4) Функция $g$, сабо сомой, не обязана быть вычислимой. Однако если $V$ окажется вычислимо перечислимым, то $g$ будет вычислимой. Действительно, для вычисления $g(x)$ нужно, получив $x$ на входе, запустить процесс перечисления $V$ и ждать, когда пара $(x,y)$ попадёт в $V$ для некоторого $y$ (для каждого $x$ это произойдёт не более одного раза, а в нашем случае ровно один раз). Как только обнаруживаем $y$, для которого $(x,y) \in V$, останавливаем процесс и полагаем $g(x) = y$.

5) Для любого $x$ имеем $U_x \supset U_{x+1}$ и $g(x) = \min U_x \leqslant \min U_{x+1} = g(x+1)$, так что $g(0) \leqslant g(1) \leqslant \ldots$. Кроме того, поскольку $f$ инъективна, то при каждом $m$ неравенство $f(x) < m$ может выполняться лишь для конечного количества иксов. Значит, для некоторого $n_m$ будет $f(z) \geqslant m$ при всех $z > n_m$ и $g(n_m) = \min U_{n_m} = \min \{ f(n_m+1), f(n_m+2), \ldots \} \geqslant m$. Таким образом, $\lim_{t \to \infty} g(t) = +\infty$.

6) Ну и всё практически. Пусть $V$ перечислимо, тогда, как было отмечено выше, $g$ вычислима. Как теперь для произвольного $x \in \mathbb{N}$ определить, принадлежит ли $x$ множеству $X$? Так как $X$ есть область значений $f$, то $x \in X$ тогда и только тогда, когда $x = f(t)$ для некоторого $t$. Поскольку $g$ неограниченно возрастает, то, вычисляя последовательно $g(0)$, $g(1)$ и т. д., найдём число $t_x$, для которого $g(t_x) > x$. Однако $g(t_x) = \min \{ f(t_x+1), f(t_x+2), \ldots \}$, так что если $t$ со свойством $x = f(t)$ существует, то он обязан быть $\leqslant t_x$. Остаётся лишь вычислить конечное число значений $f(0), f(1), \ldots, f(t_x)$ и проверить, не равно ли одно из них иксу.

-- Вс фев 20, 2011 22:32:53 --

Переписал то же самое, что и выше, только разжевал более подробно. Надеюсь, стало понятнее

-- Вс фев 20, 2011 22:39:39 --

P. S.

(Для тех, кто шарит )

Для произвольного перечислимого $U$ имеем $V \in \Sigma^{-1}_\omega$. Более того, для каждого $V \in \Sigma^{-1}_\omega$ нетрудно построить перечислимое $U$ с этим самым $V$. Таким образом, в общем случае $V$ даже не попадает на конечный уровень иерархии Ершова; сие равносильно $V \not\leqslant_{btt} \varnothing'$.

При желании можно добиться того, чтобы $U$ было супернизким и $V \equiv_m U'$. Как следует из последних результатов Файзрахманова, $V$ в этом случае будет собственным $\Delta^{-1}_\omega$-множеством.

Тьфу ты,блин, опять ошибочка вкралась

Множество $V$, конечно же, получается из $\Sigma^{-1}_2$. Спать пора

[Until_Go_Pause]

Профессор Снэйп
Спасибо огромное за подробное объяснение, теперь мне все понятно.

Проверьте, пожалуйста, решение задачи: "Как построить универсальное множество для класса всех перечислимых множеств натуральных чисел, исходя из того, что всякое перечислимое множество есть множество значений некоторой функции $U_n$?"

Решение:
Пусть $U$ - универсальная функция для класса вычислимых функций одного аргумента. Т.е. для каждого $n$ функция $U_n: x \to U(n, x) $ является вычислимой, и все вычислимые функции встречаются среди $U_n$. Т.к. $U_n$ - вычислимые функции (все вычислимые функции, которые бывают), то области их значений - перечислимые множества (все, которые бывают). Тогда множество $W = \{(n, U_n(x))| x \in \mathbb N\}$ будет универсальным.

[Профессор Снэйп]

Until_Go_Pause в сообщении #415218 писал(а):

Как построить универсальное множество

Осталось лишь понять, что Вы называете "универсальным множеством".

Впрочем, думаю, Ваш пример годится практически для любого определения универсальности.

Кстати, стандартный пример креативного множества чуть-чуть другой: $K = \{ n : U_n(n)$ определено$\}$. Оно вычислимо изоморфно построенному Вами, хотя с доказательством существования вычислимого изоморфизма надо немного повозиться. Подробности в Роджерсе и много где ещё.

Ещё есть самое известное: множество проблемы остановки $\{ (n,x) : U_n(x)$ определено $\}$. Тоже вычислимо изоморфно$K$.

-- Пн фев 21, 2011 06:04:05 --

(Для тех, кто шарит - 2)

То, что для $U \in \Sigma^0_1$ будет $V \in \Sigma^{-1}_2$, вроде как понятно.

Интересно подумать, какие именно $\Sigma^{-1}_2$-множества реализуются в виде таких $V$, хотя бы с точностью до $m$-эквивалентности. Если $A = W_n \setminus W_m \in \Sigma^{-1}_2$, то положив $U = (W_n \times \{ 1 \}) \cup (W_m \times \{ 0 \})$, получаем $A \leqslant_1 V$ функцией $x \mapsto (x,1)$. Так что универсальное множество из $\Sigma^{-1}_2$ точно реализуется. А вот далее... Надо будет с утра помыслить.

[Until_Go_Pause]

Профессор Снэйп в сообщении #415255 писал(а):

Until_Go_Pause в сообщении #415218 писал(а):

Как построить универсальное множество

Осталось лишь понять, что Вы называете "универсальным множеством".

Я использую определение: "Множество $W \in \mathbb N \times \mathbb N$ называется универсальным для некоторого класса множеств натуральных чисел, если все сечения $W_n = \{x | (n, x) \in W\}$ множества $W$ принадлежат этому классу и других множеств в этом классе нет".

Если Вас не затруднит, то подскажите пожалуйста, первый шаг в задаче: "Существует ли разрешимое множество пар натуральных чисел, универсальное для класса всех разрешимых множеств натуральных чисел". Я предполагал, что такое множество существует, а затем пытался прийти к тому, что проблема остановки при наличии такого множества разрешима, но пришел лишь к тому, что проблема остановки для программ, реализующих функцию с разрешимым множеством значений, разрешима, что, как я понимаю, противоречием не является.

[Профессор Снэйп]

Until_Go_Pause в сообщении #415376 писал(а):

Существует ли разрешимое множество пар натуральных чисел, универсальное для класса всех разрешимых множеств натуральных чисел

Нет, не существует.

Обычная диагональка. Пусть $U$ --- требуемое универсальное и $U_n = \{ x : (n,x) \in U \}$. Положим $V = \{ n : n \not\in U_n \}$. Тогда $V$ разрешимо и $V \neq U_n$ для любого $n \in \mathbb{N}$.

[Until_Go_Pause]

Профессор Снэйп в сообщении #415449 писал(а):

Until_Go_Pause в сообщении #415376 писал(а):

Существует ли разрешимое множество пар натуральных чисел, универсальное для класса всех разрешимых множеств натуральных чисел

Нет, не существует.

Обычная диагональка. Пусть $U$ --- требуемое универсальное и $U_n = \{ x : (n,x) \in U \}$. Положим $V = \{ n : n \not\in U_n \}$. Тогда $V$ разрешимо и $V \neq U_n$ для любого $n \in \mathbb{N}$.

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

[Профессор Снэйп]

Until_Go_Pause в сообщении #415376 писал(а):

Множество $W \subseteq \mathbb N \times \mathbb N$ называется универсальным для некоторого класса множеств натуральных чисел, если все сечения $W_n = \{x | (n, x) \in W\}$ множества $W$ принадлежат этому классу и других множеств в этом классе нет.

(Оффтоп)

При цитировании исправил опечатку, заменив $\in$ на $\subseteq$

Until_Go_Pause в сообщении #415218 писал(а):

построить универсальное перечислимое множество для класса всех перечислимых множеств натуральных чисел

И тут внёс небольшое исправление, добавив слово выделенное курсивом.

К чему я всё это. К тому, что хочу усложнить задачу: вдруг кто-нибудь захочет порешать.

Итак, требуется построить универсальное перечислимое множество для класса всех перечислимых множеств со свойством $W_n \neq W_m$ при $n \neq m$

[Until_Go_Pause]

Еще одна задачка: "Доказать, что существует счетное число перечислимых множеств, никакие два из которых нельзя отделить разрешимым множеством".

Опр.: два непересекающихся множества $X$ и $Y$ отделяются множеством $Z$, если множество $Z$ содержит одно из них и не пересекается с другим.

Пусть $d$ - вычислимая функция, не имеющая всюду определенного вычислимого продолжения. Пусть $X_i = \{x | d(x) = i, i \in \mathbb N\}$. Очевидно, что таких $X_i$ счетное число, и что все они перечислимы.
Докажем, что множества $X_i$ и $X_{i+1}$ не отделяются никаким разрешимым множеством. От противного: пусть существует разрешимое множество $Z$ такое, что $X_i$ и $X_{i+1}$ отделяются множеством $Z$. Пусть $X_i \subset Z$ и $X_{i+1} \cap Z = \varnothing$

Дальше, как я понимаю, нужно предъявить функцию, которая была бы всюду определенным вычислимым продолжением функции $d$, использую характеристическую функцию множества $Z$, но не могу придумать, как это сделать.

[Профессор Снэйп]

Until_Go_Pause в сообщении #417533 писал(а):

Доказать, что существует счетное число перечислимых множеств, никакие два из которых нельзя отделить разрешимым множеством

Вероятно, в условие надо ещё добавить, чтобы эти множества были попарно непересекающимися. А то если в пересечениях есть общие элементы, то неотделимость вроде как очевидна.

Until_Go_Pause в сообщении #417533 писал(а):

Очевидно, что таких $X_i$ счетное число

Не обязательно. Можно даже выбрать $d$ со значениями в $\{ 0,1 \}$.

Я бы посоветовал Вам сделать так. Пусть $l(x), r(x)$ и $c(x,y)$ --- такие вычислимые функции, что $x = c(l(x), r(x))$. Рассмотрите $d(x) = U_{l(x)}(r(x))$.