Так о чем арифметика?

[Свободный Художник]

Какая арифметика будет все же слабейшей?
Быть может, эта:

(A1). $\forall x P(0, x, x)$;
(A2). $\forall x \forall y \forall z [P(x, y, z) \Rightarrow P(s(x), y, s(z))]$?

Здесь $s$ есть унарный функциональный символ, $P$ есть тернарный предикатный символ, $0$ есть символ индивидной константы.
Будем обозначать теорию указанной сигнатуры с двумя аксиомами (A1) и (A2) как $T_0$.
Формула $P(x, y, z)$ содержательно интерпретируется как $x + y = z$.
В теории $T_0$ доказуемы все интуитивно истинные факты об операции сложения на натуральных числах и не доказуемы интуитивно ложные. Например, факт $1 + 2 = 4$ недоказуем (при соответствующей трансляции в $P(s(0), s(s(0)), s(s(s(s(0)))))$). Может это уже само по себе немало?

Ведь писал же Э. Ландау в предисловии к своей знаменитой книге:
Ландау Э. Основы анализа.
Действия над целыми, рациональными, иррациональными, комплексными числами.
Перевод с немецкого Д. А. Райкова.
М.: Гос. изд-во иностранной литературы, 1947, cc. 7 — 8.
http://www.px-pict.com/9/6/4/2/2.html

Цитата:

Прошу — забудь все, чему ты учился в школе; потому что ты этому не научился.
Прошу, однако, всюду вызывать в своем представлении соответствующие разделы школьного курса; потому что тебе все же не следует его забывать.
Никакой таблицы умножения, даже теоремы $2*2 = 4$ я не даю; однако, я рекомендую тебе, в качестве упражнения к главе 1, определить: $2 = 1 + 1$, $4 = ((1 + 1) + 1) + 1$ и доказать указанную теорему.

В теории $T_0$ мы можем доказать теорему о том, что $2 + 3 = 5$.

Теория $T_0$ заимствована из:
Агафонов В. Н., Борщев В. Б., Воронков А. А.
Логическое программирование в узком смысле.
В книге: Логическое программирование: Сборник статей. Под ред. Агафонова В. Н.
М.: Мир, 1988, сс. 302 — 303.
http://www.px-pict.com/9/6/4/4/1.html
с соответствующей переформулировкой, ибо там она “заточена” для нужд логического программирования, а здесь мы ее снова “расточили” на нормальный язык исчисления предикатов.

[Xaositect]

Свободный Художник в сообщении #234002 писал(а):

Какая арифметика будет все же слабейшей?

Зависит от того, что считать арифметикой.
Я бы сказал, что арифметика --- это теория, у которой модели "не меньше" $\mathbb{N}$ в некотором смысле, а для $T_0$ любая абелева группа будет моделью ($s(x) = x+c$, $c$ - некоторый фиксированный элемент, даже не обязательно ненулевой)

[Свободный Художник]

Разумеется, $T_0$ “очень некатегорична”, т. е. имеет много неизоморфных между собой моделей.
Однако, во множестве всех ее моделей имеется и та, что нам нужна. Элементами ее множества-носителя служат элементы универсума Эрбрана, упоминавшегося выше. Обозначим эту модель $M_0$. Поскольку она в определенном смысле “объективно” выделена среди всех прочих, то мы можем считать, что теория $T_0$ специфицирует именно ее.

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

[Xaositect]

Свободный Художник в сообщении #234281 писал(а):

Поскольку она в определенном смысле “объективно” выделена среди всех прочих, то мы можем считать, что теория специфицирует именно ее.

В каком смысле? Слишком расплывчато как-то.

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

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

Свободный Художник в сообщении #234281 писал(а):

Поскольку она в определенном смысле “объективно” выделена среди всех прочих, то мы можем считать, что теория специфицирует именно ее.

В каком смысле? Слишком расплывчато как-то.

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

[Свободный Художник]

