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

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

Получилось решить задачу? Или она уже потеряла актуальность?

[Until_Go_Pause]

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

Получилось решить задачу? Или она уже потеряла актуальность?

Получилось все-таки продолжить мое решение:

Пусть $d(x)$ - вычислимая функция, не имеющая всюду определенного вычислимого продолжения. Пусть $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$. Рассмотрим функцию $f(x)=\left\{ \begin{array}{*{35}l} 1 &, d(x) = i \\ 0 &, d(x)= i+1 \\ \text{не определена} &, \text{иначе}\\ \end{array} \right.$
Очевидно, что $f(x)$ не имеет всюду определенного вычислимого продолжения, т.к. если бы такое продолжение было, то $d(x)$ тоже имела бы всюду определенное вычислимое продолжение. Но характеристическая функция множества $Z$ является всюду определенным вычислимым продолжением функции $f(x)$ - противоречие.

Верно?

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

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

Верно?

НЕТ, не верно!!!

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

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

С чего Вы это взяли?

-- Ср мар 02, 2011 19:56:17 --

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

Очевидно, что $f(x)$ не имеет всюду определенного вычислимого продолжения, т.к. если бы такое продолжение было, то $d(x)$ тоже имела бы всюду определенное вычислимое продолжение.

И это не верно.

И вообще непонятно, почему надо доказывать неотделимость $X_i$ от $X_{i+1}$, а не $X_i$ от $X_j$ при $i \neq j$...

[Until_Go_Pause]

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

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

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

С чего Вы это взяли?

А разве мы не можем выбрать такую функцию $d(x)$, чтобы $X_i$ было счетное число?

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

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

Очевидно, что $f(x)$ не имеет всюду определенного вычислимого продолжения, т.к. если бы такое продолжение было, то $d(x)$ тоже имела бы всюду определенное вычислимое продолжение.

И это не верно.

Почему? Ведь если бы$f(x)$ имела бы всюду определенное вычислимое продолжение, то мы могли бы положить $d(x)$ равным этому самому вычислимому продолжению $f(x)$ там, где $d(x)$ не определена.

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

И вообще непонятно, почему надо доказывать неотделимость $X_i$ от $X_{i+1}$, а не $X_i$ от $X_j$ при $i \neq j$...

Да, вот тут полностью согласен.

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

Скучно...

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

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

А разве мы не можем выбрать такую функцию $d(x)$, чтобы $X_i$ было счетное число?

Вы утверждаете, что можно --- Вам это и доказывать. До сих пор Вы утверждали, что утверждение очевидно для произвольной непродолжаемой $d$. Однако для произвольной $d$ оно не верно.

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

Почему? Ведь если бы$f(x)$ имела бы всюду определенное вычислимое продолжение, то мы могли бы положить $d(x)$ равным этому самому вычислимому продолжению $f(x)$ там, где $d(x)$ не определена.

Наоборот. Если $f$ непродолжаема, то $d$ тоже непродолжаема. В обратную сторону неверно.

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

Задело меня за живое. По теории вычислимости так редко задачи появляются, а тут в кои-то веки появилась, но топикстартер впал в заблуждение и упорствует в нём!

ТС, похоже, правильное решение уже не интересует. Но на всякий случай поясню некоторые подробности, мало ли кто зайдёт почитать

1) Частичная вычислимая функция, не имеющая продолжения до всюду определённой вычислимой функции, может принимать как счётное множество значений, так и любое конечное множество значений мощности $\geqslant 2$.

Пример со счётным множеством значений --- функция $\psi(x) = \varphi_x(x)$, где $\varphi_x(y)$ --- значение, вычисленное на машине с номером $x$ от аргумента $y$ ($\varphi_x(y) = U_x(y)$ согласно одному из обозначений топикстартера). Ясно, что множество значений $\psi$ равно $\mathbb{N}$ (для любого $a \in \mathbb{N}$ существует $b \in \mathbb{N}$, для которого $\varphi_b(y) = a$ при любом $y$, и $\psi(b) = a$). Если предположить, что $\psi(x) = f(x)$ для некоторой всюду определённой вычислимой $f$ и любого $x$ из области определения $\psi$, то $f(y) + 1 = \varphi_c(y)$ для некоторого $c \in \mathbb{N}$ и $\psi(c) = \varphi_c(c) = f(c) + 1 = \psi(c) + 1$, значения в обоих частях равенства определены и налицо противоречие.

Пример с $k$ различными значениями для $k \geqslant 2$... Пусть $h$ --- вычислимая всюду определённая функция из $\mathbb{N}$ на $\{ 0, \ldots , k-1 \}$, $s$ --- перестановка множества $\{ 0, \ldots, k-1 \}$ без неподвижных точек и $\psi_k(x) = h(\psi(x))$. Противоречие получается, если рассмотреть $c \in \mathbb{N}$ со свойством $h(\varphi_c(y)) = s(f(y))$, где $f$ предположительно продолжает $\psi_k$.

