2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 О выразимости предиката для суммы натуральных чисел
Сообщение12.12.2016, 17:41 


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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение12.12.2016, 21:04 


11/08/16

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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение12.12.2016, 21:52 


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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение12.12.2016, 22:30 


11/08/16

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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 00:43 
Заслуженный участник


27/04/09
28128
В том, что ни $+$, ни $S$ нету.

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

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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 01:15 


11/08/16

312
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)$. Если вы перечислите в такой же манере все остальные аксиомы, вы получите определения ваших предикатов и всей арифметики в целом. Это по-прежнему элементарно, так что я не вижу, в чем затруднение.

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 01:26 
Заслуженный участник


27/04/09
28128
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)$).

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 01:40 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 02:09 


11/08/16

312
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 $. Таким образом из сложения можно получить $<$, но вряд ли можно наоборот. Вряд ли можно придумать, как снять квантор. То есть добавление $<$ ничего полезного не дает.

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 02:12 
Заслуженный участник
Аватара пользователя


08/11/11
5940
knizhnik в сообщении #1176464 писал(а):
Ну и зачем придумывать свое определение сложения, когда Пеано все придумал?


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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 02:20 


11/08/16

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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 02:23 
Заслуженный участник


27/04/09
28128
knizhnik в сообщении #1176464 писал(а):
Если сократить список до $0,',=$, то становится видно, что без рекурсии здесь ничего сделать нельзя. А $a<c \Leftrightarrow \exists b \ b\neq 0 \wedge a+b=c $. Таким образом из сложения можно получить $<$, но вряд ли можно наоборот. Вряд ли можно придумать, как снять квантор. То есть добавление $<$ ничего полезного не дает.
Видно, но не очевидно. Вот стандартная модель арифметики. Она вкладывается во все остальные. Автоморфизмов нетривиальных у неё нет, и потому нельзя показать неопределимость через неинвариантность относительно них, что было бы удобно.

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 10:21 


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

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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 10:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: О выразимости предиката для суммы натуральных чисел
Сообщение13.12.2016, 11:06 


11/08/16

312
С какого момента слушать запись?
alex_dorin в сообщении #1176515 писал(а):
Если нужно использовать аксиому индукции для этого, это не страшно.
Нет, это проблема. Предположим, вы определяете сложение аксиоматически. Тогда что вы можете сказать про свойства этой операции? Даже элементарные законы коммутативности и ассоциативности выводятся по индукции.
alex_dorin в сообщении #1176515 писал(а):
наверняка она будет использована не для бесконечного множества предикатных переменных, а для какого-то конечного числа предикатов
Почему вы решили, что всевозможных свойств, относящихся к сложению, конечное число? Очевидно, что это не так.
alex_dorin в сообщении #1176515 писал(а):
Аксиома индукции - формула логики второго порядка
Тут всю схему надо, именно схему индукции. Без нее определение грозит быть неточным.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group