Функции проекций на языке элементарной арифметики

[alex.polusov]

Здравствуйте! Помогите решить задачу!

Язык элементарной арифметики предназначен для записи утверждений о натуральных числах. (включая ноль).
Сигнатура такого языка содержит:

функциональные символы(операции) $+^2, \cdot^2, S^1$
и предикатный символ $=^2$.
Степень означает количество принимаемых аргументов. $S$ означает увеличение числа на 1. Остальные символы используются в привычной нам интерпретации.

(Возможно я описал арифметику Пеано, но я не уверен)

Кроме того, дана функция(двухместный предикат) Геделя -$ S(x,c)$, такая, что для произвольного(конечного) множества $X$ найдется такое $c$, что $S(x,c)$ будет истиной для любого $x$ в $X$. (кодируем любые последовательности одним числом)

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

$nonZero(n) := \exists x. S(x) = n$
$isZero(n) := \neg nonZero(n)$
$isOne(n) := \exists x. S(x) = n \/ isZero(x)$
$lessOrEqual(a,b) := \exists y. a + y = b$
$divides(a,b) := exists y. a \cdot y = b$


Теперь нам дали следующую операцию:
$pair(x,y) = (x+y) \cdot (x+y) +x$
Нужно найти операции fst, snd такие что $fst(pair(x,y)) = x и snd(pair(x,y)) = y$.

Я попытался построить похожие операции: isFst, isSnd, но очевидно, что они не подходят под определение выше(отличаются арностью).

$isFst(x, c) := \exists b. (b \cdot b \leqslant c) \bigwedge (Sb \cdot Sb > c) & (b \cdot b + x = c)$

$isSnd(y, c) := \exists b. (b \cdot b \leqslant c) \bigwedge (Sb \cdot Sb > c) & \exists x. isFst(x, c) \bigwedge (x + y = b)$

Подскажите, может быть я что-то упускаю, и есть какой-то трюк который превращает предикат в операцию?

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»