Пятая аксиома Пеано и Ларина

[Someone]

Unx в сообщении #1090902 писал(а):

Я уже все подряд читаю.

Очень плохо.

Unx в сообщении #1090902 писал(а):

что здесь считать носителем интерпретации

То самое множество, которое Вы выбрали для построения интерпретации.

Unx в сообщении #1090902 писал(а):

что значит термин индивидные переменные

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

P.S. Если Вы читаете всё подряд, сваливаете всё в одну кучу и не понимаете обычного русского языка, то единственное, что могу посоветовать — бросить всё и заняться чем-нибудь более понятным.

[Xaositect]

Unx в сообщении #1090902 писал(а):

Так написано в книге. Помогите понять, что значит термин индивидные переменные. И что здесь считать носителем интерпретации (может быть множество $A$ - носитель структуры)?

Как правило, если Вам что-то непонятно в параграфе 3.2, есть смысл прочитать предыдущие параграфы. В данном случае - параграф 3.1

[Unx]

Думаю, что само определение истинности наверное не нужно переписывать. Важно, что в книге оно дается при некоторой оценке $\pi$. То есть всем переменным присвоены конкретные значения, а тогда и все функции тоже принимают конкретные значения. Но если вернуться к определению модели, то в нем оценка не упоминается:

Unx в сообщении #1090385 писал(а):

Модель. Пусть $S$ - это набор предложений. Моделью множества $S$ называется структура $\mathcal M$ такая что $\mathcal M \vDash \sigma$ для любого $\sigma \in S$, причем имеет место равенство сигнатур $sig(\mathcal M)=sig(S)$.

Если с выражением $\mathcal M, \pi \vDash \sigma$ теперь все более или менее понятно, то что такое $\mathcal M \vDash \sigma$ ?

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

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

Какие тогда переменные языка формальной теории не являются индивидными? Хотелось бы увидеть пример.

[Xaositect]

Тут сейчас начнется путаница, потому что терминология в разных книгах по логике может очень сильно различаться. В Вашем определении $S$ - это набор предложений. Предложением обычно называются замкнутые формулы, то, что у Верещагина-Шеня названо "суждениями" в конце параграфа 3.2. Там доказывается, что истинность замкнутых формул от оценки не зависит.

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

[Unx]

Цитата:

Это позволяет легко доказать (индукцией по построению формулы) такое утверждение: если две оценки придают одинаковые значения всем параметрам формулы $\varphi$, то $[\varphi](\pi_1)=[\varphi](\pi_2)$. Другими словами, истинность формулы определяется значениями её параметров.
45.
Проведите это индуктивное рассуждение подробно.

А что значит индукцией по построению формулы? Как доказать это подробно?

[arseniiv]

Множество формул определяется индуктивно, т. е. как наименьшее множество $i[\mathcal O]$, замкнутое относительно набора каких-то операций (и констант — как нульместных операций) $\mathcal O$. В данном случае это подмножество всех возможных строк в определённом алфавите (должно быть ясно каком, это написано явно в определении формулы ). При этом, если множества значений всех операций попарно не пересекаются, для каждого элемента $i[\mathcal O]$ существует операция, применением которой к каким-то элементам он получен. Можно ввести функцию $h\colon i[\mathcal O]\to\mathbb N$ такую, что $h(\text{константа}) = 1$ и $h(f(e_1,\ldots,e_n)) = 1 + \max_{i} h(e_i)$, и теперь обычная натуральночисленная индукция по $h$ влечёт индукцию по построению: если для каждой $f\in\mathcal O$ доказано $\varphi(e_1)\wedge\ldots\wedge\varphi(e_n)\Rightarrow\varphi(f(e_1,\ldots,e_n))$, то $\forall a\in i[\mathcal O].\;\varphi(a)$.

Это, кстати, тоже в какой-то книжке рассматривается (разумеется)…

[Unx]

(Оффтоп)

arseniiv, я что-то снова ничего не понял из написанного.

Xaositect в сообщении #1090939 писал(а):

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

Скорее вопрос к Xaositect, как эта теорема доказывается, если явно в книге она никак не доказывается. Мне тут всё не очевидно.

Поскольку в определении модели требуется истинность только предложений, то есть формул, которые не содержат свободного вхождения переменных, значит как-то можно обойтись без оценки. Я дам определение истинности. Надеюсь, что участники подскажут правильно ли оно сформулировано.
Определим операцию $[\varphi]$ взятия истинностного значения формулы $\varphi$ следующим образом:
1) $[P(t_1,t_2, \ldots, t_m)]$ равно истине, если для любых элементов $t_1,t_2, \ldots, t_m$, принадлежащих носителю структуры, предикат $P$ дает истинное значение в данной интерпретации.
2) $[\neg \varphi]=\neg [\varphi]$
3) $[\varphi \land \psi]=[\varphi] \land [\psi]$
Нестрого:
4) $[\forall x \varphi]$ равно истине, если для любого $x$ из носителя структуры $[\varphi]$ равно истине
5) $[\exists x \varphi]$ равно истине, если найдется $x$ в носителе структуры, такой что $[\varphi]$ равно истине
причем $x$ входит связанно
А как определения (5) и (4) сформулировать строго? И правильно ли я написал (1)-(3)? Что вы скажете?

