Существуют ли принципиально недоказуемые гипотезы?

[z-theory]

mihaild в сообщении #1615050 писал(а):

А нет понятия "недоказуема вообще", доказуемость всегда в конкретной теории

Я неточно выразился. Возможно, точнее было бы сказать, что недоказуема ни в одной из возможных теорий, которые потенциально могут существовать в математике или другими словами которые потенциально может породить пытающийся определить доказуемость данного утверждения конструктивно мыслящий условный сверхразум за бесконечное время. Хотя не уверен, что стало более понятно. Но все равно данная формулировка будет не совсем точна. К сожалению, как я понял, единственный способ задать вопрос так, чтобы тебя недвусмысленно понял собеседник — использовать математическую нотацию.

[mihaild]

z-theory в сообщении #1615083 писал(а):

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

Любое синтаксически корректное утверждение доказуемо в некоторой теории.

[iifat]

Mikhail_K
Не силён в философии, но аксиомы, имхо, не принимаются актом веры. Исключительно полезностью и интересностью.
Ну и, кроме того, что произойдёт при таком подходе с аксиомой, скажем, параллельности? Сколько параллельных умещается на кончике иглы можно провести через точку, не лежащую на прямой? Ни одной, одну или две? Предлагаете выкинуть две геометрии из трёх? Или разобьём математиков на три фракции и устроим промежду ними кровавые религиозные войны?

[Mikhail_K]

iifat в сообщении #1615096 писал(а):

Не силён в философии, но аксиомы, имхо, не принимаются актом веры.

"Актом веры" у Манина - это метафора, на самом деле сказанное имеет точный математический смысл. Текст не философский (и автор - не философ, а математик). И, как я понимаю, относится этот текст только к арифметике, а не к геометрии или теории множеств (но меня очень интересует, можно ли распространить что-то подобное на другие математические теории, пробовали ли это делать и что получилось).

[Anton_Peplov]

DieselMachine в сообщении #1615082 писал(а):

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

Запросто. Но мы не можем этого знать. Чтобы убедиться. что короткое доказательство есть, нужно предъявить это короткое доказательство. А вот как убедиться. что короткого доказательства нет? Да никак. Всегда будет надежда, что оно есть, просто мы до него пока не додумались.

DieselMachine в сообщении #1615082 писал(а):

Классификация простых конечных групп в переработанном виде опубликована частично тремя авторами в девяти из четырнадцати томов.

Ну, можно придумать задачу классификации какого-нибудь более обширного класса групп. А то и полугрупп, чтобы уж точно не справиться.
О полугруппах, кстати, вообще очень мало доказанных теорем по сравнению с группами. Уж слишком большую свободу оставляет определение полугруппы.

[diletto]

Anton_Peplov в сообщении #1615108 писал(а):

Чтобы убедиться. что короткое доказательство есть, нужно предъявить это короткое доказательство. А вот как убедиться. что короткого доказательства нет? Да никак. Всегда будет надежда, что оно есть, просто мы до него пока не додумались.

Есть ли корреляция между длиной формального и неформального доказательства?
И может ли быть несколько формальных доказательств у одного и того же утверждения?

[EminentVictorians]

diletto в сообщении #1615135 писал(а):

Есть ли корреляция между длиной формального и неформального доказательства?

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

diletto в сообщении #1615135 писал(а):

И может ли быть несколько формальных доказательств у одного и того же утверждения?

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

[пианист]

(Оффтоп)

z-theory в сообщении #1615049 писал(а):

существуют ли в математике принципиально недоказуемые утверждения (гипотезы)?

Существуют.
Гипотеза $H_0$. Существуют недоказуемые гипотезы.
Если гипотеза $H_0$ доказуема, то применяем, и доказываем, что существуют. Если не, то $H_0$ та самая, недоказуемая.

[z-theory]

Anton_Peplov в сообщении #1615108 писал(а):

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

А вот это, кстати, тоже интересный вопрос. Гипотетически можно допустить существование физического способа доказательства. Например, вдруг может оказаться, что доказательство утверждения можно свести к некоторой задаче (например, связанной с простыми числами), практически решаемой (пусть и не сегодня) на квантовом компьютере. Можем ли мы в этом считать, что мы доказали доказуемость утверждения, при этом не решив практически задачу — мы ведь даже не включали квантовый компьютер?!

-- 29.10.2023, 17:20 --

пианист в сообщении #1615139 писал(а):

Существуют.
Гипотеза $H_0$. Существуют недоказуемые гипотезы.
Если гипотеза $H_0$ доказуема, то применяем, и доказываем, что существуют. Если не, то $H_0$ та самая, недоказуемая.

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

Mikhail_K в сообщении #1615079 писал(а):

