www.wikidata.uk-ua.nina.az

Неконструктивне доведення неефективне доведення клас математичних доведень що доводять лише існування в заданій як прави

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

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

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

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

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

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

Принцип Діріхле Редагувати

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

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

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

Тут твердження існування немає, але воно виникне, якщо, наприклад, замість дискретних ящиків розглядати відрізок та значення функції на ньому. Якщо збігається, то збігається майже скрізь, тобто множина точок, де воно не збігається має міру нуль. Але ми не можемо нічого сказати про цю множину, а значить, не можемо нічого сказати і про точки, де ряд збігається. Ми довели, що ряд збігається майже скрізь, але де саме — незрозуміло. У цьому полягає неконструктивність.

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

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

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

Різниця розміру множин Редагувати

Якщо , то .

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

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

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

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

Див. також: Засновок

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

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

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

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

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

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

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

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

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

Геометрія чисел Редагувати

Нехай дано замкнуте опукле тіло об'ємом , симетричне відносно початку координат. Якщо розглянути функцію

то очевидно, що , отже

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

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

Комбінаторна геометрія Редагувати

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

Теорія чисел Редагувати

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

Див. також Редагувати

Примітки Редагувати

  1. Bridges, Douglas; Palmgren, Erik (2018). У Zalta, Edward N.; Nodelman, Uri. Constructive Mathematics. The Stanford Encyclopedia of Philosophy (вид. Summer 2018). Metaphysics Research Lab, Stanford University. 
  2. Чандрасекхаран, 1968, с. 136—137.
  3. . Архів оригіналу за 28 серпня 2018. Процитовано 31 березня 2018. 
  4. D. Bevan, «Sets of Points Determining Only Acute Angles and Some Related Colouring Problems», Electron. J. Combin., 13:1 (2006), 24 p. оригіналу за 2 травня 2018. Процитовано 31 березня 2018. 
  5. Л. В. Бучок, «О двух новых подходах к получению оценок в проблеме Данцера-Грюнбаума, Матем. заметки, 2010, том 87, выпуск 4, страницы 519—527». оригіналу за 12 травня 2018. Процитовано 31 березня 2018. 
  6. Кейперс, 1963.