Свободный Художник в сообщении #234281 писал(а):

Разумеется, $T_0$ “очень некатегорична”, т. е. имеет много неизоморфных между собой моделей.
Однако, во множестве всех ее моделей имеется и та, что нам нужна. Элементами ее множества-носителя служат элементы универсума Эрбрана, упоминавшегося выше. Обозначим эту модель $M_0$. Поскольку она в определенном смысле “объективно” выделена среди всех прочих, то мы можем считать, что теория $T_0$ специфицирует именно ее.

Профессор Снэйп в сообщении #234350 писал(а):

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

Свободный Художник в сообщении #234281 писал(а):

Поскольку она в определенном смысле “объективно” выделена среди всех прочих, то мы можем считать, что теория специфицирует именно ее.

В каком смысле? Слишком расплывчато как-то.

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

А я думал, что выделенность нужной нам модели $M_0$ теории $T_0$ обеспечивается особым видом аксиом последней. Тем обстоятельством, что аксиомы теории $T_0$ являются так называемыми “хорновскими дизъюнктами”:
http://en.wikipedia.org/wiki/Horn_clause

Аксиома (A2) эквивалентна хорновскому дизъюнкту $\forall x \forall y \forall z [\neg P(x, y, z) \lor P(s(x), y, s(z))]$.
Совокупность моделей теории, аксиоматизированной посредством множества хорновских дизъюнктов, обладает рядом замечательных свойств, некоторые из которых приведены здесь:
Кейслер Г. Дж., Чэн Ч.Ч. Теория моделей.
М.: Мир, 1977, сc. 16 — 32:
http://www.px-pict.com/9/6/2/3/2/2/12.html

Эти-то замечательные свойства и обеспечивают, на мой взгляд, в некотором смысле “особую роль” модели $M_0$ среди всех других прочих моделей теории $T_0$.
Подробности надо будет еще посмотреть

-- Чт авг 13, 2009 21:56:55 --

Раз уж зашел разговор о хорновских дизъюнктах, то следует отметить, что с их помощью мы можем аксиоматизировать также некоторую слабенькую систему (положительных) рациональных чисел. А именно, рассмотрим теорию со следующими аксиомами:

Свободный Художник в сообщении #149232 писал(а):

Кажется, в системе $\mathbf{SBT}$ можно очень просто определить отношение $<$ строгого линейного порядка на множестве положительных рациональных чисел. Для этого достаточно постулировать следующие “определяющие соотношения” (которые, очевидно, справедливы при указанной интерпретации операций $V$ и $H$):
(v1). Для любого $x, V(x) < 1$,
(h1). Для любого $x, 1 < H(x)$,
(v2). Если $x < y$, то $V(x) < V(y)$,
(h2). Если $x < y$, то $H(x) < H(y)$,
(trans). Если $x < y$ и $y < z$, то $x < z$.

Докажем, например, что $\dfrac4{7} < \dfrac2{3}$.
$V(H(1)) = \dfrac2{3}$; $V(H(V(V(1)))) = \dfrac4{7}$.

Доказательство.
(1) Для любого $x, V(x) < 1$ -- аксиома (v1);
(2) $V(V(1)) < 1$ -- из (1);
(3) $H(V(V(1))) < H(1)$ -- из (2) по аксиоме (h2);
(4) $V(H(V(V(1)))) < V(H(1))$ -- из (3) по аксиоме (v2).

где $V$ и $H$ есть унарные функциональные символы, $<$ есть бинарный предикатный символ, $1$ есть символ индивидной константы.
Будем обозначать теорию указанной сигнатуры с пятью аксиомами (v1), (h1) , (v2) , (h2) и (trans) как $T_1$.
Бинарный предикатный символ $<$ содержательно интерпретируется как отношение “строго меньше” на множестве положительных рациональных чисел.
В теории $T_1$ доказуемы все интуитивно истинные факты о плотном линейном порядке без концевых точек (о котором уже много писали на этом форуме) и не доказуемы интуитивно ложные. Например, факт $\dfrac 7{4} < \dfrac 8{5}$ недоказуем.