Несложным обобщением приведённых выше примеров можно понять, что непродолжаемую $\psi$ можно выбрать так, что область значений $\psi$ --- любое наперёд заданное вычислимо перечислимое подмножество $\mathbb{N}$, содержащее более одного элемента.

2) Пусть $d$ --- некоторая частичная вычислимая функция из $\mathbb{N}$ в $\mathbb{N}$, $i \neq j$ --- натуральные числа и

$$ f(x) = \begin{cases} 0, &d(x) = i \\ 1, &d(x) = j \\ \text{не определено}, &\text{иначе} \end{cases} $$

Топикстартер утверждает, что если $d$ не имеет всюду определённого вычислимого продолжения, то $f$ также не имеет такого продолжения. Однако это опять же неверно!!! Возьмём, например,

$$ d(x) = \begin{cases} 2\varphi_y(y), &x = 2y \\ 2\varphi_y(y)+1, &x = 2y + 1 \end{cases} $$

Если предположить, что $d$ имеет всюду определённое вычислимое продолжение $g$, то, положив $h(x) = \lfloor g(2x)/2 \rfloor$, получим всюду определённое вычислимое продолжение $\psi(x) = \varphi_x(x)$, что, как было установлено выше, невозможно. Однако если теперь взять $i = 0$ и $j = 1$, то $f(x)$ имеет всюду определённое вычислимое продолжение --- характеристическую функцию множества нечётных чисел.

И, кстати, если уж продолжать этот пример, то множества $\{ x : d(x) = 0 \}$ и $\{ x : d(x) = 1 \}$ отделяются друг от друга вычислимым множеством $\{ 2x : x \in \mathbb{N} \}$, что зарубает лживые измышления топикстартера на корню!!!

3) Остаётся резонный вопрос --- как же тогда решать задачу?

Ну, например, так. Полагаем $X_i = \{ x : \varphi_x(x) = i \}$ (то есть здравое зерно в конструкции топикстартера было, требовалось лишь задать $d$ более конструктивно). Имеем $X_0, X_1, \ldots$ --- счётное семейство непустых непересекающихся перечислимых подмножеств $\mathbb{N}$. Пусть теперь $i \neq j$ и вычислимое множество $Z$ таково, что $X_i \subseteq Z$, $X_j \subseteq \overline{Z}$. Пусть $a,b \in \mathbb{N}$ таковы, что $\varphi_a(y) = i$ и $\varphi_b(y) = j$ для любых $y \in \mathbb{N}$. Положим

$$ f(x) = \begin{cases} b, & x \in Z \\ a, & x \not\in Z \end{cases} $$

Тогда $f$ всюду определена и вычислима. По теореме о неподвижной точке существует $n \in \mathbb{N}$, такое что $\varphi_n(y) = \varphi_{f(n)}(y)$ для всех $y \in \mathbb{N}$. Однако если $f(n) = b$, то $\varphi_n(n) = \varphi_b(n) = j$, $n \in X_j \subseteq \overline{Z}$ и $f(n) = a$. С другой стороны, если $f(n) = a$, то $\varphi_n(n) = \varphi_a(n) = i$, $n \in X_i \subseteq Z$ и $f(n) = b$. В обоих случаях противоречие!

4)

(Оффтоп)

А без теоремы о неподвижной точке, увы, никуда Неотделимость прообразов нуля и единицы --- характеризующее свойство главной вычислимой нумерации семейства $\{ \varnothing, \{ 0 \}, \{ 1 \} \}$, главность в данном случае эквивалентна предполноте, предполнота --- полноте относительно $\varnothing$, и ещё предполнота эквивалентна существованию эффективно вычисляемой неподвижной точки. Если вкратце, то не будет неподвижной точки --- не будет главности, и, как следствие, не будет неотделимости.

[Until_Go_Pause]

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

P.S. К сожалению, Вы были не совсем внимательны (хотя это скорее я слишком коряво написал свою мысль), т.к. я утверждал, что если $f(x)$ имеет всюду определенное вычислимое продолжение, то и $d(x)$ тоже его имела бы. Вы же считаете, что я утверждал, что если $d(x)$ не имеет всюду определённого вычислимого продолжения, то $f(x)$ также не имеет такого продолжения.

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

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

я утверждал, что если $f(x)$ имеет всюду определенное вычислимое продолжение, то и $d(x)$ тоже его имела бы. Вы же считаете, что я утверждал, что если $d(x)$ не имеет всюду определённого вычислимого продолжения, то $f(x)$ также не имеет такого продолжения.

Это одно и то же.

$$ (A \rightarrow B) \equiv (\neg B \rightarrow \neg A) $$