Кардиналы, исчисление высказываний

[Spook]

1. Доказать, что множество формул $\Gamma$ непротиворечиво тогда и только тогда, когда найдется формула, невыводимая из $\Gamma$.

Можно доказать, что если $\Gamma$ противоречиво, то из него выводима любая формула: пусть $\Gamma\vdash A$, $\Gamma\vdash\neg{A}$, $B$ - любая формула.
Тогда,
         $\Gamma,\neg{B}\vdash A$
         $\Gamma,\neg{B}\vdash\neg{A}$
         $\Gamma\vdash\neg{\neg{B}}$
         $\neg{\neg{B}}\vdash B$
         $\Gamma\vdash B$
Непонятно только, поможет ли это в данной задаче.
Кстати, как обозначается значок секвенции (крест, без левой четвертинки) и отрицание(перед формулой чтобы)?

2. В одном учебнике встретил утверждение. что $\eta+\eta=\eta$, но $\lambda+\lambda\neq\lambda$. Здесь $\eta$ и $\lambda$ - порядковые типа множеств рациональных и действительных чисел (с их естественным порядком). Почему это так?

[Someone]

Spook в сообщении #188359 писал(а):

TEX зачем-то все сдвинул влево

Это не \TeX, это HTML. Если Вам нужен отступ в начале строки (или длинный промежуток между словами), напишите несколько раз   (код заканчивается точкой с запятой):

     5     5.

1. А если $\Gamma$ непротиворечиво, то одна из двух формул $A$ и $\neg A$ невыводима.

2. $\lambda$ связно, а $\lambda+\lambda$ - нет.

Spook в сообщении #188359 писал(а):

Кстати, как обозначается значок секвенции (крест, без левой четвертинки) и отрицание(перед формулой чтобы)?

$\vdash$ и $\neg$?

$\vdash$ и $\neg$

[math]\TeX[/math]

[Профессор Снэйп]

Spook писал(а):

В одном учебнике встретил утверждение. что $\eta+\eta=\eta$, но $\lambda+\lambda\neq\lambda$. Здесь $\eta$ и $\lambda$ - порядковые типа множеств рациональных и действительных чисел (с их естественным порядком). Почему это так?

$\eta + \eta = \eta$, потому что любые два счётных плотных линейных порядка без концов изоморфны. Наличие изоморфизма доказывается при помощи очень красивой конструкции, именуемой челночным методом. Если интересно, могу всё расписать подробно.

$\lambda + \lambda \neq \lambda$, поскольку в $\lambda + \lambda$ найдётся ограниченное сверху непустое множество, не имеющее супремума (это множество --- первое слагаемое). А в $\lambda$ это не выполнено.

[Spook]

Someone писал(а):

1. А если $\Gamma$ непротиворечиво, то одна из двух формул $A$ и $\neg A$ невыводима.

Да, сразу как-то в голове не уложилось, теперь ясно как все оформить в решение задачи.

Someone писал(а):

$\vdash$ и $\neg$?

Точно, именно эти символы. Спасибо, все исправил.

Someone писал(а):

2. $\lambda$ связно, а $\lambda+\lambda$ - нет.

А почему $\lambda+\lambda$ не связно? Потому что как бы два интервала объединяем?

Профессор Снэйп писал(а):

Если интересно, могу всё расписать подробно.

Да, напишите пожалуйста, было бы очень интересно.

Профессор Снэйп писал(а):

$\lambda + \lambda \neq \lambda$, поскольку в $\lambda + \lambda$ найдётся ограниченное сверху непустое множество, не имеющее супремума (это множество --- первое слагаемое). А в $\lambda$ это не выполнено.

Это вроде понятно. Видимо это как-то связано со связностью-несвязностью, про которую говорил Someone. Но непонятно, почему эти рассуждения нельзя применить к $\eta+\eta$ и $\omega+\omega$ ($\omega$ - это порядковый тип множества натуральных чисел)

[Xaositect]

Spook в сообщении #188657 писал(а):

Это вроде понятно. Видимо это как-то связано со связностью-несвязностью, про которую говорил Someone. Но непонятно, почему эти рассуждения нельзя применить к $\eta+\eta$ и $\omega+\omega$ ($\omega$ - это порядковый тип множества натуральных чисел)

В $\mathbb{Q}$ есть множество, которое ограничено сверху, но не имеет точной верхней грани (пример: $\{q|q^2<2\}$), поэтому к $\eta$ это док-во неприменимо. А к $\omega+\omega\neq\omega$ применимо похожее рассуждение: "нижнее" множество натуральных чисел ограничено сверху, но не имеет максимума.

[Spook]

Xaositect, тогда не понятно, почему я не могу сказать ""нижнее"множество рациональных чисел ограничено сверху, но не имеет максимума". Это же верно. Видимо, важна плотность множества рациональных чисел во множестве действительных чисел.

[Xaositect]

Spook в сообщении #188684 писал(а):

