О выразимости предиката для суммы натуральных чисел

[alex_dorin]

Здравствуйте !
Можно ли в логике первого порядка выразить понятие суммы 2-х натуральных чисел предикатом,
используя предикаты "равно", "больще" (или "меньше"), предикат получения для натурального следующего нат. числа ?

[knizhnik]

Здравствуйте !
Я так понимаю, что предикаты - это свойства, а сумма и получение следующего числа - операции. Как вы увязываете одно с другим и что хотите получить? Не в логике, а просто своими словами?

[alex_dorin]

предикат $NEXT(y,x)$ - натуральное $y$ следует после натурального $x$
(всегда, если нужно, можно элиминировать функциональные символы - то, что обычно называется операцией).

[knizhnik]

$N(y,x) \Leftrightarrow y=x'$
$S(a,b,c) \Leftrightarrow a=b+c$
Все элементарно, в чем затруднение?

[arseniiv]

В том, что ни $+$, ни $S$ нету.

-- Вт дек 13, 2016 02:47:46 --

Гораздо интереснее, почему такое ограничение на формулы с одними только предикатными символами.

[knizhnik]

arseniiv в сообщении #1176443 писал(а):

В том, что ни $+$, ни $S$ нету.

Вы - alex_dorin? Если у вас нет ни сложения, ни последования, то выразить ничего нельзя. Как вы хотите выражать? Через что? Через умножение? Это невозможно.
Но можно определить наши предикаты $N(y,x)$ и $S(a,b,c)$ через стандартный набор аксиом арифметики. Допустим самая первая аксиома $\forall x \ 0 \neq x'$ в новой записи выглядит так: $\forall x \ \neg N(0,x)$. Четвертая аксиома $\forall x,y \ x+y'=(x+y)'$ теперь выглядит так: $\forall x,y,z,a,b \ N(z,y) \wedge S(a,x,y) \wedge S(b,x,z) \Rightarrow N(b,a)$. Если вы перечислите в такой же манере все остальные аксиомы, вы получите определения ваших предикатов и всей арифметики в целом. Это по-прежнему элементарно, так что я не вижу, в чем затруднение.

[arseniiv]

knizhnik в сообщении #1176450 писал(а):

Это невозможно.

Ну так доказательства этого ТС, видимо, и хочет. (Кстати, он ясно дал понять, что умножения у него нет.) Я вообще-то тоже вижу, что сложение через $0,',=,<$ (хотя у нас здесь и ноль тоже не перечисляли) неопределимо, но что-то не могу предложить ответа почему именно.

knizhnik в сообщении #1176450 писал(а):

Если вы перечислите в такой же манере все остальные аксиомы, вы получите определения ваших предикатов и всей арифметики в целом.

Вообще-то было бы полезным добавить $\forall x\exists!y\,N(y,x)$ и $\forall b\forall c\exists!a\,S(a,b,c)$.

-- Вт дек 13, 2016 03:29:15 --

И вообще вы забыли, что ноль тоже надо тогда заменять на предикатный символ $O$ (и добавлять про него $\exists!x\,O(x)$).

[g______d]

А рекурсией можно пользоваться? Ведь есть же определение сложения в стиле $a+b=a'$ если $b=1$ и $a+b=(a+c)'$, если $b=c'$ для некоторого $c$. Переводить на язык предикатов мне лень, но я могу попробовать, если кто-нибудь сформулирует, что именно дано.

[knizhnik]

g______d в сообщении #1176458 писал(а):

А рекурсией можно пользоваться?

Рекурсия - это фактически индукция. А индукция - это не формула, это схема аксиом. Поэтому если ТС хочет, как он говорит, выразить предикатом, то нельзя.

g______d в сообщении #1176458 писал(а):

Ведь есть же определение сложения в стиле $a+b=a'$ если $b=1$ и $a+b=(a+c)'$, если $b=c'$ для некоторого $c$.

Ну и зачем придумывать свое определение сложения, когда Пеано все придумал? Если вопрос о том, как аксиоматизировать, то все элементарно, просто подставить и все. Но нам нужно выразить.

