Математическое доказательство - Mathematical proof

П. Окси. 29, один из старейших сохранившихся фрагментов Евклидова Элементы, учебник, используемый на протяжении тысячелетий для обучения методам корректуры. Диаграмма прилагается к книге II, предложение 5.^[1]

А математическое доказательство является выводимый аргумент для математическое утверждение, показывая, что высказанные предположения логически гарантируют вывод. В аргументе могут использоваться другие ранее установленные утверждения, такие как теоремы; но каждое доказательство, в принципе, может быть построено с использованием только определенных основных или исходных предположений, известных как аксиомы,^[2][3][4] наряду с принятыми правилами вывод. Доказательства являются примерами исчерпывающих дедуктивное мышление которые устанавливают логическую достоверность, чтобы отличаться от эмпирический аргументы или не исчерпывающие индуктивное мышление которые устанавливают «разумное ожидание». Представления многих случаев, в которых утверждение верно, недостаточно для доказательства, которое должно продемонстрировать, что утверждение верно в все возможные случаи. Недоказанное утверждение, которое считается истинным, известно как догадка, или гипотеза, если она часто используется в качестве предположения для дальнейшей математической работы.^[5]

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

История и этимология

Слово «доказательство» происходит от латинского проба (тестировать). Родственными современными словами являются английские «проба», «испытательный срок» и «вероятность», испанский язык. пробар (понюхать или попробовать, а иногда потрогать или протестировать),^[6] Итальянский провар (попробовать) и немецкий пробирен (пытаться). Юридический термин «честность» означает авторитет или надежность, силу свидетельских показаний для доказательства фактов, когда они даются лицами с репутацией или статусом.^[7]

Аргументы правдоподобия с использованием эвристических приемов, таких как изображения и аналогии, предшествовали строгому математическому доказательству.^[8] Вполне вероятно, что идея продемонстрировать вывод впервые возникла в связи с геометрия, возникшие в практических задачах измерения земель.^[9] Развитие математических доказательств в первую очередь является результатом древнегреческая математика, и одно из его величайших достижений.^[10] Фалес (624–546 до н. Э.) И Гиппократ Хиосский (ок. 470–410 до н. э.) дал некоторые из первых известных доказательств геометрических теорем. Евдокс (408–355 до н.э.) и Theaetetus (417–369 до н. Э.) Сформулировал теоремы, но не доказал их. Аристотель (384–322 г. до н.э.) указанные определения должны описывать концепцию, определяемую в терминах других уже известных концепций.

Математическое доказательство произвело революцию Евклид (300 г. до н.э.), который представил аксиоматический метод все еще используется сегодня. Это начинается с неопределенные условия и аксиомы, предложения относительно неопределенных терминов, которые считаются самоочевидно истинными (от греческого «axios», что-то достойное). Исходя из этого, метод доказывает теоремы с использованием дедуктивная логика. Книга Евклида, Элементы, читали все, кто считался образованным на Западе до середины 20 века.^[11] В дополнение к теоремам геометрии, таким как теорема Пифагора, то Элементы также охватывает теорию чисел, включая доказательство того, что квадратный корень из двух иррационально, и доказательство того, что существует бесконечно много простых чисел.

Дальнейшие успехи также имели место в средневековая исламская математика. В то время как более ранние греческие доказательства были в основном геометрическими демонстрациями, развитие арифметика и алгебра исламские математики допускали более общие доказательства без зависимости от геометрической интуиции. В 10 веке н.э. Иракский математик Аль-Хашими работал с числами как таковыми, называемыми «линиями», но не обязательно рассматриваемыми как измерения геометрических объектов, для доказательства алгебраических утверждений относительно умножения, деления и т. д., включая существование иррациональные числа.^[12] An индуктивное доказательство для арифметические последовательности был представлен в Аль-Фахри (1000) пользователя Аль-Караджи кто использовал это, чтобы доказать биномиальная теорема и свойства Треугольник Паскаля. Альхазен также разработал метод доказательство от противного, как первая попытка доказать Евклидово параллельный постулат.^[13]

