Ещё раз о конструктивных и неконструктивных доказательствах

[epros]

Следует ли объекты, существование которых недоказуемо, в каком-либо смысле приравнивать к несуществующим?

Насколько я понимаю, ответ на этот вопрос зависит от используемой логической системы. Хотелось бы разобраться...

Приведу пример несуществующего объекта. Несуществование "минимального положительного рационального числа" легко доказывается от противного: если бы такое число существовало, то поделив его на 2 мы бы получили меньшее положительное рациональное число, что является противоречием с исходным предположением.

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

Посмотрим, как обстоят дела в традиционной логике, принимающей доказательства от противного. Здесь за доказательство обычно принимается конечная последовательность конечных утверждений, построенных в соответствии с правилами вывода (т.е. подстановками из аксиом и ранее доказанных утверждений). Известно, что есть высказывания о существовании, которые не доказаны и не опровергнуты. Например, высказывание: "существует нечётное совершенное число". Допустим, что в результате рассмотрения общей модели теории чисел получено доказательство того, что невозможно построить конечный вывод данного утверждения. Т.е. по-сути мы имеем доказанное утверждение о недоказуемости существования. Но ведь если разобраться, то из недоказуемости существования нечётного совершенного числа следует, что проверка любого примера числа на то, что оно является нечётным совершенным, не может дать положительного результата. Но ведь известно, что проверка любого примера является конечной операцией, т.е. она всегда может быть выполнена, т.е. неполучение положительного результата будет означать отрицательный результат. Получается, что из "недоказуемости существования" следует несуществование (как и в случае с минимальным положительным рациональным числом).

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

[Lyoha]

epros писал(а):

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

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

[epros]

Lyoha писал(а):

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

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

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

Доказательства существования и несуществования представляются мне не вполне логически равноценными. Например, за доказательство существования можно считать предъявление проверяемого примера и не принимать ничего иного (как я понимаю, конструктивисты примерно так и делают). С несуществованием так не поступишь. Я не знаю случаев, чтобы несуществование чего-либо доказывалось иначе, как от противного - через приведение к противоречию предположения а возможности привести пример. Может быть Вы знаете?

[Батороев]

epros писал(а):

Например, высказывание: "существует нечётное совершенное число".

Прочитал эту фразу и решил поразмышлять, существует ли такое число?

Допустим, что имеется нечетное число $ N = abc $,
где $ a,b,c $ - простые числа.
Если число N - совершенное, то:
$ abc - ac - bc - ab - a - b - c - 1 = 0 $ (1)

Теперь рассмотрим выражение:
$ M = (a-1)(b-1)(c-1) = abc - ac - bc - ab + a + b + c - 1 $.

С учетом (1) имеем:
$ M = 2a + 2b + 2c = 2(a -1) + 2(b - 1) + 2(c - 1) + 6 $,
чего быть не может, т.к. четность правой части уступает четности числа M.

От количества множителей, как мне кажется, суть не меняется.
Например, при четном числе множителей имеем:
$ N = abcd $
$ abcd - bcd - acd - abd - abc - ab - ac - cd - bc - a - b -c - d - 1 = 0 $
$ M = abcd - bcd - acd - abd - abc + ab + ac + cd + bc - a - b -c - d + 1 = 0 $
$ M = 2cd + 2 bd + 2 ad + 2ac + 2 = 2(cd + bd + ad + ac) + 2 $,
т.е. четность правой части опять уступает четности числа M.

[Macavity]

Батороев писал(а):

epros писал(а):

Например, высказывание: "существует нечётное совершенное число".

Прочитал эту фразу и решил поразмышлять, существует ли такое число?

Допустим, что имеется нечетное число $ N = abc $,
где $ a,b,c $ - простые числа.
Если число N - совершенное, то:
$ abc - ac - bc - ab - a - b - c - 1 = 0 $ (1)

Теперь рассмотрим выражение:
$ M = (a-1)(b-1)(c-1) = abc - ac - bc - ab + a + b + c - 1 $.