В этом смысле теорию $T_1$ можно рассматривать, по-видимому, как некоторую зачаточную форму арифметики (положительных) рациональных чисел.

Аксиоматику “полноценной” теории плотного линейного порядка без концевых точек можно посмотреть здесь:
http://www.px-pict.com/9/6/2/4/3/1/1.html

[maxmatem]

моё понимание арифметики -это наука как раз и изучающ
ая такой дует как числа и операции над ними ! ведь если не задумываться о сущьности числа а только представлять его себе как нечто абстрактное , прозрачное то арифметика не получится!

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

Простая модель --- это модель, реализующая только главные типы. Чем Вам такая "выделенность" не нравится?

[Свободный Художник]

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

Свободный Художник в сообщении #234002 писал(а):

Какая арифметика будет все же слабейшей?
Быть может, эта:

(A1). $\forall x P(0, x, x)$;
(A2). $\forall x \forall y \forall z [P(x, y, z) \Rightarrow P(s(x), y, s(z))]$?

Здесь $s$ есть унарный функциональный символ, $P$ есть тернарный предикатный символ, $0$ есть символ индивидной константы.
Будем обозначать теорию указанной сигнатуры с двумя аксиомами (A1) и (A2) как $T_0$.
Формула $P(x, y, z)$ содержательно интерпретируется как $x + y = z$.

На примере “маленькой” модели $M_{small}$ теории $T_0$ хотелось бы уточнить терминологию, используемую в теории моделей.
Определим модель $M_{small}$ теории $T_0$ следующим образом.
В качестве множества-носителя $D$ модели берем двухэлементное множество $\{0, 1\}$. После того, как мы определились с носителем модели, мы должны связать с тернарным предикатным символом $P$ теории $T_0$ некоторое тернарное отношение, заданное на $D$,
с унарным функциональным символом $s$ теории $T_0$ -- некоторую унарную функцию, определенную на множестве $D$,
и, наконец, с символом индивидной константы $0$ -- некоторый элемент множества $D$.
Делаем это так: $P \to \{<0,0,0>, <0,1,1>, <1,0,1>, <1,1,0> \}$;
$s \to \{<0,1>, <1,0> \}$;
$0 \to 0$.

Получаем систему вида $M_{small} =\: < \{0, 1\}, \{<0,0,0>, <0,1,1>, <1,0,1>, <1,1,0> \}, \{<0,1>, <1,0> \}, 0 >$.
Обе аксиомы теории $T_0$ истинны в модели $M_{small}$:
$M_{small} \vDash \forall x P(0, x, x)$;
$M_{small} \vDash \forall x \forall y \forall z [P(x, y, z) \Rightarrow P(s(x), y, s(z))]$.
--------------

Однако, нелогические символы $P, s, 0$ теории $T_0$ могут быть проинтерпретированы (при одном и том же “носителе” $D = \{0, 1\}$) и многими другими способами. В результате будут получаться системы, отличные от приведенной выше системы $M_{small}$.
В некоторых из этих систем аксиомы теории $T_0$ будут истинны, а в некоторых – ложны.
Разве оправданно называть все эти мыслимые системы “моделями” (как иногда делают)?

Ведь, наверное, их было бы правильнее называть “возможными интерпретациями” соответствующего первопорядкового языка, а “моделями теории” – только те из интерпретаций, в которых аксиомы данной теории истинны.

То есть я это к тому, что модель – она всегда некоторой теории модель, тогда как интерпретация – она языка интерпретация (а в одном и том же языке существует много различных теорий).
-------------------------------

