Как называется теорема без доказательств

Что такое аксиома, теорема и доказательство теоремы

Понятие аксиомы

Аксиома — это правило, которое считают верным и которое не нужно доказывать. В переводе с греческого «аксиома» значит принятое положение — то есть взяли и договорились, что это истина, с которой не поспоришь.

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

Синоним аксиомы — постулат. Антоним — гипотеза.

Основные аксиомы евклидовой геометрии

Учить наизусть эти аксиомы не обязательно. Главное — помнить о них и держать под рукой, чтобы при доказательстве теоремы сослаться на одну из них.

А теперь давайте рассмотрим несколько аксиом из геометрии за 7 и 8 класс.

Самая известная аксиома Евклида — аксиома о параллельных прямых. Звучит она так:

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

У этой аксиомы два следствия:

Аксиома Архимеда заключается в том, что, если отложить достаточное число раз меньший из двух отрезков, то можно покрыть больший из них. Звучит так:

Если на прямой есть меньший отрезок А и больший отрезок B, то, можно сложить А достаточное количество раз, чтобы покрыть B.

На картинке можно увидеть, как это выглядит:

Из этого следует, что не существует бесконечно малых и бесконечно больших величин. В качестве математической формулы аксиому можно записать так: А + А + … + А = А * n > В, где n — это натуральное число.

Понятие теоремы

Что такое аксиома мы уже поняли, теперь узнаем определение теоремы.

Теорема — логическое следствие аксиом. Это утверждение, которое основано на аксиомах и общепринятых утверждениях, которые были доказаны ранее, и доказывается на их основе.

Состав теоремы: условие и заключение или следствие.

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

Лемма — это вспомогательная теорема, с помощью которой доказываются другие теоремы. Пример леммы: если одна из двух параллельных прямых пересекает плоскость, то и вторая прямая тоже пересекает эту плоскость.

Следствие — утверждение, которое выводится из аксиомы или теоремы. Следствие, как и теорему, необходимо доказывать.

Примеры следствий из аксиомы о параллельности прямых:

Доказательство теоремы — это процесс обоснования истинности утверждения.

Каждая доказанная теорема служит основанием доказательства для следующей теоремы. Именно поэтому так важно изучать геометрию последовательно, переходя от аксиом к теоремам.

Способы доказательства геометрических теорем

Часть аналитического способа — доказательство от противного, когда для доказательства данного предложения убеждают в невозможности предположения противоположного.

Приемы для доказательства в геометрии:

Обратная теорема — это такой перевертыш: в ней условие исходной теоремы дано заключением, а заключение — условием.

Прямая и обратная теорема взаимно-обратные. Например:

В первой теореме данное условие — это равенство сторон треугольника, а заключение — равенство противолежащих углов. А во второй всё наоборот.

Противоположная теорема — это утверждение, в котором из отрицания условия вытекает отрицание заключения.

Вот, как выглядит взаимное отношение теорем на примере:

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

Для тех, кто хочет связать свою жизнь с точными науками, Skysmart предлагает курс подготовки к ЕГЭ по математике (профиль).

Теоремы без доказательств

Теорема Пифагора: квадрат гипотенузы равен сумме квадратов катетов.

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

Теорема косинусов: квадрат одной стороны треугольника равен сумме квадратов двух других сторон минус удвоенное произведение этих сторон на косинус угла между ними. В виде формулы это выглядит так:

где a, b и c — стороны плоского треугольника,

α — угол, противолежащий стороне а.

Следствия из теоремы косинусов:

Понятия свойств и признаков

У нас есть список аксиом и мы уже знаем, что такое теорема и как ее доказывать. Есть два типа утверждений среди теорем, которые часто встречаются при изучении новых фигур: свойства и признаки.

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

Свойство — такое утверждение, которое должно выполняться для данного типа объектов. У ноутбука есть клавиатура — это свойство есть у каждого ноутбука. А у электронной книги такого свойства нет.

