ZFC противоречива?

[Niclax]

Здравствуйте! Помогите разобраться с основаниями математики, а то я что-то совсем запутался.
Если система аксиом Цермело-Френкеля непротиворечива, то, по теореме Геделя, нельзя доказать имеет ли уравнение решение в целых числах, но если бы оно его имело, то его можно было бы просто подставить, значит оно не имеет решений, а это противоречит утверждению теоремы, значит система противоречива - противоречие, значит система противоречива!

[Someone]

Ничего не понял. Приведите точные формулировки теорем, которые Вы упоминаете.

-- Сб июл 17, 2010 13:57:14 --

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

[Niclax]

Someone
Точные формулировки см. например здесь http://ru.wikipedia.org/wiki/Теорема_Гёделя_о_неполноте - в частности, полиномиальная форма.

Цитата:

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

Ну если решение существует, то рано или поздно оно найдется, не через миллион, так через миллиард лет.
То есть, если бы решение существовало, то это было бы доказуемо, но это не так, значит оно не существует, но это тоже не так в силу теоремы. Парадокс, однако.

[neo66]

Niclax в сообщении #339651 писал(а):

Ну если решение существует, то рано или поздно оно найдется, не через миллион, так через миллиард лет.

Дело не в этом. Если я правильно понимаю:

Существуют диофантовы уравнения, которые не имеют решений. Но Вы никогда не сможете этого доказать.

[Someone]

Тут нужно чётко понимать, о какой доказуемости или недоказуемости идёт речь. Когда говорят, что в такой-то теории некое утверждение не доказуемо, то оно не доказуемо именно средствами этой теории. А средствами более сильной теории это утверждение вполне может быть доказуемо.
Например, существуют арифметические утверждения, недоказуемые средствами арифметики Пеано, однако вполне доказуемые средствами теории множеств (http://en.wikipedia.org/wiki/Goodstein%27s_theorem, теорема Гудстейна).

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

[Niclax]

Еще раз : Есть диофантово уравнение. Утверждается, что существование решения у него невозможно ни доказать, ни опровергнуть. Но отсюда получается, что решения не существует, так как иначе быть не может. Вопрос в том, можно ли считать это доказательством. Как я понимаю, нельзя?

[gris]

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

[Someone]

Niclax в сообщении #339730 писал(а):

Еще раз : Есть диофантово уравнение. Утверждается, что существование решения у него невозможно ни доказать, ни опровергнуть. Но отсюда получается, что решения не существует, так как иначе быть не может. Вопрос в том, можно ли считать это доказательством. Как я понимаю, нельзя?

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

[Maslov]

Niclax в сообщении #339626 писал(а):

Если система аксиом Цермело-Френкеля непротиворечива, то, по теореме Геделя, нельзя доказать имеет ли уравнение решение в целых числах

Объясните, пожалуйста, при чём здесь теорема Гёделя?

Niclax в сообщении #339730 писал(а):

Еще раз : Есть диофантово уравнение. Утверждается, что существование решения у него невозможно ни доказать, ни опровергнуть. Но отсюда получается, что решения не существует, так как иначе быть не может. Вопрос в том, можно ли считать это доказательством. Как я понимаю, нельзя?

Вопрос о разрешимости диофантовых уравнений -- это десятая проблема Гильберта. Ю.Матиясевич доказал, что эта этот вопрос алгоритмически неразрешим, т.е., не существует единого алгоритма, способного по произвольному диофантову уравнению определить, имеет ли оно корни.
Для каждого конкретного случая могут существовать специальные способы решения проблемы, но единого способа нет.
Та же ситуация, например, с проблемой остановки: отсутствие общего алгоритма решения задачи об остановке машины Тьюринга вовсе не означает, что любая машина Тьюринга будет работать вечно.

-- Вс июл 18, 2010 14:03:12 --

gris в сообщении #339733 писал(а):

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

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

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

Не, ну что вы... Конечно же можно написать диофантово уравнение, которое

1) Имеет решение, если ZFC противоречива.
2) Не имеет решения, если ZFC непротиворечива. Причём в этом случае отсутствие решений нельзя доказать средствами самой ZFC.

[Dandan]

Niclax в сообщении #339626 писал(а):

Здравствуйте! Помогите разобраться с основаниями математики, а то я что-то совсем запутался.
Если система аксиом Цермело-Френкеля непротиворечива, то, по теореме Геделя, нельзя доказать имеет ли уравнение решение в целых числах, но если бы оно его имело, то его можно было бы просто подставить, значит оно не имеет решений, а это противоречит утверждению теоремы, значит система противоречива - противоречие, значит система противоречива!

Если диофантово уравнение имеет решение - то, конечно же, существует доказательство этого - просто берем подставляем решение. Но, если диофантово уравнение НЕ имеет решения, то доказательство этого (того, что оно не имеет решения) может и не существовать, а может и существовать, как карта ляжет... Именно так и следует все это понимать.

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

Dandan в сообщении #343046 писал(а):

Но, если диофантово уравнение НЕ имеет решения, то доказательство этого (того, что оно не имеет решения) может и не существовать, а может и существовать, как карта ляжет...

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