Математическая логика

[Dmitry Tkachenko]

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).$

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

[Brukvalub]

В 1. нужно выписать такое свойство множества, которое выполняется только для бесконечного множества. Например, только в бесконечном подмножестве множества натуральных чисел нет наибольшего элемента.

[Dmitry Tkachenko]

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

-- 27.12.2015, 23:12 --

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

[Someone]

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).$

Это правильно написано? Тогда подсказывать тоже непонятно как. Поскольку решение настолько тривиально…

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

[Dmitry Tkachenko]

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$ (теорема о дедукции)

[Someone]

Dmitry Tkachenko в сообщении #1086375 писал(а):

Можно ли слева $\exists x_1$ и $\forall x_2$ менять местами, а справа вынести $\exists x_1$ ?

Нельзя. Ни то, ни другое.

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

Dmitry Tkachenko в сообщении #1086375 писал(а):

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

Ну посмотрите аксиомы ZFC. Там среди аксиом есть подходящее высказывание.

[gefest_md]

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)$ (в конце, до применения теоремы о дедукции).