Dovada neconstructivă

Dovada neconstructivă ( demonstrație ineficientă ) - o clasă de demonstrații matematice care dovedesc doar existența într-o mulțime dată (de obicei infinită) a unui element care satisface proprietățile date, dar nu oferă nicio informație despre celelalte proprietăți ale elementului, adică nu permite nici prezentarea, nici descrierea aproximativă. Demonstrațiile care dovedesc existența unui element prin prezentarea unei modalități de obținere a acelui element se numesc constructive .

Dacă o formulă este dovedită în demonstrația în care una dintre mărimi este o constantă, dar valoarea ei nu poate fi restabilită, atunci acest număr se numește o constantă ineficientă .

Această noțiune nu trebuie confundată cu cazul în care o constantă (sau un alt obiect de interes) este pur și simplu foarte dificil de exprimat sau se încadrează în afara așteptărilor rezonabile. De exemplu, dovada în care apare numărul Graham este constructivă deoarece numărul Graham, deși foarte mare, poate fi descris în mod specific.

Natura dovezilor neconstructive

De regulă, dovezile neconstructive apar atunci când sunt folosite unele afirmații și tehnici tipice în cursul demonstrației, care nu sunt constructive în sine. Adesea, dovezile neconstructive sunt conduse prin contradicție .

Principiul lui Dirichlet

Multe astfel de dovezi se bazează pe diverse forme și generalizări ale principiului Dirichlet. În sine, acest principiu

Dacă elementele se află în celule, atunci există o celulă cu cel puțin două elemente $n+1$ $n$

afirmă existenţa, dar nu permite găsirea obiectului dorit.

Acest grup include și aplicarea inegalității lui Markov și a inegalităților rezultate pentru sume obișnuite. De exemplu, dacă se știe că suma este suficient de mare, iar elementele din ea sunt mărginite de sus ( ), atunci se poate demonstra că există multe elemente a căror valoare este relativ mare și apropiată de . Acest „multe” înseamnă un anumit set de elemente, iar acest lucru , dacă el sau elementele sale sunt folosite în continuare în demonstrație, va face demonstrația neconstructivă, deoarece este imposibil să știi nimic despre ea decât că există. $\sum \limits _{i=1}^{n}{a_{i}}$ $a_{i}<M$ $M$ $A$ $A$

Considerații similare principiului lui Dirichlet stau la baza bazei aritmetice a metodei probabilistice , unde aproape toate demonstrațiile se dovedesc a fi neconstructive.

Se poate folosi și afirmația inversă a principiului Dirichlet pentru mulțimi infinite:

Dacă există un număr finit de iepuri într-un număr finit de cutii, atunci fiecare cutie conține un număr finit de iepuri.

Aici nu apare afirmația existenței, dar va apărea dacă, de exemplu, în loc de casete discrete, luăm în considerare un segment și valorile unei funcții pe acesta. Dacă converge, atunci converge aproape peste tot , adică mulțimea de puncte în care nu converge are măsura zero. Dar nu putem spune nimic despre acest set, ceea ce înseamnă că nu putem spune nimic despre punctele în care seria converge. Am demonstrat că seria converge aproape peste tot, dar unde exact nu este clar. Aici se află neconstructivitatea. $(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))$

Setați diferența de dimensiune

Dacă , atunci . $|A|<|B|$ $\există x\in B:\ x\nu \in A$

Dacă reformulăm acest lucru în termenii principiului Dirichlet, obținem următoarele:

dacă unii dintre iepuri sunt într-una dintre cuști, dar există cel mult un iepure în fiecare cușcă, atunci cel puțin un iepure nu este în nicio cușcă. $n+1$ $n$

În exemplul descris mai sus cu integrala de serie, s-a folosit doar această tehnică, dar trebuie remarcat că în această tehnică nu contează dacă seturile au fost și constructive înainte. Chiar dacă au fost unic determinate, existența elementului a fost dovedită neconstructiv (în cadrul mulțimii ). $A$ $B$ $X$ $B$

Folosirea existenței ca o condiție prealabilă

Majoritatea teoremelor matematice sunt formulate conform principiului „Dacă […], atunci […]”. Dacă prima parte a acestei propoziții (premisă) conține unele condiții care se referă doar la existența unor elemente cu anumite proprietăți, atunci dovada unei astfel de afirmații poate fi constructivă numai în sensul de a indica în mod clar dependența obiectului dorit (existența din care se dovedeşte) din obiectul căruia se presupune existenţa . Cu toate acestea, caracterul constructiv al probei în acest sens nu garantează încă caracterul constructiv al afirmațiilor mai ample pentru a căror dovadă se va folosi aceasta - pentru a asigura caracterul constructiv al acestora, este de asemenea necesar să se asigure caracterul constructiv al dovezii proprietății existenţa asumată aici.

