Первая аксиома Пеано

[arseniiv]

vesennygnom в сообщении #1403566 писал(а):

Я к тому, что за suc допустим должна стоять некая машина, которая выдает единицы и прибавляет их к имеющимся.

Как раз нет. Сами записи $1,\; SSSSSSSSSS1\; SSS1$ вполне можно воспринимать как натуральные числа, аксиомы индукции говорят, что других нет, а остальные две аксиомы кроме вводящих 0 и S говорят, что разные записи задают разные числа.

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

vesennygnom в сообщении #1403566 писал(а):

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

Ну так это не «единица», это «ноль или единица». Просто единица никак с битами не соотносится.

vesennygnom в сообщении #1403566 писал(а):

не совсем понял это. аксиоматика вводит еще и инкремент, который не менее важен и дает все остальное

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

-- Сб июл 06, 2019 18:36:17 --

Connector в сообщении #1403572 писал(а):

Первая аксиома может формулироваться несколько иначе:
Существует такой $1$ $\in$ $N$, что для любого $x$ $\in$ $N$, $Sc(x)$ $\ne$ $1$.
Хотя с логической точки зрения такое утверждение избыточно.
Тогда единица с самого начала вводится как элемент, обладающий некоторым свойством — а именно начальный элемент (хотя, конечно, остаётся основным объектом, допускающим только аксиоматическое определение).

Не-не-не, так вы всё запутаете.

В традиционных аксиомах (4 + аксиома/схема аксиом индукции) первая аксиома это $1\in\mathbb N$. В аксиомах теории первого порядка (2 + схема индукции) первая аксиома будет или $\not\exists n.\;Sn=1$, или $Sm = Sn \to m = n$ (кто как захочет, это уже не так важно), а константа $1$ и символ $S$ изначально входят в язык (потому две первые традиционные аксиомы и выкидываются; их нельзя выразить напрямую, а если написать косвенно что-то типа $\exists n.\;n=1$, получится лишняя доказуемая из чистой логики аксиома). Никаких специальных свойств «начальности». Все аксиомы определяют все натуральные числа, а так же отношение их равенства, одинаково. Нельзя сказать, что аксиома $\not\exists n.\;Sn=1$ определяет специально единицу, и нельзя сказать, что форма $\exists i. \not\exists n.\;Sn=i$ приемлема (с ней может и можно что-то сделать, но никто почему-то этим не занимается).

[vesennygnom]

Цитата:

Ну так это не «единица», это «ноль или единица». Просто единица никак с битами не соотносится.

именно единица, тк нуля у пеано нет.

Цитата:

$\exists i. \not\exists n.\;Sn=i$

- это случай когда $i == 1$? - сорри наверное случай,когда их несколько?

[Someone]

vesennygnom в сообщении #1403598 писал(а):

именно единица, тк нуля у пеано нет.

Не важно, есть там ноль или нет. Бит — это либо единица измерения информации, либо объект, который имеет два возможных состояния. Число $1$ не является ни тем, ни другим. Более того, конкретизировать каким-либо способом природу натуральных чисел крайне нежелательно. Это ничем не помогает в арифметике как математической теории и помешает её приложениям, так как в разных приложениях натуральные числа интерпретируются по-разному.

Кроме того, часто удобно начинать натуральный ряд с нуля, а не с единицы. Это требует лишь небольшого изменения аксиом.

[Connector]

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

не-не-не, так вы всё запутаете.
В традиционных аксиомах (4 + аксиома/схема аксиом индукции) первая аксиома это $1\in\mathbb N$. В аксиомах теории первого порядка (2 + схема индукции) первая аксиома будет или $\not\exists n.\;Sn=1$, или $Sm = Sn \to m = n$ (кто как захочет, это уже не так важно), а константа $1$ и символ $S$ изначально входят в язык (потому две первые традиционные аксиомы и выкидываются; их нельзя выразить напрямую, а если написать косвенно что-то типа $\exists n.\;n=1$, получится лишняя доказуемая из чистой логики аксиома). Никаких специальных свойств «начальности». Все аксиомы определяют все натуральные

