Рекурсивно перечислимые множества

[Everest]

Множество $A$ называется рекурсивно-перечислимым, если $A=\varnothing$ или существует общерекурсивная функция $f$ такая, что $f(N)=A$.

Так вот есть теорема: Если $A$ и $B$ рекурсивно-перечислимы, то и $A \cap B$ $A \cup B$ тоже рекурсивно перечислимы.

Для объединения все очевидно. Пусть $f(N)=A, g(N)=B$, тогда
$\psi_{A \cup B}(n)=f(n)$, если $n=2k$.
$\psi_{A \cup B}(n)=g(n)$, если $n=2k+1$.

Но вот насчет пересечения ничего не придумал. Поэтому прошу мне помочь.

Может видели где-нибудь доказательство этой теоремы в литературе? Прошу подсказать :)

[Xaositect]

Ну, во-первых, у нас есть примитивно-рекурсивная биекция $\mathbb{N}^2\leftrightarrow\mathbb{N}$ (напр, $\sigma(x,y) = 2^x(2y+1)$, $\lambda(z) = ord_2(z)$(макс.степень двойки, на которую делится $z$), $\rho(x) = (x/\lambda(x) - 1)/2$, $\sigma^{-1}(x) = (\lambda(x),\rho(x))$).
Далее, можно рассмотреть $\varphi(x,y) = \begin{cases}a, f(x)=g(y)=a\\0, f(x)\neq g(y)\end{cases}$ и $\varphi'(x) = \varphi(\lambda(x),\rho(x))$ будет перечислять $(A\cap B)\cup \{0\}$. Ну а дальше пара слов про то, что этот 0 ничего не портит.

По поводу литературы - в Роджерсе ("Теория рекурсивных функций и эффективная вычислимость") наверняка есть. Обычно его доказывают для какого-то другого (эквивалентного) определения рекурсивно-перечислимых множеств, напр. как области определения или значений частично-рекурсивной функции.

[Everest]

Не совсем уловил: как он перечислять будет. Поясните пожалуйста в двух словах :)

[Xaositect]

Ну как
$(\lambda(x),\rho(x))$ пробегает все возможные пары натуральных чисел.
Если при этом значения $f$ на левой части и $g$ на правой равны, то это значение принадлежит пересечению. А иначе мы выдаем 0.
Так что получаем, что образ всего $\mathbb{N}$ будет как раз состоять из пересечения и нуля.

[Everest]

Все разобрался. Просто огромное Вам спасибо :) Вы очень выручили :)

[Dandan]

число n $\implies$ пара чисел x, y $\implies$ выводим f(x), если f(x) = g(y)

[Everest]

А $\rho (x)=\frac{\frac{x}{\lambda(x)}-1}{2}$ именно так?

[Xaositect]

ну вроде да
в общем, разберитесь сами с этой биекцией, она достаточно просто пишется. Или посмотрите в том же Роджерсе или Мендельсоне(в Мендельсоне "введение в математическую логику" точно была в главе про примитивно-рекурсивные, в Роджерсе должна быть)

[Dandan]

эту биекцию очень просто понять, если на нее посмотреть

1 2 4 7 ...
3 5 8 ...
6 9 ...
10...
...

т.е. идем по диагоналям сверху вниз

[Xaositect]

Это не та, которую я написал, но да, эту тоже можно :)