Существуют ли неразрешимые множества натуральных чисел?

[epros]

Феликс Шмидель в сообщении #591604 писал(а):

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

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

Феликс Шмидель в сообщении #591604 писал(а):

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

Не понимаю, причём тут равенства без переменных?

Феликс Шмидель в сообщении #591604 писал(а):

Мы не умеем проверять даже утверждение о несуществовании натуральных решений уравнения $2x=5$.

Не знаю, что Вы имеете в виду под "проверять", но в арифметике Пеано утверждение $\nexists x ~ 2x=5$ доказуемо.

Феликс Шмидель в сообщении #591604 писал(а):

Но это не означает, что эти утверждения принципиально непроверяемы никаким образом.

Я не утверждал "принципиальную непроверяемость", я спросил: проверяемо ли? И если Вы утверждаете, что проверяемо, то будьте добры это доказать.

[Феликс Шмидель]

epros в сообщении #591618 писал(а):

Феликс Шмидель в сообщении #591604 писал(а):

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

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

Цитата:

Феликс Шмидель в сообщении #591604 писал(а):

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

Не понимаю, причём тут равенства без переменных?

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

Цитата:

Феликс Шмидель в сообщении #591604 писал(а):

Мы не умеем проверять даже утверждение о несуществовании натуральных решений уравнения $2x=5$.

Не знаю, что Вы имеете в виду под "проверять", но в арифметике Пеано утверждение $\nexists x ~ 2x=5$ доказуемо.

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

Цитата:

Феликс Шмидель в сообщении #591604 писал(а):

Но это не означает, что эти утверждения принципиально непроверяемы никаким образом.

Я не утверждал "принципиальную непроверяемость", я спросил: проверяемо ли? И если Вы утверждаете, что проверяемо, то будьте добры это доказать.

Я не утверждаю, что проверяемо.

[epros]

Феликс Шмидель в сообщении #591642 писал(а):

Поэтому, если предположить, что она непротиворечива, то утверждение о несуществовании решений истинно.

Я всё ещё не понимаю: это вывод или это определение "истинности"? И причём тут равенства без переменных? Если Вы уверены в непротиворечивости аксиом и из них следует утверждение о несуществовании, то можете спокойно считать это утверждение истинным.

Феликс Шмидель в сообщении #591642 писал(а):

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

Я всё ещё не понимаю какой смысл Вы вкладываете в понятие истинности. Утверждение о существовании чётного нечётного совершенного числа истинно или нет?

Феликс Шмидель в сообщении #591642 писал(а):

Я не утверждаю, что проверяемо.

А ЧТО проверяемо? "Равенства без переменных" типа $3=2$ или $5=2+3$ проверяемы именно путём построения доказательства (или опровержения) в аксиоматике Пеано. Но есть высказывания арифметики, которые пока не удалось доказать или опровергнуть. Они "проверямы" или нет? Короче: Как Вы определяете проверяемость?

[venco]

epros в сообщении #591654 писал(а):

Утверждение о существовании чётного совершенного числа истинно или нет?

Вы, наверное, хотели сказать "... нечётного ...", а то с чётными как раз проблем нет.

[epros]

venco в сообщении #591658 писал(а):

Вы, наверное, хотели сказать "... нечётного ...", а то с чётными как раз проблем нет.

Сорри, заговариваться начал. Разумеется нечётного.

[Феликс Шмидель]

epros в сообщении #591654 писал(а):

Я всё ещё не понимаю: это вывод или это определение "истинности"? И причём тут равенства без переменных? Если Вы уверены в непротиворечивости аксиом и из них следует утверждение о несуществовании, то можете спокойно считать это утверждение истинным.

Вывод, конечно. А равенства без переменных (без связанных и без свободных, типа $3=2$ или $8=2+3\cdot 2$) при том, что доказуемость всех тех равенств из них, которые истинны используется в этом выводе. Система аксиом может быть непротиворечива и утверждение о несуществовании натуральных решений уравнения $2x=4$ доказуемым в ней, но это утверждение не является истинным.

Цитата:

Я всё ещё не понимаю какой смысл Вы вкладываете в понятие истинности. Утверждение о существовании чётного нечётного совершенного числа истинно или нет?