Xaositect, тогда не понятно, почему я не могу сказать ""нижнее"множество рациональных чисел ограничено сверху, но не имеет максимума". Это же верно. Видимо, важна плотность множества рациональных чисел во множестве действительных чисел.

Доказательство того, что $\lambda+\lambda\neq\lambda$, основано на том, что для порядкого типа $\lambda$ выполняется утверждение "любое ограниченное сверху подмножество имеет супремум", а для $\lambda+\lambda$ приводится пример множества, для которого это неверно.

В случае $\eta+\eta$ мы не можем таким способом прийти к противоречию.

[Профессор Снэйп]

Spook писал(а):

Профессор Снэйп писал(а):

Если интересно, могу всё расписать подробно.

Да, напишите пожалуйста, было бы очень интересно.

Линейный порядок называется порядком без концов, если для любого $x$ найдутся $y$ и $z$, такие что $y < x < z$. Линейный порядок называется плотным, если для любых $x$ и $y$, таких что $x < y$, существует $z$, для которого $x < z < y$. Очевидно, что $\eta$ и $\eta + \eta$ --- счётные плотные линейные порядки без концов.

Теорема: Все счётные плотные линейные порядки без концов изоморфны.

Доказательство. Пусть $\langle A, <_A \rangle$ и $\langle B, <_B \rangle$ --- два счётных плотных линейных порядка без концов. Покажем, что они изоморфны.

В силу счётности имеем $A = \{ a_0, a_1, \ldots \}$ и $B = \{ b_0, b_1, \ldots \}$.

Частичным изоморфизмом этих порядков назовём такое конечное подмножество $f$ множества $A \times B$, что для любых $\langle a, b \rangle, \langle a', b' \rangle \in f$ выполнено $a <_A a' \Leftrightarrow b <_B b'$.

Определим по индукции последовательность $f_0 \subseteq f_1 \subseteq \ldots$ частичных изоморфизмов.

1) Зафиксируем произвольные $a \in A$, $b \in B$ и положим $f_0 = \{ \langle a,b \rangle \}$.

2) Пусть $f_{2t}$ определено. Если для некоторого $b \in B$ справедливо $\langle a_t,b \rangle \in f_{2t}$, то полагаем $f_{2t+1} = f_{2t}$. В противном случае пусть $f_{2t} = \{ \langle a^1, b^1 \rangle, \ldots, \langle a^s, b^s \rangle \}$ при некотором $s > 0$ и $a^1 <_A a^2 <_A \ldots <_A a^s$ (соответственно $b^1 <_B \ldots <_B b^s$). Далее действуем в зависимости от того, какой из трёх нижеперечисленных случаев выполняется.

a) $a_t <_A a^1$. Так как второй порядок не имеет левого конца, то найдётся $b \in B$, такой что $b <_B b^1$. Выберем один из таких $b$ и положим $f_{2t+1} = f_{2t} \cup \{ \langle a_t, b \rangle \}$.

b) $a^s <_A a_t$. Так как второй порядок не имеет правого конца, то $b^s <_B b$ для некоторого $b \in B$. Выберем один из таких $b$ и положим $f_{2t+1} = f_{2t} \cup \{ \langle a_t, b \rangle \}$.

c) $a^i <_A a_t <_A a^{i+1}$ для некоторого $i \in [1,s)$. Так как второй порядок плотен, то найдётся $b \in B$ со свойством $b^i <_B b <_B b^{i+1}$. Опять выберем один из таких $b$ и положим $f_{2t+1} = f_{2t} \cup \{ \langle a_t, b \rangle \}$.

3) Пусть определено $f_{2t+1}$. Действуем "симметрично" предыдущему случаю. Если для некоторого $a \in A$ справедливо $\langle a,b_t \rangle \in f_{2t+1}$, то полагаем $f_{2t+2} = f_{2t+1}$. В противном случае пусть $f_{2t+1} = \{ \langle a^1, b^1 \rangle, \ldots, \langle a^s, b^s \rangle \}$ при некотором $s > 0$ и $b^1 <_B b^2 <_B \ldots <_B b^s$ (соответственно $a^1 <_A \ldots <_A a^s$). Далее действуем в зависимости от того, какой из трёх нижеперечисленных случаев выполняется.

a) $b_t <_B b^1$. Так как первый порядок не имеет левого конца, то найдётся $a \in A$, такой что $a <_A a^1$. Выберем одно из таких $a$ и положим $f_{2t+2} = f_{2t+1} \cup \{ \langle a, b_t \rangle \}$.

b) $b^s <_B b_t$. Так как первый порядок не имеет правого конца, то $a^s <_A a$ для некоторого $a \in A$. Выберем одно из таких $a$ и положим $f_{2t+2} = f_{2t+1} \cup \{ \langle a, b_t \rangle \}$.

c) $b^i <_B b_t <_B b^{i+1}$ для некоторого $i \in [1,s)$. Так как первый порядок плотен, то найдётся $a \in A$ со свойством $a^i <_A a <_A a^{i+1}$. Опять выберем одно из таких $a$ и положим $f_{2t+2} = f_{2t+1} \cup \{ \langle a, b_t \rangle \}$.

