Что такое доказательство в математике
Математическое доказательство
На протяжении всей истории математики представление о способах и допустимых методах доказательства существенно менялось, в основном, в сторону большей формализации и бо́льших ограничений. Ключевой вехой в вопросе формализации доказательства стало создание математической логики в XIX веке и формализация её средствами основных техник доказательства. В XX веке построена теория доказательств — теория, изучающая доказательство как математический объект. С появлением во второй половине XX века компьютеров особое значение получило применение методов математического доказательства для проверки и синтеза программ, и даже было установлено структурное соответствие между компьютерными программами и математическими доказательствами (соответствие Карри — Ховарда), на основе которого созданы средства автоматического доказательства.
Основные приёмы, используемые при построении доказательств: прямое доказательство, математическая индукция и её обобщения, доказательство от противного, контрапозиция, построение, перебор, установление биекции, двойной счёт; в приложениях в качестве математических доказательств привлекаются также методы, не дающие формального доказательства, но обеспечивающие практическую применимость результата — вероятностные, статистические, приближённые. В зависимости от раздела математики, используемого формализма или математической школы не все методы могут приниматься безоговорочно, в частности, конструктивное доказательство предполагает серьёзные ограничения.
Математическое доказательство
В математике доказа́тельством называется цепочка логических умозаключений, показывающая, что при каком-то наборе аксиом и правил вывода верно некоторое утверждение. В зависимости от контекста, может иметься в виду доказательство в рамках некоторой формальной системы (построенная по специальным правилам последовательность утверждений, записанная на формальном языке) или текст на естественном языке, по которому при желании можно восстановить формальное доказательство. Доказанные утверждения в математике называют теоремами (в математических текстах обычно подразумевается, что доказательство кем-либо найдено; исключения из этого обычая в основном составляют работы по логике, в которых исследуется само понятие доказательства); если ни утверждение, ни его отрицание ещё не доказаны, то такое утверждение называют гипотезой. Иногда в процессе доказательства теоремы выделяются доказательства менее сложных утверждений, называемых леммами.
Содержание
Формальными доказательствами занимается специальная ветвь математики — теория доказательств. Сами формальные доказательства математики почти никогда не используют, поскольку для человеческого восприятия они очень сложны и часто занимают очень много места. Обычно доказательство имеет вид текста, в котором автор, опираясь на аксиомы и доказанные ранее теоремы, с помощью логических средств показывает истинность некоторого утверждения. В отличие от других наук, в математике недопустимы эмпирические доказательства: все утверждения доказываются исключительно логическими способами. В математике важную роль играют математическая интуиция и аналогии между разными объектами и теоремами; тем не менее, все эти средства используются учёными только при поиске доказательств, сами доказательства не могут основываться на таких средствах. Доказательства, написанные на естественных языках, могут быть не очень подробными в расчёте на то, что подготовленный читатель сам сможет восстановить детали. Строгость доказательства гарантируется тем, что его можно представить в виде записи на формальном языке (это и происходит при компьютерной проверке доказательств).
Ошибочным доказательством называется текст, содержащий логические ошибки, то есть такой, по которому нельзя восстановить формальное доказательство. В истории математики были случаи, когда выдающиеся учёные публиковали неверные «доказательства», однако обычно их коллеги или они сами довольно быстро находили ошибки (одна из наиболее часто неправильно доказывавшихся теорем — Великая теорема Ферма. До сих пор встречаются люди, не знающие о том, что она доказана, и предлагающие новые неверные «доказательства» [1] [2] ). Ошибочным может быть только признание доказательством «доказательства» на естественном или формальном языке; формальное доказательство ошибочным не может быть по определению.
В математике существуют нерешённые проблемы, решение которых учёным очень хотелось бы найти. Некоторые из них можно найти в статье «Гипотеза». За доказательства особенно интересных и важных утверждений математические общества назначают премии. [источник не указан 1311 дней]
В информатике математические доказательства используются для верификации и анализа правильности алгоритмов и программ. см. логика в информатике> в рамках технологий доказательного программирования.
Формальное доказательство
Когда говорят о формальном доказательстве, прежде всего описывают формальную модель — множество аксиом, записанных с помощью формального языка, и правил вывода. Формальным выводом называется конечное упорядоченное множество строк, написанных на формальном языке, таких, что каждая из них либо является аксиомой, либо получена из предыдущих строк применением одного из правил вывода. Формальным доказательством утверждения называется формальный вывод, последней строкой которого является данное утверждение. Утверждение, имеющее формальное доказательство, называется теоремой, а множество всех теорем в данной формальной модели (рассматриваемое вместе с алфавитом формального языка, множествами аксиом и правил вывода) называется формальной теорией.
Теория называется полной, если для любого утверждения доказуемо оно или его отрицание, и непротиворечивой, если в ней не существует утверждений, которые можно доказать вместе с их отрицаниями (или, эквивалентно, если в ней существует хотя бы одно недоказуемое утверждение). Большинство «достаточно богатых» математических теорий, как показывает первая теорема Гёделя о неполноте, являются неполными либо противоречивыми. Самым распространённым набором аксиом в наше время является аксиоматика Цермело — Френкеля с аксиомой выбора (хотя некоторые математики выступают против использования последней). Теория на основе этой системы аксиом не полна (например, континуум-гипотеза не может быть ни доказана, ни опровергнута в ней — в предположении, что эта теория непротиворечива). Несмотря на повсеместное использование этой теории в математике, её непротиворечивость не может быть доказана методами её самой. Тем не менее, подавляющее большинство математиков верит в её непротиворечивость, считая, что в противном случае противоречия уже давно были бы обнаружены.
Исторический очерк
Что и требовалось доказать
Традиционно окончание доказательства обозначалось сокращением «Q.E.D.», от латинского выражения лат. Quod Erat Demonstrandum («Что и требовалось доказать»).
Математическое доказательство
Ошибочным доказательством называется текст, содержащий логические ошибки, то есть такой, по которому нельзя восстановить формальное доказательство. В истории математики были случаи, когда выдающиеся учёные публиковали неверные «доказательства», однако обычно их коллеги или они сами довольно быстро находили ошибки. (Одна из наиболее часто неправильно доказывавшихся теорем — Великая теорема Ферма. До сих пор встречаются люди, не знающие о том, что она доказана, и предлагающие новые неверные «доказательства».) Ошибочным может быть только признание «доказательства» на естественном или формальном языке доказательством; формальное доказательство ошибочным не может быть по определению.
В математике существуют нерешённые проблемы, решение которых учёным очень хотелось бы найти. Некоторые из них можно найти в статье « Гипотеза ». За доказательства особенно интересных и важных утверждений математические общества назначают премии.
Формальное доказательство
Теория называется полной, если для любого утверждения доказуемо либо оно, либо его отрицание, и непротиворечивой, если в ней не существует утверждений, которые можно доказать вместе с их отрицаниями. Большинство математических теорий, как показывает первая теорема Гёделя о неполноте, являются неполными, то есть в них существуют утверждения, об истинности которых ничего сказать нельзя. Самым распространённым набором аксиом в наше время является аксиоматика Цермело — Френкеля с аксиомой выбора (хотя некоторые математики выступают против использования последней). Теория на основе этой системы аксиом не полна (например, континуум-гипотеза не может быть ни доказана, ни опровергнута в ней). Несмотря на повсеместное использование этой теории в математике, её непротиворечивость не может быть доказана методами её самой. Тем не менее, подавляющее большинство математиков верит в её непротиворечивость, считая, что в противном случае противоречия уже давно были бы обнаружены.
См. также
ar:برهان رياضي ca:Demostració matemàtica cs:Matematický důkaz da:Bevis (matematik) fa:برهان he:הוכחה hu:Matematikai bizonyítás is:Stærðfræðileg sönnun ka:დამტკიცება mk:Математички доказ nds:Bewies (Mathematik) nl:Wiskundig bewijs no:Matematisk bevis pl:Dowód (matematyka) sl:Matematični dokaz th:การพิสูจน์ vi:Chứng minh định lý zh-classical:證明 zh-min-nan:Chèng-bêng
Математическое доказательство
Ошибочным доказательством называется текст, содержащий логические ошибки, то есть такой, по которому нельзя восстановить формальное доказательство. В истории математики были случаи, когда выдающиеся учёные публиковали неверные «доказательства», однако обычно их коллеги или они сами довольно быстро находили ошибки. (Одна из наиболее часто неправильно доказывавшихся теорем — Великая теорема Ферма. До сих пор встречаются люди, не знающие о том, что она доказана, и предлагающие новые неверные «доказательства».) Ошибочным может быть только признание «доказательства» на естественном или формальном языке доказательством; формальное доказательство ошибочным не может быть по определению.
В математике существуют нерешённые проблемы, решение которых учёным очень хотелось бы найти. Некоторые из них можно найти в статье « Гипотеза ». За доказательства особенно интересных и важных утверждений математические общества назначают премии.
Формальное доказательство
Теория называется полной, если для любого утверждения доказуемо либо оно, либо его отрицание, и непротиворечивой, если в ней не существует утверждений, которые можно доказать вместе с их отрицаниями. Большинство математических теорий, как показывает первая теорема Гёделя о неполноте, являются неполными, то есть в них существуют утверждения, об истинности которых ничего сказать нельзя. Самым распространённым набором аксиом в наше время является аксиоматика Цермело — Френкеля с аксиомой выбора (хотя некоторые математики выступают против использования последней). Теория на основе этой системы аксиом не полна (например, континуум-гипотеза не может быть ни доказана, ни опровергнута в ней). Несмотря на повсеместное использование этой теории в математике, её непротиворечивость не может быть доказана методами её самой. Тем не менее, подавляющее большинство математиков верит в её непротиворечивость, считая, что в противном случае противоречия уже давно были бы обнаружены.
См. также
ar:برهان رياضي ca:Demostració matemàtica cs:Matematický důkaz da:Bevis (matematik) fa:برهان he:הוכחה hu:Matematikai bizonyítás is:Stærðfræðileg sönnun ka:დამტკიცება mk:Математички доказ nds:Bewies (Mathematik) nl:Wiskundig bewijs no:Matematisk bevis pl:Dowód (matematyka) sl:Matematični dokaz th:การพิสูจน์ vi:Chứng minh định lý zh-classical:證明 zh-min-nan:Chèng-bêng
Математическое доказательство
Математическое доказательство, формальное доказательство — правильно сформулированный порядок логических утверждений, связанных отношением следования (импликации, влечения, вывода) непрерывной цепью от аксиом к искомому утверждению.
Доказательство необходимо, как завершительный шаг цикла развития любой теории в формальных науках: имея фиксированный логический язык, аксиоматическую систему и набор известных теорем, сообщество исследователей решает статус некоторых гипотез, проводя доказательство их истинности или ложности: в первом случае гипотеза обретает статус теоремы, а во втором случае говорят, что гипотеза опровергается. Также могут строить математическое доказательство теоремам, которые уже́ доказаны иным способом: для более краткого и/или простого доказательства, в практике образования, в поисках альтернативной системы аксиом, либо в преследовании математической красоты.
В зависимости от контекста, может подразумеваться доказательство в рамках определенной формальной системы (построенная по особым правилам последовательность утверждений, записанная на формальном языке) или текст на естественном языке, согласно которому при желании возможно восстановить формальное доказательство. Иногда в процессе доказательства теоремы выделяются доказательства менее сложных утверждений (лемм).
Формальными доказательствами занимается специальный раздел математики — теория доказательств. Сами формальные доказательства математики почти никогда не используют, так как для человеческого восприятия они очень сложны и часто занимают слишком много места. Обычное доказательство имеет вид текста, в котором автор, опираясь на аксиомы и доказанные ранее теоремы, с помощью логических средств показывает истинность некоторого утверждения. В отличие от других наук, в математике недопустимы эмпирические доказательства, то есть все утверждения доказываются исключительно логическим способом. В математике важную роль играют математическая интуиция и аналогии между различными объектами и теоремами; однако, все эти средства используются учеными только при поиске доказательств, сами доказательства не могут базироваться на таких средствах.
[править] Парадоксы
Некорректное ведение доказательства может вести к парадоксам. Так парадокс под названием «Доказательство одноцветности всех лошадей» — пример некорректного применения метода математической индукции.