2014 dxdy logo

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

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


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


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

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

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

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

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



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


20/08/14
5557
Назовем алфавитом языка арифметики алфавит, состоящий из:
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
6014
Ну, если искать что-то аналогичное универсальной машине, то существует формула $U(x)$ с одной свободной переменной, для которой не существует алгоритма, который по натуральному числу $n$ определяет, истинно ли суждение $U(n)$.

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


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

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


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


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

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

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

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

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


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

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

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

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

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


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


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

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


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

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


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

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