2014 dxdy logo

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

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




 
 Математическая логика
Сообщение27.12.2015, 21:42 
1. Пример формулы логики предикатов, которая была бы выполнимой на некотором бесконечном множестве и тождественно ложной на всех конечных множествах.
2. Не используя теорему Гёделя докажите, что $\vdash \exists x_1 \forall x_2 (A \vee B) \to \forall x_2 (\exists x_1 A \vee \exists x_1 B).$

Первое вообще кажется странным. Можно ли пример, как делать второе?

 
 
 
 Re: Математическая логика
Сообщение27.12.2015, 22:10 
Аватара пользователя
В 1. нужно выписать такое свойство множества, которое выполняется только для бесконечного множества. Например, только в бесконечном подмножестве множества натуральных чисел нет наибольшего элемента.

 
 
 
 Re: Математическая логика
Сообщение27.12.2015, 23:40 
Brukvalub, то есть нужно описАть все аксиомы строгого порядка и условие несуществование максимального элемента? Тогда на всех конечных нет интерпретации, а на бесконечном есть...

-- 27.12.2015, 23:12 --

Не понимаю как это строго записать.
А если нужна формула тождественно истинная на бесконечных множествах и не тождественно истинная на конечных?

 
 
 
 Re: Математическая логика
Сообщение28.12.2015, 00:31 
Аватара пользователя
Dmitry Tkachenko в сообщении #1086355 писал(а):
нужно описАть все аксиомы строгого порядка и условие несуществование максимального элемента?
Не обязательно именно это, но что-нибудь в таком роде. А вообще, Вы что изучаете-то? Аксиоматическую теорию множеств? Тогда у Вас должен быть готовый ответ.

Dmitry Tkachenko в сообщении #1086355 писал(а):
А если нужна формула тождественно истинная на бесконечных множествах и не тождественно истинная на конечных?
То есть, истинная для всех бесконечных множеств, но ложная для некоторых конечных? Ну, уж не знаю, как и подсказать, чтобы не получилось сразу полного решения…

Dmitry Tkachenko в сообщении #1086314 писал(а):
Не используя теорему Гёделя докажите, что $\vdash \exists x_1 \forall x_2 (A \vee B) \to \forall x_2 (\exists x_1 A \vee \exists x_1 B).$
Это правильно написано? Тогда подсказывать тоже непонятно как. Поскольку решение настолько тривиально…

Подумайте сами ещё.

 
 
 
 Re: Математическая логика
Сообщение28.12.2015, 01:01 
Someone,курс состоит из логики высказываний, логики предикатов, формальных теорий и теории алгоритмов.

Someone в сообщении #1086370 писал(а):
Поскольку решение настолько тривиально…
Пробую:

У нас нет значка $\vee,$ но $A\vee B$ можно записать как $\neg A\to B.$
Можно ли слева $\exists x_1$ и $\forall x_2$ менять местами, а справа вынести $\exists x_1$ ?

$B_1=\forall x_2 \exists x_1 (A \vee B)$ (гипотеза)
$B_2=\forall x_2 \exists x_1 (A \vee B) \to \exists x_1 (A \vee B)$ (из аксиомы исчисления предикатов $\forall A(x) \to A(t)$)
$B_3=\exists x_1 (A \vee B)$ (modus ponens к $B_1$ и $B_2$)
$B_4=\forall x_2 \exists x_1 (A \vee B)$ (правило Gen к $B_3$)
$\vdash B_1\to B_4$ (теорема о дедукции)

 
 
 
 Re: Математическая логика
Сообщение28.12.2015, 03:32 
Аватара пользователя
Dmitry Tkachenko в сообщении #1086375 писал(а):
Можно ли слева $\exists x_1$ и $\forall x_2$ менять местами, а справа вынести $\exists x_1$ ?
Нельзя. Ни то, ни другое.

А зачем, собственно говоря? Предположим, что посылка истинна. Что это означает? Что из этого следует для заключения?

Dmitry Tkachenko в сообщении #1086375 писал(а):
курс состоит из логики высказываний, логики предикатов, формальных теорий и теории алгоритмов.
Ну посмотрите аксиомы ZFC. Там среди аксиом есть подходящее высказывание.

 
 
 
 Re: Математическая логика
Сообщение28.12.2015, 14:01 
Аватара пользователя
Dmitry Tkachenko в сообщении #1086375 писал(а):
Можно ли слева $\exists x_1$ и $\forall x_2$ менять местами, а справа вынести $\exists x_1$ ?
Вообще-то нельзя делать так, как Вы это спросили. Но если очень хочется, можно добавить доказательства предложений:

$\exists x_1\forall x_2(A\vee B)\to B_1$ (в начале),
$B_4\to\forall x_2(\exists x_1 A\vee\exists x_1 B)$ (в конце, до применения теоремы о дедукции).

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group