[arseniiv]

(Оффтоп)

Unx в сообщении #1091910 писал(а):

я что-то снова ничего не понял из написанного.

Ужасно. Давайте я возьму конкретный пример: выражения из констант $1$, $0$, плюсов и обращений знака в польской записи. Возьмём алвавит $A = \{0, 1, {+}, {-}\}$ и множество всех строк над ним $A^*$. (Это $\{\varepsilon,0,1,{+},{-},00,01,0{+},0{-},10,\ldots,{-}{+},{-}{-},000,001,\ldots\}$, где $\varepsilon$— обозначение пустой строки.) Теперь определим несколько операций на $A^*$:
• $o() = 0$,
• $e() = 1$,
• $n(s) = -s$,
• $p(s_1,s_2) = +s_1s_2$.

Множество $I = i[o, e, n, p] \subset A^*$ состоит из множества интереснейших строк. Выпишу несколько множеств уровня $h$ на нём:
• $h = 1\colon\;\; 0, 1;$
• $h = 2\colon\;\; {-}0, -1, +00, +01, +10, +11;$
• $h = 3\colon\;\; {-}{-}0, -{-}1, -{+}00, -{+}01, -{+}10, -{+}11, +{-}00, +{-}01, +{-}10, +{-}11,$ $+0{-}0, +0{-}1, +1{-}0,$ $+1{-}1, +{-}0{-}0, +{-}0{-}1, +{-}1{-}0, +{-}1{-}1, +0{+}00, +1{+}01, \ldots,$ $+{-}1{+}10, \ldots, +{+}10{+}00, \ldots, +{+}11{+}11$.

Как нам доказать какое-то утверждение $\varphi$ обо всех элементах множества $I$? Кажется естественным вот такое правило вывода: если
• $\varphi(o())$ и $\varphi(e())$,
• $\forall s\in A^*.\;\varphi(s)\Rightarrow \varphi(n(s))$,
• $\forall s_1,s_2\in A^*.\;\varphi(s_1)\wedge\varphi(s_2)\Rightarrow \varphi(p(s_1,s_2))$,
то $\forall s\in I.\;\varphi(s)$.

Это вот и есть та самая индукция, назовём её (1). Но пускай мы ей не доверяем. Мы так же определили $h\colon I\to\mathbb N$, и можем взять обычную натуральночисленную индукцию (2), которую будем доказывать для формулы $\psi(n)\equiv\forall s\in I.\;h(s) = n\Rightarrow\varphi(s)$ — внимание, эта формула имеет свободной переменной только $n$. Эта индукция требует от нас, чтобы мы показали $\psi(1)\equiv\forall s\in I.\;h(s) = 1\Rightarrow\varphi(s)$ и $\forall n\in\mathbb N.\;\psi(n)\Rightarrow\psi(n+1)$, и выдаст тогда $\forall n\in\mathbb N.\;\psi(n)$, откуда нетрудно получить $\forall s\in I.\;\varphi(s)$. Итак, мы можем получить то, что нам обещает индукция (1), если выведем из её требований то, что нужно индукции (2). База индукции очевидна: у нас по построению $h$ только два элемента, на которых она равна 1, и именно для них требование индукции (1) у нас готовое. Переход тоже довольно простой, просто если расписывать в деталях, нудный.

Теперь понятно, как выглядит и почему работает структурная индукция?

-- Пн янв 18, 2016 23:46:09 --

Unx в сообщении #1091910 писал(а):

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

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

[Unx]

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

Теперь определим несколько операций на $A^*$:
• $o() = 0$,
• $e() = 1$,

Почему скобки оставлены пустые? Над какими элементами выполняются эти операции?

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

Множество $I = i[o, e, n, p] \subset A^*$

Что вы обозначаете как $i[o, e, n, p]$?

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

множеств уровня $h$

Что такое уровень $h$?

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

несколько множеств уровня $h$ на нём

На чём? Несколько множеств на множестве? Я не понимаю вашу терминологию.

Я увидел, что мое определение модели не подойдет для системы аксиом 1-5. К примеру аксиома (3) $x \in \mathbb{N} \rightarrow Sx \neq 0$ не содержит связанных переменных. Тут имеется отношение "принадлежать множеству" и отношение "не равно", которые в интерпретации становятся некоторыми предикатами. Связанных переменных нет.
Тогда нужно где-то взять другое определение модели, которое подойдет для любой системы формул (не обязательно предложений).

[arseniiv]

Unx в сообщении #1092734 писал(а):

Почему скобки оставлены пустые? Над какими элементами выполняются эти операции?

К $()$, единственному элементу нулевой декартовой степени чего угодно. Я их поставил (так и думал, что зря!) просто для симметрии (или от нечего делать — развлекаюсь как могу) с операциями остальных арностей, а так их обычно опускают и отождествляют с константами. (И, вроде, это уже здесь звучало.)