Давным-давно я прочитал в книге Ю.И. Манина "Математика как метафора" вот такой отрывок.

[diletto]

EminentVictorians в сообщении #1615138 писал(а):

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

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

[Anton_Peplov]

EminentVictorians уже ответил, но все же скажу своими словами и, может быть, более обстоятельно.

diletto в сообщении #1615135 писал(а):

Есть ли корреляция между длиной формального и неформального доказательства?

Непонятно, как измерять длину неформальных доказательств. У одного и того же утверждения может быть много неформальных доказательств, использующих разные логические цепочки и даже разные области математики. Взгляните, сколько есть доказательств бесконечности множества простых чисел. Как сравнить длину доказательства Эйлера с длиной доказательства Фюрстенберга? Первое опирается на основную теорему арифметики, то есть ее нужно предварительно доказать. Второе - на топологию, то есть сначала нужно ввести топологические понятия и доказать про них теоремы. Ладно, в этом случае у нас есть явный фаворит - доказательство Евклида. Оно и короткое, и без лишних сущностей. А если фаворита нет?

Чтобы сравнивать длину доказательств, нужно искусственно ограничить набор средств (далее универсум) - множество понятий и теорем, на которые мы ссылаемся. Например, "если в доказательстве используются понятия и теоремы, которые не изучают в средней школе, то по ходу доказательства определяем эти понятия и доказываем эти теоремы через то, что изучают в средней школе". В "школьном" универсуме, боюсь, доказательство Уайлса теоремы Ферма будет занимать не сто страниц, а сто тысяч.

Ладно, зафиксируем универсум, в котором доказываем теоремы. Тогда для любой доказанной теоремы обязано существовать кратчайшее доказательство, даже если мы его не знаем. (А мы, вполне возможно, его не знаем. В истории математики много раз было, что первое доказательство теоремы было сложным, а потом пришел, скажем, Гильберт и предложил гораздо более простое доказательство.)

Тогда коррелирует ли длина кратчайшего доказательства в данном универсуме с длиной кратчайшего формального доказательства? Разумеется. Эти две длины будут отличаться ровно на число символов, потребное, чтобы кратчайшим образом выразить использованные средства универсума на языке формальной теории.

-- 29.10.2023, 23:17 --

diletto в сообщении #1615191 писал(а):

Быть может, есть методы приведения формальных цепочек к простейшему (кратчайшему) виду?

Не знаю, есть ли практичные способы. Но принципиальный способ сокращения формального доказательства прост как бревно. Пусть у нас есть формальное доказательство длиной $n$ символов. Меняя $k$ от 1 до $n-1$, перебираем все строки из $k$ символов, пока одна из них не окажется формальным доказательством искомой теоремы. Если не найдем - значит, наше доказательство длиной $n$ символов и есть самое короткое.

[diletto]

EminentVictorians, Anton_Peplov,
Спасибо!
Ещё один дурацкий вопрос (я ведь никогда не видел этих формальных цепочек) по поводу

Anton_Peplov в сообщении #1615195 писал(а):

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

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

[Anton_Peplov]

diletto в сообщении #1615197 писал(а):

формальные теории предусматривают расширения?

Да. Они так и называются - расширениями. Расширение теории, не влияющее на доказуемость утверждений, называется консервативным.

diletto в сообщении #1615197 писал(а):

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

Это как раз пример консервативного расширения теории.

[Dicson]

z-theory в сообщении #1615049 писал(а):

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

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

Но вся математика нам, во-первых, неизвестна, а во-вторых, сделать вывод о всей математике (например, что это именно вся математика), можно только выйдя за её рамки. Но за рамками математики нет математики, поэтому вывод о всей математике будет не математический. Тем не менее всю математику несложно представить и, таким образом, ответить на ваш вопрос, хотя и не математически.

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

Таким образом, физическая теория всего - это математическая теория, которая описывает всё, в том числе и саму себя (всё есть математика и она следует из самой себя). Следовательно, объект "вся математика" - это именно физическая теория всего.

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

В итоге ответ на ваш вопрос: ничего "принципиально" недоказуемого в математике нет. Потому что если построить "всю математику", то всё мыслимые утверждения, как минимум в принципиальном смысле, строго разделятся на истинные и ложные.

Так? Или, может быть, нет?

(Ответ (без пояснений))

Олег Ухналёв https://youtu.be/QjrrOR6Eaaw

[DieselMachine]

Anton_Peplov в сообщении #1615051 писал(а):

z-theory в сообщении #1615049 писал(а):

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

Конечно. Нужно просто принять это утверждение за аксиому другой теории. Вот и будет доказательство из одной строчки. А если примем за аксиому отрицание этого утверждения, получим опровержение из одной строчки. Теории-то можно строить, в общем, какие угодно.

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