Современный теория доказательств рассматривает доказательства как индуктивно определенные структуры данных, не требуя предположения, что аксиомы «истинны» в каком-либо смысле. Это позволяет параллельным математическим теориям как формальным моделям данной интуитивной концепции, основанным на альтернативных наборах аксиом, например Аксиоматическая теория множеств и Неевклидова геометрия.

Природа и цель

На практике доказательство выражается на естественном языке и представляет собой строгий аргумент, призванный убедить аудиторию в истинности утверждения. Стандарт строгости не абсолютен и менялся на протяжении всей истории. Доказательство может быть представлено по-разному в зависимости от целевой аудитории. Чтобы получить признание, доказательство должно соответствовать общественным стандартам строгости; ан аргумент считается неопределенным или неполным, может быть отклонено.

Понятие доказательства формализовано в области математической логики.^[14] А формальное доказательство написано в формальный язык вместо естественного языка. Формальное доказательство - это последовательность формул на формальном языке, начинающаяся с предположения, и каждая последующая формула является логическим следствием предыдущих. Это определение делает концепцию доказательства доступной для изучения. Действительно, поле теория доказательств изучает формальные доказательства и их свойства, наиболее известным и удивительным является то, что почти все аксиоматические системы могут генерировать определенные неразрешимые заявления не доказуемо в системе.

Определение формального доказательства предназначено для того, чтобы охватить концепцию доказательств, как написано в математической практике. Обоснованность этого определения сводится к вере в то, что опубликованное доказательство в принципе может быть преобразовано в формальное доказательство. Однако за пределами области автоматизированного помощники доказательства, на практике это делается редко. Классический вопрос философии: являются ли математические доказательства аналитический или синтетический. Кант, который представил аналитическое и синтетическое различие, считал математические доказательства синтетическими, тогда как Куайн утверждал в своем 1951 г. "Две догмы эмпиризма "что такое различие несостоятельно.^[15]

Доказательствами можно восхищаться за их математическая красота. Математик Пол Эрдёш был известен описанием доказательств, которые, как он находил, были особенно изящными, взятыми из «Книги», гипотетического фолианта, содержащего самые прекрасные методы доказательства каждой теоремы. Книга Доказательства из КНИГИ, опубликованная в 2003 году, посвящена представлению 32 доказательств, которые особенно понравились редакции.

Методы

Прямое доказательство

В прямом доказательстве вывод устанавливается путем логического объединения аксиом, определений и предыдущих теорем.^[16] Например, прямое доказательство можно использовать, чтобы доказать, что сумма двух даже целые числа всегда четный:

Рассмотрим два четных целых числа Икс и у. Поскольку они четные, их можно записать как Икс = 2а и у = 2бсоответственно для целых чисел а и б. Тогда сумма Икс + у = 2а + 2б = 2(а+б). Следовательно Икс+у имеет коэффициент 2 и по определению является четным. Следовательно, сумма любых двух четных целых чисел четная.

Это доказательство использует определение четных целых чисел, целочисленные свойства закрытие при сложении и умножении, и распределенность.

Доказательство математической индукцией

Несмотря на свое название, математическая индукция - это метод вычет, а не форма индуктивное мышление. При доказательстве методом математической индукции доказывается единственный «базовый случай» и доказывается «правило индукции», устанавливающее, что любой произвольный случай подразумевает следующий случай. Поскольку в принципе правило индукции можно применять многократно (начиная с доказанного базового случая), отсюда следует, что все (обычно бесконечно многие) случаи доказуемы.^[17] Это позволяет избежать необходимости доказывать каждый случай индивидуально. Вариант математической индукции доказательство бесконечным спуском, что может быть использовано, например, для доказательства иррациональность квадратного корня из двух.^[5]