Примеры геометрических свойств мы уже знаем: у квадрата все стороны равны. Это верно для любого квадрата, поэтому это — свойство.

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

Признак — это то, по чему мы однозначно распознаем объект.

Звезды в темном небе — признак того, что сейчас ночь. Если человек ходит с открытым зонтом — это признак того, что сейчас идет дождь. При этом ночью не обязательно должны быть видны звезды, иногда может быть облачно. Значит это не свойство ночи.

А теперь вернемся к геометрии и рассмотрим четырехугольник ABCD, в котором AB = BD = 10 см.

Является ли равенство диагоналей признаком прямоугольника? У такого четырехугольника, где AB = BD, диагонали равны, но он не является прямоугольником. Это свойство, но не его признак.

Но если в четырехугольнике противоположные стороны параллельны AB || DC и AD || BC и диагонали равны AB = BD, то это уже верный признак прямоугольника. Смотрите рисунок:

Иногда свойство и признак могут быть эквивалентны. Лужи — это верный признак дождя. У других природных явлений не бывает луж. Но если приходит дождь, то лужи на асфальте точно будут. Значит, лужи — это не только признак, но и свойство дождя.

Такие утверждения называют необходимым и достаточным признаком.

Источник

Доказывают ли изначально аксиомы, чтобы потом принимать их на веру?

В википедии прочитал, что

Аксио́ма (др.-греч. ἀξίωμα — утверждение, положение) или постула́т — исходное положение какой-либо теории, принимаемое в рамках данной теории истинным без требования доказательства и используемое при доказательстве других её положений, которые, в свою очередь, называются теоремами[1].

Необходимость в принятии аксиом без доказательств следует из индуктивного соображения: любое доказательство вынуждено опираться на какие-либо утверждения, и если для каждого из них требовать своих доказательств, цепочка получится бесконечной. Чтобы не уходить в бесконечность, нужно где-то эту цепочку разорвать — то есть какие-то утверждения принять без доказательств, как исходные. Именно такие, принятые в качестве исходных, утверждения и называются аксиомами[2].

Вот появилась у Евклида идея, он потестил ее, смотрит, всегда сходится, и потом заявляет, что это Аксиома? А как же доказательство?

Извиняюсь, за глупые вопросы, но, все же интересно стало, как это так получается.

Нет, все именно так, как написано в вики.
Более того может быть несколько различных наборов аксиом (см. геометрия Лобачевского), которые приводят к разным результатам. Но они все правильные и подходят для разных случаев.

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

Аксиомы доказать невозможно. Но можно сделать одну классную вещь. А именно — построить модель теории. Другими словами: найти в соседней теории, которой вы «доверяете» (например, теории действительных чисел или евклидовой геометрии) такие «точки» и «прямые», чтобы они отвечали всем аксиомам. И эти аксиомы нужно доказывать, чтобы показать, что, например, R² с «точками» (x,y) и «прямыми» ax+by+c=0 — действительно модель евклидовой геометрии.

Да, и математики часто, но некорректно говорят: «Векторное пространство — это совокупность из основного множества X, числового поля K, операций x+y и x·k такая, что отвечает аксиомам…» Вообще-то, требованиям, а не аксиомам, и эти «аксиомы» нужно доказывать, чтобы доказать, что, например, R² — векторное пространство над полем R.

Да, а что же Евклид? А Евклид, вероятно, сам не догадывался, какую классную штуку он придумал. К тому же исчерпывающую аксиоматику евклидовой геометрии придумали ≈1900. Страшна, как чёрт, шесть базовых понятий… Но это зачастую и не требуется, чтобы решать задачи — надо как-то определить объект изучения и начать доказывать теорему за теоремой. Большинство из нас, даже выпускники вуза, не знают ни теорию действительного числа, ни аксиоматику Пеано для арифметики, ни аксиоматику для теории множеств…

