2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Теорема Геделя о неполноте
Сообщение20.12.2014, 21:53 
Заслуженный участник
Аватара пользователя


20/08/14
8062
Назовем алфавитом языка арифметики алфавит, состоящий из:
1) десятичных цифр для записи натуральных чисел
2) символа $x$ и нижнего индекса для записи переменных (различные переменные, входящие в одно и то же выражение, можно обозначать $x_1$, $x_2$, ...).
3) знаков арифметических операций $+$, $\times$
4) скобок и знака равенства $=$
5) знаков логических операций "и", "или", "не", кванторов существования $\exists$ и всеобщности $\forall$.

Конечный упорядоченный набор символов языка арифметики назовем фразой языка арифметики.
Существует класс фраз, называемых суждениями. Его можно определить, определив индуктивно сначала терм, затем формулу, а уж затем - суждение как формулу без свободных параметров, но мне кажется, здесь это излишне. Понятие суждения в языке арифметике вполне совпадает с этим же понятием в логике. Например, $4 = 2 + 2$, $\forall x_1 \exists x_2 x_2 = x_1 + 1$ - суждения. На языке арифметики можно записать как вполне тривиальные суждения ("шесть делится на три"), так и очень нетривиальные (теорема Лагранжа - "всякое натуральное число представимо в виде суммы не более чем четырех квадратов натуральных чисел"), в том числе недоказанные (гипотеза Гольдбаха).

Теорема Геделя о неполноте утверждает:
Не существует алгоритма, который для каждого суждения языка арифметики определяет, истинно оно или ложно.

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

Вопрос:
Существует ли суждение языка арифметики, для которого ни один алгоритм не определяет, истинно оно или ложно?
Конечно, такая формулировка неудачна. Всегда можно взять два алгоритма, один из которых всегда печатает "оно ложно", а другой "оно истинно", и сказать, что уж один-то из этих алгоритмов истинность/ложность утверждения определяет. Я не об этом. Не знаю, как сформулировать корректнее. Приведу пример. Похожая теорема доказывается для алгоритмов: "не существует алгоритма, которых для всякого алгоритма $A$ и всяких входных данных $\alpha$ определял бы, остановится ли этот алгоритм при этих входных данных". Затем строится универсальный алгоритм $U(n, \alpha)$, который для каждой пары $(n, \alpha)$ реализует алгоритм $A_n (\alpha)$, где $n$ - номер алгоритма $A_n$ в эффективной нумерации всех алгоритмов. Получается, что для универсального алгоритма $U(n, \alpha)$ не существует алгоритма, который для любого $(n, \alpha)$ определял бы, остановится ли $U(n, \alpha)$ или нет.
Существует ли в языке арифметики "универсальное суждение", на проблеме истинности которого любой алгоритм споткнется так же, как на проблеме остановки универсального алгоритма?
Тут, конечно, есть разница. Универсальный алгоритм может принимать различные (да фактически любые) входные данные, и неразрешимость проблемы его остановки формулируется именно как "не существует алгоритма, который для любого $(n, \alpha)$ определял бы, остановится ли $U(n, \alpha)$ или нет". Суждение же свободных параметров не содержит. И все-таки мне кажется, что какое-то такое "алгоритмически недоказуемое и неопровержимое суждение" должно существовать.

Или мне кажется?

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение21.12.2014, 00:58 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Ну, если искать что-то аналогичное универсальной машине, то существует формула $U(x)$ с одной свободной переменной, для которой не существует алгоритма, который по натуральному числу $n$ определяет, истинно ли суждение $U(n)$.

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение21.12.2014, 01:15 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Что-то тут не то. Anton_Peplov, Вы точно знаете, что в теореме Гёделя речь идёт об истинности? Ничего, что истинность суждения зависит от модели? Ведь в вашей постановки никакая модель не предполагается.

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение23.12.2014, 14:02 
Заслуженный участник
Аватара пользователя


20/08/14
8062
Someone в сообщении #950172 писал(а):
Вы точно знаете, что а теореме Гёделя речь идёт об истинности?


Существует синтаксическая и семантическая формулировка теоремы Геделя о неполноте. Я привел семантическую. В синтаксической понятие истинности не используется, но я с ней не знаком.

Доказательство данной формулировки теоремы Геделя базируется на понятии арифметического множества. Множество натуральных чисел $M$ называется арифметическим, если существует такая формула языка арифметики $U(x)$ с одной свободной переменной $x$, что для всякого $n \in M$ суждение $U(n)$ истинно.
Доказывается, что:
а) всякое перечислимое множество арифметично (доказательство долгое и сложное)
б) дополнение арифметического множества до всего натурального ряда арифметично

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

Конечно, использованное здесь понятие "истинности" должно опираться на некоторую символическую логику, но Успенский эту логику не обсуждает.

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение23.12.2014, 14:30 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
И всё-таки: не спутали ли Вы невыводимость с истинностью?

Anton_Peplov в сообщении #950085 писал(а):
Не знаю, как сформулировать корректнее.
А если посмотреть в учебнике?

Anton_Peplov в сообщении #950085 писал(а):
И все-таки мне кажется, что какое-то такое "алгоритмически недоказуемое и неопровержимое суждение" должно существовать.
Это усиливает мои подозрения, что Вы в самом деле спутали истинность и выводимость. А примеры утверждений, которые в арифметике Пеано недоказуемы и неопровержимы (причём, без всяких упоминаний об алгоритмах), известны. Например, теорема Гудстейна. Кстати, истинность таких утверждений зависит от модели. Например, теорема Гудстейна истинна в так называемой "стандартной" модели, но может быть ложной в "нестандартной" модели (и такую "нестандартную" модель арифметики Пеано можно построить).