Література Редагувати

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Nekonstruktivne dovedennya neefektivne dovedennya klas matematichnih doveden sho dovodyat lishe isnuvannya v zadanij yak pravilo neskinchennij mnozhini elementa sho zadovolnyaye zadanim vlastivostyam ale ne daye niyakoyi informaciyi pro inshi vlastivosti elementa tobto ne dozvolyayut ni pred yaviti jogo ani priblizno opisati Dovedennya yaki dovodyat isnuvannya elementa nadayuchi sposib oderzhannya cogo elementa nazivayut konstruktivnimi Yaksho v dovedenni dovoditsya formula v yakij odna z velichin stala ale yiyi znachennya vidnoviti nemozhlivo ce chislo nazivayut neefektivnoyu staloyu 1 Ce ponyattya ne slid plutati z vipadkom koli stalu abo inshij shukanij ob yekt prosto duzhe skladno viraziti abo vona vihodit za mezhi rozumnih ochikuvan Napriklad dovedennya v yakomu vinikaye chislo Grema ye konstruktivnim oskilki chislo Grema hoch i duzhe velike ale jogo mozhna opisati konkretno Zmist 1 Priroda nekonstruktivnih doveden 1 1 Princip Dirihle 1 2 Riznicya rozmiru mnozhin 1 3 Vikoristannya isnuvannya yak peredumovi 2 Prikladi nekonstruktivnih doveden 2 1 Teoriya obchislyuvanosti 2 2 Geometriya chisel 2 3 Kombinatorna geometriya 2 4 Teoriya chisel 3 Div takozh 4 Primitki 5 LiteraturaPriroda nekonstruktivnih doveden RedaguvatiMozhe vikoristovuvatisya takozh obernena postanovka principu Dirihle dlya neskinchennih mnozhin Princip Dirihle Redaguvati Dokladnishe Princip DirihleDo ciyeyi zh grupi mozhna vidnesti zastosuvannya nerivnosti Markova i nerivnosti dlya zvichajnih sum sho viplivaye z neyi Napriklad yaksho vidomo sho suma i 1 n a i displaystyle sum limits i 1 n a i nbsp dosit velika a elementi v nij obmezheni zverhu a i lt M displaystyle a i lt M nbsp to mozhna pokazati sho isnuye bagato elementiv znachennya yakih vidnosno velike i blizke do M displaystyle M nbsp Ce bagato oznachaye deyaku mnozhinu A displaystyle A nbsp elementiv i ce A displaystyle A nbsp yaksho vono abo jogo elementi bude vikoristano dali v dovedenni zrobit dovedennya nekonstruktivnim oskilki nichogo krim togo sho vono isnuye pro nogo diznatisya nemozhlivo Yaksho v skinchennomu chisli yashikiv mistitsya skinchenna kilkist krolikiv to v kozhnomu yashiku mistitsya skinchenna kilkist krolikiv Analogichni principu Dirihle mirkuvannya lezhat v arifmetichnij osnovi jmovirnisnogo metodu de majzhe vsi dovedennya viyavlyayutsya nekonstruktivnimi Bagato takih doveden zasnovani na riznih formah ta uzagalnennyah principu Dirihle Sam soboyu cej principTut tverdzhennya isnuvannya nemaye ale vono vinikne yaksho napriklad zamist diskretnih yashikiv rozglyadati vidrizok 0 1 displaystyle 0 1 nbsp ta znachennya funkciyi na nomu Yaksho 0 1 i 1 f i x d x displaystyle int limits 0 1 left sum limits i 1 infty f i x right dx nbsp zbigayetsya to i 1 f i x displaystyle sum limits i 1 infty f i x nbsp zbigayetsya majzhe skriz tobto mnozhina tochok de vono ne zbigayetsya maye miru nul Ale mi ne mozhemo nichogo skazati pro cyu mnozhinu a znachit ne mozhemo nichogo skazati i pro tochki de ryad zbigayetsya Mi doveli sho ryad zbigayetsya majzhe skriz ale de same nezrozumilo U comu polyagaye nekonstruktivnist Nekonstruktivni dovedennya yak pravilo vinikayut pri zastosuvanni pid chas dovedennya deyakih tipovih tverdzhen i prijomiv yaki sami ye nekonstruktivnimi Chasto nekonstruktivni dovedennya vedutsya vid suprotivnogo Yaksho n 1 displaystyle n 1 nbsp elementiv lezhat u n displaystyle n nbsp komirkah to isnuye komirka z ne mensh nizh dvoma elementami stverdzhuye isnuvannya ale ne dozvolyaye znajti shukanogo ob yekta Riznicya rozmiru mnozhin Redaguvati Yaksho A lt B displaystyle A lt B nbsp to x B x A displaystyle exists x in B x not in A nbsp Yaksho pereformulyuvati ce v terminah principu Dirihle to vijde take yaksho z n 1 displaystyle n 1 nbsp krolikiv deyaki sidyat u odnij iz n displaystyle n nbsp klitok ale v kozhnij klitci sidit ne bilshe odnogo krolika to hocha b odin krolik ne sidit u zhodnij iz klitok V opisanomu vishe prikladi z integralom ryadu zastosovano same cej prijom ale slid zaznachiti sho v comu prijomi ne vazhlivo chi buli mnozhini A displaystyle A nbsp i B displaystyle B nbsp konstruktivnimi ranishe Navit yaksho voni buli odnoznachno viznachenimi isnuvannya elementa x displaystyle x nbsp dovedeno nekonstruktivno u ramkah mnozhini B displaystyle B nbsp Vikoristannya isnuvannya yak peredumovi Redaguvati Div takozh Zasnovok Bilshist matematichnih teorem formulyuyutsya za principom Yaksho to Yaksho persha chastina cogo rechennya peredumova mistit yakis umovi sho stosuyutsya lishe isnuvannya elementiv z timi chi inshimi vlastivostyami to dovedennya takogo tverdzhennya mozhe buti konstruktivnim lishe v sensi chitkogo vkazannya zalezhnosti shukanogo ob yekta isnuvannya yakogo dovoditsya vid ob yekta isnuvannya yakogo pripuskayetsya Odnak konstruktivnist dovedennya v comu sensi she ne garantuye konstruktivnosti shirshih tverdzhen dlya dovedennya yakih vikoristovuvatimetsya ce dlya zabezpechennya yihnoyi konstruktivnosti neobhidno zabezpechiti she konstruktivnist dovedennya pripushenoyi tut vlastivosti isnuvannya Napriklad nehaj dovoditsya deyake tverdzhennya dlya bud yakoyi bezperervnoyi funkciyi f displaystyle f nbsp ta deyakoyi tochki x 0 displaystyle x 0 nbsp takoyi sho f x 0 gt 0 displaystyle f x 0 gt 0 nbsp Za viznachennyam neperervnosti e gt 0 d d e gt 0 x x x 0 lt d f x f x 0 lt e displaystyle forall varepsilon gt 0 exists delta delta varepsilon gt 0 forall x x x 0 lt delta Rightarrow f x f x 0 lt varepsilon nbsp Z cogo legko vivesti sho m gt 0 x 0 x 0 m f x d x 1 001 m f x displaystyle exists mu gt 0 int limits x 0 x 0 mu f x dx leq 1 001 mu f x nbsp Dovedennya cogo mozhna vvazhati konstruktivnim oskilki mi mozhemo ociniti m displaystyle mu nbsp u terminah zalezhnosti d e displaystyle delta varepsilon nbsp Odnak yaksho mi potim budemo vikoristovuvati dovedenij naslidok dlya pevnoyi funkciyi f displaystyle f nbsp pro yaku nam vidomo sho vona neperervna ale ne vidoma chitka zalezhnist d e displaystyle delta varepsilon nbsp tobto neperervnist f displaystyle f nbsp dovedeno nekonstruktivno to otrimayemo nekonstruktivne dovedennya oskilki ne zmozhemo vidnoviti i m displaystyle mu nbsp Prikladi nekonstruktivnih doveden RedaguvatiTeoriya obchislyuvanosti Redaguvati Dokladnishe Teoriya obchislyuvanostiIsnuvannya neobchislennoyi mnozhini klasichnij priklad nekonstruktivnogo dovedennya cherez riznicyu rozmiriv mnozhin Formalizaciya ponyattya algoritmu svogo chasu porodila pitannya chi isnuye mnozhina naturalnih chisel dlya yakoyi ne isnuye algoritmu strogishe mashini Tyuringa yaka pereviryaye dovilne chislo na nalezhnist cij mnozhini Vidpovidno do teoremi Kantora potuzhnist mnozhini vsih pidmnozhin naturalnih chisel dorivnyuye kontinuumu Oskilki bud yaka mashina Tyuringa zadayetsya skinchennim chislom simvoliv mnozhina vsih mashin Tyuringa ye zlichennoyu Oskilki kontinuum bilshij vid zlichennoyi mnozhini a kozhnomu algoritmu vidpovidaye deyaka mnozhina to krim deyakoyi zlichennoyi mnozhini funkcij inshi funkciyi viyavlyayutsya neobchislyuvanimi Odnak pro te yak voni vlashtovani na osnovi cih mirkuvan nichogo skazati ne mozhna tomu take dovedennya ye nekonstruktivnim Slid zaznachiti sho niyake nekonstruktivne dovedennya ne skasovuye mozhlivosti inshogo konstruktivnogo dovedennya Zokrema deyaki prikladi nezlichennih mnozhin i funkcij a takozh algoritmichno nerozv yaznih zadach yaki mozhna zvesti do nih vse taki vidomi div Problema zupinki Staranni bobri en Desyata problema GilbertaGeometriya chisel Redaguvati Dokladnishe Geometriya chiselNehaj dano zamknute opukle tilo A R n displaystyle A subset mathbb R n nbsp ob yemom V A gt 2 n displaystyle V A gt 2 n nbsp simetrichne vidnosno pochatku koordinat Yaksho rozglyanuti funkciyu f x 1 x n c 1 c n Z n 2 c 1 x 1 2 c n x n A displaystyle 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 nbsp to ochevidno sho 0 2 0 2 f x 1 x n d x 1 d x n V A gt 2 n displaystyle int limits 0 2 dots int limits 0 2 f x 1 dots x n dx 1 dots dx n V A gt 2 n nbsp otzhe x 1 x n f x 1 x n 2 displaystyle exists x 1 dots x n f x 1 dots x n geq 2 nbsp tak sho isnuyut tochki x y A displaystyle overline x overline y in A nbsp riznicya yakih ye parnoyu tochkoyu cilochiselnoyi gratki Cherez vlastivosti opuklosti ta simetrichnosti z cogo legko vivesti sho v A displaystyle A nbsp lezhit hocha b odna cila tochka krim 0 0 displaystyle 0 dots 0 nbsp Odnak pro te yaka same cya tochka nichogo skazati ne mozhna Dovedene tverdzhennya nazivayut teoremoyu Minkovskogo 2 Opisane dovedennya ye nekonstruktivnim cherez te sho vikoristovuye princip Dirihle Kombinatorna geometriya Redaguvati Dokladnishe Kombinatorna geometriyaDeyaki dovedennya sho stosuyutsya zadachi Dancera Gryunbauma ru buli nekonstruktivnimi cherez zastosuvannya jmovirnisnogo metodu 3 4 5 Teoriya chisel Redaguvati Dokladnishe Teoriya chiselVikoristovuyuchi kriterij Vejlya mozhna pokazati sho dlya bud yakoyi neskinchennoyi poslidovnosti chisel a 1 lt a 2 lt lt a n lt displaystyle a 1 lt a 2 lt dots lt a n lt dots nbsp dlya majzhe vsih chisel 3 0 1 displaystyle xi in 0 1 nbsp poslidovnist a n 3 n 1 displaystyle a n xi n 1 infty nbsp rivnomirno rozpodilena za modulem 1 tobto mnozhina znachen dlya yakih ce ne tak maye nulovu miru Odnak take dovedennya ne daye zmogi pred yaviti mnozhinu vinyatkiv vona ochevidno zalezhit vid poslidovnosti a n n 1 displaystyle a n n 1 infty nbsp tobto z nogo nemozhlivo zrozumiti chi rivnomirno rozpodilena poslidovnist a n 3 n 1 displaystyle a n xi n 1 infty nbsp dlya yakogos konkretnogo zadanogo 3 displaystyle xi nbsp 6 Div takozh RedaguvatiKonstruktivizm matematika Konstruktivne dovedennyaPrimitki Redaguvati Bridges Douglas Palmgren Erik 2018 U Zalta Edward N Nodelman Uri Constructive Mathematics The Stanford Encyclopedia of Philosophy vid Summer 2018 Metaphysics Research Lab Stanford University Chandrasekharan 1968 s 136 137 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 Arhiv originalu za 28 serpnya 2018 Procitovano 31 bereznya 2018 D Bevan Sets of Points Determining Only Acute Angles and Some Related Colouring Problems Electron J Combin 13 1 2006 24 p Arhiv originalu za 2 travnya 2018 Procitovano 31 bereznya 2018 L V Buchok O dvuh novyh podhodah k polucheniyu ocenok v probleme Dancera Gryunbauma Matem zametki 2010 tom 87 vypusk 4 stranicy 519 527 Arhiv originalu za 12 travnya 2018 Procitovano 31 bereznya 2018 Kejpers 1963 Literatura RedaguvatiK Chandrasekharan Vvedenie v analiticheskuyu teoriyu chisel Mir 1968 S 45 Lourens Kejpers Garold Niderrejter Ravnomernoe raspredelenie posledovatelnostej Mir 1963 407 s Otrimano z https uk wikipedia org w index php title Nekonstruktivne dovedennya amp oldid 40230670