Необходимость в принятии аксиом без доказательств следует из индуктивного соображения: любое доказательство вынуждено опираться на какие-либо утверждения, и если для каждого из них требовать своих доказательств, цепочка получится бесконечной. Чтобы не уходить в бесконечность, нужно где-то эту цепочку разорвать — то есть какие-то утверждения принять без доказательств, как исходные.

Источник

Как называется теорема без доказательств

Чем теорема отличается от аксиомы? И мне вопросик теорема вопросик аксиома

Теоре́ма (др.-греч. θεώρημα — «зрелище, вид; взгляд; представление, положение») — утверждение, для которого в рассматриваемой теории существует доказательство (иначе говоря, вывод). В отличие от теорем, аксиомами называются утверждения, которые в рамках конкретной теории принимаются истинными без всяких доказательств или обоснований.

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

Аксио́ма (др.-греч. ἀξίωμα — утверждение, положение), постула́т — исходное положение какой-либо теории, не доказываемое в рамках данной теории и лежащее в основе доказательства других ее положений.[1] В современной науке аксиомы — это те положения теории, которые принимаются за исходные, причём вопрос об истинности решается либо в рамках других научных теорий, либо посредством интерпретации данной теории.[1] Аксиоматиза́ция теории — явное указание конечного или счётного, рекурсивно перечислимого (как, например, в аксиоматике Пеано) набора аксиом и правил вывода. После того как даны названия изучаемым объектам и их основным отношениям, а также аксиомы, которым эти отношения должны подчиняться, всё дальнейшее изложение должно основываться исключительно лишь на этих аксиомах, не опираясь на обычное конкретное значение этих объектов и их отношений. Утверждения на основе аксиом называются теоремами. С формальной точки зрения, сами аксиомы также входят в число теорем. Примеры различных, но равносильных наборов аксиом можно встретить в математической логике и Евклидовой геометрии. Набор аксиом называется непротиворечивым, если из аксиом набора, пользуясь правилами логики, нельзя прийти к противоречию, то есть доказать одновременно и некое утверждение, и его отрицание. Аксиомы являются своего рода «точками отсчёта» для построения теорий в любой науке, при этом сами они не доказываются, а выводятся непосредственно из эмпирического наблюдения (опыта) или обосновываются в более глубокой теории. Австрийский математик Курт Гёдель доказал «теоремы о неполноте», согласно которым всякая система математических аксиом (формальная система) начиная с определённого уровня сложности либо внутренне противоречива, либо неполна (то есть в достаточно сложных системах найдётся хотя бы одно высказывание, истинность и ложность которого не может быть доказана средствами самой этой системы).[2]

Прочитайте и сами сделайте вывод

Юлия Сергеевна, я точно не помню. Там чего-то без доказательств, а к чему-то доказательство нужно. Или там где-то что-то однозначно, а что-то под сомнение ставится.

Если коротко,то. Теорема-утверждение,для которого требуется доказательство.Оксиома-не требует доказательства.

Аксиома принимается без доказательств, а теорему устанешь доказывать

Аксиома, в отличие то теоремы, не требует доказательств

Источник

О теоремах, данных без доказательств

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

Однажды для меня стало большим откровением, что в обычных школах некоторые теоремы и формулы давались без доказательства. То есть, людям просто говорили, что есть теорема Фалеса, а есть — формула Герона. А потом сразу давали задачи, которые можно было решить с их использованием. Это для меня было абсолютным разрывом мозга. Это не укладывалось в голове. Я совершенно не мог понять, какой смысл в том, чтобы проходить формулу, не выводя её — это же тогда просто бессмысленный набор букв и знаков. Ну или максимум «занимательный факт»: британские учёные выяснили, что.

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

