Доказать, что существует множество, не ПРМ

[miraina]

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

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

1) Положим $g ( x ) = sign ( F ( x, x ) )$ , где $F ( x, x )$ − общерекурсивная функция.

2) Так как $F ( x, x )$ общерекурсивна, то $ g ( x )$ также общерекурсивная функция и принимает значения 0 или 1.

3) Вот этот шаг мне непонятен: почему из того, что функция ПРМ следуем, что мы обязательно найдем $n$ ?
Предположим, что $g ( x )$ является примитивно рекурсивной.
Тогда существует $n$ , что для любого $ x$: $\overline{sign}{F ( x, x ) } = F ( n, n )$

4) Почему это противоречие?
Откуда при $x = n$ получили бы противоречие: $\overline{sign}{F ( n, n ) } = F ( n, n )$ . Таким образом, получили, что множество, характеристической функцией которого служит функция $g ( x )$ определяет рекурсивное множество, которое не является примитивно рекурсивным.

Простите, если спрашиваю простые вещи. Заранее спасибо!

[nikvic]

Напишите аккуратнее, что Вы хотите доказать.

[miraina]

nikvic в сообщении #699507 писал(а):

Напишите аккуратнее, что Вы хотите доказать.

Поправила:

Цитата:

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

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

[nikvic]

Наверное, всё-таки рекурсивное множество, которое не есть ПРМ.
В 1) строится универсальная ОРФ, являющаяся универсальной для характеристических функций всех ПРМ. Из неё "диагональю" строится одноместная функция $g$. Если она ПР, то у неё есть "имя" по 1), конкретное число. Но это число можно использовать и как аргумент!