De exemplu, să demonstrăm o afirmație pentru orice funcție continuă și un anumit punct (cum ar fi ). Prin definiția continuității, . Este ușor de dedus de aici că . Dovada acestui lucru poate fi considerată constructivă, deoarece putem evalua în termeni de dependență . Totuși, dacă atunci folosim corolarul dovedit pentru o anumită funcție , despre care știm că este continuă, dar nu cunoaștem o dependență clară (adică continuitatea este demonstrată neconstructiv), atunci vom obține un non- dovada constructiva, din moment ce nu putem restaura si . $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$

Exemple de dovezi neconstructive

Teoria computabilității

Existența unei mulțimi necalculabile este un exemplu clasic de demonstrație neconstructivă în ceea ce privește diferența dintre dimensiunile mulțimilor.

Formalizarea conceptului de algoritm la un moment dat a dat naștere la întrebarea - există o mulțime de numere naturale pentru care nu există un algoritm (mai strict, o mașină Turing ) care verifică un număr arbitrar pentru a face parte din această mulțime.

Conform teoremei lui Cantor , cardinalitatea mulțimii tuturor submulților de numere naturale este egală cu continuumul . Deoarece orice mașină Turing este dată de un număr finit de simboluri, mulțimea tuturor mașinilor Turing este numărabilă .

Deoarece continuumul este mai mare decât o mulțime numărabilă și fiecare algoritm corespunde unui anumit set computabil, atunci, pe lângă un anumit set numărabil de funcții, alte funcții se dovedesc a fi necalculabile. Cu toate acestea, pe baza acestor argumente, nu se poate spune nimic despre modul în care sunt aranjate, deci o astfel de dovadă nu este constructivă.

Trebuie remarcat faptul că nicio dovadă neconstructivă nu anulează posibilitatea unei alte dovezi, constructive . În special, sunt încă cunoscute câteva exemple de mulțimi și funcții necalculabile (precum și probleme indecidabile din punct de vedere algoritmic care pot fi reduse la ele), vezi:

Geometria numerelor

Să fie dat un corp convex închis de volum , simetric față de originea coordonatelor . Dacă luăm în considerare funcția $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})\în A}\right\rbrace

este evident că , prin urmare $\int \limits _{0}^{2}\dots \int \limits _{0}^{2}{f(x_{1},\dots ,x_{n})dx_{1}\ puncte dx_{n}}=V(A)>2^{n}$

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

deci există puncte a căror diferență este un punct par al rețelei întregi . Prin proprietățile convexității și simetriei, este ușor să deducem din aceasta că există cel puțin un punct întreg, altul decât . Cu toate acestea, este imposibil de spus care este exact acest punct. ${\overline {x}},{\overline {y}}\in A$ $A$ $(0,\dots ,0)$

Afirmația dovedită se numește teorema lui Minkowski [1] . Dovada descrisă este neconstructivă datorită faptului că folosește principiul Dirichlet.

Geometrie combinatorie

Unele dintre dovezile referitoare la problema Danzer-Grünbaum nu au fost constructive din cauza aplicării metodei probabilistice [2] [3] [4] .

Teoria numerelor

Folosind criteriul Weyl , se poate demonstra că pentru orice succesiune infinită de numere, pentru aproape toate numerele , șirul este distribuit uniform modulo 1 , adică setul de valori pentru care nu este cazul are măsura zero . Cu toate acestea, o astfel de dovadă nu permite un set de excepții (depinde evident de succesiune ). adică este imposibil de înțeles din ea dacă șirul este distribuit uniform pentru un anumit dat . [5] $a_{1}<a_{2}<\dots <a_{n}<\dots$ $\xi \in (0;1)$ ${(a_{n}\xi )}_{n=1}^{\infty )$ $(a_{n})_{n=1}^{\infty )$ ${(a_{n}\xi )}_{n=1}^{\infty )$ $\xi$

Vezi și

Matematică constructivă

Note

↑ Chandrasekharan, 1968 , p. 136-137.
↑ P. Erdos, Z. Furedi. Cel mai mare unghi dintre n puncte din spațiul euclidian d-dimensional // Matematică combinatorie.--Marseille-Luminy, 1981.--P. 275-283; Matematică din Olanda de Nord. Stud.--75.--North-Holland, Amsterdam, 1983 (link inaccesibil) . Preluat la 31 martie 2018. Arhivat din original la 28 august 2018. (nedefinit)
^ D. Bevan, „Sets of Points Determining Only Acute Angles and Some Related Coloring Problems”, Electron. J. Combin., 13:1 (2006), 24 p. . Preluat la 31 martie 2018. Arhivat din original la 2 mai 2018. (nedefinit)
↑ L. V. Buchok, „Despre două abordări noi pentru obținerea estimărilor în problema Danzer-Grunbaum”, Mat. note, 2010, volumul 87, numărul 4, paginile 519-527" . Preluat la 31 martie 2018. Arhivat din original la 12 mai 2018. (nedefinit)
↑ Kuipers, 1963 .

Literatură

K. Chandrasekharan. O introducere în teoria analitică a numerelor . - Lumea, 1968.
Lawrence Kuipers, Harold Niederreiter. Distribuția uniformă a secvențelor. - Mir, 1963. - 407 p.