что следует из теоремы Геделя

[Nxx]

Цитата:

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

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

[Xaositect]

Nxx в сообщении #222362 писал(а):

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

В теории утверждения доказуемы или недоказуемы.
Истинны или ложны они в интерпретации.

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

[Nxx]

Цитата:

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

А это известно - действительно она непротиворечива или нет? И если известно, то откуда, если это недоказуемо?

[epros]

Xaositect в сообщении #222366 писал(а):

Истинны или ложны они в интерпретации.

Добавлю: и эту истинность тоже нужно доказывать, но уже не в самой теории, а в метатеории.

[Инт]

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

Вы не поняли. Теорема Гудстейна - это не "неразрешимая известными на сегодня средствами проблема". Это - истинное высказывание (почему - см. выше). Но в арифметике Пеано она недоказуема. "Недоказуема" - это значит буквально: доказательства в рамках арифметики Пеано не существует.

И это не влечёт истинности утверждения Гёделя.

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

В любых "условиях", у Гёделя или не у Гёделя, а доказуемость - это существование доказательства, т.е. той самой цепочки вывода. И ничего более.

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

Что же касается якобы отсутствия в математике понятия "доказательства по существу", то это так же ложь. Любое доказательство, которое будет объявлено формальным и не будет "по существу" сами же математики пошлют куда подальше. Иными словами формальное доказательство может быть служебным приёмом, проекцией реального доказательства, но не более того.

[epros]

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

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

Вы не поняли. Теорема Гудстейна - это не "неразрешимая известными на сегодня средствами проблема". Это - истинное высказывание (почему - см. выше). Но в арифметике Пеано она недоказуема. "Недоказуема" - это значит буквально: доказательства в рамках арифметики Пеано не существует.

И это не влечёт истинности утверждения Гёделя.

Гёдель утверждает существование недоказуемого истинного утверждения. Вот Вам живой пример.

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

объявить заведомо примитивные приёмы и абсурдные логические положения арифметикой

Это называется "дать математическое определение" арифметики. Я понимаю, что Вы не знаете что такое математическое определение: Судя по тому, сколько пустого трёпа Вы вывалили относительно "эффективно вычислимых функций", "содержательных доказательств", "бесконечных алгоритмов" и прочих словосочетаний, не предъявив ни одного определения этих понятий. Так какого чёрта Вы тогда вообще лезете в математику, если не хотите давать определения понятиям?

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

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

Что же касается якобы отсутствия в математике понятия "доказательства по существу", то это так же ложь.

Не желаю далее слушать пустой философский трёп и жду математического определения понятия "доказательство по существу".

[Инт]

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

Гёдель утверждает существование недоказуемого истинного утверждения. Вот Вам живой пример.

Не вся правда - тоже ложь, которую Вы и высказали поэтому. Гёдель не только это утверждает. И им не доказанао даже, что недоказуемое утверждение строится в арифметике Пеано, т.е. что его теория арифметики это арифметика Пеано. Поскольку им воводится теория, существенно отличающаяся от арифметики Пеано. В частности, ограничивается логика: из доказуемости утверждений нельзя извлекать их истинность, иначе, арифметика Гёделя противоречива. Ваш "живой пример" не отменяет ложности гёделевых обобщений на все достаточно богатые арифметики. Но насчёт теоремы Гудстейна посмотрю, со временем, что там за дела. Ясно так же, что если указанная теорема доказуема по существу, то арифметика Пеано просто достаточно примитивна. Что и так ощущается.

Из-за того, что Вы стебаетесь над "филосовским трёпом", т.е. попросту над здравыми идеями, не отменяет некоторой реальной стратегии, которой придерживаются математики. Любые определения всегда можно свести к другим определениям и т.д. Можно тогда сказать, что формалистские рассуждения о знаках это "филосовский трёп", поскольку не определено, что есть знак и т.д. Но новые продуктивные идеи могут быть не выразимы через известное. Бесконечные алгоритмы например. Я имел ввиду, что любое действие можно разбить на более мелкие. Вполне здравая идея.

[Nxx]

Цитата:

Гёдель утверждает существование недоказуемого истинного утверждения. Вот Вам живой пример.

Истинность данной теоремы следует из аксиом арифметики Пеано? Принятие отрицания данной теоремы приведет к противоречию? Значит, она доказуема. Любое утверждение либо независимо от системы аксиом, либо доказуемо. Теорема Геделя утверждает только, что в любой теории существуют утверждения, которые можно сформулировать, но нельзя доказать или опровергнуть. При этом они, естественно, независимы от аксиом (то есть, их или их отрицания можно сами принять за дополнительные аксиомы, и получить непротиворечивую теорию).