С учетом (1) имеем:
$ M = 2a + 2b + 2c = 2(a -1) + 2(b - 1) + 2(c - 1) + 6 $,
чего быть не может, т.к. четность правой части уступает четности числа M.

От количества множителей, как мне кажется, суть не меняется.
Например, при четном числе множителей имеем:
$ N = abcd $
$ abcd - bcd - acd - abd - abc - ab - ac - cd - bc - a - b -c - d - 1 = 0 $
$ M = abcd - bcd - acd - abd - abc + ab + ac + cd + bc - a - b -c - d + 1 = 0 $
$ M = 2cd + 2 bd + 2 ad + 2ac + 2 = 2(cd + bd + ad + ac) + 2 $,
т.е. четность правой части опять уступает четности числа M.

Простые делители не обязательно имеют степень 1. Например, совершенное число 28 имеет простыми делителями 2 и 7, а 28=2^2*7 и 28=1+2+4+7+14. Вы это учитывали в Ваших выкладках?

[juna]

Извиняюсь за offtopic.
Вот здесь указано, что все нечетные совершенные должны иметь вид $p^aq_1^{2k_1}..q_r^{2k_r}$, где $p\equiv a \equiv 1 \mod 4$ и $k_i$ не могут быть все равны 1, здесь $p,q_i$ - нечетные простые. Но все равно выкладки Батороева симпатичные.

[Macavity]

Артамонов Ю.Н. писал(а):

Извиняюсь за offtopic.
Вот здесь указано, что все нечетные совершенные должны иметь вид $p^aq_1^{2k_1}..q_r^{2k_r}$, где $p\equiv a \equiv 1 \mod 4$ и $k_i$ не могут быть все равны 1, здесь $p,q_i$ - нечетные простые. Но все равно выкладки Батороева симпатичные.

Да и Ваша ссылка тоже интересная...

[Батороев]

Мне показалось, что немного проще рассматривать через M, как произведение сумм.

Допустим, что имеется нечетное число $ N = abc $,
где $ a,b,c $ - простые числа.
Если число N - совершенное, то:
$ abc - ac - bc - ab - a - b - c - 1 = 0 $ (1)

Теперь рассмотрим выражение:
$ M = (a+1)(b+1)(c+1) = abc + ac + bc + ab + a + b + c + 1 $.

С учетом (1) имеем:
$ M = 2ac + 2bc + 2ab + 2a + 2b + 2c + 2 $,
чего быть не может, т.к. четность правой части уступает четности числа M.

При четном числе множителей имеем:
$ N = abcd $
$ abcd - bcd - acd - abd - abc - ab - ac - cd - bc - a - b -c - d - 1 = 0 $
$ M = (a+1)(b+1)(c+1)(d+1) = abcd + bcd + acd + abd + abc + ab + ac + cd + bc + a + b + c + d + 1 = 0 $
$ M = 2bcd + 2acd + 2 abd + 2abc + 2cd + 2 bd + 2 ad + 2ac + 2a + 2b + 2c + 2 d + 2 $,
т.е. четность правой части опять уступает четности числа M.

Macavity писал(а):

Простые делители не обязательно имеют степень 1. Например, совершенное число 28 имеет простыми делителями 2 и 7, а 28=2^2*7 и 28=1+2+4+7+14. Вы это учитывали в Ваших выкладках?

Допустим, что имеется нечетное число $ N = a^2b $,
где $ a, b $ - простые числа.
Если число N - совершенное, то:
$ a^2b - a^2 - ab - a - b - 1 = 0 $ (1)

Теперь рассмотрим выражение:
$ M = (a+1)^2(b+1) = a^2b + a^2 + 2ab + 2a + b + 1 $.

С учетом (1) имеем:
$ M = 2a^2 + 2b + 3ab + 3a + 2 = 2(a^2+b) + 3a(b+1) + 2 $,
и здесь обнаруживаем то, что должно быть:
$ b\equiv 1\mod 4 $,
что соответствует одной из рекомендаций, указанных в ссылке Ю. А. Артамонова.
Отсюда делаем глубокомысленный вывод о том, что все это, по-видимому, пройденный путь.