А относительно самих “систем” что мы имеем? Нет для них общепринятого названия. Термин “алгебраические системы” слишком узкий. Для геометрии пришлось бы вводить понятие “геометрической системы”.
А системы, отвечающие теории частичного порядка как назвать?
Может быть, было бы оправданным ввести общее понятие “математической системы”, понимая под ним любое непустое множество с заданными на нем отношениями и операциями соответствующей арности.

Иногда такие общие системы называют просто “моделями”, что, на мой взгляд, неправильно, поскольку, как указывалось выше, “модель” всегда предполагает теорию (для которой данная система и является моделью), а систему саму по себе я могу и просто от руки выписать (если ее носитель конечен) – просто как кортеж определенного вида. После чего эта система будет вполне объективно существовать, без ссылки на какую-либо теорию.

[Свободный Художник]

Профессор Снэйп в сообщении #231342 писал(а):

Арифметика --- это наука о свойствах модели $\langle \mathbb{N}; +, \cdot, \leqslant, 0, 1 \rangle$.

А почему под “арифметикой” всегда по умолчанию понимают науку о системе натуральных чисел? В каждой книге по матлогике все арифметика Пеано, да арифметика Пеано.
Ведь представляется совершенно естественным наряду с арифметикой натуральных чисел на абсолютно равных правах развивать и арифметику положительных рациональных чисел. Берем за основу версию аксиоматики Пеано из:
Кейслер Г. Дж., Чэн Ч.Ч. Теория моделей.
М.: Мир, 1977, сc. 52 — 65:
http://www.px-pict.com/9/6/2/4/3/1/2.html

(1). $\forall x [0 \ne s(x)]$;
(2). $\forall x \forall y [(s(x) = s(y)) \Rightarrow (x = y)]$;
(3). $\forall x (x + 0 = x)$;
(4). $\forall x \forall y [x + s(y) = s(x + y)]$;
(5). $\forall x (x \cdot 0 = 0)$;
(6). $\forall x \forall y [x \cdot s(y) = (x \cdot y) + x]$;
(7). $\{\varphi (0) \land \forall x[\varphi (x) \Rightarrow \varphi (s(x))]\} \Rightarrow \forall x \varphi (x)$.

“Удваиваем” эту аксиоматику и получаем основу аксиоматики для системы положительных рациональных чисел:

(h1). $\forall x [0 \ne H(x)]$;
(v1). $\forall x [\infty \ne V(x)]$;
(h2). $\forall x \forall y [(H(x) = H(y)) \Rightarrow (x = y)]$;
(v2). $\forall x \forall y [(V(x) = V(y)) \Rightarrow (x = y)]$;
(h3). $\forall x (x \bullet 0 = x)$;
(v3). $\forall x (x \circ \infty = x)$;
(h4). $\forall x \forall y [x \bullet H(y) = H(x \bullet y)]$;
(v4). $\forall x \forall y [x \circ V(y) = V(x \circ y)]$;
(5a). $\forall x [(x \ne \infty) \Rightarrow (x \cdot 0 = 0)]$;
(5b). $\forall x [(x \ne 0) \Rightarrow (x \cdot \infty = \infty)]$;
(5c). $0 \cdot \infty = 1$;
(h6). $\forall x \forall y [x \cdot H(y) = (x \cdot y) \bullet x]$;
(v6). $\forall x \forall y [x \cdot V(y) = (x \cdot y) \circ x]$;
(7). $\{\varphi (0) \land \forall x[\varphi (x) \Rightarrow \varphi (H(x))] \land \varphi (\infty) \land \forall x[\varphi (x) \Rightarrow \varphi (V(x))]\} \Rightarrow \forall x \varphi (x)$.

Можно определить в этой системе свои рекурсивные функции и т. д.

$\bullet, \circ, \cdot$ – двуместные функциональные символы,
$H, V$ – одноместные функциональные символы,
$0, \infty, 1$ – символы индивидных констант.

[Свободный Художник]

Свободный Художник в сообщении #235980 писал(а):

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

