Характеристическая функция предиката

[Rocky095]

Доброго времени суток ув. форумчане!
Как будет выглядеть характеристическая функция предиката? ума не приложу
$\exists y_{y<x}(NU(y))$

[Sonic86]

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

[Rocky095]

$x=2^{15} \bigvee \exists y_{y<x}(NU(y) \& x=2^{57} 2^3 y 2^5)$
Х-есть гёделев номер цифры.
post583591.html#p583591 - полное задание

[Sonic86]

Ужасное оформление, конечно.
Нужно доказать примитивную рекурсивность предиката $NU$, потом использовать примитивные рекурсивности конъюнкции, ограниченного квантора.

Rocky095 в сообщении #584595 писал(а):

Х-есть гёделев номер цифры.

Это метаарифметическая интерпретация предиката $NU(x)$. А задан он как? Найдите в том же Мендельсоне и покажите его примитивную рекурсивность.
Примеры доказательства, кстати, есть в книге Мальцева Алгоритмы и рекурсивные функции.
А вообще следовало бы допилить старую тему, и не создавать дубли.

[Rocky095]

Вот какая идея пришла в голову:
так как гёделевы номера цифр можно предствать в виде $x={a_1}^{b_1} {a_2}^{b_2}....$, то нельзя ли доказать рекурсивность предиката NU(x), где х-гёделев номер цифры, тем что,возведение в степень- рекурсивно, умножение $xy$- рекурсивно, и равенство $x=y$-рекурсивно, значит x- тоже рекурсивен, так как он состоит из этих функций?

Преподу показал такой вариант решения:
Доказать, что предикат NU(x) является( или не является) (примитивно) рекурсивным, NU(x):"Х есть Гёделев номер цифры".
Доказательство:
Предположим $x=2^{15}$ гёделев номер цифры.
$\exists y_{y<x}(NU(y) \& x=2^{57} 2^3 y 2^5)=NU(x)$
$P(x)=\exists y_{y<x} P(y)= P(a)$
$C_p(x)=\prod_{y<a}C_p(y)$ (1)
$C_p(y)=C_p(y,((C_p)_\# a))$ (2)
По предложению (2) $C_p(y)$- примитивно рекурсивно, и так как по предложению (1) $C_p(x)$-примитивно рекурсивно, то и P(x)=NU(x)-примитивно рекурсивно.
Преподаватель сказал,что на месте P(a) -должно стоять представление $\exists y_{y<x}(NU(y))$ в бескванторной форме, как это записать?