Перегляд вихідного коду сторінки Неконструктивне доведення

'''Неконструктивне доведення''' ('''неефективне доведення''')&nbsp;— клас [[Доведення|математичних доведень]], що доводять лише існування в заданій (як правило, нескінченній) множині елемента, що задовольняє заданим властивостям, але не дає ніякої інформації про інші властивості елемента, тобто не дозволяють ні пред'явити його, ані приблизно описати. Доведення, які доводять існування елемента, надаючи спосіб одержання цього елемента, називають [[Конструктивне доведення|конструктивними]].

Якщо в доведенні доводиться формула, в якій одна з величин&nbsp;— стала, але її значення відновити неможливо, це число називають '''неефективною сталою'''.<ref>{{Cite book
|url=https://plato.stanford.edu/archives/sum2018/entries/mathematics-constructive/
|title=Constructive Mathematics |last=Bridges
|first=Douglas
|last2=Palmgren
|first2=Erik
|date=2018
|editor-last=Zalta
|editor-first=Edward N.
|editor2-last=Nodelman
|editor2-first=Uri
|series=The Stanford Encyclopedia of Philosophy
|publisher=Metaphysics Research Lab, Stanford University
|edition=Summer 2018
}}</ref>

Це поняття не слід плутати з випадком, коли сталу (або інший шуканий об'єкт) просто дуже складно виразити або вона виходить за межі розумних очікувань. Наприклад, доведення, в якому виникає [[число Грема]], є конструктивним, оскільки число Грема, хоч і дуже велике, але його можна описати конкретно.

== Природа неконструктивних доведень ==
Неконструктивні доведення, як правило, виникають при застосуванні під час доведення деяких типових тверджень і прийомів, які самі є неконструктивними. Часто неконструктивні доведення ведуться [[Доведення від супротивного|від супротивного]].

=== Принцип Діріхле ===
{{Докладніше|Принцип Діріхле}}
Багато таких доведень засновані на різних формах та узагальненнях [[Принцип Діріхле|принципу Діріхле]]. Сам собою цей принцип

{{Рамка}}
Якщо <math>n+1</math> елементів лежать у <math>n</math> комірках, то '''існує''' комірка з не менш ніж двома елементами.
{{/рамка}}стверджує існування, але не дозволяє знайти шуканого об'єкта.

До цієї ж групи можна віднести застосування [[Нерівність Маркова|нерівності Маркова]] і нерівності для звичайних сум, що випливає з неї. Наприклад, якщо відомо, що сума <math>\sum \limits_{i=1}^{n} {a_i}</math> досить велика, а елементи в ній обмежені зверху (<math>a_i<M</math>), то можна показати, що існує багато елементів, значення яких відносно велике і близьке до <math>M</math>. Це «багато» означає деяку множину <math>A</math> елементів, і це <math>A</math>, якщо воно або його елементи буде використано далі в доведенні, зробить доведення неконструктивним, оскільки нічого, крім того, що воно існує, про нього дізнатися неможливо.

Аналогічні принципу Діріхле міркування лежать в арифметичній основі [[Імовірнісний метод|ймовірнісного методу]], де майже всі доведення виявляються неконструктивними.

Може використовуватися також обернена постановка принципу Діріхле для нескінченних множин:

{{Рамка}}
Якщо в скінченному числі ящиків міститься скінченна кількість кроликів, то в кожному ящику міститься скінченна кількість кроликів.
{{/рамка}}

Тут твердження існування немає, але воно виникне, якщо, наприклад, замість дискретних ящиків розглядати відрізок <math>(0;1)</math> та значення функції на ньому. Якщо <math>\int \limits_{0}^{1} \left({\sum \limits_{i=1}^{\infty} {f_i(x)}}\right)dx</math> збігається, то <math>\sum \limits_{i=1}^{\infty} {f_i(x)}</math> збігається [[майже скрізь]], тобто множина точок, де воно не збігається має [[Міра множини|міру]] нуль. Але ми не можемо нічого сказати про цю множину, а значить, не можемо нічого сказати і про точки, де ряд збігається. Ми довели, що ряд збігається майже скрізь, але де саме&nbsp;— незрозуміло. У цьому полягає неконструктивність.

=== Різниця розміру множин ===
{{Рамка}}
Якщо <math>|A|<|B|</math>, то <math>\exists x \in B:\ x \not \in A</math>.
{{/рамка}}Якщо переформулювати це в термінах принципу Діріхле, то вийде таке:{{Рамка}}
якщо з <math>n+1</math> кроликів деякі сидять у одній із <math>n</math> кліток, але в кожній клітці сидить не більше одного кролика, то хоча б один кролик не сидить у жодній із кліток.
{{/рамка}}В описаному вище прикладі з інтегралом ряду застосовано саме цей прийом, але слід зазначити, що в цьому прийомі не важливо, чи були множини <math>A</math> і <math>B</math> конструктивними раніше. Навіть якщо вони були однозначно визначеними, існування елемента <math>x</math> доведено неконструктивно (у рамках множини <math>B</math>).

=== Використання існування як передумови ===
{{Див. також|Засновок}}
Більшість математичних теорем формулюються за принципом «Якщо […], то […]». Якщо перша частина цього речення (передумова) містить якісь умови, що стосуються лише існування елементів з тими чи іншими властивостями, то доведення такого твердження може бути конструктивним лише в сенсі чіткого вказання залежності шуканого об'єкта (існування якого доводиться) від об'єкта, існування якого припускається. Однак конструктивність доведення в цьому сенсі ще не гарантує конструктивності ширших тверджень, для доведення яких використовуватиметься це&nbsp;— для забезпечення їхньої конструктивності необхідно забезпечити ще конструктивність доведення припущеної тут властивості існування.

Наприклад, нехай доводиться деяке твердження для будь-якої безперервної функції <math>f</math> та деякої точки <math>x_0</math> (такої, що <math>f(x_0) > 0</math>). За визначенням неперервності, <math>\forall \varepsilon > 0 \exists \delta = \delta(\varepsilon) > 0: \forall x: |x - x_0| < \delta \Rightarrow |f(x) - f(x_0)| < \varepsilon</math> . З цього легко вивести, що <math>\exists \mu > 0: \int \limits_{x_0}^{x_0+\mu} f(x) dx \le 1.001 \mu f(x)</math> . Доведення цього можна вважати конструктивним, оскільки ми можемо оцінити <math>\mu</math> у термінах залежності <math>\delta(\varepsilon)</math>. Однак, якщо ми потім будемо використовувати доведений наслідок для певної функції <math>f</math>, про яку нам відомо, що вона неперервна, але не відома чітка залежність <math>\delta(\varepsilon)</math> (тобто неперервність <math>f</math> доведено неконструктивно), то отримаємо неконструктивне доведення, оскільки не зможемо відновити і <math>\mu</math>.

== Приклади неконструктивних доведень ==

=== Теорія обчислюваності ===
{{Докладніше|Теорія обчислюваності}}
Існування [[Обчисленна функція|необчисленної множини]]&nbsp;— класичний приклад неконструктивного доведення через різницю розмірів множин.

Формалізація поняття [[алгоритм]]у свого часу породила питання&nbsp;— чи існує множина натуральних чисел, для якої не існує алгоритму (строгіше, [[Машина Тюрінга|машини Тюрінга]]), яка перевіряє довільне число на належність цій множині.

Відповідно до [[Теорема Кантора|теореми Кантора]], [[Потужність множини|потужність]] [[Булеан|множини всіх підмножин]] натуральних чисел дорівнює [[Континуум (теорія множин)|континууму]]. Оскільки будь-яка машина Тюрінга задається скінченним числом символів, множина всіх машин Тюрінга є [[Зліченна множина|зліченною]].

Оскільки континуум більший від зліченної множини, а кожному алгоритму відповідає деяка множина, то, крім деякої зліченної множини функцій, інші функції виявляються необчислюваними. Однак про те, як вони влаштовані, на основі цих міркувань нічого сказати не можна, тому таке доведення є неконструктивним.

Слід зазначити, що ніяке неконструктивне доведення не скасовує можливості іншого, [[Конструктивне доведення|конструктивного доведення]]. Зокрема, деякі приклади незліченних множин і функцій (а також алгоритмічно нерозв'язних задач, які можна звести до них) все-таки відомі, див.:

* [[Проблема зупинки]]
* {{Не перекладено|Старанні бобри||en|Busy beaver}}
* [[Десята проблема Гільберта]]

=== Геометрія чисел ===
{{Докладніше|Геометрія чисел}}
Нехай дано [[Замкнута множина|замкнуте]] [[Опукла множина|опукле тіло]] <math>A \subset {\mathbb R}^n</math> об'ємом <math>V(A) > 2^n</math>, [[Центральна симетрія|симетричне відносно початку координат]]. Якщо розглянути функцію

: <math>f(x_1,\dots,x_n) = \# \left\lbrace{(c_1,\dots, c_n) \in {\mathbb Z_n} : (2 c_1+x_1,\dots,2 c_n+x_n) \in A}\right\rbrace</math> ,

то очевидно, що <math>\int \limits_{0}^{2} \dots \int \limits_{0}^{2} {f(x_1,\dots,x_n) d x_1 \dots d x_n} = V(A) > 2^n</math>, отже

: <math>\exists x_1,\dots,x_n: f(x_1,\dots,x_n) \ge 2</math>

так що існують точки <math>\overline{x}, \overline{y} \in A</math>, різниця яких є парною точкою [[Цілочисельна ґратка|цілочисельної ґратки]]. Через властивості опуклості та симетричності з цього легко вивести, що в <math>A</math> лежить хоча б одна ціла точка крім <math>(0,\dots,0)</math> . Однак про те, яка саме ця точка, нічого сказати не можна.

Доведене твердження називають [[Теорема Мінковського|теоремою Мінковського]]{{Sfn|Чандрасекхаран|1968|с=136—137}}. Описане доведення є неконструктивним через те, що використовує принцип Діріхле.

=== Комбінаторна геометрія ===
{{Докладніше|Комбінаторна геометрія}}
Деякі доведення, що стосуються [[Задача Данцера — Ґрюнбаума|задачі Данцера&nbsp;— Ґрюнбаума]], були неконструктивними через застосування [[Імовірнісний метод|ймовірнісного методу]]<ref>{{Cite web|url=https://pdfs.semanticscholar.org/b37c/a9ab34d969877e889e0ba25d5f5303eb36de.pdf|title=P. Erdos, Z. Furedi. The greatest angle among n points in the d-dimensional Euclidean space // Combinatorial mathematics.--Marseille-Luminy, 1981.--P. 275—283; North-Holland Math. Stud.--75.--North-Holland, Amsterdam, 1983|accessdate=2018-03-31|archivedate=2018-08-28|archiveurl=https://web.archive.org/web/20180828071359/https://pdfs.semanticscholar.org/b37c/a9ab34d969877e889e0ba25d5f5303eb36de.pdf|deadurl=yes}}</ref><ref>{{Cite web|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r12|title=D. Bevan, «Sets of Points Determining Only Acute Angles and Some Related Colouring Problems», Electron. J. Combin., 13:1 (2006), 24 p.|accessdate=2018-03-31|archivedate=2018-05-02|archiveurl=https://web.archive.org/web/20180502053848/http://www.combinatorics.org/ojs/index.php/eljc/article/view/v13i1r12|deadurl=no}}</ref><ref>{{Cite web|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mzm&paperid=6610&option_lang=rus|title=Л. В. Бучок, «О двух новых подходах к получению оценок в проблеме Данцера-Грюнбаума, Матем. заметки, 2010, том 87, выпуск 4, страницы 519—527»|accessdate=2018-03-31|archivedate=2018-05-12|archiveurl=https://web.archive.org/web/20180512043718/http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mzm&paperid=6610&option_lang=rus|deadurl=no}}</ref>.

=== Теорія чисел ===
{{Докладніше|Теорія чисел}}
Використовуючи [[Теорема Вейля про рівномірний розподіл|критерій Вейля]], можна показати, що для будь-якої нескінченної послідовності чисел <math>a_1<a_2<\dots<a_n<\dots</math> для [[Майже скрізь|майже всіх]] чисел <math>\xi \in (0;1)</math> послідовність <math>{(a_n \xi)}_{n=1}^{\infty}</math> [[Теорема Вейля про рівномірний розподіл|рівномірно розподілена за модулем 1]], тобто множина значень, для яких це не так, має нульову [[Міра множини|міру]]. Однак таке доведення не дає змоги пред'явити множину винятків (вона, очевидно, залежить від послідовності <math>(a_n)_{n=1}^{\infty}</math>). тобто з нього неможливо зрозуміти, чи [[рівномірно розподілена послідовність]] <math>{(a_n \xi)}_{n=1}^{\infty}</math> для якогось конкретного заданого <math>\xi</math>{{Sfn|Кейперс|1963}}.

== Див. також ==
* [[Конструктивізм (математика)]]
* [[Конструктивне доведення]]

== Примітки ==
{{примітки|2}}

== Література ==
* {{Книга
|автор = К. Чандрасекхаран
|заголовок = Введение в аналитическую теорию чисел
|видавництво = [[Мир (видавництво)|Мир]]
|рік = 1968
|сторінки = 45
|посилання = https://books.google.ru/books?id=N81LYAAACAAJ
|ref = Чандрасекхаран
}}
* {{Книга
|автор = Лоуренс Кейперс, Гарольд Нидеррейтер
|заголовок = Равномерное распределение последовательностей
|видавництво = [[Мир (видавництво)|Мир]]
|рік = 1963
|сторінок = 407
|ref = Кейперс
}}
[[Категорія:Доказові практики]]
[[Категорія:Теорія алгоритмів]]
[[Категорія:Логіка]]
[[Категорія:Комбінаторика]]