Основания математики - элементарное рассмотрение

[vek88]

Пусть $P(n)$, некоторый предикат, определенный на множестве $N$ натуральных чисел. Здесь и далее переменная $n$ принимает в качестве значения произвольное натуральное число. Далее $n|$ обозначает натуральное число, непосредственно следующее за $n$.

Принцип математической индукции формулируется так

$$ (P(0) \wedge \forall n (P(n) \rightarrow P(n|))) \rightarrow \forall n P(n).$$

Таким образом, если нам удалось для предиката $P(n)$ доказать два утверждения

$$P(0), \forall n (P(n) \rightarrow P(n|)),$$

то этот предикат истинен для всех натуральных числел, т.е. $\forall n P(n).$

Доказательство принципа математической индукции.

1. Итак, предположим, что доказаны два утверждения

$$P(0), \forall n (P(n) \rightarrow P(n|)).$$

Далее мы собираемся показать, что в этом случае предикат $P(n)$ истинен для всех натуральных числел, т.е. $\forall n (P(n).$

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

Знаки: $0, |$
Переменная: $x$
Аксиома: $0$
Правило вывода:

$$\frac{x}{x|}$$

3. Чтобы работать в «однотипной системе», представим утверждения пункта 1 настоящего доказательства в этой же канонической системе, добавив следующие знаки, аксиому и правило.

Знаки: $P, (, )$
Аксиома: $P(0)$
Правило вывода:

$$\frac{P(x)}{P(x|)}$$

4. Сравним аксиому и правило пункта 3 с определением натуральных чисел пункта 2. Сразу бросается в глаза некое "подобие" правил для предиката $P$ и правил, определяющих натуральные числа. Отсюда следует, что утверждение $P(n)$ выводимо для любого натурального числа $n$. Докажем это.

Пусть $n$ натуральное число. Это значит, что существует его вывод в построенном каноническом исчислении. Возьмем в этом выводе вхождение каждого натурального числа "в скобки" $P()$. Получим вывод утверждения $P(n)$. Следовательно, $P(n)$ выводимо для любого натурального $n$. Что и требовалось доказать.

Примечание. Здесь мы пока имели обычное каноническое исчисление. Поэтому И-вывод - это просто вывод, а истинность утверждения – это просто его выводимость.

5. Осталось доказать истинность утверждения

$$\forall n P(n).$$

Вот здесь уже понадобится К-система, а именно, определение квантора всеобщности.

Определение квантора $\forall$ списываем со стр. 123 "Представление в ЭВМ ..." http://narod.ru/disk/2413304001/%D0%9A% ... .djvu.html, упрощая применительно к нашему случаю. Таким образом, мы строим К-систему, включая в нее ранее построенные в этом доказательстве знаки, переменные, аксиомы и правила, и добавляя

Вспомогательные знаки: $H, \forall $
Переменная типа натуральное число: $n$
Правила (определяют квантор всеобщности):

$$\frac{\ominus P(n)}{H},$$

$$\frac{\ominus H}{\forall n P(n)}.$$

Поясним почему выражение $\forall n P(n)$ истинно.

Заметим, что это выражение имеет единственный вывод - применение второго из вышеприведенных правил. Этот вывод имеет в качестве исключений (по определению исключения в К-системе на стр. 122) все выводы константы $H$. Докажем, что все эти исключения являются Л-выводами. А значит сам вывод - И-вывод (и поэтому выражение с квантором истинно).

Все выводы константы $H$ являются применениями первого правила для различных натуральных чисел $n$. И каждый такой вывод является Л-выводом, поскольку имеет в качестве исключения И-вывод утверждения $P(n)$ для каждого натурального числа $n$ (соответствующие выводы построены в пункте 4 настоящего доказательства).

Доказан принцип математической индукции.

[vek88]

Есть ли еще какие-либо соображения по поводу моего вопроса

vek88 в сообщении #433755 писал(а):

Почему наша реальная математическая практика непротиворечива?

При этом обращаю внимание на ИМХО удивительный факт - ведь мы в большинстве своем, если даже и знаем, то не используем в повседневной математической деятельности ZFC или иные аксиоматизации теории множеств (а в большинстве своем мы и не знаем этих аксиоматизаций).

[докер]

Я очень извиняюсь, но есть необходимость публично спросить, и есть желание публично получить ответ, мне крайне любопытно обсуждение!!!, но встрять возможности нет, кто разрешит задать пару вопросов в личной переписке?

[vek88]

докер в сообщении #435316 писал(а):

есть необходимость публично спросить, и есть желание публично получить ответ,

Ну и спрашивайте публично - в чем проблема?

[докер]

Я публично хочу получить разрешение на личную переписку. Крамолу при всех озвучивать затруднительно, и в этом есть справедливость. Я не близка к математике,
но стремлюсь всеми силами. Я полагаю что именно математика очерчивает границу восприятия, и имея желание выйти за пределы, надо разбираться(мне), не куда дальше продвинутся, а где в основе математики упущения. У вас не принято полагаться на ощущения, но у меня именно ощущение чего-то сильно не хватает в основе, объема не хватает(образно говоря) как то плоско. На форуме обсуждают интуицию, но не как алгоритм более высокого порядка в сравнении с логикой, ее и алгоритмом не считают. Мне бы одного товарища для беседы хватило(но крамольного), а всех беспокоить нет нужды.

[vek88]

докер в сообщении #435636 писал(а):

Я публично хочу получить разрешение на личную переписку. Крамолу при всех озвучивать затруднительно, и в этом есть справедливость. Я не близка к математике, но стремлюсь всеми силами. Я полагаю что именно математика очерчивает границу восприятия, и имея желание выйти за пределы, надо разбираться(мне), не куда дальше продвинутся, а где в основе математики упущения. У вас не принято полагаться на ощущения, но у меня именно ощущение чего-то сильно не хватает в основе, объема не хватает(образно говоря) как то плоско. На форуме обсуждают интуицию, но не как алгоритм более высокого порядка в сравнении с логикой, ее и алгоритмом не считают. Мне бы одного товарища для беседы хватило(но крамольного), а всех беспокоить нет нужды.

докер

Зря стесняетесь озвучивать крамолу. Как говорит Козьма Прутков

Цитата:

Не говори в походе, что слаб,
Смотри как шагает Глазенап

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

Так что категорически советую: спрашивайте и ничего не бойтесь - ведь не корову проигрываете.

А можете вааще свою тему открыть, если сочтете нужным.

А личной перепиской ... ИМХО, сомневаюсь, что кто-то этим будет заниматься. Во всяком случае, я этого делать не буду.

С уважением,
vek88

[докер]

Я не стесняюсь и не боюсь, причина в другом, не зачем проламывать стены которые за спиной. Меня категорически интересует мотив с которым тот или иной выходит на форум, от этого и зависит пойдет или не пойдет человек на личную переписку, лично ваш vek88 не интерес предсказуем и нормален. Если такого парня не найдется я подожду еще, жду же почти два года на вашем форуме(только на вашем).

[Someone]

vek88 в сообщении #434390 писал(а):

4. Сравним аксиому и правило пункта 3 с определением натуральных чисел пункта 2. Сразу бросается в глаза некое "подобие" правил для предиката $P$ и правил, определяющих натуральные числа. Отсюда следует, что утверждение $P(n)$ выводимо для любого натурального числа $n$. Докажем это.

Пусть $n$ натуральное число. Это значит, что существует его вывод в построенном каноническом исчислении. Возьмем в этом выводе вхождение каждого натурального числа "в скобки" $P()$. Получим вывод утверждения $P(n)$. Следовательно, $P(n)$ выводимо для любого натурального $n$. Что и требовалось доказать.

Не получим. Вдруг при каком-нибудь $n$ будет $\neg P(n)$? Вы вспоминайте всё время множество $\mathbb N+\mathbb Z$. Правило из пункта 2 порождает всё это множество, а правило из пункта 3 - только $\mathbb N$.
И вообще, операция "возьмём в скобки" какая-то удивительная. Такой операции в математической логике нет.

[докер]

Хотя с другой стороны можно и при всех. Система счисления для начала интересует. Двоичная понятно. Десятичная, есть вопрос. Если десятичная от десяти пальцев, то глядя на ладошки очевидна ось симметрии 5 и 5, счет идет от 5 до 1с одной стороны и от 1 до 5 с другой, откуда она десятичная тогда?. Десятичная смотрится как раздутая двоичная. Деление интересует, если один кирпич разделить пополам получится 0.5 кирпича, а если делится клетка(живая) получается 2 клетки. Почему когда делят, опираются на результат деления кирпичей , а не на результат деления клеток? Я двигаюсь от аналогий, полагаю что у интуиции природа аналогий.

[vek88]

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

vek88 в сообщении #434390 писал(а):

4. Сравним аксиому и правило пункта 3 с определением натуральных чисел пункта 2. Сразу бросается в глаза некое "подобие" правил для предиката $P$ и правил, определяющих натуральные числа. Отсюда следует, что утверждение $P(n)$ выводимо для любого натурального числа $n$. Докажем это.

Пусть $n$ натуральное число. Это значит, что существует его вывод в построенном каноническом исчислении. Возьмем в этом выводе вхождение каждого натурального числа "в скобки" $P()$. Получим вывод утверждения $P(n)$. Следовательно, $P(n)$ выводимо для любого натурального $n$. Что и требовалось доказать.

(1) Не получим. Вдруг при каком-нибудь $n$ будет $\neg P(n)$? (2) Вы вспоминайте всё время множество $\mathbb N+\mathbb Z$. Правило из пункта 2 порождает всё это множество, а правило из пункта 3 - только $\mathbb N$.
(3) И вообще, операция "возьмём в скобки" какая-то удивительная. Такой операции в математической логике нет.

1. А не соблаговолит ли почтенный Someone привести пример $\neg P(n)$?

2. ИМХО и пункт 2 и пункт 3, по сути, порождают одно и то же. В первом случае, цепочка $0, 0|, ..., 0|||, ...$, во втором, $P(0), P(0|), ..., P(0|||), ...$. Чем эти две цепочки принципиально различаются, я не понимаю. Причем здесь $\mathbb N+\mathbb Z$?

3. А причем здесь, математическая логика? К примеру, когда мы говорим о подобии треугольников, это что - математическая логика? В содержательном (=интуитивном, наивном) доказательстве мы имеем право использовать все, что нам понравится - лишь бы это было очевидно и понятно всем.

[EvgenyGR]

vek88 в сообщении #435895 писал(а):

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

Интуитивно сума ряда не зависит от порядка суммирования, а вот для условно сходящихся рядов это не так. Или вот еще «обман» интуиции. Определим многомерное Булево пространство двумя способами.

Первый – элементами булевого пространства размерности N являются всевозможные последовательности из нулей и единиц длинны N.

Второй способ – пусть определенно булево пространство размерности N-1, тогда элементами булево пространство размерности N являются элементы получаемые из булевого пространства размерности N-1 сначала дописыванием ко всем элементам «0», а потом «1».

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

[vek88]

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

И вообще, операция "возьмём в скобки" какая-то удивительная. Такой операции в математической логике нет.

EvgenyGR

Ну Вы сначала хоть посмотрите, о чем идет речь. А потом пишите.

ЗЫ. Я, конечно, понимаю, что сейчас воскресенье - и мы все расслабляемся ... кто как может. Я вот пиво допиваю.

[Someone]

vek88 в сообщении #435895 писал(а):

1. А не соблаговолит ли почтенный Someone привести пример $\neg P(n)$?

Да в модели $\mathbb N+\mathbb Z$ пусть $P(n)$ истинно, если $n\in\mathbb N$, и ложно, если $n\in\mathbb Z$.

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

vek88 в сообщении #435895 писал(а):

2. ИМХО и пункт 2 и пункт 3, по сути, порождают одно и то же. В первом случае, цепочка $0, 0|, ..., 0|||, ...$, во втором, $P(0), P(0|), ..., P(0|||), ...$. Чем эти две цепочки принципиально различаются, я не понимаю. Причем здесь $\mathbb N+\mathbb Z$?

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

vek88 в сообщении #435895 писал(а):

А причем здесь, математическая логика?

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

vek88 в сообщении #435895 писал(а):

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

Тогда Вы ошиблись адресом.

[vek88]

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

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

Я говорю о конкретной теории в конкретной формальной системе. Причем здесь модель? ИМХО здесь моделью и не пахнет.

И вааще, Вы ведь знаете мою нелюбовь к моделям. Хотя это не должно вводить Вас в заблуждение - тяпнуть, кого-угодно за какую хотите модель - и за любое место модели - могу.

-- Вс апр 17, 2011 17:18:37 --

vek88 в сообщении #435919 писал(а):

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

И где же я нарушил законы .. математической логики, пардон?

-- Вс апр 17, 2011 17:21:09 --

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

Тогда Вы ошиблись адресом.

А это то Вы к чему сказали, при всем уважении к Вам? Это я говорю вполне серьезно - уже больше года на форуме и вижу, что Вы очень много знаете и многому я готов у Вас поучиться.

ЗЫ. Ребята, давайте жить дружно.

[Someone]

vek88 в сообщении #435919 писал(а):

Я говорю о конкретной теории в конкретной формальной системе. Причем здесь модель?

При том, что конкретная формальная теория обязана иметь модель, если она непротиворечива, и что построение модели - это часто кратчайший способ доказать независимость некоторого утверждения от аксиом теории. Я требуемую модель предъявил, и поэтому делаю вывод, что Ваше "доказательство" ничего не доказывает. Любите Вы модели или не любите - не имеет никакого значения.

vek88 в сообщении #435919 писал(а):

И где же я нарушил законы .. математической логики, пардон?

В математической логике нет такого правила вывода - "приписывание скобок "P(" слева и ")" справа от формулы. Такая процедура законна при построении формулы из символов алфавита, но к математической логике отношения не имеет.

vek88 в сообщении #435919 писал(а):

А это то Вы к чему сказали, при всем уважении к Вам?

К тому, что в математике нельзя использовать "всё, что нам понравится", и если Вы так думаете, как написали, то Вам надо не на математический форум, а в другое место.