Позже в университете для некоторых моих одногруппников казалось странной необходимость доказывать теоремы или выводить формулы. По школьной привычке учить формулы наизусть эти люди учили наизусть и вывод формул, не понимая, что там происходит. При этом многие из них благодаря прилежности хорошо писали контрольные; боялись же они экзамена. У меня история была обратная: всегда было очень трудно попасть на экзамен, потому, что для этого надо было сдать зачёт, а чтобы допуститься на него, нужно было написать все контрольные в семестре. Терпения же и внимательности на решение практических задачек всегда не хватало.

Экзамены по математике в университете я сдавал на 4, 4, 4 и 5 (в четвёртом семестре была теория функции комплексного переменного, которую я обожаю).

Каждый раз, когда я сдавал листочек с ответами Олегу Геннадьевичу, напротив большинства пунктов задания он ставил минус. Потом, когда он вызывал меня отвечать, он спрашивал: почему не решили эту задачу? Я говорил: забыл формулу такую-то и откуда она берётся. Он говорил: ну, а если бы знали формулу, что бы делали? Я отвечал: нашёл бы то-то, подставил бы в формулу, выразил бы это через это и получил бы ответ. Он подсказывал: ну, вот если вы возьмёте то-то, представите это как сумму этого и этого, а потом домножите на то-то, то вы увидите, как вывести формулу. Я садился, выводил формулу, и он ставил мне плюсик, не дожидаясь, пока я решу собственно задачу. Потом мы переходили к следующему пункту. Почему, спрашивал он, не доказали теорему? Я говорил: я знаю, что при соблюдении таких-то условий она вытекает из того-то через то-то и то-то, но совершенно не помню, как от вот этой формулы делается переход дальше. Он говорил: ну дак дальше из того-то следует, что так-то и так-то. А! перебивал его я, ну точно же, и тогда мы сможем заменить это на это, и там то-то то-то сократится и останется как раз то, что нам нужно!

Люди учившие всё наизусть, частенько уходили с двойками, даже если на листочке напротив всего стояли плюсы: когда в ходе разговора выяснялось, что человек не соображает, листочек уже не имел никакого значения. Он ценил понимание больше прилежности, и понимающему человеку готов был прощать лень и плохую подготовку, за что я ему очень благодарен.

Теорема и её доказательство, формула и её вывод, данные в неразрывной связке, воспитывают навык видеть во всём здравый смысл. Не обязательно знать это всё наизусть, чтобы сформировать правильное отношение к математике. Важно, что математика существовала бы, даже если бы не было Пифагора и Фалеса, Эйлера и Коши, Остроградского и Гаусса. Всё работает так, как работает, с неизбежностью, а не потому, что кто-то так придумал.

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

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

Источник

Теорема Гёделя о неполноте за 20 минут

Теореме Гёделя о неполноте, одной из самых известных теорем математической логики, повезло и не повезло одновременно. В этом она похожа на специальную теорию относительности Эйнштейна. С одной стороны, почти все о них что-то слышали. С другой — в народной интерпретации теория Эйнштейна, как известно, «говорит, что всё в мире относительно». А теорема Гёделя о неполноте (далее просто ТГН), в примерно столь же вольной фолк-формулировке, «доказывает, что есть вещи, непостижимые для человеческого разума». И вот одни пытаются приспособить её в качестве аргумента против материализма, а другие, напротив, доказывают с её помощью, что бога нет. Забавно не только то, что обе стороны не могут оказаться правыми одновременно, но и то, что ни те, ни другие не удосуживаются разобраться, что же, собственно, эта теорема утверждает.

Итак, что же? Ниже я попытаюсь «на пальцах» рассказать об этом. Изложение моё будет, разумеется нестрогим и интуитивным, но я попрошу математиков не судить меня строго. Возможно, что для нематематиков (к которым, вообще-то, отношусь и я), в рассказанном ниже будет что-то новое и полезное.

Математическая логика — наука действительно довольно сложная, а главное — не очень привычная. Она требует аккуратных и строгих манёвров, при которых важно не перепутать реально доказанное с тем, что «и так понятно». Тем не менее, я надеюсь, что для понимания следующего ниже «наброска доказательства ТГН» читателю понадобится только знание школьной математики/информатики, навыки логического мышления и 15-20 минут времени.

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

