Г. Б. Шабат Теорема Гёделя о неполноте (по Ю. В. Матиясевичу) Мы приведём способ построения истинного, но недоказуемого утверждения



Скачать 21.55 Kb.
Дата27.04.2018
Размер21.55 Kb.
ТипИзложение

15.02.2011

Г.Б. Шабат

Теорема Гёделя о неполноте (по Ю.В. Матиясевичу)
Мы приведём способ построения истинного, но недоказуемого утверждения.

Это утверждение будет о диофантовом уравнении – т.е. речь идёт о содержательной математике, а не о чисто логической «игре».

Речь идёт о результате Юрия Матиясевича (1970). Он изложен в его книге «Десятая проблема Гильберта», М., Наука, 1993. Популярное изложение см. Ф.П. Варлаховский, А.Н. Колмогоров. «О решении десятой проблемы Гильберта». "Квант" №7, 1970. Сс. 39-44. (http://kolmogorov.pms.ru/kvant-o_reshenii_desyatoj_problemy_gilberta.html)
В дальнейшем тексте все числа целые.
Основной результат Матиясевича, который мы будем использовать без доказательства, таков:
Основная теорема. Перечислимость множества влечёт его диофантовость.
Поясним термины.
Определение 1. Множество K называется перечислимым, если существует правило, позволяющее получать одно за другим числа данного множества (и только их) так, что любое число из множества K будет получено.
Упражнение 1. Докажите, что перечислимы множества а) чётных чисел, б) чисел Фибоначчи, в) простых чисел.
Определение 2. Множество D называется диофантовым, если существует такой многочлен , что .
Пример. Множество чисел a, кратных данному числу c, является диофантовым, так как многочлен a - cx имеет корни в том и только в том случае, если а кратно с.
Основная идея восходит к парадоксу лжеца. Мы построим теорему, которая будет утверждать: «Я недоказуема».
Рассмотрим множество всех многочленов P от параметра a и набора переменных x1, x2, x3, …
Упражнение 2. Как занумеровать все многочлены с произвольным числом переменных?
Предположим, что существует алгоритм, позволяющий за конечное число шагов выяснять, существует ли решение у данного диофантова уравнения. Будем называть это свойство уравнения выводимостью.

Тогда множество (a, n) таких, что , перечислимо.

По основной теореме, это множество является и диофантовым, т.е. существует такой многочлен , что для каждой пары (a, n), для которой Pn не имеет решений (и только для них), уравнение = 0 имеет решение.
Обозначив выводимость уравнения знаком |=, запишем последнее утверждение в символьной форме:

.

Теперь положим n=a («диагональное» рассуждение Кантора). Получим:



.

Выберем в качестве многочлен . Имеем:



.

То есть выводимость неразрешимости уравнения оказалась равносильна его разрешимости.


(Матиясевичу удалось построить такой многочлен, он имеет 13-ю степень.)

Итак, перед нами альтернатива:



  1. У многочлена P есть корни. Тогда можно доказать, что их нет, и математика противоречива.

  2. У многочлена P нет корней. Тогда этого доказать нельзя, т.е. существуют истинные, но недоказуемые утверждения.

Заметим, что выбор между этими двумя возможностями не следует из самой теории, а является делом веры.
Каталог: nir
nir -> Род племя народность народ нация
nir -> Студенческая научно-практическая конференция
nir -> Отчет научно-исследовательской работы " Анализ системы управления персоналом в органах государственного (муниципального) управления "
nir -> Национализм
nir -> Исследование показателей психологического благополучия пациентов госпиталя ВОВ
nir -> Неонатальная империя — под неонатальной, то есть «младенческой империей»
nir -> Идентичность
nir -> Наглядность в компьютерном обучении физике


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©znate.ru 2017
обратиться к администрации

    Главная страница