Пусть теперь $f = \bigcup_{n \in \mathbb{N}} f_n$. Легко видеть, что $f$ --- искомый изоморфизм порядков. $\qed$

Надеюсь, понятно, почему метод, используемый в конструкции из доказательства, назван "челночным". Мы по шагам мотаемся туда-сюда между двумя порядками, как челнок в швейной машинке. На нечётных шагах вида $2t+1$ мы прихватываем стежком элемент $a_t$ первого порядка, на чётных шагах вида $2t+2$ --- элемент $b_t$ второго порядка. В пределе мы захватываем стежками все элементы обоих порядков, сшивая их изоморфизмом $f$.

P. S. Про "связность" $\lambda$ и "несвязность" $\lambda + \lambda$ я, честно говоря, сам не понял. Связность вроде бы топологическое понятие. Разве что речь идёт о топологии, имеющей в качестве базиса множество всех интервалов; это, конечно, корректно, но, на мой взгляд, чересчур надуманно в плане напрасного привлечения лишних сущностей. Что касается $\omega$, то, как уже было замечено, $\omega + \omega \neq \omega$. Действительно, в $\omega + \omega$ есть элемент, для которого существует бесконечно много меньших элементов, а в $\omega$ такого элемента нет.

P. P. S. В качестве упражнения докажите, что $\lambda = \lambda + 1 + \lambda$, $\eta = \eta + 1 + \eta$ и $\omega \neq \omega + 1 + \omega$

[Spook]

Xaositect, да, спасибо, я понял теперь.

Профессор Снэйп, спасибо за метод, буду разбираться.

Профессор Снэйп писал(а):

В качестве упражнения докажите, что $\lambda = \lambda + 1 + \lambda$, $\eta = \eta + 1 + \eta$ и $\omega \neq \omega + 1 + \omega$

1. Пусть $A=\{x|x\in\mathbb{R},x<0\}$, $B=0$, $C=\{x|x\in\mathbb{R},x>0\}$. Тогда $\overline{A}=\overline{C}=\lambda$ и $\overline{A}+\overline{B}+\overline{C}=\lambda$

2. По-моему, можно применить эту теорему. Или вот так (хотя не уверен):
пусть $A=\{x|x\in\mathbb{Q},x<0\}$, $B=0$, $C=\{x|x\in\mathbb{Q},x>0\}$. Тогда $\overline{A}=\overline{C}=\eta$ и $\overline{A}+\overline{B}+\overline{C}=\eta$

3. Действительно, в $\omega+1+\omega$ есть элемент, для которого существует бесконечно много меньших элементов, а в $\omega$ такого элемента нет .

[Профессор Снэйп]

Spook писал(а):

3. Действительно, в $\omega+1+\omega$ есть элемент, для которого существует бесконечно много меньших элементов, а в $\omega$ такого элемента нет .

Ага. А ещё $1 + \omega = \omega$ и $\omega + 1 + \omega = \omega + \omega \neq \omega$ по предыдущему

[Чудо-в-перьях]

Someone писал(а):

[
1. А если $\Gamma$ непротиворечиво, то одна из двух формул $A$ и $\neg A$ невыводима.

А может быть, обе невыводимы, если $\Gamma$ неполно? Тогда хотя бы одна из двух формул невыводима.

[gefest_md]

Spook писал(а):

1. Доказать, что множество формул $\Gamma$ непротиворечиво тогда и только тогда, когда найдется формула, невыводимая из $\Gamma$.

Непривычная формулировка. Не имеет ли смысл говорить о пустоте списка формул (множества)?

Spook писал(а):

Можно доказать, что если $\Gamma$ противоречиво, то из него выводима любая формула: пусть $\Gamma\vdash A$, $\Gamma\vdash\neg{A}$, $B$ - любая формула.
Тогда,
         $\Gamma,\neg{B}\vdash A$
         $\Gamma,\neg{B}\vdash\neg{A}$
         $\Gamma\vdash\neg{\neg{B}}$
         $\neg{\neg{B}}\vdash B$
         $\Gamma\vdash B$
Непонятно только, поможет ли это в данной задаче.
Кстати, как обозначается значок секвенции (крест, без левой четвертинки) и отрицание(перед формулой чтобы)?

Здесь принято использовать сразу слабое $\neg$-удаление ($A,\,\neg A\vdash B$). Оно доказывается в классической системе, но в интуиционисткой её принимают за аксиому.

[Чудо-в-перьях]

gefest_md писал(а):

Spook писал(а):

1. Доказать, что множество формул $\Gamma$ непротиворечиво тогда и только тогда, когда найдется формула, невыводимая из $\Gamma$.

Непривычная формулировка. Не имеет ли смысл говорить о пустоте списка формул (множества)?

По Чёрчу формулировка, кажется