Трансфинитная индукция и непротиворечивость теории множеств

[epros]

Someone писал(а):

"Противоречие" есть только на уровне бытовой логики, которая сваливает всё в одну бесформенную кучу.

Вот на уровне моей "бытовой логики" я и не могу понять, существует ли такая (вполне определённая) сущность как "аксиоматическая теория множеств" или существуют только её различные интерпретации, зависимые от де-факто принятого синтаксиса мета-языка и проч.

Someone писал(а):

Что касается зависимости от интерпретации, то что Вас, собственно говоря, удивляет? Все формализованные теории зависимы от интерпретации, включая арифметику натуральных чисел.

Да нет, ничего не смущает. Просто у меня есть такое подозрение, что для любой (сколь угодно хорошо формализованной) теории для любого её утверждения (теоремы) при желании можно построить такую интерпретацию теории, что в ней станет доказуемым (т.е. теоремой) утверждение, прямо противоположное данному.

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

Someone писал(а):

Вы не слышали о нестандартных моделях арифметики Пеано? Например, с несчётным натуральным рядом.

Увы нет. Но я, кажется, примерно догадываюсь о чём идёт речь.

Кстати, я как раз дозрел до того, чтобы задаться вопросом, каким образом аксиоматика Пеано (стандартная) скрещивается с аксиоматикой теории множеств (например, ZF). И я понял, что многого здесь не понимаю.

С одной стороны, вроде бы можно записать в качестве определения нечто вроде:
$\mathbb{N} \equiv \{\{\}, n | n = m \cup \{m\} \wedge m \in \mathbb{N}\}$
что подразумевает:
$\{\} = 1, 1 \cup \{1\} = 2, 2 \cup \{2\} = 3, ...$
Вроде бы это даже подходит под аксиому бесконечности (которая разрешает существование множества, включающего последователя для каждого своего элемента). Что касается других аксиом Пеано (помимо аксиом единицы и последователя, которые явно вошли в данную запись), то они вроде бы тоже учтены:
- Предшественнику единицы в этом множестве просто неоткуда взяться.
- Единственность последователя $n$ вроде бы следует из его определения как $n \cup \{n\}$.
- Аксиома индукции не вошла, но можно считать, что она является следствием трансфинитной индукции по отношению порядка $\in$, которая присутствует где-то в более общей аксиоматике.

Но вот в чём проблема: Это определение очевидным образом тавтологично, и я не очень понимаю, что с этим можно сделать. Действительно, как можно определять понятие (в данном случае - $\mathbb{N}$) таким образом, что правая часть определения записана через само это понятие?

Я посмотрел, какую аксиоматику предлагал сам Пеано (который не привязывался к аксиомактике теории множеств), и у меня тоже возникли вопросы. Давайте я для начала выпишу эту аксиоматику, чтобы можно было посмотреть, правильно ли я её понимаю. Итак, определяем предикат $P_N(n)$, который читается как "является натуральным числом", как удовлетворяющий следующим аксиомам:
1. $P_N(1)$
2. $P_N(n) \to (n = n)$
3. $P_N(n) \wedge P_N(m) \to [(n = m) \leftrightarrow (m = n)]$
4. $P_N(n) \wedge P_N(m) \wedge P_N(k) \to [(n = m) \wedge (m = k) \to (n = k)]$
5. $P_N(n) \wedge (m = n) \to P_N(m)$
6. $P_N(n) \to P_N(inc\{n\})$
7. $P_N(n) \wedge P_N(m) \to [(n = m) \leftrightarrow (inc\{n\} = inc\{m\})]$
8. $P_N(n) \to \overline{inc(n) = 1}$
9. $P(1) \wedge [P_N(n) \wedge P(n) \to P(inc\{n\})] \to [P_N(n) \to P(n)]$

Аксиомы 2 - 5 сейчас вроде бы принято относить к базовой аксиоматике, определяющей отношение равенства:
2. $n = n$ - рефлексивность
3. $(n = m) \leftrightarrow (m = n)$ - симметричность
4. $(n = m) \wedge (m = k) \to (n = k)$ - транзитивность
5. $P(n) \wedge (m = n) \to P(m)$ - замкнутость предиката $P(n)$ по отношению к равенству

Из оставшихся пяти аксиом (собственно и относимых сегодня к аксиоматике Пеано):
1. Аксиома единицы - с ней всё ясно

Аксиомы 6 - 8 определяют функцию $inc\{n\}$ (взятия последователя):
6. Существование последователя
7. Инъективность функции (единственность последователя)
8. Отсутствие предшественника единицы

И наконец:
9. Аксиома индукции

Что мне здесь непонятно:
- Аксиома (5) - замкутость по отношению к равенству - если её не относить собственно к аксиоматике Пеано, то она является высказыванием в логике второго порядка, поскольку является утверждением относительно любого предиката. Поэтому я не могу понять, как она может быть частью теории, записанной в логике первого порядка.
- Аксиома индукции (9), собственно, тоже является высказыванием относительно любого предиката, а потому непонятен её статус в теории первого порядка.

Насколько я понимаю, конструктивное решение может быть, например, таково:
- Аксиома (5) не исключается из аксиоматики Пеано, т.е. необходимость её формулировки для произвольного предиката отпадает.
- Аксиома бесконечности (из теории множеств) не принимается. Как следствие этого "множество всех натуральных чисел" как понятие вообще не определяется. Аксиомы (6) и (7) - существование и единственность последователя - трактуются как индуктивная схема для построения определений следующих натуральных чисел через предыдущие. Естественно, множество всех актуально определённых чисел остаётся всегда конечным.
- Аксиома (9) - индукция - выносится за рамки арифметики натуральных чисел, т.е.она появляется в аксиоматике теории только после того, как арифметика закончена на каком-то из актуально определённых натуральных чисел, и относится она к определению того конкретного предиката $P(n)$, который мы намерены определить на конечном множестве актуально определённых натуральных чисел.