Хотя, почему, собственно, мы говорим о “системе положительных рациональных чисел”?
Ведь изначально так не было. Не было таких объектов, как “рациональные числа”. Изначально строго различались “числа” и “отношения”. Это были сущности двух разных типов (или сортов). И эта “парадигма” была очень авторитетна:
http://www.px-pict.com/7/3/1/3.html
http://www.px-pict.com/7/4/2/2.html

Что же такого экстраординарного должно было произойти, чтобы эта парадигма “поплыла” и числа превратились в отношения? Что подвигло И. Ньютона написать свою еретическую фразу:

Цитата:

Под числом мы понимаем не столько множество единиц, сколько отвлеченное отношение какой-нибудь величины к другой величине того же рода …

http://www.px-pict.com/7/3/1/8/3/1.html
(допустив, таким образом, прямую коллизию типов)

Почему бы было не оставить все как есть, т. е. числа называть числами, а отношения – отношениями (не смешивая их)?

Ведь вполне можно допустить, что отношения живут своей собственной жизнью, отличной от жизни чисел. Например, та единственная операция, которая выполнялась над отношениями – операция “составления” отношений:
http://www.px-pict.com/7/4/2/2.html#2
заставляет нас признать ядром “арифметики отношений” структуру, известную ныне как “группоид Брандта”.

В свете вышеизложенного можно выразить мысль, что “полноценная” арифметика – это наука, скорее, об отношениях, чем о числах. А “предварительная” арифметика (арифметика “чисел”) становится полноценной только после погружения в поле своих отношений …
http://www.px-pict.com/9/5/4/3/1.html

[Yarkin]

Свободный Художник в сообщении #237997 писал(а):

В свете вышеизложенного можно выразить мысль, что “полноценная” арифметика – это наука, скорее, об отношениях, чем о числах. А “предварительная” арифметика (арифметика “чисел”) становится полноценной только после погружения в поле своих отношений …

Наверно, И. Ньютон не имел в виду эти "отношения".

[Свободный Художник]

Yarkin в сообщении #238164 писал(а):

Наверно, И. Ньютон не имел в виду эти "отношения".

А какие имел?
И о каких отношениях Вы пишите в кавычках?

[ewert]

Свободный Художник в сообщении #237997 писал(а):

Что же такого экстраординарного должно было произойти, чтобы эта парадигма “поплыла” и числа превратились в отношения?

Ничего, т.к. ничего такого и не происходило. Эти две ссылки описывают, как, наоборот, отношения потихонечку превращались в числа.

Свободный Художник в сообщении #237997 писал(а):

Почему бы было не оставить все как есть, т. е. числа называть числами, а отношения – отношениями (не смешивая их)?

Потому, что Вы недоцитировали Ньютона:

Цитата:

Число бывает трёх видов: целое, дробное и глухое. Целое число есть то, что измеряется единицей; дробное -- кратной долей единицы; глухое число несоизмеримо с единицей.

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

[Свободный Художник]

ewert в сообщении #238407 писал(а):

Свободный Художник в сообщении #237997 писал(а):

Что же такого экстраординарного должно было произойти, чтобы эта парадигма “поплыла” и числа превратились в отношения?

Ничего, т.к. ничего такого и не происходило. Эти две ссылки описывают, как, наоборот, отношения потихонечку превращались в числа.

Разумеется, у меня опечатка.
Имелось в виду, конечно, следующее: “Что же такого экстраординарного должно было произойти, чтобы эта парадигма “поплыла” и отношения превратились в числа?”

ewert в сообщении #238407 писал(а):

Свободный Художник в сообщении #237997 писал(а):

Почему бы было не оставить все как есть, т. е. числа называть числами, а отношения – отношениями (не смешивая их)?

Потому, что Вы недоцитировали Ньютона:

А давайте ограничимся сначала рассмотрением арифметики “рациональных чисел”. Тут-то Вы согласитесь со мной, что не было никаких оснований для того, чтобы числа сожрали отношения?