g______d в сообщении #1176458 писал(а):

если кто-нибудь сформулирует, что именно дано.

Предположим, дано $0,',=,<$ и больше ничего.

arseniiv в сообщении #1176455 писал(а):

Вообще-то было бы полезным добавить $\forall x\exists!y\,N(y,x)$ и $\forall b\forall c\exists!a\,S(a,b,c)$.
И вообще вы забыли, что ноль тоже надо тогда заменять на предикатный символ $O$ (и добавлять про него $\exists!x\,O(x)$).

Согласен. Принимается.

arseniiv в сообщении #1176455 писал(а):

Я вообще-то тоже вижу, что сложение через $0,',=,<$ (хотя у нас здесь и ноль тоже не перечисляли) неопределимо, но что-то не могу предложить ответа почему именно.

Если сократить список до $0,',=$, то становится видно, что без рекурсии здесь ничего сделать нельзя. А $a<c \Leftrightarrow \exists b \ b\neq 0 \wedge a+b=c $. Таким образом из сложения можно получить $<$, но вряд ли можно наоборот. Вряд ли можно придумать, как снять квантор. То есть добавление $<$ ничего полезного не дает.

[g______d]

knizhnik в сообщении #1176464 писал(а):

Ну и зачем придумывать свое определение сложения, когда Пеано все придумал?

Это и есть определение Пеано.

[knizhnik]

Кажется, вы его трансформировали. Ну ладно.
Все аксиомы Пеано можно было бы соединить знаком $\wedge$ в одну длинную неудобную формулу, о которой возможно спрашивал ТС. Но нам мешает индукция, потому что она схема. Но все это даже не входит в понятие выразить. Выразить - значит написать формулу вида $S(a,b,c) \Leftrightarrow \ldots $ , где $S(a,b,c)$ используется в самом начале только один раз!

[arseniiv]

knizhnik в сообщении #1176464 писал(а):

Если сократить список до $0,',=$, то становится видно, что без рекурсии здесь ничего сделать нельзя. А $a<c \Leftrightarrow \exists b \ b\neq 0 \wedge a+b=c $. Таким образом из сложения можно получить $<$, но вряд ли можно наоборот. Вряд ли можно придумать, как снять квантор. То есть добавление $<$ ничего полезного не дает.

Видно, но не очевидно. Вот стандартная модель арифметики. Она вкладывается во все остальные. Автоморфизмов нетривиальных у неё нет, и потому нельзя показать неопределимость через неинвариантность относительно них, что было бы удобно.

[alex_dorin]

Александр Шень
Избранные темы Computer Science. Лекция 6
https://www.lektorium.tv/lecture/13964

Как я понял, утверждает, что это возможно.
Если нужно использовать аксиому индукции для этого, это не страшно, т.к наверняка она будет использована не для бесконечного множества предикатных переменных, а для какого-то конечного числа предикатов (предикатных переменных. Аксиома индукции - формула логики второго порядка).
К сожалению, я не понял соображений А. Шеня (это лекция школьникам).

[Xaositect]

Вообще-то, он как раз говорит, что сложение выразить нельзя, можно выразить только предикаты $L_c(x, y) = x \leq y + c$ для целой константы $c$ и их булевы комбинации. В частности, можно выразить сложение с константой, а вот с переменной уже нельзя.

[knizhnik]

С какого момента слушать запись?

alex_dorin в сообщении #1176515 писал(а):

Если нужно использовать аксиому индукции для этого, это не страшно.

Нет, это проблема. Предположим, вы определяете сложение аксиоматически. Тогда что вы можете сказать про свойства этой операции? Даже элементарные законы коммутативности и ассоциативности выводятся по индукции.

alex_dorin в сообщении #1176515 писал(а):

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

Почему вы решили, что всевозможных свойств, относящихся к сложению, конечное число? Очевидно, что это не так.

alex_dorin в сообщении #1176515 писал(а):

Аксиома индукции - формула логики второго порядка

Тут всю схему надо, именно схему индукции. Без нее определение грозит быть неточным.