Вы совершенно правы, я имел в виду второй вариант аксиоматики и при этом неправильно сформулировал первую аксиому. В этой схеме изначально вводится тройка $(\mathbb{N}, 1, S)$, и затем аксиомами накладываются условия на ее элементы. Но что, если рассмотреть пару $(\mathbb{N}, S)$, а первую аксиому сформулировать так: В $\mathbb{N}$ существует такой $x$, что для любого $n$ из $\mathbb{N}$ $x$ $\ne$ $S(n)$ ? Затем обозначить этот $x$ через «$1$», чтобы проще сформулировать аксиому индукции; тогда константа $1$ не будет входить в язык изначально.

(Оффтоп)

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

[vesennygnom]

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

[Someone]

vesennygnom в сообщении #1403615 писал(а):

получается арифметика никаким способом с материальным заданием числа не связана?

Абсолютно никаким. Математические объекты — это чисто логические конструкции.

[Connector]

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

Абсолютно никаким. Математические объекты — это чисто логические конструкции.

Я понимаю, о чем Вы, но так ведь тоже нельзя: существуют интерпретации этих логических конструкций.

(Сейчас пришло в голову UPD ошибка!)

первую аксиому, о которой я говорил ($1$ не следует ни за кем) можно заменить эквивалентной:
для любого $n$ из $\mathbb{N}$, $S(n)$ $\ne$ $n$.

[arseniiv]

vesennygnom в сообщении #1403598 писал(а):

Цитата:

$\exists i. \not\exists n.\;Sn=i$

- это случай когда $i == 1$? - сорри наверное случай,когда их несколько?

Это случай, когда есть вообще какие-то элементы, не являющиеся ничьим последователем. Их может быть больше одного, пока мы не удостоверимся, что они все равны. Вообще это часть разговора с Connector, я не рекомендую такую модификацию аксиом, тем более что мы её пока недоописали и она вообще здесь оффтоп.

vesennygnom в сообщении #1403615 писал(а):

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

Верно и это, и то, что индукция позволяет нам отождествить натуральные числа с конечными записями вида $S\ldots S1$. Противоречия между этими вещами нет, потому что «конечная запись» обычно не может быть определена в обход определения натуральных чисел.

На неформальном уровне, если считать, что мы понимаем, что такое конечная запись, построенная по определённым правилам из определённых букв, то попытавшись формализовать свойства вот такого класса записей $S\ldots S1$, мы легко придём к аксиомам Пеано или чему-то очень похожему.

(Вариации аксиоматики Connector)

Connector в сообщении #1403608 писал(а):

Но что, если рассмотреть пару $(\mathbb{N}, S)$, а первую аксиому сформулировать так: В $\mathbb{N}$ существует такой $x$, что для любого $n$ из $\mathbb{N}$ $x$ $\ne$ $S(n)$ ? Затем обозначить этот $x$ через «$1$», чтобы проще сформулировать аксиому индукции; тогда константа $1$ не будет входить в язык изначально.

Если удастся сделать выводимым $\exists! i. \forall n.\; Sn\ne i$ (видимо, проще сразу это и постулировать вместо просто существования без единственности), то вероятно (но в аксиоме индукции нельзя будет использовать никакую 1, надо в ней будет писать честную замену). Но это практически неудобно: $S$ в сигнатуре, единица не в сигнатуре, остановились на полпути, и непонятно с какой целью. Притом после определения 1 мы фактически получим обычный случай, когда в сигнатуре оба символа, но притом нам ещё будет надо вывести аксиомы теоремы индукции в привычном виде. Одни неудобства же.

Connector в сообщении #1403620 писал(а):

Сейчас пришло в голову: первую аксиому, о которой я говорил ($1$ не следует ни за кем) можно заменить эквивалентной:
для любого $n$ из $\mathbb{N}$, $S(n)$ $\ne$ $n$.