Обычное применение доказательства с помощью математической индукции - доказать, что свойство, которое, как известно, выполняется для одного числа, выполняется для всех натуральных чисел:^[18]Позволять N = {1,2,3,4,...} - набор натуральных чисел, а п(п) математическое выражение, содержащее натуральное число п принадлежащий N такой, что

• (я) п(1) верно, т.е. п(п) верно для п = 1.
• (ii) п(п+1) верно всякий раз, когда п(п) верно, т.е. п(п) верно означает, что п(п+1) правда.
• потом п(п) верно для всех натуральных чисел п.

Например, по индукции можно доказать, что все натуральные числа вида 2п − 1 странные. Позволять п(п) представлять "2п − 1 нечетное ":

(я) Для п = 1, 2п − 1 = 2(1) − 1 = 1, и 1 нечетно, так как оставляет остаток 1 при делении на 2. Таким образом п(1) правда.

(ii) Для любого п, если 2п − 1 нечетный (п(п)), тогда (2п − 1) + 2 также должно быть нечетным, потому что добавление 2 к нечетному числу приводит к нечетному числу. Но (2п − 1) + 2 = 2п + 1 = 2(п+1) − 1, так 2(п+1) − 1 нечетный (п(п+1)). Так п(п) подразумевает п(п+1).

Таким образом 2п − 1 нечетно для всех натуральных чисел п.

Более короткая фраза «доказательство по индукции» часто используется вместо «доказательство с помощью математической индукции».^[19]

Доказательство противопоставлением

Доказательство противопоставлением делает вывод заявление "если п тогда q"путем установления логически эквивалентного контрапозитивный заявление: "если не q тогда не п".

Например, противопоставление может использоваться, чтобы установить, что, учитывая целое число ${ displaystyle x}$, если ${ displaystyle x ^ {2}}$ четно, тогда ${ displaystyle x}$ даже:

Предположим ${ displaystyle x}$ нет даже. потом ${ displaystyle x}$ странно. Произведение двух нечетных чисел нечетное, поэтому ${ Displaystyle х ^ {2} = х cdot x}$ странно. Таким образом ${ displaystyle x ^ {2}}$ нет даже. Таким образом, если ${ displaystyle x ^ {2}}$ является даже предположение должно быть ложным, поэтому ${ displaystyle x}$ должно быть даже.

Доказательство от противного

В доказательство от противного, также известный по латинской фразе сокращение до абсурда (путем сведения к абсурду) показано, что если какое-то утверждение считается истинным, возникает логическое противоречие, следовательно, утверждение должно быть ложным. Известный пример включает доказательство того, что ${ displaystyle { sqrt {2}}}$ является иррациональный номер:

Предположим, что ${ displaystyle { sqrt {2}}}$ были рациональным числом. Тогда это можно было бы записать в самых низких терминах как ${ displaystyle { sqrt {2}} = {a over b}}$ где а и б ненулевые целые числа с нет общего фактора. Таким образом, ${ displaystyle b { sqrt {2}} = а}$. Квадрат обеих сторон дает 2б² = а². Поскольку 2 делит выражение слева, 2 должно также делить выражение равенства справа. Это, а² четно, что означает, что а также должно быть четным, как показано в предложении выше (доказательство противопоставлением). Итак, мы можем написать а = 2c, где c также является целым числом. Подстановка в исходное уравнение дает 2б² = (2c)² = 4c². Разделив обе стороны на 2, дает б² = 2c². Но тогда, по тому же аргументу, что и раньше, 2 делит б², так б должно быть даже. Однако если а и б оба четные, их общий множитель равен 2. Это противоречит нашему предыдущему утверждению, что а и б не имеют общего фактора, поэтому мы вынуждены заключить, что ${ displaystyle { sqrt {2}}}$ - иррациональное число.

Перефразируя: если бы можно было написать ${ displaystyle { sqrt {2}}}$ как дробь, эта дробь никогда не может быть записана в наименьших числах, так как 2 всегда можно вывести на множители из числителя и знаменателя.

Доказательство построением