Я не знаю, истинно это утверждение или нет, и это неважно для понимания его смысла и того, что оно либо истинно, либо ложно. Что касается смысла понятия истинности, то я вкладываю в это понятие тот же смысл, какой вкладывал Гёдель, когда утверждал, что его предложение $G$ недоказуемо, но истинно (при условии непротиворечивости системы аксиом) и Тарский, когда утверждал, что арифметическая истина невыразима (в отличие от доказуемости, которая выразима).

Цитата:

А ЧТО проверяемо? "Равенства без переменных" типа $3=2$ или $5=2+3$ проверяемы именно путём построения доказательства (или опровержения) в аксиоматике Пеано.

Для проверки таких равенств, существует алгоритм, который не зависит от той или иной системы аксиом.
Этот алгоритм сложения и умножения в столбик учат в начальных классах.

Цитата:

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

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

[Someone]

Феликс Шмидель в сообщении #591704 писал(а):

Для проверки таких равенств, существует алгоритм, который не зависит от той или иной системы аксиом.
Этот алгоритм сложения и умножения в столбик учат в начальных классах.

Неправда, зависит. Другое дело, что аксиомы Пеано сформулированы именно так, чтобы этот алгоритм из них следовал. Ну, мы ведь хотим аксиоматизировать именно знакомую со школы арифметику натуральных чисел, а не что-то другое.

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

[Феликс Шмидель]

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

Неправда, зависит.

Цитата:

Истинность арифметического утверждения в действительности зависит от модели арифметики Пеано.

А если система аксиом Пеано противоречива? О каких моделях тогда идёт речь? В этом случае утверждение $2\cdot 2=4$ перестанет быть истинным?

[epros]

Феликс Шмидель в сообщении #591704 писал(а):

Вывод, конечно.

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

Феликс Шмидель в сообщении #591704 писал(а):

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

А как Вы тогда определите, что оно не истинно?

Феликс Шмидель в сообщении #591704 писал(а):

Что касается смысла понятия истинности, то я вкладываю в это понятие тот же смысл, какой вкладывал Гёдель, когда утверждал, что его предложение $G$ недоказуемо, но истинно (при условии непротиворечивости системы аксиом) и Тарский, когда утверждал, что арифметическая истина невыразима (в отличие от доказуемости, которая выразима).

А какой смысл вкладывали Гёдель и Тарский? Насколько я знаю, они делали выводы в рамках мета-теории, т.е. их истинность - следствие мета-доказуемости.

Феликс Шмидель в сообщении #591704 писал(а):

Для проверки таких равенств, существует алгоритм, который не зависит от той или иной системы аксиом.
Этот алгоритм сложения и умножения в столбик учат в начальных классах.

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

-- Ср июл 04, 2012 09:24:51 --

Феликс Шмидель в сообщении #591927 писал(а):

А если система аксиом Пеано противоречива? О каких моделях тогда идёт речь? В этом случае утверждение $2\cdot 2=4$ перестанет быть истинным?

Тут я вижу два варианта:
1) Моделирующая мета-теория скажет, что у арифметики нет модели (ибо теория моделей говорит, что у противоречивых теорий не бывает моделей).
2) Если моделирующая мета-теория всё же ухитрится построить модель, значит сама эта мета-теория противоречива.

[Феликс Шмидель]

Цитата:

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

Ничего подобного. Я вывожу истинность утверждений о несуществовании решений диофантовых уравнений из их доказуемости. Истинность равенств без переменных определяется алгоритмом их проверки, а доказуемость всех таких истинных равенств является условием для вывода. Другим условием является непротиворечивость системы аксиом.

Цитата:

Цитата:

Система аксиом может быть непротиворечива и утверждение о несуществовании натуральных решений уравнения $2x=4$ доказуемым в ней, но это утверждение не является истинным.

А как Вы тогда определите, что оно не истинно?

Очень просто. Я знаю, что $2\cdot2=4$, значит уравнение $2x=4$ имеет решение в натуральных, числах, а то, что в некоторой непротиворечивой системе аксиом доказуемо обратное не означает истинность этого обратного.

Цитата:

А какой смысл вкладывали Гёдель и Тарский? Насколько я знаю, они делали выводы в рамках мета-теории, т.е. их истинность - следствие мета-доказуемости.

Гёдель был платонистом и считал натуральные числа реально существующими в мире идей, а арифметические утверждения объективно истинными или ложными.

Цитата:

А если система аксиом Пеано противоречива? О каких моделях тогда идёт речь? В этом случае утверждение перестанет быть истинным?

Тут я вижу два варианта:
1) Моделирующая мета-теория скажет, что у арифметики нет модели (ибо теория моделей говорит, что у противоречивых теорий не бывает моделей).
2) Если моделирующая мета-теория всё же ухитрится построить модель, значит сама эта мета-теория противоречива.

Согласно определению истинности арифметических утверждений, которое дал Someone, утверждение $2\cdot 2=4$ перестанет быть истинным.

[epros]

Феликс Шмидель в сообщении #592108 писал(а):

Я знаю, что $2\cdot2=4$

Просто Вы не задумывались ОТКУДА Вы это знаете. Я, например, знаю это из определения произведения, кое заключено в аксиомах Пеано. И больше, вроде, этого узнать неоткуда. Будет другое определение произведения - будет и другое знание о том, «истинно» ли равенство $2 \cdot 2 = 4$. Например, из определения произведения по модулю $3$ я знаю, что это равенство - ложно.

Феликс Шмидель в сообщении #592108 писал(а):

значит уравнение $2x=4$ имеет решение в натуральных, числах, а то, что в некоторой непротиворечивой системе аксиом доказуемо обратное…

Вы говорите странные вещи. В непротиворечивой системе НЕ МОГУТ быть доказуемы одновременно и $2 \cdot 2 = 4$, и $\nexists x ~ 2 \cdot x=4$. А если первое недоказуемо, то ничто не мешает нам считать его ложным (см. выше пример произведения по модулю $3$).

Феликс Шмидель в сообщении #592108 писал(а):

Гёдель был платонистом и считал натуральные числа реально существующими в мире идей, а арифметические утверждения объективно истинными или ложными.

Начхать на его философские воззрения. Его утверждение об истинности $G$ приняли только потому, что он его ДОКАЗАЛ.

Феликс Шмидель в сообщении #592108 писал(а):

Согласно определению истинности арифметических утверждений, которое дал Someone, утверждение $2\cdot 2=4$ перестанет быть истинным.

Если Вы имели в виду, что оно станет ложным, то нет. Просто понятие истинности для него потеряет смысл.

[Someone]

Феликс Шмидель в сообщении #592108 писал(а):

Согласно определению истинности арифметических утверждений, которое дал Someone

Стоп! А где это я давал определение истинности? Не помню.

[Феликс Шмидель]

Цитата:

Вы говорите странные вещи. В непротиворечивой системе НЕ МОГУТ быть доказуемы одновременно и $2 \cdot 2 = 4$, и $\nexists x ~ 2 \cdot x=4$. А если первое недоказуемо, то ничто не мешает нам считать его ложным (см. выше пример произведения по модулю $3$).

Конечно, уравнение $2x=4$ может не иметь решений, но оно не может не иметь решений в натуральных числах.
Я говорил о системах аксиом, которые можно использовать для доказательства несуществования решений диофантовых уравнений (в натуральных числах, а не каких-то других). Непротиворечивости такой системы аксиом для этого недостаточно, нужна ещё доказуемость всех истинных арифметических равенств без переменных.
Если утверждение о несуществовании решений диофантового уравнения недоказуемо в системе аксиом Пеано, но доказуемо в другой системе аксиом, удовлетворяющей указанным двум условиям, то оно истинно.
Таким образом понятие истинности арифметических утверждений определяется через понятие непротиворечивости системы аксиом.

Цитата:

Начхать на его философские воззрения. Его утверждение об истинности $G$ приняли только потому, что он его ДОКАЗАЛ.

Он вовсе не доказал $G$ из аксиом Пеано, напротив он доказал, что $G$ не следует из аксиом Пеано.
$G$ следует из утверждения о непротиворечивости системы аксиом Пеано.

Цитата:

Согласно определению истинности арифметических утверждений, которое дал Someone, утверждение $2\cdot 2=4$ перестанет быть истинным.

Если Вы имели в виду, что оно станет ложным, то нет. Просто понятие истинности для него потеряет смысл.

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

-- Ср июл 04, 2012 23:04:07 --

Цитата:

Стоп! А где это я давал определение истинности? Не помню.

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

Истинность арифметического утверждения в действительности зависит от модели арифметики Пеано...любое доказуемое утверждение будет истинным в любой модели.

Вы правы, это не определение истинности.
Тогда вопрос: как Вы понимаете истинность утверждения $2\cdot 2=4$ если не существует моделей арифметики Пеано?

[epros]

Феликс Шмидель в сообщении #592195 писал(а):

Конечно, уравнение $2x=4$ может не иметь решений, но оно не может не иметь решений в натуральных числах.

А что такое «решение в натуральных числах» определяется ничем иным, как аксиомами Пеано. Ходим по кругу?

Феликс Шмидель в сообщении #592195 писал(а):

нужна ещё доказуемость всех истинных арифметических равенств без переменных

Ходим по кругу!!! Как Вы определяете «истинность» арифметических равенств без переменных? Хотя бы того же $2 \times 2 = 4$? Я Вам уже сказал, что это определяется ничем иным, как аксиомами Пеано. У Вас другие соображения?

Феликс Шмидель в сообщении #592195 писал(а):

Если утверждение о несуществовании решений диофантового уравнения недоказуемо в системе аксиом Пеано, но доказуемо в другой системе аксиом, удовлетворяющей указанным двум условиям, то оно истинно.

Да ну? А если в одной «такой» системе оно доказуемо, а в другой - опровержимо?

Феликс Шмидель в сообщении #592195 писал(а):

Он вовсе не доказал $G$ из аксиом Пеано

Я не сказал, что он это доказал «из аксиом Пеано», я сказал, что он это доказал в мета-теории.

Феликс Шмидель в сообщении #592195 писал(а):

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

Чтобы утверждать такие вещи, надо сначала определить, откуда Вы берете истинность. Я Вам привёл пример модели вычислений, в которой утверждение $2 \times 2 = 4$ ложно. И рассуждать о том, чем будет заменена аксиоматика Пеано, если обнаружится её противоречивость, бессмысленно - до тех пор, пока мы не увидим новой аксиоматики.

[Феликс Шмидель]

Цитата:

Как Вы определяете «истинность» арифметических равенств без переменных? Хотя бы того же $2 \times 2 = 4$? Я Вам уже сказал, что это определяется ничем иным, как аксиомами Пеано. У Вас другие соображения?

Да, для этого не нужны аксиомы Пеано. Можно принять все такие истинные (согласно алгоритму проверки) равенства за аксиомы и добавить другие аксиомы, не обязательно аксиомы Пеано.

Цитата:

Если утверждение о несуществовании решений диофантового уравнения недоказуемо в системе аксиом Пеано, но доказуемо в другой системе аксиом, удовлетворяющей указанным двум условиям, то оно истинно.

Да ну? А если в одной «такой» системе оно доказуемо, а в другой - опровержимо?

Тогда оно всё равно истинно, я же доказал это.

Цитата:

Я не сказал, что он это доказал «из аксиом Пеано», я сказал, что он это доказал в мета-теории.

Его теорема это теорема арифметики Пеано, а не мета-теории.
Он доказал, что из утверждения о непротиворечивости системы аксиом следует $G$.

Цитата:

Чтобы утверждать такие вещи, надо сначала определить, откуда Вы берете истинность. Я Вам привёл пример модели вычислений, в которой утверждение $2 \times 2 = 4$ ложно. И рассуждать о том, чем будет заменена аксиоматика Пеано, если обнаружится её противоречивость, бессмысленно - до тех пор, пока мы не увидим новой аксиоматики.

Можно все истинные (согласно алгоритму проверки) равенства без переменных принять за аксиомы и добавить другие аксиомы, не обязательно аксиомы Пеано.
Я сказал, что если обнаружится её противоречивость, система аксиом Пеано будет заменена более совершенной.
Это не бессмысленно.