Естественно, теории при этом получаются заведомо разными в зависимости от того, на каком конкретно натуральном числе мы остановились. На первый взгляд обобщение этих теорий на "все натуральные числа" представляется естественным. Однако я что-то пока никак не пойму, как это можно сделать на формальном языке логики первого порядка без тавтологии в определениях.

P.S.Кстати, я тут подумал как определяется предикат $P_{\infty}(\alpha)$ - "является ординалом", и там вроде бы можно обойтись без тавтологий. Сначала определяем предикат $T(\alpha)$ - "содержит только подмножества":
$T(\alpha) \equiv \forall \beta \in \alpha : \beta \subseteq \alpha$ (где $\beta \subseteq \alpha \equiv \forall \gamma \in \beta : \gamma \in \alpha$)
Т.е. $T(\alpha) \equiv \forall \beta \in \alpha \verb
Таким образом мы гарантируем, что $\alpha$, для которого выполняется данный предикат, является множеством, содержащим только элементы "заключённые в фигурные скобки" (в том числе - пустое множество $\{\}$), "внутренность" которых (если она не пуста) тоже присутствует в списке элементов множества.
Поскольку не очевидно, что из $T(\alpha)$ следует $\forall \beta \in \alpha: T(\beta)$, то добавим это условие в определение $P_{\infty}(\alpha)$:
$P_{\infty}(\alpha) \equiv T(\alpha) \wedge \forall \beta \in \alpha: T(\beta)$

Видно, что:
- $P_{\infty}(\{\})$ - Поскольку $\beta \in \{\}$ ложно, из него следует любое утверждение. А поскольку с квантора $\forall \beta \in \{\}$ начинаются обе части конъюнкции, составляющей $P_{\infty}(\{\})$, то обе они истинны и конъюнкция в целом истинна.
- $P_{\infty}(\alpha) \to P_{\infty}(\alpha \cup \{\alpha\})$ - непосредственно проверяется для обоих элементов пары $\{\beta, \{\beta\}\}$, где $\{\beta\} = \alpha$
- $P_{\infty}(\alpha) \to [\beta \in \alpha \to P_{\infty}(\beta)]$ - тоже нетрудно доказать.

Ясно также, что натуральное число - это ординал, меньший чем $\omega_0$, но как последнее условие записать - ума не приложу. Что касается отношения "меньше", то оно записывается как $\in$, но вот как определить $\omega_0$...

P.P.S. Вау! Я кажется сообразил, как без всяких тавтологий определить $\omega_0$, оно же $\mathbb{N}$, а именно - через ординалы. Логика такова:
1. Берём определённый выше предикат $P_{\infty}(\alpha)$ - "является ординалом".
2. Определяем предикат "является предельным" следующим образом: $L(\alpha) \equiv \forall \beta \in \alpha \verb - т.е. что между данным ординалом и любым ординалом, который меньше него, имеется ещё ординал.
3. Через них определяем предикат: "является счётной бесконечностью" следующим образом: $P_0(\alpha) \equiv P_{\infty}(\alpha) \wedge L(\alpha) \wedge \exists \beta \in \alpha \wedge[\beta \in \alpha \wedge L(\beta) \to \beta = \{\}]$ - т.е. предельный ординал, меньше которого есть только один предельный ординал - единица.

Дело за малым: доказать, что $\exists! \omega_0 : P_0(\omega_0)$ - счётная бесконечность существует и единственна...

[Macavity]

Someone писал(а):

П.Дж.Коэн. Теория множеств и континуум-гипотеза. "Мир", Москва, 1969.

Цитата:

Умер математик Пол Коэн, доказавший недоказуемость континуум-гипотезы

29 Марта 2007, 06:22

В США в возрасте 72 лет скончался математик Пол Джозеф Коэн.



Коэн достиг значительных успехов в самых разных областях математики. Как отмечает Brisbane Times, в 1964 году ученый был удостоен премии Бохера за достижения в области анализа, а в 1966 году получил медаль Филдса - эквивалент Нобелевской премии - за изучение логики. В следующем году исследования в области логики принесли ему также Национальную медаль за научные достижения.

Ученик Коэна, профессор Принстонского университета Питер Сарнак назвал покойного "одним из самых блестящих математиков двадцатого века". Благодаря работам Коэна, сказал Сарнак, "математика стала выглядеть простой и унифицированной".

Вершиной профессиональной деятельности Коэна в области теории множеств его коллеги называют опубликованное в 1963 году доказательство невозможности доказательства так называемой континуум-гипотезы (доказательство невозможности опровергнуть которую было сделано в 1940 году Куртом Гёделем).

В отличие от некоторых математиков, надевающих на себя маску нелюдимых сверхинтеллектуалов, Коэн всегда оставался человеком с разнообразными интересами. Он говорил на английском, шведском, французском, испанском, немецком и идише, играл на фортепиано и скрипке, пел в хоре Стэнфордского университета и в шведской фолк-группе.

Коэн, сын еврейских эмигрантов из Польши, вырос в Бруклине, там же начал свое образование, а в 1953 году отправился учиться в Чикагский университет. В 1961 году он начал научную и преподавательскую деятельность в Стэнфордском университете, где продолжал работать до 2004 года. Учебную работу он не оставлял до последних месяцев cвоей жизни.

[Someone]

Macavity писал(а):

Умер математик Пол Коэн, доказавший недоказуемость континуум-гипотезы

Увы...

[Macavity]

Someone писал(а):

Macavity писал(а):

Умер математик Пол Коэн, доказавший недоказуемость континуум-гипотезы

Увы...

Да, печально...