Доказательство построением или доказательство примером - это построение конкретного примера со свойством, чтобы показать, что нечто, обладающее этим свойством, существует. Джозеф Лиувиль, например, доказали существование трансцендентные числа путем создания явный пример. Его также можно использовать для построения контрпример чтобы опровергнуть утверждение, что все элементы обладают определенным свойством.

Доказательство истощением

При доказательстве методом исчерпания вывод делается путем разделения его на конечное число случаев и доказательства каждого в отдельности. Количество случаев иногда может стать очень большим. Например, первое доказательство теорема четырех цветов был доказательством исчерпания с 1 936 дел. Это доказательство было спорным, потому что большинство случаев было проверено компьютерной программой, а не вручную. Кратчайшее известное доказательство теоремы о четырех цветах на 2011 год^{[Обновить]} по-прежнему насчитывается более 600 случаев.^[20]

Вероятностное доказательство

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

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

Вероятностное доказательство не следует путать с аргументом о том, что теорема «вероятно» истинна, с «аргументом правдоподобия». Работа над Гипотеза Коллатца показывает, насколько правдоподобие далеко от подлинного доказательства. Хотя большинство математиков не думают, что вероятностное свидетельство свойств данного объекта считается истинным математическим доказательством, некоторые математики и философы утверждали, что по крайней мере некоторые типы вероятностных свидетельств (например, вероятностный алгоритм для проверки простоты) так же хороши, как и настоящие математические доказательства.^[21][22]

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

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

Неконструктивное доказательство

Неконструктивное доказательство устанавливает, что математический объект с определенным свойством существует - без объяснения, как такой объект должен быть найден. Часто это принимает форму доказательства от противоречия, в котором доказывается невозможность существования объекта. Напротив, конструктивное доказательство устанавливает, что конкретный объект существует, путем предоставления метода его обнаружения. Известный пример неконструктивного доказательства показывает, что существует два иррациональные числа а и б такой, что ${ displaystyle a ^ {b}}$ это рациональное число:

Либо ${ displaystyle { sqrt {2}} ^ { sqrt {2}}}$ - рациональное число, и все готово (возьмите ${ displaystyle a = b = { sqrt {2}}}$), или ${ displaystyle { sqrt {2}} ^ { sqrt {2}}}$ иррационально, поэтому мы можем написать ${ displaystyle a = { sqrt {2}} ^ { sqrt {2}}}$ и ${ displaystyle b = { sqrt {2}}}$. Тогда это дает ${ displaystyle left ({ sqrt {2}} ^ { sqrt {2}} right) ^ { sqrt {2}} = { sqrt {2}} ^ {2} = 2}$, что, таким образом, является рациональным в форме ${ displaystyle a ^ {b}.}$

Статистические доказательства в чистой математике

Выражение «статистическое доказательство» может использоваться технически или в разговорной речи в областях чистая математика, например, с участием криптография, хаотическая серия, а также вероятностный или аналитический теория чисел.^[23][24][25] Реже он используется для обозначения математического доказательства в области математики, известной как математическая статистика. Смотрите также "Статистическое доказательство с использованием данных "раздел ниже.

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

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

Неразрешимые заявления

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

Математики показали, что есть много утверждений, которые нельзя ни доказать, ни опровергнуть. Теория множеств Цермело – Френкеля с аксиомой выбора (ZFC), стандартной системой теории множеств в математике (при условии, что ZFC непротиворечива); увидеть список операторов, неразрешимых в ZFC.

(Первая) теорема Гёделя о неполноте показывает, что многие системы аксиом, представляющие математический интерес, будут иметь неразрешимые утверждения.

Эвристическая математика и экспериментальная математика

В то время как ранние математики, такие как Евдокс Книдский не использовал доказательства, из Евклид к фундаментальная математика развития конца 19-го и 20-го веков доказательства были существенной частью математики.^[26] С увеличением вычислительной мощности в 1960-х годах началась значительная работа по исследованию математические объекты вне рамок доказательства теорем,^[27] в экспериментальная математика. Ранние пионеры этих методов планировали, что работа в конечном итоге будет встроена в классическую структуру теорем доказательства, например раннее развитие фрактальная геометрия,^[28] который в конечном итоге был так встроен.

