Истинность схем

[knizhnik]

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

-- 17.01.2017, 08:41 --

Правда выразимых формулой предикатов все же счетное количество. Что же проверять? Истинность схемы для всех предикатов или только для выразимых?

[Someone]

Аксиомы не доказывают.

Или Вы не полностью сформулировали задачу?

[knizhnik]

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

[Someone]

Ну, они как-то единообразно должны доказываться. Сразу для всех предикатов.

[knizhnik]

Важно не только, как осуществляется проверка истинности, но и что подлежит этой проверке. Предикаты бывают выразимые, невыразимые и все вместе. Какие из них входят в схему?

[arseniiv]

«В» схему индукции $\varphi[0/x]\wedge\forall x(\varphi\to\varphi[Sx/x])\to\forall x\,\varphi$ «входит» формула $\varphi$, и я бы не сказал, что снять здесь кавычки осмысленно*. Раз схема представляет собой множество аксиом, и истинность только их и надо узнать, то ясно, что никакого несчётного количества аксиом не будет, если в язык входит лишь счётное количество формул. В данном случае входит. А что-то кроме формул подформулами формулы вы сделать не сможете.

* Можно, конечно, понимать схему как формулу расширенного языка с пропозициональными переменными и операциями подстановки, и тогда переменная $\varphi$ действительно входит туда в самом нормальном смысле. Но в конечном итоге мы всё равно будем делать по этой схеме множество формул исходного языка, иначе зачем звать её схемой.

[knizhnik]

Ладно, я понял. Пусть в схему можно подставить только формулы. При подстановке получаются новые формулы. Как проверить их истинность?

[knizhnik]

Возможно ли, что никто из участников не знает, как доказывается истинность схем? Поскольку в старых темах речь о моделях арифметики, то у них есть ответ на мой вопрос. Иначе можно дойти до того, что не существует ни одной модели в силу невозможности перебрать бесконечное множество аксиом. Должен существовать общий метод, общий подход.

-- 18.01.2017, 08:51 --

Someone, вот вы пишете:

Someone в сообщении #240861 писал(а):

В качестве "стандартной" модели натурального ряда берётся наименьшее индуктивное множество.

Скажите, вы чисто механически запомнили эту формулировку? Или вы понимаете, как доказать, что данное нечто на самом деле является моделью?

-- 18.01.2017, 09:01 --

arseniiv, вы пишете то же самое, и к вам тот же вопрос:

arseniiv в сообщении #1176468 писал(а):

Вот стандартная модель арифметики. Она вкладывается во все остальные.

arseniiv в сообщении #1161158 писал(а):

Натуральные числа — это пересечение всех индуктивных множеств

[arseniiv]

knizhnik в сообщении #1185586 писал(а):

Пусть в схему можно подставить только формулы. При подстановке получаются новые формулы. Как проверить их истинность?

Ну вот вам неформальный набросок. Возьмём формулу $\varphi$ со свободными переменными $x, v_1,\ldots,v_n$* и посмотрим на соответствующую ей аксиому $\varphi[0/x]\wedge\forall x(\varphi\to\varphi[Sx/x])\to\forall x\,\varphi$ схемы индукции. Надо проверить, что при всех значениях $v_1,\ldots,v_n$ если $A\equiv\varphi[0/x]\wedge\forall x(\varphi\to\varphi[Sx/x])$ истинна, то истинна и $\forall x\,\varphi$, в стандартной интерпретации. $A$ истинна тогда и только тогда, когда $A_0\equiv\varphi[0/x]$ и $A_S\equiv\forall x(\varphi\to\varphi[Sx/x])$ обе истинны.

Придадим какие-нибудь значения $v_1,\ldots,v_n$. Интерпретация $\varphi$ при этом будет задавать какое-то подмножество $N\subset\mathbb N$. Когда $A_0$ истинна, это множество содержит ноль. Когда $A_S$ истинна, это множество вместе с $n$ содержит всегда $n+1$. Таким образом, $N$ индуктивно, и $\mathbb N\subset N$, так что $\mathbb N=N$, и выполняется $\forall x\,\varphi$.

* Если $x$ не входит в них, ясно как.