Но если речь идёт о теоремах Гёделя, то там рассматриваются вполне "конкретные" высказывания.

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение23.12.2014, 15:04 
Заслуженный участник
Аватара пользователя


20/08/14
8062
Someone в сообщении #951174 писал(а):
А если посмотреть в учебнике?


Порекомендуйте учебник.

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение23.12.2014, 23:04 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
С. К. Клини. Математическая логика. "Мир", Москва, 1973.
П. Дж. Коэн. Теория множеств и континуум-гипотеза. "Мир", Москва, 1969. (Это не учебник.)

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение31.12.2018, 21:17 


26/12/18
155
Присоединение Гёделева недоказуемого предложения "я недоказуемо" к аксиомам арифметики (Пеано) естественно, поскольку оно представляется "очевидно верным", хоть и вычурным и не очень интересным арифметическим фактом; на неформальном, интуитивном уровне оно будет "доказуемым" по построению, хоть и построено было (Гёделем) с целью остаться именно формально недоказуемым.

А вот в чём будут значение/смысл присоединения к арифметике отрицания (поскольку в равной степени невыводимого) Гёделева предложения, то бишь присоединения "заведомо неверного" арифметического предложения наподобие, скажем, 2+2=5? Какая будет польза от полученной нестандартной, насколько могу судить, модели?

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение31.12.2018, 21:27 
Заслуженный участник


02/08/11
6874
Anton_Peplov в сообщении #951165 писал(а):
конечно, использованное здесь понятие "истинности" должно опираться на некоторую символическую логику
Наоборот же. Истинность требует только задания семантики (модели) и больше ничего. А вот как раз для выводимости нужны логические правила вывода. А ещё вы определили алфавит, но совсем не упомянули аксиомы (логики и арифметики) - они нужны и для семантики и для синтаксиса.

(Я же всё правильно сказал, да?)

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение01.01.2019, 00:19 
Заслуженный участник
Аватара пользователя


11/12/05
9953
warlock66613 в сообщении #1365159 писал(а):
(Я же всё правильно сказал, да?)
(Верно, только поздновато, года на 4.)

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение01.01.2019, 11:13 
Заслуженный участник
Аватара пользователя


20/08/14
8062
Dan B-Yallay в сообщении #1365177 писал(а):
(Верно, только поздновато, года на 4.)
И на проработанный мною учебник по предмету, после которого я уже разобрался в вопросе.

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

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение03.01.2019, 09:45 


26/12/18
155
Sycamore в сообщении #1365158 писал(а):
Присоединение Гёделева недоказуемого предложения "я недоказуемо" к аксиомам арифметики (Пеано) естественно, поскольку оно представляется "очевидно верным", хоть и вычурным и не очень интересным арифметическим фактом; на неформальном, интуитивном уровне оно будет "доказуемым" по построению, хоть и построено было (Гёделем) с целью остаться именно формально недоказуемым.

А вот в чём будут значение/смысл присоединения к арифметике отрицания (поскольку в равной степени невыводимого) Гёделева предложения, то бишь присоединения "заведомо неверного" арифметического предложения наподобие, скажем, 2+2=5? Какая будет польза от полученной нестандартной, насколько могу судить, модели?

Сообщение сверху скорее неудачно отражает следующий вопрос о напрашивающемся различии между как-бы двумя классами аксиоматически/формально недоказуемых предложений. С одной стороны, это класс оригинальных Гёделевых предложений "я недоказуемо", арифметических теорем Рамсея (результат Пэриса - Харрингтона, https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BD%D0%B0) и Гудстейна, диофантова примера неполноты вслед за Матиясевичем (https://ru.wikipedia.org/wiki/%D0%A2%D0 ... 0%BC%D0%B0) и других подобных, видимо "истинных/доказанных" на экспертном, хоть и неформальном, уровне предложений.

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

Напрашивается различие с первым классом: вроде никому не интересно рассматривать непротиворечивые альтернативы недоказуемым предложениям из первого класса; обозвали такие модели "нестандартными" и ... забыли, даже можно понять почему: их интуитивная "ошибочность" напрашивается...

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение03.01.2019, 11:34 
Заслуженный участник


02/08/11
6874
Аксиома выбора относится скорее к первому классу. Возьмите например такую её формулировку: "декартово произведение непустого множества непустых множеств - непусто". Таким образом, ваш первый класс - это просто то, что доказуемо в ZFC.

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение03.01.2019, 14:00 


26/12/18
155
Не встречал такой "непустой" редакции аксиомы выбора...)

Любое расширение (вкл. ZFC) арифметики Пеано будет неполным, потому исчерпать нашего первого класса не удаётся: в ZFC наверняка найдутся Гёделево "я недоказуемо" и диофантово уравнение с недоказуемым отсутствием решений, про Рамсея с Гудстейном не уверен.

 Профиль  
                  
 
 Re: Теорема Геделя о неполноте
Сообщение03.01.2019, 18:25 
Заслуженный участник
Аватара пользователя


16/07/14
8347
Цюрих
А можно взять такую формулировку: "в любой игре без случайности и с полной информацией у одного из игроков есть выигрышная стратегия". Это не относит аксиому детерменированности к первому классу?

"Доказанные на экспертном уровне арифметические утверждения" - это, скорее всего, именно доказанные в ZF (даже аксиома выбора не нужна - арифметические утверждения, доказуемые в ZFC, доказуемы и в ZF).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group