Не эквивалентной — так мы сделаем моделями наших аксиом циклы (из более чем двух элементов), например $\{a,b\}$ с $S(a) = b, S(b) = a$. Правда тут игнорируется схема индукции, которую пока что не перезаписали по-новому без 1.

[Connector]

(Оффтоп)

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

Не эквивалентной — так мы сделаем моделями наших аксиом циклы (из более чем двух элементов), например $\{a,b\}$ с $S(a) = b, S(b) = a$. Правда тут игнорируется схема индукции, которую пока что не перезаписали по-новому без 1.

Точно, я поторопился! Можно так: для любого $n$ из $\mathbb{N}$ максимальна цепочка от $n$ до $n$ имеет нулевую длину (но как определить здесь цепь? Все слишком сложно).

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

Если удастся сделать выводимым $\exists! i. \forall n.\; Sn\ne i$ (видимо, проще сразу это и постулировать вместо просто существования без единственности), то вероятно (но в аксиоме индукции нельзя будет использовать никакую 1, надо в ней будет писать честную замену). Но это практически неудобно: $S$ в сигнатуре, единица не в сигнатуре, остановились на полпути, и непонятно с какой целью. Притом после определения 1 мы фактически получим обычный случай, когда в сигнатуре оба символа, но притом нам ещё будет надо вывести аксиомы теоремы индукции в привычном виде. Одни неудобства же.

Да, это действительно неудобно. Просто задался целью исключить единицу из сигнатуры.
Чтобы доказать единственность, в аксиоме индукции придётся говорить о «по крайней мере одной» из единиц.

UPD. vesennygnom, поменьше обращайте внимания на мои сообщения — во-первых, это большей частью оффтопик, во-вторых — см. замечания arseniiv.
ИМХО, «найти $x$» — это вообще странная постановка задачи.
Кстати, если не ошибаюсь, $\mathbb{N}$ можно определить как наименьшее бесконечное вполне упорядоченное множество — но тогда это будут уже не аксиомы Пеано.

[vesennygnom]

Цитата:

Вы совершенно правы, я имел в виду второй вариант аксиоматики и при этом неправильно сформулировал первую аксиому. В этой схеме изначально вводится тройка $(\mathbb{N}, 1, S)$, и затем аксиомами накладываются условия на ее элементы. Но что, если рассмотреть пару $(\mathbb{N}, S)$, а первую аксиому сформулировать так: В $\mathbb{N}$ существует такой $x$, что для любого $n$ из $\mathbb{N}$ $x$ $\ne$ $S(n)$ ? Затем обозначить этот $x$ через «$1$», чтобы проще сформулировать аксиому индукции; тогда константа $1$ не будет входить в язык изначально.

то есть, чтобы найти х, мы должны применить S(n) к каждому $n\in\mathbb{N}$? или это просто типа постулат существования? с моей точки зрения, невозможно перебрать бесконечное множество циклом.. И еще - $\mathbb{N}$ ту упорядочено или нет? если упорядочено, то про х можно сразу сказать, что это первый элемент упорядоченного множества
и еще вопрос - а что ,если единиц несколько? будут несколько множеств $\mathbb{N}$ в зависимости от начальной единицы?
или единица будет не совсем единица а 0.9, допустим? тогда число, полученное применением функции S, будет иметь погрешность в 10%

-- 06.07.2019, 22:36 --

короче друзья математики! что бы мне почитать по этому поводу? теория чисел?
чтобы доступно и с задачками

-- 06.07.2019, 22:51 --

Цитата:

UPD. vesennygnom, поменьше обращайте внимания на мои сообщения.

высокая математика?
на само деле меня напрягает, что я еле понимаю язык на котором вы говорите

[arseniiv]

