Неконструктивне доведення

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

Якщо в доведенні доводиться формула, в якій одна з величин — стала, але її значення відновити неможливо, це число називають неефективною сталою.

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

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

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

Принцип Діріхле

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

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

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

Багато таких доведень засновані на різних формах та узагальненнях принципу Діріхле. Сам собою цей принцип

Тут твердження існування немає, але воно виникне, якщо, наприклад, замість дискретних ящиків розглядати відрізок $(0;1)$ та значення функції на ньому. Якщо $\int \limits _{0}^{1}\left({\sum \limits _{i=1}^{\infty }{f_{i}(x)}}\right)dx$ збігається, то $\sum \limits _{i=1}^{\infty }{f_{i}(x)}$ збігається майже скрізь, тобто множина точок, де воно не збігається має міру нуль. Але ми не можемо нічого сказати про цю множину, а значить, не можемо нічого сказати і про точки, де ряд збігається. Ми довели, що ряд збігається майже скрізь, але де саме — незрозуміло. У цьому полягає неконструктивність.

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

Якщо $n+1$ елементів лежать у $n$ комірках, то існує комірка з не менш ніж двома елементами.

стверджує існування, але не дозволяє знайти шуканого об'єкта.

Різниця розміру множин

Якщо $|A|<|B|$, то $\exists x\in B:\ x\not \in A$.

Якщо переформулювати це в термінах принципу Діріхле, то вийде таке:

якщо з $n+1$ кроликів деякі сидять у одній із $n$ кліток, але в кожній клітці сидить не більше одного кролика, то хоча б один кролик не сидить у жодній із кліток.

В описаному вище прикладі з інтегралом ряду застосовано саме цей прийом, але слід зазначити, що в цьому прийомі не важливо, чи були множини $A$ і $B$ конструктивними раніше. Навіть якщо вони були однозначно визначеними, існування елемента $x$ доведено неконструктивно (у рамках множини $B$).

Використання існування як передумови

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

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

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

Теорія обчислюваності

Існування необчисленної множини - класичний приклад неконструктивного доведення через різницю розмірів множин.

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

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

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

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

• Проблема зупинки
• Старанні бобри
• Десята проблема Гільберта

Геометрія чисел

Нехай дано замкнуте опукле тіло $A\subset {\mathbb {R} }^{n}$ об'ємом $V(A)>2^{n}$, симетричне відносно початку координат. Якщо розглянути функцію

$f(x_{1},\dots ,x_{n})=\#\left\lbrace {(c_{1},\dots ,c_{n})\in {\mathbb {Z} _{n}}:(2c_{1}+x_{1},\dots ,2c_{n}+x_{n})\in A}\right\rbrace$ ,

то очевидно, що $\int \limits _{0}^{2}\dots \int \limits _{0}^{2}{f(x_{1},\dots ,x_{n})dx_{1}\dots dx_{n}}=V(A)>2^{n}$, отже

$\exists x_{1},\dots ,x_{n}:f(x_{1},\dots ,x_{n})\geq 2$

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

Доведене твердження називають теоремою Мінковського. Описане доведення є неконструктивним через те, що використовує принцип Діріхле.

Комбінаторна геометрія

Деякі доведення, що стосуються задачі Данцера — Ґрюнбаума, були неконструктивними через застосування ймовірнісного методу.

Теорія чисел

Використовуючи критерій Вейля, можна показати, що для будь-якої нескінченної послідовності чисел $a_{1}<a_{2}<\dots <a_{n}<\dots$ для майже всіх чисел $\xi \in (0;1)$ послідовність ${(a_{n}\xi )}_{n=1}^{\infty }$ рівномірно розподілена за модулем 1, тобто множина значень, для яких це не так, має нульову міру. Однак таке доведення не дає змоги пред'явити множину винятків (вона, очевидно, залежить від послідовності $(a_{n})_{n=1}^{\infty }$). тобто з нього неможливо зрозуміти, чи рівномірно розподілена послідовність ${(a_{n}\xi )}_{n=1}^{\infty }$ для якогось конкретного заданого $\xi$.

Див. також

• Конструктивізм (математика)
• Конструктивне доведення

Література

• К. Чандрасекхаран. Введение в аналитическую теорию чисел. — Мир, 1968. — С. 45.
• Лоуренс Кейперс, Гарольд Нидеррейтер. Равномерное распределение последовательностей. — Мир, 1963. — 407 с.