Комментарии 138
Все это уже было в симпсонах у Пенроуза. Но статья неплохая, спасибо.
Спасибо всем за замечание. Перепутанные кванторы переставил.
Тогда хочется добавить замечание, что утверждение критянина «Все критяне — лжецы» — не является парадоксом.
Отрицанием этого утверждения является «Не все критяне — лжецы», а вовсе не «Все критяне — не лжецы», как обычно подразумевается. В этом случае Эпименид — лжец, но не все критяне лжецы. Никакого парадокса.
Даже сокращение охватываемого каким-либо утверждением множества субъектов, что-либо когда-либо заявлявших, т.е. со всех критян до одного Эпименида, — «Я лгу», тоже не становится парадоксом. Максимум на парадокс тянет утверждение «Это утверждение ложно».
Здесь уже вспоминали Смаллиана, который, в своей книге «Алиса в стране смекалки», довольно подробно разбирает этот и другие «парадоксы»
Отрицанием этого утверждения является «Не все критяне — лжецы», а вовсе не «Все критяне — не лжецы», как обычно подразумевается. В этом случае Эпименид — лжец, но не все критяне лжецы. Никакого парадокса.
Даже сокращение охватываемого каким-либо утверждением множества субъектов, что-либо когда-либо заявлявших, т.е. со всех критян до одного Эпименида, — «Я лгу», тоже не становится парадоксом. Максимум на парадокс тянет утверждение «Это утверждение ложно».
Здесь уже вспоминали Смаллиана, который, в своей книге «Алиса в стране смекалки», довольно подробно разбирает этот и другие «парадоксы»
Еще более разжевано это же можно прочесть в книге https://ru.wikipedia.org/wiki/Гёдель,_Эшер,_Бах
которую я никогда не устану рекламировать — уж слишком она хороша :)
которую я никогда не устану рекламировать — уж слишком она хороша :)
Я бы еще дополнил Смаллианом. Forever Undecided. Уже есть аж 2 перевода на русский, хотя несколько лет назад еще ни одного не было.
Вовеки неразрешимо. Головоломное руководство по Геделю
Вовеки неразрешимое. Путь к Геделю через занимательные загадки
Вовеки неразрешимо. Головоломное руководство по Геделю
Вовеки неразрешимое. Путь к Геделю через занимательные загадки
Обозначим множество всех ФСП буквой F. Понятно, что его можно упорядочить по алфавиту (по какому именно, нам непринципиально). Таким образом, любой ФСП соответствует её номер k в упорядоченном списке, и мы будем обозначать её Fk.
Это почему? Каким таким образом из того, что множество упорядочено, следует, что оно счётно?
Множество действительных чисел упорядочено. И Кантор именно таким диагональным способом доказывал, что оно несчётно.
Вы сомневаетесь в том, что множество слов над конечным алфавитом счётно?
Слов ограниченной длины? Не сомневаюсь. Даже конечно.
А если неограниченной? Ваше же доказательство блестяще показывает, что множество функций натурального аргумента несчётно. Хотя можно и проще — конечный алфавит 0,1,2,3,4,5,6,7,8,9. Множество слов — все действительные числа между 0 и 1. Континуум.
А если неограниченной? Ваше же доказательство блестяще показывает, что множество функций натурального аргумента несчётно. Хотя можно и проще — конечный алфавит 0,1,2,3,4,5,6,7,8,9. Множество слов — все действительные числа между 0 и 1. Континуум.
Нет не все действительные. 0,(3) нет например. Зато если 0 на A заменить, то получится, что можно каждому числу сопоставить натуральное, переведя из одиннадцатеричной системы счисления.
А если неограниченной?
И неограниченной — тоже. Вам ниже уже ответили.
И ответили неправильно. Множество слов неограниченной длины не счетно.
Докажите?
Выстроим все слова в алфавитном порядке. Сопоставим слову его номер в этом списке. Множество пронумеровано. Q.e.d.
Именно
Вы правы в том, что это множество счётное, но так занумеровать слова не получится. Если длина слов не ограничена, то Вы не сможете выстроить их все в алфавитном порядке. Пусть у Вас всего две буквы: А и Б. Тогда алфавитный список слов будет иметь вид:
А
АА
ААА
АААА…
Вы даже не доберётесь до слов, в которых есть буква Б. То есть занумеровать-то, конечно, можно, но по-другому, как-нибудь так: сперва все однобуквенные (их конечное число), затем двухбуквенные и т. д.
А
АА
ААА
АААА…
Вы даже не доберётесь до слов, в которых есть буква Б. То есть занумеровать-то, конечно, можно, но по-другому, как-нибудь так: сперва все однобуквенные (их конечное число), затем двухбуквенные и т. д.
Вы таки очевидно неправы. Множество всех слов бесконечной длины на алфавите размерности по крайней мере 2 — несчётно. Это прямо следует из диагонального аргумента Кантора: множество всех бесконечных слов на алфавите {0,1} несчётно. А поскольку в информатике доказывается равномощность алфавитов размерности 2 и более, это утверждение естественно обобщается на любой алфавит размерности больше 1.
Дальше вольный перессказ диагонального аргумента Кантора.
Пусть есть 2-буквенный алфавит {a, b} и множество S всех слов бесконечной длины из этого алфавита.
Предположим, что мы каким-то образом пронумеровали множество S, таким образом, что S = {s₁, s₂, ...}. Cконструируем теперь новый элемент sₓ, такой, что n-тым его символом является "инверсия" n-того символа в строке sₙ. Под "инверсией" я понимаю функцию вида f('a') = 'b'; f('b') = 'a'. Ясно, что sₓ не входит в множество {s₁,s₂,...}. Действительно, это не s₁, поскольку sₓ отличается от s₁ в первом символе (по построению), это не s₂, поскольку sₓ отличается от него во втором символе (по построению) и тд. Однако, sₓ очевидно является элементом S по определению множества S. Мы пришли к противоречию, следовательно, наше предположение, что мы каким-то образом пронумеровали множество S — ложно, S ≠ {s₁, s₂, ...}.
Очевидно, что если добавить к множеству S слова конечной длины, оно от этого не станет счётным.
Неправы тут, к сожалению, вы. Как сказано в самом тексте, и потом несколько раз — в комментариях, в наброске доказательства используется счётность множества слов КОНЕЧНОЙ длины. Явный способ их нумерации тоже несколько раз упомянут.
Мой комментарий относился конкретно к этой ветке, а не к основному тексту. И тут речь шла про слова неограниченной, i.e. потенциально бесконечной длины. Исключая вариант что Вы "неограниченной длины" читаете строго как "неограниченной, но конечной длины".
А вот что пост прошлогодний и что мой комментарий можно расценить как некромантию — это я как-то проглядел...
НЛО прилетело и опубликовало эту надпись здесь
Исключая вариант что Вы "неограниченной длины" читаете строго как "неограниченной, но конечной длины".
Специально сделал эту оговорку. Очевидно вопрос немного несовпадающей терминологии, дальнейшее обсуждение умеренно бессмысленно.
На всякий случай: я понимаю, что бесконечное множество всех конечных строк над счётным алфавитом — счётно, можно мне это не объяснять.
Достаточно попросить доказать более слабое утверждение. Есть алфавит из одной буквы и нет ограничения на длину слова. Пусть уважаемый Welran попробует доказать несчетность множества слов, не смотря на очевидный способ нумерации.
Уже было
Для этого вам сначала придется доказать что мощность множества слов алфавита из одной буквы эквивалентная мощности множества слов из 2 и более букв (что очевидно не так).
А почему не так? Мне кажется это совсем не очевидно, более того мощность таких множеств эквивалентна.
Если бы алфавит размерности 1 был равномощен алфавитам размерности 2 и более, то мы бы, вероятно, использовали единичную, а не двоичную систему счисления в информационной технике.
Доказательство "на пальцах":
Любой элемент множества действительных чисел имеет представление (возможно бесконечной длины) в P-ичной системе счисления для ∀ P≥2, P∈ℕ (это, надеюсь, очевидно). Значит, множество всех строк алфавита размерности ≥2 по меньшей мере не менее мощно, чем множество всех действительных чисел.
Множество всех строк алфавита размерности 1 очевидно равномощно множеству натуральных чисел, поскольку каждому элементу множества строк можно взаимно однозначно сопоставить натуральное число (количество символов в строке).
Множество действительных чисел несчётно, т.е. более мощно, чем множество натуральных чисел (см. диагональный аргумент Кантора).
Следовательно, множество всех строк алфавита размерности 1 менее мощно, чем множество всех строк алфавита размерности P, ∀ P≥2, P∈ℕ.
Q.e.d.
Так вы собираетесь доказывать своё утверждение?
Я могу доказать, что множество слов (не важно какой длины) на конечном алфавите счётно, а вы в состоянии доказать обратное?
Я могу доказать, что множество слов (не важно какой длины) на конечном алфавите счётно, а вы в состоянии доказать обратное?
Я немного разочарован. Математические доказательства не определяются результатом голосования.
Действительные числа в диапазоне [0; 1) можно рассматривать как слова бесконечной длины над алфавитом 0-9.
Вы готовы доказать что множество действительных чисел счетно?
PS да, я понимаю, что исходно звучало слово "неограниченной", а не "бесконечной". Но всем кроме вас очевидно что Welran и petropavel попросту перепутали эти два понятия. Или читали другие книги, где термины определяются немного иначе (к сожалению, такое частенько бывает).
Можно было бы просто написать об этом. Более того, ниже уже так и сделали. Зачем вы так упорно пытаетесь выбить ответ от пользователя, который не может вам ответить в силу отрицательной кармы?
Вы готовы доказать что множество действительных чисел счетно?
Нет, не готов. А Вы готовы доказать, что множество слов построенных на конечном алфавите взаимно однозначно отображается на множество действительных чисел?
Достаточно того факта, что любое действительное число из указанного интервала — это уже "слово" над алфавитом 0-9
Любое конечное представление действительного числа неограниченной длины (иными словами рациональное число), да. Но не иррациональное число (не имеющее конечного представления). Разница тонкая, да. Бесконечность — вообще коварная штука. Нельзя просто так взять число не имеющее конечного представления и запросто оперировать с ним как с элементом множества. Это прямой путь к парадоксам.
Обычно уточняют, что слово — последовательность конечной, но неограниченной длины (т.е. не берем расчет бесконечные строки, ведь множество бесконечных последовательностей, составленных конечным алфавитом, и правда не счетно). Тогда все просто: Сперва сортируем по алфавиту все слова длины 1, затем все слова длины 2 и т.д. Счетное объединение конечных множеств вполне себе счетно.
А, тогда да. Если конечной — то согласен. Но в тексте просто
Будем считать, там было написано «Рассмотрим класс строк конечной длины, состоящих из арабских цифр...»
Рассмотрим класс строк текста, состоящих из арабских цифр, переменных (букв латинского алфавита), принимающих натуральные значения, пробелов, знаков арифметических действий, равенства и неравенства, кванторов ∃ и ∀ и, быть может, каких-то ещё символовтак что было неоднозначно. Мне как-то не пришло в голову, что имеются в виду только строки конечной длины.
Будем считать, там было написано «Рассмотрим класс строк конечной длины, состоящих из арабских цифр...»
С точки зрения математика вы, конечно, правы. Хотя программист во мне не смог представить строку бесконечной длины:)
Вы просто не писали на Хаскеле.
string = 'a' : stringСтрока выше задает строку, состоящую из бесконечного числа символов 'a'.
И кто сказал, что она не элемент счётного множества?
При чем тут вообще множество? Я про строки и программирование говорил.
Вы правы в том, что из упорядоченности вовсе не следует счётность, но пример с континуумом некорректен: речь же в тексте идёт о словах КОНЕЧНОЙ (пусть и неограниченной) длины, а числа между 0 и 1 имеют в своей записи бесконечное число цифр после запятой (кроме счётного подмножества).
Насколько я понимаю, под «диагональным методом» вы понимаете доказательство того (не очевидного) факта, что множество рациональных чисел — счётно (при этом, вещественные числа, помимо рациональных, включает иррациональные, множество которых, как раз, континуально, таким образом и множество действительных чисел континуально, то есть не счётно). Доказательство счётности множества рациональных чисел было построено как раз на том, что их удалось упорядочить, раздав каждому из чисел порядковые номера. Множество слов, построенных на конечном алфавите также легко «пересчитать» подобным образом. Если считать буквы алфавита цифрами, произвольное слово будет представляться числом, записанным в системе счисления с основанием равным количеству букв в алфавите. Множество бесконечно, но при этом счётно. Прошу простить за капитанство.
Дополню. Множество действительных чисел упорядочено, но номер каждому действительному числу раздать не получится. Поскольку между двумя взятыми наугад различными действительными числами всегда найдётся хотя бы ещё одно действительное число.
А вот это как раз не «поскольку». Между двумя взятыми наугад различными рациональными числами тоже найдётся хотя бы ещё одно рациональное число. Однако же…
Главное здесь не то, что на рациональных числах задано отношение порядка. Оно никак не помогает пронумеровать рациональные числа! Именно потому, что между двумя рациональными числами тоже всегда найдётся хотя бы одно рациональное. Суть в том, что используя трюк с нумерацией рациональных чисел «змейкой» можно задать другое отношение порядка, уже позволяющее пронумеровать рациональные числа, поскольку в этом порядке между двумя соседними рациональными числами ещё одно число уже не втиснуть.
Кстати, меня смущает в змейковой нумерации рациональных чисел то, что некоторые числа там встречаются даже в начале подсчета по несколько раз (1/1, 2/2 и т.д.) — а во всем подсчете так и вообще бесконечное количество. Надо бы модифицировать эту нумерацию, пропуская сократимые дроби.
Зачем? Оттого, что есть повторы в нумерации, рациональных не может стать больше (а наоборот «меньше», раз некоторые выкидываются). Т. е. нумерация змейкой утверждает, что рациональных не больше чем натуральных. То что их не меньше, чем натуральных, очевидно.
Для эстетов есть последовательность Калкина — Уилфа.
Между двумя действительными числами всегда есть континуум действительных чисел. То есть не хотя бы одно. И между двумя рациональными числами бесконечное множество рациональных чисел — но по Кантору оно более «редкое». Там их опять можно пронумеровать. В обоих случаях любой отрезок числовой прямой, какой бы он ни был длины, и на множестве рациональных, и на множестве действительных чисел является однозначным отображением другого отрезка любой длины (в том числе бесконечно большой). Удивительное свойство, которое напрочь убивает воображение. Понять это можно, вообразить — нельзя. Как и можно понять разницу между действительными и рациональными числами — но она невообразима.
Наоборот, я имел в виду доказательство (тоже не очевидного) факта, что множество действительных чисел несчётно. Там было точно так же, как в посте — пусть оно счётно, выпишем все действительные числа от 0 до 1 по порядку, посмотрим на первую цифру первого числа, вторую цифру второго, и так далее. Построим новое число, где на n-й позиции будет 1, если у n-го действительного числа на n-й позиции 0, иначе там будет 0. Получается новое действительное число которое отличается от уже всех пронумерованных.
И всё, что мы таким образом можем выяснить — это то, что выражение содержащее самоотрицание не является высказыванием (то есть чем-то осмысленным). «Этот тезис ложен» — противоречивое выражение. Он не может быть ни истинным ни ложным, так как отрицает сам себя. Это бессмыслица. Аналогично и с «доказательством» Канотора — он определил число через самоотрицание, но из того, что такое число невозможно, сделал неправильные выводы: вместо того, чтобы понять, несостоятельность завуалированного высказывания «возьмём такое число из D, такое, что оно не равно любому числу из D», он решил, что «одно **бесконечное** множество может быть минимум на один элемент больше другого **бесконечного** множества». И понеслось…
Он не говорил "возьмём такое число из D, такое, что оно не равно любому числу из D", а конструктивно построил такое число.
Или вы из тех, кто считает закон исключенного третьего ересью?
**Завуалированно** сказал ровно это. Присмотритесь внимательнее:
1. Предположим, что мы пересчитали все числа из D.
2. Построим такое число d из D, что оно не равно каждому числу из (1). Например, «диагональным методом». Но метод тут может быть совершенно любой.
3. Если число d не равно ни одному числу из D, значит оно не входит в D, что противоречит исходному посылу (1).
4. Противоречие (3) говорит нам, что ошибка либо в исходном посыле (1), либо в определении числа d (2).
5. Кантор решил, что ошибка в (1) и пришёл к довольно глупому выводу: **бесконечное** множество D минимум на 1 элемент больше **бесконечного** множества N.
6. Почему-то никого не смущает, что число d определяется через самоотрицание. Так же как и «брадобрей d — это тот, кто бреет всех жителей деревни D, которые не бреют себя сами».
1. Предположим, что мы пересчитали все числа из D.
2. Построим такое число d из D, что оно не равно каждому числу из (1). Например, «диагональным методом». Но метод тут может быть совершенно любой.
3. Если число d не равно ни одному числу из D, значит оно не входит в D, что противоречит исходному посылу (1).
4. Противоречие (3) говорит нам, что ошибка либо в исходном посыле (1), либо в определении числа d (2).
5. Кантор решил, что ошибка в (1) и пришёл к довольно глупому выводу: **бесконечное** множество D минимум на 1 элемент больше **бесконечного** множества N.
6. Почему-то никого не смущает, что число d определяется через самоотрицание. Так же как и «брадобрей d — это тот, кто бреет всех жителей деревни D, которые не бреют себя сами».
> континуально, то есть не счётно
Строго говоря, «континуум» и «несчётно» — не синонимы. Континуум — это ведь не любое несчётное множество, а множество, равномощное множеству вещественных чисел. Но есть и более мощные несчётные множества.
Строго говоря, «континуум» и «несчётно» — не синонимы. Континуум — это ведь не любое несчётное множество, а множество, равномощное множеству вещественных чисел. Но есть и более мощные несчётные множества.
Кхм. Насколько я понимаю, имелся ввиду диагональный аргумент Кантора, доказывающий, во-первых существования несчётных множеств, во-вторых несчётности множества действительных чисел. https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
Что м-во рациональных чисел равномощно м-ву натуральных это из другой немного оперы.
Спасибо, хорошо читается.
Как понимаю арифметика непротиворичива, но неполна.
Так вот есть ли примеры истинных арифметических утверждений недоказуемых в рамках арифметики?
И доказуема ли их недоказуемость?
Так вот есть ли примеры истинных арифметических утверждений недоказуемых в рамках арифметики?
И доказуема ли их недоказуемость?
Вопросы хороши, но хороших ответов у меня нет. Возможно, копать нужно в сторону второй теоремы Гёделя.
НЛО прилетело и опубликовало эту надпись здесь
Конечно, такие теоремы довольно просто строить. Для примера — теорема Гудстейна.
Советую покурить вот это. Буквально прямой ответ на ваш вопрос.
Немного не успел)
Очевидно, что любой ФСП из F можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение.
Вообще-то только если в формуле нет неограниченных кванторов. Если формула имеет вид «exists x: f(x)», то максимум вы можете написать алгоритм, который будет говорить true если формула истинна и зависать иначе. А если в начале больше одного разнотипного квантора (например, «exists x: forall y: f(x, y)»), то и этого не можете. Это основа теориии алгоритмов.
Также, вы в начале алгоритмом называете что-то, что обязано завершаться. Предположим, что вы вправе в своем материале вводить свою терминологию, но всё-таки не стоит так делать. Алгоритм — это всё что можно накодить, в том числе бесконечные циклы и т. д. Обязаны завершаться, например, примитивно-рекурсивные функции, но они намного слабее алгоритмов.
Напоследок:
всякая ли функция над множеством высказываний вычислима? Как вы уже догадываетесь, ТГН утверждает, что нет, не всякая — существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.
У вас после «иными словами» идёт сравнительно правильная формулировка. А вот перед этим намного более простое утверждение, которое не имеет отношения к ТНГ и которое, кстати, относится к первой части моего комментария, иными словами, противоречит вашему утверждению, о том что каждой формуле можно сопоставить завершающийся алгоритм.
Прошу прощения, но данная статья это какая-то каша с кучей ошибок, про теорему Геделя можно прочитать на википедии, там же есть набросок доказательства. На английской поподробнее, а совсем подробно в книге Верещагина-Шеня.
Очевидно, что любой ФСП из F можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение.
Вообще-то только если в формуле нет неограниченных кванторов.
Нет. Подставляем в ФСП натуральное число, получаем высказывание, для которого, по предположению теоремы, всегда существует эквивалентный алгоритм.
У вас после «иными словами» идёт сравнительно правильная формулировка. А вот перед этим намного более простое утверждение, которое не имеет отношения к ТНГ
Какое? Вот это?
ТГН утверждает, что нет, не всякая — существуют невычислимые функции такого типа
А в чём ваши претензии?
Прошу прощения, но данная статья это какая-то каша с кучей ошибок, про теорему Геделя можно прочитать на википедии, там же есть набросок доказательства. На английской поподробнее, а совсем подробно в книге Верещагина-Шеня.
Не сомневаюсь, что ошибки и неточности есть, но надеюсь, что не «куча». Что касается Википедии и проч., то наличие N (хороших) текстов по предмету не является запретом для написания одного (допустим, не очень хорошего). Моей задачей было не привести строгое и исчерпывающее доказательство теоремы, а дать представление о таковом. Возможно, я с ней не справился.
Нет. Подставляем в ФСП натуральное число, получаем высказывание, для которого, по предположению теоремы, всегда существует эквивалентный алгоритм.
У вас не написано «предположим», у вас написано «очевидно». А дальше ложное утверждение.
ТГН утверждает, что нет, не всякая — существуют невычислимые функции такого типаА в чём ваши претензии?
В том, что ТНГ должно формулироваться как существование недоказуемой формулы в непротиворечивой арифметике. Утверждение выше это не ТНГ.
Некоторая вольность формулировок — цена за то, чтобы текст не был слишком тяжёл для чтения.Там ведь много где нужно делать оговорки. Впрочем, я сейчас попытался чуть подправить текст в соответствии с вашими замечаниями.
Это не вольность формулировок, а другая теорема. Если знаете английский, вот. Утверждение «существуют невычислимые функции такого типа (арифметические формулы с параметрами)», это частный, почти тривиальный, случай теоремы Поста (по ссылке как раз говорится, что вычислимыми такие функции будет только в том случае, если они не начинаются с кванторов).
ТГН о другом.
ТГН о другом.
ТНГ должно формулироваться как существование недоказуемой формулы в непротиворечивой арифметике.
Лично мне больше нравится такое определение — существование утверждения, не поддающегося полному описанию через его свойства, но лишь через исключение свойств, которые утверждению точно не соответствуют. Ну не люблю я слово *недоказуемая*.
То что вы говорите не похоже скорее на философию, а не на математику. Теорема Геделя это сложный математически стогий результат, с чёткими условиями выполнения, а не какой-то принцип или еще что-то. Может я не прав, но тогда формализуйте понятия «утверждение», «описание», «свойства», а то я не до конца понимаю, что они значат.
Действительно, это больше философский подход.
Наверняка меня заминусуют, но я все-же попробую.
Та-же теорема Гудстейна.(утверждение)
В рамках арифметики Пеано применим принцип матиндукции. пусть это будет *описание*
Свойства, которые по средствам матиндукции по началу применимы для описания данного утверждения в целом не полны.
Однако под описание отрицания принципа матиндукции свойства утверждения теоремы Гудстейна вполне себе подходят.
И да, оно не приведет к доказательству, однако исключит попытку пойти по ложному пути.
Как пример из реального мира — хотелось бы попробовать взять сознание. Но мне не нужна отрицательная карма. Это скользкая тема.
Наверняка меня заминусуют, но я все-же попробую.
Та-же теорема Гудстейна.(утверждение)
В рамках арифметики Пеано применим принцип матиндукции. пусть это будет *описание*
Свойства, которые по средствам матиндукции по началу применимы для описания данного утверждения в целом не полны.
Однако под описание отрицания принципа матиндукции свойства утверждения теоремы Гудстейна вполне себе подходят.
И да, оно не приведет к доказательству, однако исключит попытку пойти по ложному пути.
Как пример из реального мира — хотелось бы попробовать взять сознание. Но мне не нужна отрицательная карма. Это скользкая тема.
Прошу меня извинить. немного неточно выразился.
Свойства, которые по средствам матиндукции по началу применимы для описания данного утверждения в целом не полны. Скорее противоречивы
Однако под описание отрицания принципа матиндукции свойства утверждения теоремы Гудстейна вполне себе подходят. Однако вот здесь как раз они неполны.
Свойства, которые по средствам матиндукции по началу применимы для описания данного утверждения в целом не полны. Скорее противоречивы
Однако под описание отрицания принципа матиндукции свойства утверждения теоремы Гудстейна вполне себе подходят. Однако вот здесь как раз они неполны.
Пара вопросов.
1. Я иногда встречал такие суждения, что «такая-то теория одновременно непротиворечива и полна». Как я понимаю из подобных суждений, какие-то системы высказываний могут не попадать под теорему Геделя. Сам с этим не сталкивался, но можно привести примеры таких систем? И каков критерий того, что к данной системе высказываний будет применима теорема Геделя?
2. Читал, что метод геделевской нумерации применяется не только к доказательству данной теоремы, но и для решения многих задач по теории автоматов. Поэтому вопрос — где найти подробное (уровень — для чайников) описание, как применять геделевскую нумерацию к конкретным задачам?
1. Я иногда встречал такие суждения, что «такая-то теория одновременно непротиворечива и полна». Как я понимаю из подобных суждений, какие-то системы высказываний могут не попадать под теорему Геделя. Сам с этим не сталкивался, но можно привести примеры таких систем? И каков критерий того, что к данной системе высказываний будет применима теорема Геделя?
2. Читал, что метод геделевской нумерации применяется не только к доказательству данной теоремы, но и для решения многих задач по теории автоматов. Поэтому вопрос — где найти подробное (уровень — для чайников) описание, как применять геделевскую нумерацию к конкретным задачам?
Вырожденный случай полной непротиворечивой дедуктики описан в конце текста.
Что касается остальной части вопроса — то тут, увы, я не специалист. Быть может, комментаторы подтянутся?
Что касается остальной части вопроса — то тут, увы, я не специалист. Быть может, комментаторы подтянутся?
1. Теория должна описывать натуральные числа, сложение и умножение (естественным образом). Тогда применима теорема Геделя. Причина в том, что на натуральных числах со сложением и умножением можно эмулировать работу машин Тьюринга, т. е. записывать алгоритмы. Если выбросить из арифметики Пеано умножение, например, то она может быть станет полной и непротиворечивой (а может и нет, но похожую полную непротиворечивую точно можно придумать).
2. Верещагин, Шень «Лекции по математической логике и теории алгоритмов». Третья часть. Но это большая сложная книга. И строится на фундаменте первых двух частей, которые тоже большие сложные книги. Однако начинать читать можно без каких-либо знаний, все три части можно за полгода осилить разбираясь или в режиме «факты без доказательств» за пару недель.
2. Верещагин, Шень «Лекции по математической логике и теории алгоритмов». Третья часть. Но это большая сложная книга. И строится на фундаменте первых двух частей, которые тоже большие сложные книги. Однако начинать читать можно без каких-либо знаний, все три части можно за полгода осилить разбираясь или в режиме «факты без доказательств» за пару недель.
«Иными словами, не всякое верное высказывание можно доказать.»
— Дилетантский вопрос, как мы знаем, что высказывание верное, если мы это не можем проверить?
— Дилетантский вопрос, как мы знаем, что высказывание верное, если мы это не можем проверить?
Никак. Но истинность высказывания не зависит от того, знаем ли мы об этом.
Никак.
Скажем, высказывание вида «для любых x и y f(x,y)=0» может быть верным — f(x,y) ни для одной пары натуральных аргументов не отличается от нуля. Но доказать это — то есть свести высказывание к известным аксиомам, мы не можем.
Скажем, высказывание вида «для любых x и y f(x,y)=0» может быть верным — f(x,y) ни для одной пары натуральных аргументов не отличается от нуля. Но доказать это — то есть свести высказывание к известным аксиомам, мы не можем.
Существует такая замкнутая формула арифметики, что мы не можем доказать ни её ни её отрицание (средствами арифметики). А ведь хотя бы одна из них должна быть истинной. Вот и получается недоказуемая верная формула. Ну или же всё-таки арифметика противоречива и доказать можно всё что угодно.
> А ведь хотя бы одна из них должна быть истинной.
Докажите этот тезис. ;-)
Докажите этот тезис. ;-)
Да легко. Мое последнее предложение говорит об том, что я предполагаю непротиворечивость арифметики, то есть считаю, что наши привычные натуральные числа это её модель. А в модели любая замкнутая формула однозначным образом разбирается и оценивается. Каково бы ни было значение формулы, значение её отрицания противоположно (потому что при разборе (по определению модели) внешнее отрицание всегда будет применено последним).
Тут вы делаете предположение, что формула возвращает значение булевого типа. Довольно необоснованное предположение.
Это определение формулы. Термы возвращают элементы множества-носителя модели (числа), а термы связанные предикатами, логическими операторами и кванторами называются формулами. К термам понятие выводимости/доказуемости вообще неприменимо.
«Проверить» — не значит «доказать», Аксиомы арифметики и геометрии мы проверяем тем, что каждый раз применяя их, получаем верный результат. И верим (!), что и в следующий раз результат получится верный. А вот доказать не можем. Нет более простых понятий, из которых они складываются. А потому и не можем построить доказывающие их суждения.
Интересно, а в нашей вселенной возможно создание сверхтьюрингового компьютера и опровержение данной теоремы?
Математику не обманешь.
В строгом доказательстве Теоремы Гёделя не используется понятия машины тьюринга. Поэтому никакая "сверхтьюринговость" не поможет, чтобы это слово не означало.
в строгом доказательстве отсутствует оракул и получение результатов из будущего.
согласно ОТО есть получение результатов из будущего.
согласно квантовой механики есть оракул.
Если мир соответствовал бы классической механики, то вопросов бы не было.
согласно ОТО есть получение результатов из будущего.
согласно квантовой механики есть оракул.
Если мир соответствовал бы классической механики, то вопросов бы не было.
Во-первых, всевозможные оракулы и получения результатов из будущего не расширяют рамки возможностей машины Тьюринга. Это просто ускорители.
Во-вторых, доказательство не привязано ни к одной модели вычислений.
нет. с помощью получения информации из будущего можно пройти до бесконечности любую рекурсивную функцию.
Т.е. решить проблему останова со всеми вытекающими,
А доказательство неполноты основано на том, что мы не можем пройти рекурсивную функцию до бесконечности и получить однозначный ответ.
Т.е. решить проблему останова со всеми вытекающими,
А доказательство неполноты основано на том, что мы не можем пройти рекурсивную функцию до бесконечности и получить однозначный ответ.
Доказательство основано как минимум на теории множеств непротиворечивость которой не доказана.
Разве нет однозначного соответствия между decidability и computability?
Может я глупая картофелина, но подскажите пожалуйста, что нужно изучить, и чтобы понять эту статью? Я её прочёл, но ничего не понял, хотя автор заверил, что он сам не математик. За саму статью спасибо, хочу прочесть еще раз, когда начну понимать.
Я надеялся, что школьного курса достаточно, чтобы понять процентов 75 как минимум. Хотя, может быть, я слишком хорошо думаю о современной школе?
Если не прочтёте ещё раз, то понимание вряд ли придёт само.
хочу прочесть еще раз, когда начну понимать
Если не прочтёте ещё раз, то понимание вряд ли придёт само.
У меня знания математики до 9 класса. Никакой математической логики или дискретной математики мы не проходили, но у меня в планах их изучать, но даже курсы «для чайников» как-то слишком сложно даются, будто все вводящие книги или учебники сделаны так, что тебе необходимы объяснения специалистов, будто самому не осилить.
Погуглите что-нибудь типа [математическая логика для чайников].
Позвольте узнать, как вы читали статью? Как какую-нибудь новость, где читаешь и всё понятно? — для этого надо неплохо разбираться в математике и логике, чтобы так сходу прочесть и понять.
Вы перечитывали по 5-10 раз фразы, смысл которых не ясен? Медленно, слово за словом пытаясь понять что значит каждое слово, зачем оно в этом предложении и какой несёт смысл? Если нет, то попробуйте. Я именно так и читаю всякие определения и описания, если сходу не ясно, что там написано. Часть про «поверить на слово», вывод её и из неё я перечитал раз 5-7 и чувствую, что не до конца понял.
Ещё можно не читать какие-нибудь дополняющие и уточняющие обороты из предложений, чтобы понять общий смысл. Как будет понятен общий смысл можно читать предложения с уточняющими оборотами.
Так же можно читать информацию по ссылкам. Она тоже может помогать. Хотя математические статьи в вики могут гораздо сложнее. Но если по ходу чтения в них что-нибудь поймёте, вернувшись сюда вам будет проще. Пока будете читать что-то в вики и не понимать, открывайте ссылки на новые термины. Вот так прочитаете с десяток другой подобных статьей или сложнее. Вернётесь сюда и будет легче читать. Это такое неструктурированное изучение области))
С точки зрения терминов автор вроде прав, школьных знаний хватит. Хотя если вы не очень были в математике, не особо вникали в доказательства теорем, то может этого будет недостаточно.
Если не знаете, что значит термин — погуглите. Погуглите термины, которые автор объяснил кратко, может более полное определение поможет.
Вы перечитывали по 5-10 раз фразы, смысл которых не ясен? Медленно, слово за словом пытаясь понять что значит каждое слово, зачем оно в этом предложении и какой несёт смысл? Если нет, то попробуйте. Я именно так и читаю всякие определения и описания, если сходу не ясно, что там написано. Часть про «поверить на слово», вывод её и из неё я перечитал раз 5-7 и чувствую, что не до конца понял.
Ещё можно не читать какие-нибудь дополняющие и уточняющие обороты из предложений, чтобы понять общий смысл. Как будет понятен общий смысл можно читать предложения с уточняющими оборотами.
Так же можно читать информацию по ссылкам. Она тоже может помогать. Хотя математические статьи в вики могут гораздо сложнее. Но если по ходу чтения в них что-нибудь поймёте, вернувшись сюда вам будет проще. Пока будете читать что-то в вики и не понимать, открывайте ссылки на новые термины. Вот так прочитаете с десяток другой подобных статьей или сложнее. Вернётесь сюда и будет легче читать. Это такое неструктурированное изучение области))
С точки зрения терминов автор вроде прав, школьных знаний хватит. Хотя если вы не очень были в математике, не особо вникали в доказательства теорем, то может этого будет недостаточно.
Если не знаете, что значит термин — погуглите. Погуглите термины, которые автор объяснил кратко, может более полное определение поможет.
Где-то год назад я понимал в математике гораздо меньше. Хотя и сейчас остаюсь дилетантом, но теперь уже математические суждения меня не пугают. По крайней мере знаю, что можно найти более простое описание того же самого, что написано сложно. В общем, универсальный совет для желающих понимать математику — ищите для каждого встреченного материала более простое описание. Оно есть. Всегда. Хотя лопатить часто придется ох как много.
С формальной точки зрения теорема Гёделя не очень интересна, но из неё есть интересные следствия. Я бы даже сказал вольные философские умозаключения. Ну например, такое, не знаю, на сколько точно оно соответствует тому что стремился показать сам Гёдель, но тем не менее:
Теорема: Существует такая теорема которую нельзя ни доказать, ни опровергнуть.
Доказательство собственно в самой формулировке теоремы.
Теорема: Существует такая теорема которую нельзя ни доказать, ни опровергнуть.
Доказательство собственно в самой формулировке теоремы.
Краткий пересказ статьи: если язык логических высказываний достаточно сложный, чтобы на нем можно было описать любой алгоритм, переводящий число в истину/ложь, то в это языке существует парадоксальное высказывание.
Вопрос к тем, кто в отличие от меня знает математику…
Есть аксиоматика А (включающая аксиоматику Пеано, замкнутая для логики первого порядка, короче все условия для ТГН), согласно ТГН, в этой аксиоматике существует утверждение Р, которое в этой аксиоматике истинно, но недоказумо.
я беру обратное утверждение и строю аксиоматику А+~P
если аксиоматика А непротиворечива, то и новая аксиоматика непротиворечива, т.к. если бы она была противоречивой, это опровергало бы Р в А и приводило бы к противоречию с условиями. имеем две непротиворечивых аксиоматики, в одной Р — истинно, в другой — ложно.
вопрос такой. если Р истинно в аксиоматике А, может ли оно в принципе быть ложным в аксиоматике, включающей А в качестве подмножества? ну или где у меня ошибка в рассуждениях?
Есть аксиоматика А (включающая аксиоматику Пеано, замкнутая для логики первого порядка, короче все условия для ТГН), согласно ТГН, в этой аксиоматике существует утверждение Р, которое в этой аксиоматике истинно, но недоказумо.
я беру обратное утверждение и строю аксиоматику А+~P
если аксиоматика А непротиворечива, то и новая аксиоматика непротиворечива, т.к. если бы она была противоречивой, это опровергало бы Р в А и приводило бы к противоречию с условиями. имеем две непротиворечивых аксиоматики, в одной Р — истинно, в другой — ложно.
вопрос такой. если Р истинно в аксиоматике А, может ли оно в принципе быть ложным в аксиоматике, включающей А в качестве подмножества? ну или где у меня ошибка в рассуждениях?
Если брать тот вариант теоремы, который говорит про существование истинного, но недоказуемого P — то там отрицание P противоречит самому себе.
в этой аксиоматике существует утверждение Р, которое в этой аксиоматике истинно, но недоказумо
Не совсем, оно истинно «в реальности», а не в А. Если добавить отрицание P к A, то полученная аксиоматика снова будет непротиворечива, но она просто уже не будет описывать привычную нам арифметику, а какую-то другую.
Вы смешиваете аксиоматику и «реальный мир», обе аксиоматики не противоречивы и имеют право на жизнь. И противоречия никакого нет, так произошло с континуум-гипотезой, которую доказали, что она непротиворечива и появилась ZFC и альтернативная аксиоматика.
Если брать простой пример, то в геометрии параллельные прямые могут пересекаться, а могут не пересекаться и это 2 непротиворечивые геометрии, в реальном мире этот вопрос открытый.
Для теории чисел и для теоремы Ферма рассуждения о неполноте могут выглядеть так, мы знаем, что числа существуют и не существуют. Но если числа реально существуют и так как множество параметров счетное, то существует конечный вывод противоречия, значит Теорема Ферма может трактоваться только как: доказательство о несуществовании чисел может быть получено из аксиоматики Пеано (что до сих пор не известно) или не может быть получено (или в крайнем случае существуют такие числа — как оказалось, нет).
Если брать простой пример, то в геометрии параллельные прямые могут пересекаться, а могут не пересекаться и это 2 непротиворечивые геометрии, в реальном мире этот вопрос открытый.
Для теории чисел и для теоремы Ферма рассуждения о неполноте могут выглядеть так, мы знаем, что числа существуют и не существуют. Но если числа реально существуют и так как множество параметров счетное, то существует конечный вывод противоречия, значит Теорема Ферма может трактоваться только как: доказательство о несуществовании чисел может быть получено из аксиоматики Пеано (что до сих пор не известно) или не может быть получено (или в крайнем случае существуют такие числа — как оказалось, нет).
А нельзя ли узнать, почему, собственно, количество аксиом обязано быть конечным?
Действительно, если исходить из идеи о первичности идей над реальностью, то в идеале никаких аксиом быть вообще не должно — всё должно быть доказуемо из самого себя, либо из одного-единственного «базового» положения (в рамках религиозного мышления это должно быть что-то вроде «бог есть», хотя возможны варианты).
Однако если исходить из идеи первичности реальности над идеями, то бишь, что все идеи есть лишь свойство объективной реальности или, в случае, если мы говорим о нашем мышлении, результат анализа данных, поступающих из реальности, то никакого отторжения идея бесконечности числа аксиом вообще не вызывает. Есть аксиомы арифметики, геометрии, физики, других естественных наук, и кроме арифметики и геометрии, обычно сложно даже представить число этих аксиом. Можно ли у бесконечного мира найти конечное число свойств, если мы говорим о физике (царице естественных наук)?
В целом, я в ТГН вижу лишь «мягкое» доказательство двух вещей: 1) первичности материального над идеальным (мир вовсе не устроен «идеально»); 2) бесконечности верных недоказуемых утверждений, являющихся отправными точками для доказательства или опровержения других утверждений, то есть аксиом.
Хотя, конечно, я не изучал вопрос глубоко.
Действительно, если исходить из идеи о первичности идей над реальностью, то в идеале никаких аксиом быть вообще не должно — всё должно быть доказуемо из самого себя, либо из одного-единственного «базового» положения (в рамках религиозного мышления это должно быть что-то вроде «бог есть», хотя возможны варианты).
Однако если исходить из идеи первичности реальности над идеями, то бишь, что все идеи есть лишь свойство объективной реальности или, в случае, если мы говорим о нашем мышлении, результат анализа данных, поступающих из реальности, то никакого отторжения идея бесконечности числа аксиом вообще не вызывает. Есть аксиомы арифметики, геометрии, физики, других естественных наук, и кроме арифметики и геометрии, обычно сложно даже представить число этих аксиом. Можно ли у бесконечного мира найти конечное число свойств, если мы говорим о физике (царице естественных наук)?
В целом, я в ТГН вижу лишь «мягкое» доказательство двух вещей: 1) первичности материального над идеальным (мир вовсе не устроен «идеально»); 2) бесконечности верных недоказуемых утверждений, являющихся отправными точками для доказательства или опровержения других утверждений, то есть аксиом.
Хотя, конечно, я не изучал вопрос глубоко.
А нельзя ли узнать, почему, собственно, количество аксиом обязано быть конечным?
Из приведённого наброска доказательства следует, что дело не в конечности числа аксиом, а в том, что даже бесконечным числом аксиом вы не превратите дедуктику в полную непротиворечивую.
Немножко в сторону от темы. ТГН утверждает, что ‘'в достаточно сложных языках существуют недоказуемые высказывания”. А есть такая теорема, которая доказывает, что существуют доказуемые высказывания? Для меня это гораздо менне очевидное, чем утверждение Гёделя.
Вот вы пишите: «Доказать её можно, тождественно преобразуя… Переход от одной формулы к другой происходит по некоторым известным правилам…”. Ниоткуда не следует, что некие “известные” правила будут существовать в любом случае.
Вот вы пишите: «Доказать её можно, тождественно преобразуя… Переход от одной формулы к другой происходит по некоторым известным правилам…”. Ниоткуда не следует, что некие “известные” правила будут существовать в любом случае.
Для любой системы с пустым набором аксиом не существует доказуемых высказываний, это очевидно. Точно так же очевидно, что для любой системы с непустым набором аксиом существует хотя бы столько же доказуемых высказываний сколько в ней аксиом.
Это само-собой. С аксиомами понятно. Но как быть с остальными преобразованиями, которые делаются до аксиом (в вашем примере 1,2, и 3)? Мой вопрос — есть ли формальное определения существования таких утверждений истинность которых можно доказать при помощи последовательности преобразований, каждое из которых поддержано аксиомой?
С другой стороны почему вообще надо было ожидать, что конечное число
аксиом позволит описывать бесконечное многообразие возможных
предложений? Просто, imho, начиная с Греков и кончая Гильбертом
математики очень хотели, чтобы подобное было возможным. Вот это желание и
привычка к нему были настолько сильными, что опровержение созданное
Геделем произвело эффект ядерной бомбы, что до сих пор переживается.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Теорема Гёделя о неполноте за 20 минут