Ничего не читать. Без понимания, что такое язык и теория первого порядка, лучше не начинать, а чтобы разобраться с ними, лучше сначала продвинуться дальше аксиом Пеано. (UPD. А теория чисел не о построениях числовых систем, а больше уже о… хм, в двух словах так не опишешь, ну вот большая и малая теоремы Ферма это всё она.)

vesennygnom в сообщении #1403634 писал(а):

И еще - $\mathbb{N}$ ту упорядочено или нет?

Вообще обычно добавляют аксиомы порядка, описывающие $<$, но в классические минимальные аксиомы оно не входит. (Ну и сложение и умножение тоже определяются отдельными аксиомами.)

vesennygnom в сообщении #1403634 писал(а):

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

Всё не так просто, потому что определение порядка обычно не независимо от 1.

vesennygnom в сообщении #1403634 писал(а):

и еще вопрос - а что ,если единиц несколько? будут несколько множеств $\mathbb{N}$ в зависимости от начальной единицы?

Аксиомы Пеано не описывают вообще весь мир, они описывают только множество натуральных чисел, где единица только одна. Однако описывают они его через 1 и $S$, то есть:
(1) чтобы проверить, дали нам $N$, достойное звания множества натуральных чисел, или нет, нам должны вместе с ним дать и функцию $s\colon N\to N$ и элемент $i\in N$, и лишь тогда мы сможем проверить, и
(2) если два разных набора $(N,i,s)$ и $(N',i',s')$ удовлетворяют аксиомам, то они для нас одинаково хороши, мы можем их и не различать. Пусть хоть тыща единиц и $N'''$ у нас будет разных.

Вообще правда в (2) я не совсем честен, но куча математиков не парятся и вам не советуют.

vesennygnom в сообщении #1403634 писал(а):

или единица будет не совсем единица а 0.9, допустим? тогда число, полученное применением функции S, будет иметь погрешность в 10%

No comment.

(Оффтоп)

Connector в сообщении #1403629 писал(а):

Точно, я поторопился! Можно так: для любого $n$ из $\mathbb{N}$ максимальна цепочка от $n$ до $n$ имеет нулевую длину (но как определить здесь цепь? Все слишком сложно).

В логике первого порядка проще всего не начинать. В логике второго… но мы же не будем в неё выходить? Проще уж взять ZFC и там найти $\mathbb N$ на дне индуктивного множества.

И вот смотрите что вы натворили. Тему надо было отдельную открывать.

-- Вс июл 07, 2019 01:05:15 --

vesennygnom в сообщении #1403634 писал(а):

на само деле меня напрягает, что я еле понимаю язык на котором вы говорите

В данном случае Connector просто неторопливо что-то переоткрывает на диване, но чтобы после этого расставить всё по местам, требуется гораздо более высокий уровень, чем, да, который вы скорее всего готовы прямо сейчас выдержать. (Увы.)

[Someone]

Connector в сообщении #1403620 писал(а):

Я понимаю, о чем Вы, но так ведь тоже нельзя: существуют интерпретации этих логических конструкций.

Именно так и необходимо. А то, что интерпретации существуют, и некоторые из них оказываются полезными — это просто замечательно. Хотя, конечно, на самом деле хорошие аксиомы придумываются не путём высасывания из пальца, а с оглядкой на некоторую подразумеваемую интерпретацию. Хотя бы внутриматематическую.

[vesennygnom]

Цитата:

Без понимания, что такое язык и теория первого порядка, лучше не начинать, а чтобы разобраться с ними, лучше сначала продвинуться дальше аксиом Пеано

куда продвинуться?

[arseniiv]

Ну, у вас же наверно стояли за этим вопросом какие-то бо́льшие цели.

[vesennygnom]

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

Ну, у вас же наверно стояли за этим вопросом какие-то бо́льшие цели.

я по диплому математик, но работаю программистом. Где то читал прочитал про формализацию Пеано и меня заинтересовала эта рекурсивная машина.
вы написали продвинуться дальше аксиом пеано - это значит изучить остальные формализации $\mathbb{N}$ ? где про них прочитать?