[Lyoha]

epros писал(а):

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

А конструктивный анализ годится на что-либо большее, чем подсчёт сдачи в магазине?

[Someone]

epros писал(а):

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

В конструктивном анализе есть свой аналог несчётности - неперечислимость. Например, множество конструктивных действительных чисел (КДЧ) конструктивно неперечислимо. В том смысле, что существует алгоритм, который по заданной конструктивной последовательности КДЧ строит КДЧ, заведомо не принадлежащее этой последовательности.

Добавлено спустя 10 минут 23 секунды:

Lyoha писал(а):

А конструктивный анализ годится на что-либо большее, чем подсчёт сдачи в магазине?

Конструктивный анализ в значительной степени "параллелен" классическому, хотя отличия есть. Например, все конструктивные функции (определённые на подмножествах множества КДЧ) непрерывны на своей области определения. Конструктивная функция, непрерывная на некотором отрезке, не обязана принимать на нём наименьшее и наибольшее значения и не обязана принимать все промежуточные значения.

Какова область применения конструктивного анализа - не знаю, никогда этим не занимался.

[epros]

Someone писал(а):

...существует алгоритм, который по заданной конструктивной последовательности КДЧ строит КДЧ, заведомо не принадлежащее этой последовательности.

Да, я знаю. При этом также можно построить конструктивную последовательность КДЧ, которая включает как исходную последовательность, так и данное число.

А в итоге и из того, и из другого ничего интересного не следует (в смысле - не следует никаких принципиальных различий между "континуумом" и "счётным множеством", как в традиционном анализе).

Lyoha писал(а):

А конструктивный анализ годится на что-либо большее, чем подсчёт сдачи в магазине?

Я точно знаю, на что он не годится: на то, чтобы доказывать существование невыразимых и нигде неприменимых математических понятий типа "нелинейная аддитивная функция на $\mathbb{R}$". В остальном, насколько я понимаю, никакая физическая теория (т.е. теория, оперирующая измеримыми величинами) разницы не заметит.

[Lyoha]

epros писал(а):

Lyoha писал(а):
А конструктивный анализ годится на что-либо большее, чем подсчёт сдачи в магазине?

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

Ну во-первых, физика оперирует не только "измеримыми величинами".

А во-вторых, верна ли моя догадка, что конструктивный анализ кроме гипотезы континума отвергает ещё по крайней мере и аксиому выбора? Если да, то он отвергает все аксиомы, выходящие за рамки целочисленного счёта, или только некоторые избранные? В любом случае, ИМХО, его возможности ограничены бухгалтерской математикой.

[Someone]

Lyoha писал(а):

А во-вторых, верна ли моя догадка, что конструктивный анализ кроме гипотезы континума отвергает ещё по крайней мере и аксиому выбора? Если да, то он отвергает все аксиомы, выходящие за рамки целочисленного счёта, или только некоторые избранные?

Конструктивный анализ даже логику другую использует, неклассическую. Закон исключённого третьего, например, не признаёт (это делает невозможными доказательства "от противного"), и ещё некоторые отличия есть. Гипотезы континуума и аксиомы выбора там совсем нет. Если Вам нужна функция выбора для некоторой (конструктивно определённой) совокупности множеств, то будьте любезны указать алгоритм выбора. Но в конструктивном анализе есть метрические пространства, понятия непрерывности, производной, интеграла и т.п. Так что теория там достаточно богатая. Правда, я слышал, что чуть ли не любое утверждение классического анализа можно "вложить" в конструктивный анализ, навесив двойное отризание всюду, где только можно, но подробнее не знаю.

[epros]

Lyoha писал(а):

Ну во-первых, физика оперирует не только "измеримыми величинами".

Например?