Начнём с того, что попытаемся разобраться, что такое доказательство. Возьмём какую-нибудь школьную задачку по арифметике. Например, пусть требуется доказать верность следующей незамысловатой формулы: «» (напомню, что символ читается «для любого» и называется «квантор всеобщности»). Доказать её можно, тождественно преобразуя, скажем, так:

Изложим то же самое чуть более формально. Пусть у нас есть множество, состоящее из строк символов какого-то алфавита, и существуют правила, по которым из этих строк можно выделить подмножество так называемых высказываний — то есть грамматически осмысленных фраз, каждая из которых истинна или ложна. Можно сказать, что существует функция , сопоставляющая высказываниям из одно из двух значений: ИСТИНА или ЛОЖЬ (то есть отображающая их в булево множество из двух элементов).

Назовём такую пару — множество высказываний и функция из в — «языком высказываний». Заметим, что в повседневном смысле понятие языка несколько шире. Например, фраза русского языка «А ну иди сюда!» не истинна и не ложна, то есть высказыванием, с точки зрения математической логики, не является.

Для дальнейшего нам понадобится понятие алгоритма. Приводить здесь формальное его определение я не буду — это завело бы нас довольно далеко в сторону. Ограничусь неформальным: «алгоритм» — эта последовательность однозначных инструкций («программа»), которая за конечное число шагов переводит исходные данные в результат. Выделенное курсивом принципиально важно — если на каких-то начальных данных программа зацикливается, то алгоритма она не описывает. Для простоты и в применении к нашему случаю читатель может считать, что алгоритм — это программа, написанная на любом известном ему языке программирования, которая для любых входных данных из заданного класса гарантированно завершает свою работу с выдачей булевого результата.

Спросим себя: для всякой ли функции существует «доказывающий алгоритм» (или, короче, «дедуктика»), эквивалентный этой функции, то есть переводящий каждое высказывание именно в то булево значение, что и она? Лаконичнее тот же вопрос можно сформулировать так: всякая ли функция над множеством высказываний вычислима? Как вы уже догадываетесь, из справедливости ТГН следует, что нет, не всякая — существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.

Очень может быть, что это утверждение вызовет у вас внутренний протест. Связано это с несколькими обстоятельствами. Во-первых, когда нас учат школьной математике, то иногда возникает ложное впечатление почти полной тождественности фраз «теорема верна» и «можно доказать или проверить теорему ». Но, если вдуматься, это совершенно не очевидно. Некоторые теоремы доказываются довольно просто (например, перебором небольшого числа вариантов), а некоторые — очень сложно. Вспомним, например, знаменитую Великую теорему Ферма:

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

Второй интуитивный довод против ТГН более тонок. Допустим, у нас есть какое-то недоказуемое (в рамках данной дедуктики) высказывание. Что мешает нам принять его в качестве новой аксиомы? Тем самым мы чуть усложним нашу систему доказательств, но это не страшно. Этот довод был бы совершенно верен, если бы недоказуемых высказываний было конечное число. На практике же может произойти следующее — после постулирования новой аксиомы вы наткнётесь на новое недоказуемое высказывание. Примете его в качестве ещё аксиомы — наткнётесь на третье. И так до бесконечности. Говорят, что дедуктика останется неполной. Мы можем также принять силовые меры, чтобы доказывающий алгоритм заканчивался через конечное число шагов с каким-то результатом для любого высказывания языка. Но при этом он начнёт врать — приводить к истине для неверных высказываний, или ко лжи — для верных. В таких случаях говорят, что дедуктика противоречива. Таким образом, ещё одна формулировка ТГН звучит так: «Существуют языки высказываний, для которых невозможна полная непротиворечивая дедуктика» — отсюда и название теоремы.

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