Unx в сообщении #1092734 писал(а):

Что вы обозначаете как $i[o, e, n, p]$?

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

наименьшее множество $i[\mathcal O]$, замкнутое относительно набора каких-то операций (и констант — как нульместных операций) $\mathcal O$

Собсвенно, я же приводил конкретный пример подобного множества, т. к. вы сказали, что в общем не понятно. Вообще, не знаю, может быть, упоминание явной конструкции с объединениями спасёт дело? $i[\mathcal O] = \bigcup_{n\in\mathbb N} A_n$, где $A_0 = \varnothing$, $A_{n+1} = \bigcup_{f\in\mathcal O} \{ f(x_1,\ldots,x_k) : x_1,\ldots,x_k\in A_n \}$. Можете угадать, при чём здесь соответствующая $h$.

Unx в сообщении #1092734 писал(а):

Что такое уровень $h$?

Множество уровня $a$ функции $f$ — это прообраз $f^{-1}(\{a\}) \equiv \{ x\in\operatorname{dom}f : f(x) = a\}$ этого $a$. Стандартная терминология.

Unx в сообщении #1092734 писал(а):

На чём? Несколько множеств на множестве?

«На нём» относится к $I$, т. к. мы могли бы определить другую функцию, подобную $h$, на другом индуктивно определённом множестве — в конце концов, в общем определении я её назвал тоже $h$, и был бы смысл называть её вместо этого $h_I$, неудачно подобрал слова. Короче, это означало, что рассматриваются именно множества уровня именно той конкретной функции $h\colon I\to\mathbb N$.

Unx в сообщении #1092734 писал(а):

Я увидел, что мое определение модели не подойдет для системы аксиом 1-5. К примеру аксиома (3) $x \in \mathbb{N} \rightarrow Sx \neq 0$ не содержит связанных переменных.

Есть ещё соглашение интерпретировать такие формулы как замкнутые, полученные дописыванием вокруг них $\forall v$ для каждой свободной $v$. Или, эквивалентно, это понимается как синтаксический сахар для такой замкнутой формулы, а интерпретация не доопределяется. Обычно слово об этом встречается в основном тексте — надеюсь, вы всё же стараетесь читать без пропусков.

[Unx]

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

наименьшее множество $i[\mathcal O]$, замкнутое относительно набора каких-то операций

Что значит наименьшее и наибольшее множество?

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

$h(f(e_1,\ldots,e_n)) = 1 + \max_{i} h(e_i)$

Что вы обозначили через $\max_{i} h(e_i)$?

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

Есть ещё соглашение интерпретировать такие формулы как замкнутые, полученные дописыванием вокруг них $\forall v$ для каждой свободной $v$.

Меня интересует первая аксиома $0 \in \mathbb{N}$.
Если под $\mathbb{N}$ понимается одно конкретное множество (константа), то квантор не нужен. Если $\mathbb{N}$ является переменной, то получится $\forall \mathbb{N} \ 0 \in \mathbb{N}$. Какой вариант из двух?

[Someone]

Unx в сообщении #1096390 писал(а):

Меня интересует первая аксиома $0 \in \mathbb{N}$.
Если под $\mathbb{N}$ понимается одно конкретное множество (константа), то квантор не нужен. Если $\mathbb{N}$ является переменной, то получится $\forall \mathbb{N} \ 0 \in \mathbb{N}$. Какой вариант из двух?

Никакой. В арифметике нет ни константы $\mathbb N$, ни переменной $\mathbb N$, и этот символ (вместе с $\in$) используется для сокращения фразы "является натуральным числом". Поскольку в арифметике нет никаких объектов, кроме натуральных чисел, то фраза эта никакой смысловой нагрузки не несёт.

[Unx]

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

В арифметике нет ни константы $\mathbb N$, ни переменной $\mathbb N$,

Арифметика - это формальная теория? Тогда всё, что у нас есть: константные символы, предикатные символы, функциональные символы и переменные. И больше ничего.

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

и этот символ (вместе с $\in$) используется для сокращения фразы

$\in$ обозначает двуместное отношение. С этим отношением мы связываем предикат $P$ (имеется в виду переход от синтаксиса к семантике):
$P(x,X)=1$, если $x \in X$
$P(x,X)=0$, если $x \notin X$
Все формулы (по определению) - это предикатные символы, либо предикатные символы с некоторыми логическими знаками. Как они строятся - написано в учебниках. А если речь идет о формальной теории, то ничем кроме формул мы не располагаем.

Давайте уважать литературу и ссылаться на нее. Иначе просто разговор заходит в тупик.

[Someone]

Unx в сообщении #1096427 писал(а):

$\in$ обозначает двуместное отношение

В арифметике нет отношения "$\in$".

Unx в сообщении #1096427 писал(а):

Давайте уважать литературу и ссылаться на нее.

Давайте.

С. К. Клини. Математическая логика. "Мир", Москва, 1973.

§ 38 посвящён формальной арифметике.

[Unx]

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

В арифметике нет отношения "$\in$".

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