Насколько я знаю, физика не занимается принципиально ненаблюдаемыми сущностями. А наблюдаемость и измеримость - это практически синонимы.

Приведу пример столкновения физики с неконструктивными понятиями. СТО, как известно, основана на двух известных постулатах. Зададимся вопросом, как вывести из них формулу преобразований Лоренца? Схема такова: с помощью первого постулата делаем вывод о том, что преобразования между ИСО - линейные, затем помощью второго собственно получаем общую формулу для матрицы преобразования. Трудность возникает уже на первом шаге. Казалось бы, из утверждения о том, что первый закон Ньютона (прямолиненйное равномерное движение) должен сохранять своё действие в любой ИСО, непосредственно следует, что преобразование между ИСО сохраняет прямые линии. Но вот является ли преобразование, сохраняющее прямые линии, линейным? Аддитивность такого преобразования, т.е. то, что $F(\vec{a} + \vec{b}) = F(\vec{a}) + F(\vec{b})$, достаточно легко доказывается. Но это ведь ещё не означает линейность... Я задаюсь вопросом, а существуют ли вообще нелинейные аддитивные функции на $\mathbb{R}$ и выясняю, что в функциональном анализе, оказывается, доказывается, что такие функции "существуют", правда доказательство - неконструктивно. Что это значит? А это значит, что пример такой функции мне привести никто не может. Замечательно, но что делать физику? Закладывать в СТО третий постулат - непрерывности преобразования перехода между ИСО, и всё только из-за возможности существования неких мифических преобразований, примера которых привести невозможно? (Правда оказалось, что для более чем одномерного пространства доказательство линейности преобразования, сохраняющего прямые линии, возможно и без требования непрерывности, но оно достаточно нетривиально).

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

Lyoha писал(а):

А во-вторых, верна ли моя догадка, что конструктивный анализ кроме гипотезы континума отвергает ещё по крайней мере и аксиому выбора? Если да, то он отвергает все аксиомы, выходящие за рамки целочисленного счёта, или только некоторые избранные? В любом случае, ИМХО, его возможности ограничены бухгалтерской математикой.

И аксиому выбора, и аксиому бесконечности. И, как уже заметил Someone, - закон исключённого третьего (вместе с правилом снятия двойного отрицания), т.е. не признаёт доказательств от противного.

Вместе с тем трактовка, что он якобы ограничен сферой "целочисленного счёта", абсолютно неверна. В некотором смысле конструктивизм - это математика конечных операций. На первый взгляд может показаться, что этим отвергается достаточно "богатый" кусок математики, оперирующей с бесконечностями. Но если разобраться, то оказывается, что в жизни-то эти бесконечности никогда и не используются. Например, если взять любое действительное число, скажем $\pi$, то мы в принципе всегда работаем только с конечной точностью его представления. Ну и, конечно же, теоретически должна быть предусмотрена возможность работать с представлением любой точности. Конструктивизм предоставляет эту возможность. Единственное, что он отрицает, это что возможно представление "бесконечной" точности.

[Кардановский]

epros: С понятием "минимальное положительное рациональное число", действительно ,получается логико-математический парадокс:оно, вроде бы, должно быть вот тут,где то рядом с 0 на числовой оси, но указать его точно, вроде бы, не представляется возможным ! Позволю себе предложить вариант выхода из этого логического тупика,который, что особенно неприятно, притаился в самом основании теории чисел. Я предлагаю ввести в математику самое минимальное положительное число директивно. Т.е. условиться математикам считать,например, самым малым положительным рациональным числом 10 в степени минус факториал 10 в 1000000000 степени. Это,разумеется,как пример! Можно условиться взять за минимальное подобное число и еще меньшее число-не суть важно! Таким образом, можно ввести обновленное,конкретизированное понятие"минимального положительного рационального числа" , т.е. ввести понятие числового кванта! Такая квантовая теория чисел могла бы ,как представляется, снять многие противоречия! Правда, при этом,придется пересматривать много теорем классической теории чисел...Но, ничто не вечно под Луной...