Доказательство от противного — различия между версиями
WikiSysop (обсуждение | вклад) |
WikiSysop (обсуждение | вклад) |
||
| (не показано 10 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
| + | {| width="100%" | ||
| + | | width="40%"|[[Математика, от мамонтов до наших дней]] << | ||
| + | ! width="20%"|[[Истинность и доказуемость|Оглавление]] | ||
| + | | width="40%" align="right"| >> [[Формальные доказательства]] | ||
| + | |} | ||
| + | ---- | ||
Доказательство от противного – мощный и часто используемый в математике метод. Предположив, что некоторый факт (объект) является истинным (существует), и придя к противоречию, мы заключаем, что факт ложен (объект не существует). Рассмотрим несколько примеров. | Доказательство от противного – мощный и часто используемый в математике метод. Предположив, что некоторый факт (объект) является истинным (существует), и придя к противоречию, мы заключаем, что факт ложен (объект не существует). Рассмотрим несколько примеров. | ||
| Строка 10: | Строка 16: | ||
<math>\textstyle \lozenge</math>: Пусть это не так, и самое большое простое число | <math>\textstyle \lozenge</math>: Пусть это не так, и самое большое простое число | ||
<math>\textstyle p_{max}</math> существует. | <math>\textstyle p_{max}</math> существует. | ||
| − | Построим число <math>\textstyle p=p_1\cdot p_2\cdot ... \cdot p_{max} + 1</math>. Оно не делится ни на одно <math>\textstyle p_i</math>, и больше чем <math>\textstyle p_{max}</math>. Мы пришли к противоречию, следовательно, самого большого простого числа (как объекта!) не существует и простых чисел бесконечно много. <math>\textstyle \square</math> </blockquote> Заметим, что <math>\textstyle p</math> не обязательно простое, так как его простой множитель может находится между <math>\textstyle p_{max}</math> и <math>\textstyle p</math>, но всё равно будет большим <math>\textstyle p_{max}</math>. | + | Построим число <math>\textstyle p=p_1\cdot p_2\cdot ... \cdot p_{max} + 1</math>. Оно не делится ни на одно <math>\textstyle p_i</math>, и больше чем <math>\textstyle p_{max}</math>. Мы пришли к противоречию, следовательно, самого большого простого числа (как объекта!) не существует и простых чисел бесконечно много. <math>\textstyle \square</math> |
| − | + | </blockquote> | |
| + | Заметим, что <math>\textstyle p</math> не обязательно простое, так как его простой множитель может находится между <math>\textstyle p_{max}</math> и <math>\textstyle p</math>, но всё равно будет большим <math>\textstyle p_{max}</math>. | ||
| − | <math>\textstyle \bullet</math> '''Теорема об иррациональности'' <math>\textstyle \sqrt{2}</math> <blockquote> | + | <math>\textstyle \bullet</math> '''Теорема об иррациональности''' <math>\textstyle \sqrt{2}</math> <blockquote> |
| − | ''Не существует натуральных <math>\textstyle m</math> и <math>\textstyle n</math>, таких, что <math>\textstyle \sqrt{2 | + | ''Не существует натуральных <math>\textstyle m</math> и <math>\textstyle n</math>, таких, что <math>\textstyle \sqrt{2}=m/n</math>''. |
</blockquote> | </blockquote> | ||
| Строка 25: | Строка 32: | ||
Видно, что схема доказательства приведенных теорем одинаковая. Мы показываем, что некоторый объект не существует, если предположение о его существовании приводит к противоречию. | Видно, что схема доказательства приведенных теорем одинаковая. Мы показываем, что некоторый объект не существует, если предположение о его существовании приводит к противоречию. | ||
| − | <math>\textstyle \bullet</math> | + | <math>\textstyle \bullet</math> '''Проблема Брадобрея'''. |
| + | В некоторой деревне все мужчины бреются либо сами, либо у брадобрея. Брадобрей (мужчина) бреет только тех, кто сам не бреется. Сформулируем теорему: | ||
| + | <blockquote> | ||
| + | ''Брадобрей бреет себя сам.'' | ||
| + | </blockquote> | ||
| − | <math>\textstyle \lozenge</math> Пусть это не так, и брадобрей себя не бреет. Тогда он должен бриться у брадобрея. Значит брадобрей бреет себя. <math>\textstyle \square</math> </blockquote> Сделав отрицание теоремы, и получив противоречие, мы должны прийти к выводу, что теорема верна. Но совершенно ясно, что это не так, и мы можем построить не только обратное доказательство, но и прямое: "если брадобрей бреется сам, то он не может бриться у брадобрея ...". В этом случае вновь получается противоречие. | + | <blockquote> |
| + | <math>\textstyle \lozenge</math> Пусть это не так, и брадобрей себя не бреет. Тогда он должен бриться у брадобрея. Значит брадобрей бреет себя. <math>\textstyle \square</math> | ||
| + | </blockquote> | ||
| + | |||
| + | Сделав отрицание теоремы, и получив противоречие, мы должны прийти к выводу, что теорема верна. Но совершенно ясно, что это не так, и мы можем построить не только обратное доказательство, но и прямое: "если брадобрей бреется сам, то он не может бриться у брадобрея ...". В этом случае вновь получается противоречие. | ||
Приведенное описание деревни со строгими правилами принадлежит Бертрану Расселу, как популярная формулировка проблем, возникающих в попытке ''определить'' "множество всех тех множеств, которые не содержат себя в качестве своего элемента". Мы умышленно явный парадокс представили в виде теоремы, чтобы продемонстрировать простой факт: <blockquote> Получение противоречия в доказательстве от противного может свидетельствовать не об истинности теоремы, а о противоречивости объектов которые участвуют в её формулировке. </blockquote> Другими словами, нельзя сказать: "возьмём множество всех множеств ..." и докажем "теорему о том, что ..." Сначала необходимо убедиться, что объект, о котором будет идти речь в теореме, существует. В частности, деревня, описанная Расселом, существовать не может. Конечно, возникает вопрос – "а что значит существовать или не существовать, и где не существовать?" Есть объект, определённый выше, и мы можем использовать его при построении новых объектов и теорем о них... | Приведенное описание деревни со строгими правилами принадлежит Бертрану Расселу, как популярная формулировка проблем, возникающих в попытке ''определить'' "множество всех тех множеств, которые не содержат себя в качестве своего элемента". Мы умышленно явный парадокс представили в виде теоремы, чтобы продемонстрировать простой факт: <blockquote> Получение противоречия в доказательстве от противного может свидетельствовать не об истинности теоремы, а о противоречивости объектов которые участвуют в её формулировке. </blockquote> Другими словами, нельзя сказать: "возьмём множество всех множеств ..." и докажем "теорему о том, что ..." Сначала необходимо убедиться, что объект, о котором будет идти речь в теореме, существует. В частности, деревня, описанная Расселом, существовать не может. Конечно, возникает вопрос – "а что значит существовать или не существовать, и где не существовать?" Есть объект, определённый выше, и мы можем использовать его при построении новых объектов и теорем о них... | ||
| Строка 35: | Строка 50: | ||
Подробнее мы обсудим элементы формальных аксиоматических систем в следующем разделе, где снова проанализируем проблему брадобрея. Сейчас же рассмотрим ещё одну версию того же парадокса. | Подробнее мы обсудим элементы формальных аксиоматических систем в следующем разделе, где снова проанализируем проблему брадобрея. Сейчас же рассмотрим ещё одну версию того же парадокса. | ||
| − | <math>\textstyle \bullet</math> | + | <math>\textstyle \bullet</math> '''Проблема Библиотекаря'''. Существует Библиотека с книгами. Любая книга внутри своего текста может упомянуть сама себя (например, в списке литературы привести свое название). Соответственно все книги можно разделить на две группы. В первую попадают книги, которые на себя не ссылаются, а во вторую – ссылающиеся на себя книги. Кроме этого, существуют две книги, являющиеся каталогами всех книг Библиотеки. Первый каталог перечисляет все те книги, которые на себя не ссылаются, а второй, наоборот – все ссылающиеся на себя книги: |
| + | |||
| + | <center> | ||
| + | [[Файл:logic_lib.gif]] | ||
| + | </center> | ||
| + | |||
| + | Сформулируем теперь теорему: | ||
| + | |||
| + | <blockquote> ''Первый каталог содержит | ||
| + | в списке книг себя.'' | ||
| + | </blockquote> | ||
| + | |||
| + | <blockquote> | ||
| + | <math>\textstyle \lozenge</math> Пусть это не так. Тогда первый каталог содержится во втором (все книги перечислены в обоих каталогах и каталог есть книга). Но во втором каталоге перечисляются только самоссылающиеся книги, и первого каталога там быть не может. Мы пришли к противоречию, следовательно теорема верна. <math>\textstyle \square</math> | ||
| + | </blockquote> | ||
| − | + | Если мы остановимся на этом этапе, то получим заведомо неверный вывод. Понятно, что первый каталог на себя ссылаться не может (он является каталогом не самоссылающихся книг). Как и в случае с брадобреем, мы можем провести как обратное доказательство (от противного), так и прямое. И оба раза получить противоречие. | |
О чём оно говорит? Понятно, что не об истинности или ложности теоремы. Веря в то, что два различных доказательства должны всегда приводить к одному и тому же, мы вынуждены сделать вывод: ''объект Библиотека'', c заданными свойствами, ''существовать не может''. | О чём оно говорит? Понятно, что не об истинности или ложности теоремы. Веря в то, что два различных доказательства должны всегда приводить к одному и тому же, мы вынуждены сделать вывод: ''объект Библиотека'', c заданными свойствами, ''существовать не может''. | ||
| Строка 43: | Строка 72: | ||
Любая ссылка на "естественность" или "видимую не противоречивость" исходных определений не достойна математика, так как это уже эмоции. Единственный путь – попытаться уйти от психологических формулировок и доказательств к формальным. | Любая ссылка на "естественность" или "видимую не противоречивость" исходных определений не достойна математика, так как это уже эмоции. Единственный путь – попытаться уйти от психологических формулировок и доказательств к формальным. | ||
| − | <math>\textstyle \bullet</math> | + | <math>\textstyle \bullet</math> '''Парадокс лжеца'''. Вся математика состоит из логических утверждений. При этом логика математики бинарна. Утверждение "<math>\textstyle 2<3</math>" или истинно или ложно. Третьего не дано. Именно эта бинарность придаёт математическому доказательству ту чудесную убедительность, ради которой всё и затевалось. Введем обозначение того, что некое логическое утверждение <math>\textstyle A</math> является истинным: |
| + | |||
| + | :<math>\textstyle \mathbf{True}(A)</math>. | ||
| + | |||
| + | На самом деле обозначение <math>\mathbf{True}</math> излишне, так как записывая в качестве аксиомы или посылки некоторое утверждение <math>\textstyle A</math>, мы предполагаем его истинность. Однако, такое обозначение будет удобно для дальнейшего. ''Определим'' высказывание: | ||
| + | |||
| + | <blockquote> <math>\textstyle L \;:\; \neg \mathbf{True}(L)</math>, | ||
| − | + | </blockquote> где "<math>\textstyle \neg</math>" – знак логического отрицания, а после двоеточия идёт ''определение'' утверждения <math>\textstyle { L}</math>. Оно является вариантом парадокса лжеца: "<math>\textstyle L</math> – истинно, если не истинно <math>\textstyle L</math>". Сформулируем следующую теорему: <blockquote> ''Утверждение L является истинным: L=И.'' </blockquote> | |
| − | :<math>\lozenge_1: | + | :<math>\lozenge_1:</math> пусть L=Л => True(L)=Л => L=<math>\neg</math>True(L)=И. <math>\square</math> |
| − | + | (Далее "<math>\textstyle =></math>" означает логический вывод; "И" – истина, "Л" – ложь). В доказательстве от противного, мы пришли к противоречию. Поэтому исходная посылка <math>\textstyle L=Л</math> не верна и, следовательно, теорема верна. Однако понятно, что это не так. Мы можем провести доказательство и в прямом направлении: | |
| − | :<math>\lozenge_2: | + | :<math>\lozenge_2:</math> пусть L=И => True(L)=И => L=<math>\neg</math> True(L)=Л <math>\square,</math> |
и снова прийти к противоречию. Таким образом, мы не способны ни доказать ни опровергнуть теорему и ходим по замкнутому кругу. | и снова прийти к противоречию. Таким образом, мы не способны ни доказать ни опровергнуть теорему и ходим по замкнутому кругу. | ||
Причина этого, как и раньше, состоит в том, что объект <math>\textstyle L</math> ''используемый при формулировке теоремы'' противоречив и, следовательно, не может существовать. Второй вопрос, почему объект <math>\textstyle L</math>, построенный столь "конструктивным" образом, не существует? Вокруг парадокса лжеца ломают копья со времен древних греков. Самое простое объяснение состоит в том, что при определении <math>\textstyle L</math> используется ''бесконечная рекурсия''. Объект определяется сам через себя и при этом, говоря языком программирования, нет точки остановки этой рекурсии. Например, компьютер не смог бы оперировать с таким определением и просто "завис" бы. Это же рискует сделать и человек пытающийся глубоко вдуматься в <math>\textstyle L</math>. Поэтому, такое построение (определение) объекта <math>\textstyle L</math> просто некорректно. | Причина этого, как и раньше, состоит в том, что объект <math>\textstyle L</math> ''используемый при формулировке теоремы'' противоречив и, следовательно, не может существовать. Второй вопрос, почему объект <math>\textstyle L</math>, построенный столь "конструктивным" образом, не существует? Вокруг парадокса лжеца ломают копья со времен древних греков. Самое простое объяснение состоит в том, что при определении <math>\textstyle L</math> используется ''бесконечная рекурсия''. Объект определяется сам через себя и при этом, говоря языком программирования, нет точки остановки этой рекурсии. Например, компьютер не смог бы оперировать с таким определением и просто "завис" бы. Это же рискует сделать и человек пытающийся глубоко вдуматься в <math>\textstyle L</math>. Поэтому, такое построение (определение) объекта <math>\textstyle L</math> просто некорректно. | ||
| + | ---- | ||
| + | {| width="100%" | ||
| + | | width="40%"|[[Математика, от мамонтов до наших дней]] << | ||
| + | ! width="20%"|[[Истинность и доказуемость|Оглавление]] | ||
| + | | width="40%" align="right"| >> [[Формальные доказательства]] | ||
| + | |} | ||
| + | ---- | ||
| + | [[Истинность и доказуемость]] - о конструктивной математике, Канторе и Гёделе | ||
Текущая версия на 16:02, 29 августа 2010
| Математика, от мамонтов до наших дней << | Оглавление | >> Формальные доказательства |
|---|
Доказательство от противного – мощный и часто используемый в математике метод. Предположив, что некоторый факт (объект) является истинным (существует), и придя к противоречию, мы заключаем, что факт ложен (объект не существует). Рассмотрим несколько примеров.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Теорема Евклида о бесконечности простых чисел Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle {p_1,p_2,...}} является классическим и самым простым рассуждением от противного:
Не существует самого большого простого числа Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_{max}} .
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lozenge} : Пусть это не так, и самое большое простое число Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_{max}} существует. Построим число Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p=p_1\cdot p_2\cdot ... \cdot p_{max} + 1} . Оно не делится ни на одно Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_i} , и больше чем Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_{max}} . Мы пришли к противоречию, следовательно, самого большого простого числа (как объекта!) не существует и простых чисел бесконечно много. Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \square}
Заметим, что Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p} не обязательно простое, так как его простой множитель может находится между Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_{max}} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p} , но всё равно будет большим Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_{max}} .
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Теорема об иррациональности Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \sqrt{2}}
Не существует натуральных Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} , таких, что Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \sqrt{2}=m/n} .
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lozenge} : Пусть это не так. Сократим общие множители у Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} , и возведём всё в квадрат: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle 2=m^2/n^2} . Отсюда следует, что Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m^2=2\cdot n^2} является чётным числом, поэтому Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m} тоже чётно и представимо при помощи некоторого натурального Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle k} , как Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m=2\cdot k} . Подставляя Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m} в исходное соотношение, получаем Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n^2=2\cdot k^2} , а, следовательно, и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} чётно. Но это противоречит тому, что мы сократили все общие множители, а значит таких Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle m} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} не существует. Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \square}
Психологическая убедительность обоих доказательств не вызывает сомнений. Тем не менее, необходимо помнить, что получив противоречие, мы не всегда доказываем то, что хотим доказать. Противоречие не обязательно свидетельствует об ошибочности исходной посылки. Его может дать любое из утверждений использовавшихся при доказательстве. Особенно их много в теореме об иррациональности Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \sqrt{2}} . Однако, они на столько "очевидны", что мы считаем ошибочной именно исходную посылку.
Видно, что схема доказательства приведенных теорем одинаковая. Мы показываем, что некоторый объект не существует, если предположение о его существовании приводит к противоречию.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Проблема Брадобрея. В некоторой деревне все мужчины бреются либо сами, либо у брадобрея. Брадобрей (мужчина) бреет только тех, кто сам не бреется. Сформулируем теорему:
Брадобрей бреет себя сам.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lozenge} Пусть это не так, и брадобрей себя не бреет. Тогда он должен бриться у брадобрея. Значит брадобрей бреет себя. Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \square}
Сделав отрицание теоремы, и получив противоречие, мы должны прийти к выводу, что теорема верна. Но совершенно ясно, что это не так, и мы можем построить не только обратное доказательство, но и прямое: "если брадобрей бреется сам, то он не может бриться у брадобрея ...". В этом случае вновь получается противоречие.
Приведенное описание деревни со строгими правилами принадлежит Бертрану Расселу, как популярная формулировка проблем, возникающих в попытке определить "множество всех тех множеств, которые не содержат себя в качестве своего элемента". Мы умышленно явный парадокс представили в виде теоремы, чтобы продемонстрировать простой факт:
Получение противоречия в доказательстве от противного может свидетельствовать не об истинности теоремы, а о противоречивости объектов которые участвуют в её формулировке.
Другими словами, нельзя сказать: "возьмём множество всех множеств ..." и докажем "теорему о том, что ..." Сначала необходимо убедиться, что объект, о котором будет идти речь в теореме, существует. В частности, деревня, описанная Расселом, существовать не может. Конечно, возникает вопрос – "а что значит существовать или не существовать, и где не существовать?" Есть объект, определённый выше, и мы можем использовать его при построении новых объектов и теорем о них...
Дело в том, что математическое рассуждение явно или не явно исходит из некоторых аксиом. Именно аксиомы задают свойства объекта. Если в фиксированной системе аксиом поменять хотя бы одну аксиому, может получиться объект с совершенно другими свойствами. Понятно, что произвольно задавать аксиомы нельзя. Они не должны быть противоречивыми, иначе никакого объекта определять не будут. Или, другими словами, – объект определяемый при помощи противоречивых аксиом не существует.
Подробнее мы обсудим элементы формальных аксиоматических систем в следующем разделе, где снова проанализируем проблему брадобрея. Сейчас же рассмотрим ещё одну версию того же парадокса.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Проблема Библиотекаря. Существует Библиотека с книгами. Любая книга внутри своего текста может упомянуть сама себя (например, в списке литературы привести свое название). Соответственно все книги можно разделить на две группы. В первую попадают книги, которые на себя не ссылаются, а во вторую – ссылающиеся на себя книги. Кроме этого, существуют две книги, являющиеся каталогами всех книг Библиотеки. Первый каталог перечисляет все те книги, которые на себя не ссылаются, а второй, наоборот – все ссылающиеся на себя книги:
Сформулируем теперь теорему:
Первый каталог содержит
в списке книг себя.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \lozenge} Пусть это не так. Тогда первый каталог содержится во втором (все книги перечислены в обоих каталогах и каталог есть книга). Но во втором каталоге перечисляются только самоссылающиеся книги, и первого каталога там быть не может. Мы пришли к противоречию, следовательно теорема верна. Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \square}
Если мы остановимся на этом этапе, то получим заведомо неверный вывод. Понятно, что первый каталог на себя ссылаться не может (он является каталогом не самоссылающихся книг). Как и в случае с брадобреем, мы можем провести как обратное доказательство (от противного), так и прямое. И оба раза получить противоречие.
О чём оно говорит? Понятно, что не об истинности или ложности теоремы. Веря в то, что два различных доказательства должны всегда приводить к одному и тому же, мы вынуждены сделать вывод: объект Библиотека, c заданными свойствами, существовать не может.
Любая ссылка на "естественность" или "видимую не противоречивость" исходных определений не достойна математика, так как это уже эмоции. Единственный путь – попытаться уйти от психологических формулировок и доказательств к формальным.
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Парадокс лжеца. Вся математика состоит из логических утверждений. При этом логика математики бинарна. Утверждение "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle 2<3} " или истинно или ложно. Третьего не дано. Именно эта бинарность придаёт математическому доказательству ту чудесную убедительность, ради которой всё и затевалось. Введем обозначение того, что некое логическое утверждение Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle A} является истинным:
- Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{True}(A)} .
На самом деле обозначение Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \mathbf{True}} излишне, так как записывая в качестве аксиомы или посылки некоторое утверждение Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle A} , мы предполагаем его истинность. Однако, такое обозначение будет удобно для дальнейшего. Определим высказывание:
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L \;:\; \neg \mathbf{True}(L)} ,
где "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \neg} " – знак логического отрицания, а после двоеточия идёт определение утверждения Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle { L}} . Оно является вариантом парадокса лжеца: "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L} – истинно, если не истинно Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L} ". Сформулируем следующую теорему:
Утверждение L является истинным: L=И.
- Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \lozenge_1:} пусть L=Л => True(L)=Л => L=Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \neg} True(L)=И. Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \square}
(Далее "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle =>} " означает логический вывод; "И" – истина, "Л" – ложь). В доказательстве от противного, мы пришли к противоречию. Поэтому исходная посылка Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L=Л} не верна и, следовательно, теорема верна. Однако понятно, что это не так. Мы можем провести доказательство и в прямом направлении:
- Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \lozenge_2:} пусть L=И => True(L)=И => L=Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \neg} True(L)=Л Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \square,}
и снова прийти к противоречию. Таким образом, мы не способны ни доказать ни опровергнуть теорему и ходим по замкнутому кругу.
Причина этого, как и раньше, состоит в том, что объект Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L} используемый при формулировке теоремы противоречив и, следовательно, не может существовать. Второй вопрос, почему объект Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L} , построенный столь "конструктивным" образом, не существует? Вокруг парадокса лжеца ломают копья со времен древних греков. Самое простое объяснение состоит в том, что при определении Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L} используется бесконечная рекурсия. Объект определяется сам через себя и при этом, говоря языком программирования, нет точки остановки этой рекурсии. Например, компьютер не смог бы оперировать с таким определением и просто "завис" бы. Это же рискует сделать и человек пытающийся глубоко вдуматься в Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L} . Поэтому, такое построение (определение) объекта Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle L} просто некорректно.
| Математика, от мамонтов до наших дней << | Оглавление | >> Формальные доказательства |
|---|
Истинность и доказуемость - о конструктивной математике, Канторе и Гёделе