Связанные понятия

Визуальное доказательство

Хотя это не формальное доказательство, визуальная демонстрация математической теоремы иногда называется "доказательство без слов ". На левом рисунке ниже показан пример исторического визуального доказательства теорема Пифагора в случае треугольника (3,4,5).

• 

  Визуальное доказательство для треугольника (3, 4, 5), как в Чжуби Суаньцзин 500–200 до н. Э.

• 

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

• 

  Второе анимированное доказательство теоремы Пифагора.

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

Элементарное доказательство

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

Двухколоночное доказательство

Доказательство в две колонки, опубликованное в 1913 году.

Конкретный способ организации доказательства с использованием двух параллельных столбцов часто используется в классах элементарной геометрии в Соединенных Штатах.^[29] Доказательство записывается в виде серии строк в два столбца. В каждой строке левый столбец содержит предложение, в то время как правый столбец содержит краткое объяснение того, как соответствующее утверждение в левом столбце является либо аксиомой, либо гипотезой, либо может быть логически выведено из предыдущих предложений. . Левый столбец обычно озаглавлен «Заявления», а правый столбец обычно озаглавлен «Причины».^[30]

Разговорное употребление «математического доказательства»

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

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

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

Доказательства индуктивной логики и байесовский анализ

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

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

Доказательства как мысленные объекты

Психологизм рассматривает математические доказательства как психологические или ментальные объекты. Математик философы, такие как Лейбниц, Фреге, и Карнап по-разному критиковали эту точку зрения и пытались разработать семантику того, что они считали язык мысли, посредством чего стандарты математического доказательства могут применяться к эмпирическая наука.^{[нужна цитата ]}

Влияние математических методов доказательства за пределами математики

Философы-математики, такие как Спиноза пытались сформулировать философские аргументы в аксиоматической манере, посредством чего математические стандарты доказательства могли быть применены к аргументации в общей философии. Другие математики-философы пытались использовать стандарты математического доказательства и разума, без эмпиризма, чтобы прийти к утверждениям вне математики, но имея уверенность предложений, выведенных в математическом доказательстве, таких как Декарт ' cogito аргумент.

Завершение доказательства

Иногда сокращение "Q.E.D." написано, чтобы указать на конец доказательства. Это сокращение расшифровывается как "quod erat manifestrandum", который латинский для "то, что должно было быть продемонстрировано". Более распространенной альтернативой является использование квадрата или прямоугольника, например □ или ∎, ​​известного как "надгробие "или" халмос "после его эпоним Пол Халмос.^[5] Часто «что должно было быть показано» произносится устно при написании «QED», «□» или «∎» во время устной презентации.

Смотрите также

использованная литература

дальнейшее чтение

• Поля, Г. (1954), Математика и правдоподобные рассуждения, Princeton University Press.
• Фаллис, Дон (2002), «Чего хотят математики? Вероятностные доказательства и эпистемологические цели математиков», Logique et Analyze, 45: 373–88.
• Франклин, Дж.; Дауд, А. (2011), Доказательство в математике: введение, Кью Букс, ISBN  978-0-646-54509-7.
• Золото, Бонни; Саймонс, Роджерс А. (2008). Доказательство и другие дилеммы: математика и философия. MAA.
• Солоу, Д. (2004), Как читать и делать доказательства: введение в процессы математического мышления, Wiley, ISBN  978-0-471-68058-1.
• Веллеман, Д. (2006), Как это доказать: структурированный подход, Издательство Кембриджского университета, ISBN  978-0-521-67599-4.

внешние ссылки

• СМИ, связанные с Математическое доказательство в Wikimedia Commons
• Доказательства по математике: простые, очаровательные и ошибочные
• А урок о доказательствах, в курс от Викиверситет