Замечу также, что если бы речь шла о привычных функциях, отображающих множество вещественных чисел в него же, то «невычислимость» функции никого бы не удивила (только не надо путать «вычислимые функции» и «вычислимые числа» — это разные вещи). Любому школьнику известно, что, скажем, в случае функции вам должно сильно повезти с аргументом, чтобы процесс вычисления точного десятичного представления значения этой функции окончился за конечное число шагов. А скорее всего вы будете вычислять её с помощью бесконечного ряда, и это вычисление никогда не приведёт к точному результату, хотя может подойти к нему как угодно близко — просто потому, что значение синуса большинства аргументов иррационально. ТГН просто говорит нам о том, что даже среди функций, аргументами которой являются строки, а значениями — ноль или единица, невычислимые функции, хотя и совсем по другому устроенные, тоже бывают.

Для дальнейшего опишем «язык формальной арифметики». Рассмотрим класс строк текста конечной длины, состоящих из арабских цифр, переменных (букв латинского алфавита), принимающих натуральные значения, пробелов, знаков арифметических действий, равенства и неравенства, кванторов («существует») и («для любого») и, быть может, каких-то ещё символов (точное их количество и состав для нас неважны). Понятно, что не все такие строки осмысленны (например, «$» data-tex=»inline»/>» — это бессмыслица). Подмножество осмысленных выражений из этого класса (то есть строк, которые истинны или ложны с точки зрения обычной арифметики) и будет нашим множеством высказываний.

Примеры высказываний формальной арифметики:

и т.д. Теперь назовём «формулой со свободным параметром» (ФСП) строку, которая становится высказыванием, если в качестве этого параметра подставить в неё натуральное число. Примеры ФСП (с параметром ):

и т.д. Иными словами, ФСП эквивалентны функциям натурального аргумента с булевыми значением.

Обозначим множество всех ФСП буквой . Понятно, что его можно упорядочить (например, сначала выпишем упорядоченные по алфавиту однобуквенные формулы, за ними — двухбуквенные и т.д.; по какому именно алфавиту будет происходить упорядочивание, нам непринципиально). Таким образом, любой ФСП соответствует её номер в упорядоченном списке, и мы будем обозначать её .

Перейдём теперь к наброску доказательства ТГН в такой формулировке:

Доказывать будем от противного.

Итак, допустим, что такая дедуктика существует. Опишем следующий вспомогательный алгоритм , ставящий в соответствие натуральному числу булево значение следующим образом:

Проще говоря, алгоритм приводит к значению ИСТИНА тогда и только тогда, когда результат подстановки в ФСП её собственного номера в нашем списке даёт ложное высказывание.

Тут мы подходим к единственному месту, в котором я попрошу читателя поверить мне на слово.

Очевидно, что, при сделанном выше предположении, любой ФСП из можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение. Менее очевидно обратное утверждение:

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

Пройдя это скользкое место, мы быстро добираемся до конца.

Здесь уместно вспомнить Эпименида (см. портрет в заголовке), который, как известно, заявил, что все критяне — лжецы, сам являясь критянином. В более лаконичной формулировке его высказывание (известное как «парадокс лжеца») можно сформулировать так: «Я лгу». Именно такое высказывание, само превозглашающее свою ложность, мы и использовали для доказательства.

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

Приведённый набросок доказательства относился к формальной арифметике, но нетрудно понять, что ТГН применима и к многим другим языкам высказываний. Разумеется, не всякие языки таковы. Например, определим язык следующим образом:

Тогда соответствующий полный и непротиворечивый доказывающий алгоритм (его можно назвать «догматической дедуктикой») выглядит примерно так:

Здесь нас спасает то, что любой цитатник, очевидно, конечен, поэтому процесс «доказывания» неминуемо закончится. Таким образом, к языку догматических высказываний ТГН неприменима. Но мы ведь говорили о сложных языках, правда?

Источник