В математике и формальной логике теорема — это утверждение , которое доказано или может быть доказано. [a] [2] [3] Доказательство теоремы — это логическое рассуждение , которое использует правила вывода дедуктивной системы для установления того, что теорема является логическим следствием аксиом и ранее доказанных теорем.
В общепринятой математике аксиомы и правила вывода обычно остаются неявными, и в этом случае они почти всегда являются таковыми теории множеств Цермело–Френкеля с аксиомой выбора (ZFC) или менее мощной теории, такой как арифметика Пеано . [b] Как правило, утверждение, которое явно называется теоремой, является доказанным результатом, который не является непосредственным следствием других известных теорем. Более того, многие авторы квалифицируют как теоремы только самые важные результаты и используют термины лемма , предложение и следствие для менее важных теорем.
В математической логике понятия теорем и доказательств были формализованы для того, чтобы позволить математические рассуждения о них. В этом контексте утверждения становятся хорошо сформированными формулами некоторого формального языка . Теория состоит из некоторых базовых утверждений, называемых аксиомами , и некоторых правил вывода (иногда включаемых в аксиомы). Теоремы теории — это утверждения, которые могут быть выведены из аксиом с помощью правил вывода. [c] Эта формализация привела к теории доказательств , которая позволяет доказывать общие теоремы о теоремах и доказательствах. В частности, теоремы Гёделя о неполноте показывают, что каждая непротиворечивая теория, содержащая натуральные числа, имеет истинные утверждения о натуральных числах, которые не являются теоремами теории (то есть они не могут быть доказаны внутри теории).
Поскольку аксиомы часто являются абстракциями свойств физического мира , теоремы можно рассматривать как выражение некоторой истины, но в отличие от понятия научного закона , который является экспериментальным , обоснование истинности теоремы является чисто дедуктивным . [6] [7] Гипотеза — это предварительное предположение, которое может развиться в теорему, если будет доказано, что оно истинно.
До конца 19 века и основополагающего кризиса математики все математические теории строились из нескольких основных свойств, которые считались самоочевидными; например, фактов, что каждое натуральное число имеет последующее, и что существует ровно одна прямая , которая проходит через две заданные различные точки. Эти основные свойства, которые считались абсолютно очевидными, назывались постулатами или аксиомами ; например, постулаты Евклида . Все теоремы доказывались с использованием явно или неявно этих основных свойств, и из-за очевидности этих основных свойств доказанная теорема считалась окончательной истиной, если только в доказательстве не было ошибки. Например, сумма внутренних углов треугольника равна 180° , и это считалось несомненным фактом.
Одним из аспектов основополагающего кризиса математики было открытие неевклидовых геометрий , которые не приводят ни к какому противоречию, хотя в таких геометриях сумма углов треугольника отлична от 180°. Таким образом, свойство «сумма углов треугольника равна 180°» является либо истинным, либо ложным, в зависимости от того, принимается ли пятый постулат Евклида или отрицается. Аналогично, использование «очевидных» основных свойств множеств приводит к противоречию парадокса Рассела . Это было разрешено путем разработки правил, которые разрешены для манипулирования множествами.
Этот кризис был разрешен путем пересмотра основ математики с целью сделать их более строгими . В этих новых основах теорема — это правильно построенная формула математической теории , которая может быть доказана из аксиом и правил вывода теории. Таким образом, приведенная выше теорема о сумме углов треугольника становится: Согласно аксиомам и правилам вывода евклидовой геометрии , сумма внутренних углов треугольника равна 180° . Аналогично парадокс Рассела исчезает, поскольку в аксиоматизированной теории множеств множество всех множеств не может быть выражено правильно построенной формулой. Точнее, если множество всех множеств может быть выражено правильно построенной формулой, это означает, что теория противоречива , и каждое правильно построенное утверждение, а также его отрицание, является теоремой.
В этом контексте справедливость теоремы зависит только от правильности ее доказательства. Она независима от истинности или даже значимости аксиом. Это не означает, что значимость аксиом неинтересна, а лишь то, что справедливость теоремы независима от значимости аксиом. Эта независимость может быть полезной, позволяя использовать результаты некоторой области математики в, казалось бы, не связанных областях.
Важным следствием такого способа мышления о математике является то, что он позволяет определять математические теории и теоремы как математические объекты и доказывать теоремы о них. Примерами являются теоремы Гёделя о неполноте . В частности, существуют правильно сформулированные утверждения, относительно которых можно доказать, что они не являются теоремой охватывающей теории, хотя их можно доказать в более широкой теории. Примером является теорема Гудстейна , которая может быть сформулирована в арифметике Пеано , но доказано, что она недоказуема в арифметике Пеано. Однако она доказуема в некоторых более общих теориях, таких как теория множеств Цермело–Френкеля .
Многие математические теоремы являются условными утверждениями, доказательства которых выводят заключения из условий, известных как гипотезы или посылки . В свете интерпретации доказательства как обоснования истины, заключение часто рассматривается как необходимое следствие гипотез. А именно, что заключение истинно в случае, если гипотезы истинны — без каких-либо дополнительных предположений. Однако условное выражение также может интерпретироваться по-разному в некоторых дедуктивных системах , в зависимости от значений, приписываемых правилам вывода и условному символу (например, неклассическая логика ).
Хотя теоремы могут быть записаны в полностью символической форме (например, как предложения в исчислении высказываний ), они часто выражаются неформально на естественном языке, таком как английский, для лучшей читаемости. То же самое относится и к доказательствам, которые часто выражаются как логически организованные и четко сформулированные неформальные аргументы, призванные убедить читателей в истинности утверждения теоремы вне всякого сомнения, и из которых в принципе может быть построено формальное символическое доказательство.
Помимо лучшей читаемости, неформальные аргументы обычно легче проверить, чем чисто символические — действительно, многие математики выразили бы предпочтение доказательству, которое не только демонстрирует справедливость теоремы, но и объясняет каким-то образом, почему она, очевидно, верна. В некоторых случаях можно даже обосновать теорему, используя рисунок в качестве доказательства.
Поскольку теоремы лежат в основе математики, они также являются центральными для ее эстетики . Теоремы часто описываются как «тривиальные», или «сложные», или «глубокие», или даже «красивые». Эти субъективные суждения различаются не только от человека к человеку, но также со временем и культурой: например, по мере получения доказательства, упрощения или лучшего понимания теорема, которая когда-то была сложной, может стать тривиальной. [8] С другой стороны, глубокая теорема может быть сформулирована просто, но ее доказательство может включать удивительные и тонкие связи между разрозненными областями математики. Великая теорема Ферма является особенно известным примером такой теоремы. [9]
Логически многие теоремы имеют форму изъявительного условного предложения : если A, то B. Такая теорема не утверждает B — только то, что B является необходимым следствием A.В этом случае A называется гипотезой теоремы («гипотеза» здесь означает нечто совершенно отличное от предположения ), а B — заключением теоремы . Оба вместе (без доказательства) называются предложением или утверждением теоремы (например, « Если A, то B » — это предложение ). В качестве альтернативы A и B можно также назвать антецедентом и консеквентом соответственно. [10] Теорема «Если n — чётное натуральное число , то n /2 — натуральное число» — типичный пример, в котором гипотеза — « n — чётное натуральное число», а заключение — « n /2 — также натуральное число».
Для того, чтобы теорема была доказана, она должна быть в принципе выразима в виде точного формального утверждения. Однако теоремы обычно выражаются на естественном языке, а не в полностью символической форме — с предположением, что формальное утверждение может быть выведено из неформального.
В математике принято выбирать ряд гипотез в пределах данного языка и заявлять, что теория состоит из всех утверждений, доказуемых из этих гипотез. Эти гипотезы образуют фундаментальную основу теории и называются аксиомами или постулатами. Раздел математики, известный как теория доказательств, изучает формальные языки, аксиомы и структуру доказательств.
Некоторые теоремы являются « тривиальными », в том смысле, что они очевидным образом следуют из определений, аксиом и других теорем и не содержат никаких удивительных идей. Некоторые, с другой стороны, можно назвать «глубокими», потому что их доказательства могут быть длинными и сложными, включать области математики, поверхностно отличные от формулировки самой теоремы, или показывать удивительные связи между разрозненными областями математики. [11] Теорема может быть простой в формулировке и при этом быть глубокой. Прекрасным примером является Великая теорема Ферма , [9] и есть много других примеров простых, но глубоких теорем в теории чисел и комбинаторике , среди других областей.
Другие теоремы имеют известные доказательства, которые нелегко записать. Наиболее яркими примерами являются теорема о четырех красках и гипотеза Кеплера . Обе эти теоремы известны как истинные только путем сведения их к вычислительному поиску, который затем проверяется компьютерной программой. Первоначально многие математики не принимали эту форму доказательства, но она стала более широко принятой. Математик Дорон Зейлбергер даже зашел так далеко, что заявил, что это, возможно, единственные нетривиальные результаты, которые когда-либо доказывали математики. [12] Многие математические теоремы можно свести к более простым вычислениям, включая полиномиальные тождества, тригонометрические тождества [13] и гипергеометрические тождества. [14] [ нужна страница ]
Теоремы в математике и теории в науке принципиально различаются по своей эпистемологии . Научная теория не может быть доказана; ее ключевым атрибутом является то, что она фальсифицируема , то есть она делает предсказания о естественном мире, которые можно проверить экспериментально . Любое несоответствие между предсказанием и экспериментом демонстрирует неправильность научной теории или, по крайней мере, ограничивает ее точность или область применимости. Математические теоремы, с другой стороны, являются чисто абстрактными формальными утверждениями: доказательство теоремы не может включать эксперименты или другие эмпирические доказательства таким же образом, как такие доказательства используются для поддержки научных теорий. [6]
Тем не менее, в открытии математических теорем присутствует некоторая степень эмпиризма и сбора данных. Устанавливая шаблон, иногда с использованием мощного компьютера, математики могут иметь представление о том, что доказывать, а в некоторых случаях даже план того, как приступить к доказательству. Также возможно найти один контрпример и таким образом установить невозможность доказательства для предложения в том виде, в котором оно сформулировано, и, возможно, предложить ограниченные формы исходного предложения, которые могли бы иметь осуществимые доказательства.
Например, как гипотеза Коллатца , так и гипотеза Римана являются хорошо известными нерешенными проблемами; они были тщательно изучены с помощью эмпирических проверок, но остаются недоказанными. Гипотеза Коллатца была проверена для начальных значений до примерно 2,88 × 10 18 . Гипотеза Римана была проверена для первых 10 триллионов нетривиальных нулей дзета-функции . Хотя большинство математиков могут допустить предположение, что гипотеза и гипотеза верны, ни одно из этих утверждений не считается доказанным.
Такие доказательства не являются доказательством. Например, гипотеза Мертенса — это утверждение о натуральных числах, которое, как теперь известно, ложно, но явного контрпримера (т. е. натурального числа n, для которого функция Мертенса M ( n ) равна или превышает квадратный корень из n ) не известно: все числа, меньшие 10 14 , обладают свойством Мертенса, а наименьшее число, не обладающее этим свойством, известно только как меньшее экспоненты 1,59 × 10 40 , что приблизительно равно 10 в степени 4,3 × 10 39 . Поскольку число частиц во Вселенной обычно считается меньшим 10 в степени 100 ( гугол ), нет никакой надежды найти явный контрпример путем исчерпывающего поиска .
Слово «теория» также существует в математике, для обозначения совокупности математических аксиом, определений и теорем, как, например, в теории групп (см. математическая теория ). В науке, в частности, в физике, и в технике также есть «теоремы», но они часто содержат утверждения и доказательства, в которых важную роль играют физические предположения и интуиция; физические аксиомы, на которых основаны такие «теоремы», сами по себе фальсифицируемы.
Существует ряд различных терминов для математических утверждений; эти термины указывают на роль, которую утверждения играют в определенном предмете. Различие между различными терминами иногда довольно произвольно, и использование некоторых терминов со временем изменилось.
Другие термины также могут использоваться по историческим или традиционным причинам, например:
Некоторые известные теоремы имеют еще более необычные названия, например, алгоритм деления , формула Эйлера и парадокс Банаха–Тарского .
Теорема и ее доказательство обычно излагаются следующим образом:
Конец доказательства может быть обозначен буквами QED ( quod erat demonstrandum ) или одним из надгробных знаков, таких как «□» или «∎», означающих «конец доказательства», введенных Полом Халмошем после их использования в журналах для обозначения конца статьи. [17]
Точный стиль зависит от автора или издания. Многие издания предоставляют инструкции или макросы для набора в фирменном стиле .
Обычно теореме предшествуют определения, описывающие точное значение терминов, используемых в теореме. Также часто теореме предшествуют ряд предложений или лемм, которые затем используются в доказательстве. Однако леммы иногда встраиваются в доказательство теоремы, либо с вложенными доказательствами, либо с их доказательствами, представленными после доказательства теоремы.
Следствия теоремы приводятся либо между теоремой и доказательством, либо сразу после доказательства. Иногда следствия имеют собственные доказательства, объясняющие, почему они следуют из теоремы.
Подсчитано, что ежегодно доказывается более четверти миллиона теорем. [18]
Известный афоризм «Математик — это устройство для превращения кофе в теоремы» вероятно принадлежит Альфреду Реньи , хотя его часто приписывают коллеге Реньи Полу Эрдёшу (и Реньи, возможно, имел в виду Эрдёша), который был известен множеством выдвинутых им теорем, количеством совместных работ и пристрастием к кофе. [19]
Некоторые считают, что классификация конечных простых групп является самым длинным доказательством теоремы. Она включает десятки тысяч страниц в 500 журнальных статьях около 100 авторов. Считается, что эти статьи вместе дают полное доказательство, и несколько текущих проектов надеются сократить и упростить это доказательство. [20] Другая теорема этого типа — теорема о четырех цветах , доказательство которой, сгенерированное компьютером, слишком длинно для чтения человеком. Это одно из самых длинных известных доказательств теоремы, утверждение которой может быть легко понято неспециалистом. [ необходима цитата ]
В математической логике формальная теория — это набор предложений в формальном языке . Предложение — это правильно сформированная формула без свободных переменных. Предложение, являющееся членом теории, является одной из ее теорем, а теория — набором ее теорем. Обычно теория понимается как замкнутая относительно отношения логического следствия . Некоторые описания определяют теорию как замкнутую относительно отношения семантического следствия ( ), в то время как другие определяют ее как замкнутую относительно отношения синтаксического следствия или отношения выводимости ( ). [21] [22] [23] [24] [25] [26] [27] [28] [29] [30]
Для того чтобы теория была замкнута относительно отношения выводимости, она должна быть связана с дедуктивной системой , которая определяет, как выводятся теоремы. Дедуктивная система может быть указана явно или может быть ясна из контекста. Замыкание пустого множества относительно отношения логического следования дает множество, которое содержит только те предложения, которые являются теоремами дедуктивной системы.
В широком смысле, в котором этот термин используется в логике, теорема не обязательно должна быть истинной, поскольку содержащая ее теория может быть несостоятельной относительно данной семантики или относительно стандартной интерпретации базового языка. У непоследовательной теории все предложения являются теоремами.
Определение теорем как предложений формального языка полезно в теории доказательств , которая является разделом математики, изучающим структуру формальных доказательств и структуру доказуемых формул. Оно также важно в теории моделей , которая занимается отношениями между формальными теориями и структурами, которые способны предоставить им семантику посредством интерпретации .
Хотя теоремы могут быть неинтерпретируемыми предложениями, на практике математики больше интересуются значениями предложений, т. е. предложениями, которые они выражают. Формальные теоремы полезны и интересны тем, что их можно интерпретировать как истинные предложения, а их выводы можно интерпретировать как доказательство их истинности. Теорема, интерпретация которой является истинным утверждением о формальной системе (в отличие от внутри формальной системы), называется метатеоремой .
Некоторые важные теоремы математической логики:
Концепция формальной теоремы является принципиально синтаксической, в отличие от понятия истинного предложения, которое вводит семантику . Различные дедуктивные системы могут давать другие интерпретации в зависимости от предположений правил вывода (т. е. убеждения , обоснования или других модальностей ). Надежность формальной системы зависит от того, являются ли все ее теоремы также истинами . Истинность — это формула, которая истинна при любой возможной интерпретации (например, в классической пропозициональной логике истинами являются тавтологии ). Формальная система считается семантически полной , когда все ее теоремы также являются тавтологиями.
Медиа, связанные с теоремами на Wikimedia Commons