[epros]

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

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

Гёдель утверждает существование недоказуемого истинного утверждения.

... Гёдель не только это утверждает.

В первой теореме о неполноте - только это (применительно к любой теории, содержащей стандартную арифметику Пеано).

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

Ясно так же, что если указанная теорема доказуема по существу

Не "по существу", а существует формальное доказательство конечности для каждой последовательности Гудстейна в отдельности.

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

то арифметика Пеано просто достаточно примитивна

Согласно первой теореме Гёделя о неполноте любая формальная теория "достаточно примитивна" в том смысле, что не всё в ней можно доказать.

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

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

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

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

Любые определения всегда можно свести к другим определениям и т.д. Можно тогда сказать, что формалистские рассуждения о знаках это "филосовский трёп", поскольку не определено, что есть знак и т.д. Но новые продуктивные идеи могут быть не выразимы через известное.

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

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

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

И так разбивать до бесконечности? Ничего себе, здравая... Алгоритмы обычно обределяются через "базовые" операции. Это такая операция, смысла которой никому объяснять не нужно. Например, в нормальном алгоритме Маркова за базовую операцию принимается поиск и замена подстроки. Можно, конечно, начать "разбивать" и дальше, только в итоге, если процесс "разбиения" никогда не кончится, мы описания алгоритма так и не получим.

-- Вт июн 16, 2009 17:08:35 --

Nxx в сообщении #222536 писал(а):

Истинность данной теоремы следует из аксиом арифметики Пеано?

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

Nxx в сообщении #222536 писал(а):

Принятие отрицания данной теоремы приведет к противоречию?

Нет, не приведёт. Получим омега-противоречивую теорию (это не означает противоречивость).

Nxx в сообщении #222536 писал(а):

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

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

[Nxx]

Цитата:

Нет, не приведёт. Получим омега-противоречивую теорию (это не означает противоречивость).

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

Цитата:

Потому что доказано мета-теоретически, причём без дополнительных допущений (кроме допущения о том, что всё доказанное в арифметике - истинно).

То есть, эта теорема следует из аксиом ариметики без дополнений? Или ваш термин "истинно" надо как-то по-другому понимать?

[Xaositect]

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

[Nxx]

Цитата:

Утверждение не может быть истинно в системе аксиом.

Утверждение может быть совместимо с системой акиом и несовместимо. Если совместимо - может быть зависимо и независимо от системы аксиоом.

Цитата:

Утверждение может быть истинно в модели системы аксиом

"Модель системы аксиом" имеет какие-то аксиомы, дополняющие первоначальную систему или нет?

[Xaositect]

Nxx в сообщении #222604 писал(а):

"Модель системы аксиом" имеет какие-то аксиомы, дополняющие первоначальную систему или нет?

Модель теории --- это некоторая алгебраическая структура. Рассуждения о ней ведутся в метатеории, которая может не иметь ничего общего с теорией.

[epros]

Nxx в сообщении #222590 писал(а):

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

Nxx, вроде бы, я уже всё сказал. Доказано, что для любого $n$ существует доказательство $p(n)$. Уже отсюда можно метатеоретически сделать вывод, что $(\forall n)(p(n))$ истинно. Однако в самой арифметике доказательства последнего утверждения нет.

-- Вт июн 16, 2009 21:16:32 --

Xaositect в сообщении #222593 писал(а):

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

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

Мне интересно доказательство в теории, в которой вообще нет никакой дополнительной аксиоматики помимо утверждения, что "всё, доказанное в арифметике, истинно". Тогда автоматически из $(\forall n)(A \vdash p(n))$ получаем $(\forall n)(p(n))$. Здесь $A \vdash$ читается как "доказуемо в арифметике".

[Nxx]

Цитата:

Nxx, вроде бы, я уже всё сказал. Доказано, что для любого $n$ существует доказательство $p(n)$. Уже отсюда можно метатеоретически сделать вывод, что $(\forall n)(p(n))$ истинно. Однако в самой арифметике доказательства последнего утверждения нет.

В метатеории это можно доказать только если расширить систему аксиом.

Цитата:

Мне интересно доказательство в теории, в которой вообще нет никакой дополнительной аксиоматики помимо утверждения, что "всё, доказанное в арифметике, истинно".

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