Ei-rakentava todiste

Ei-konstruktiivinen todistus ( tehoton todistus ) - matemaattisten todisteiden luokka, joka todistaa vain elementin olemassaolon tietyssä (yleensä äärettömässä) joukossa, joka täyttää tietyt ominaisuudet, mutta ei anna mitään tietoa elementin muista ominaisuuksista, eli ei salli sen esittämistä tai likimääräistä kuvaamista. Todistuksia, jotka todistavat elementin olemassaolon esittämällä tavan saada se elementti, kutsutaan konstruktiivisiksi .

Jos todistuksessa on todistettu kaava, jossa yksi suureista on vakio, mutta sen arvoa ei voida palauttaa, niin tätä lukua kutsutaan tehottomaksi vakioksi .

Tätä käsitettä ei pidä sekoittaa tapaukseen, jossa vakio (tai muu kiinnostava kohde) on yksinkertaisesti erittäin vaikea ilmaista tai se jää kohtuullisten odotusten ulkopuolelle. Esimerkiksi todiste, jossa Grahamin luku esiintyy , on rakentava, koska Grahamin luku, vaikka se onkin erittäin suuri, voidaan kuvata tarkasti.

Ei-konstruktiivisten todisteiden luonne

Ei-konstruktiiviset todistukset syntyvät pääsääntöisesti, kun todistuksen aikana käytetään joitain tyypillisiä väitteitä ja tekniikoita, jotka eivät sinänsä ole rakentavia. Usein ei-konstruktiiviset todistukset suoritetaan ristiriidalla .

Dirichlet'n periaate

Monet tällaiset todisteet perustuvat Dirichlet-periaatteen erilaisiin muotoihin ja yleistyksiin. Sinänsä tämä periaate

Jos elementit sijaitsevat soluissa, on solu, jossa on vähintään kaksi elementtiä $n+1$ $n$

väittää olemassaolon, mutta ei salli halutun kohteen löytämistä.

Tähän ryhmään kuuluu myös Markovin epäyhtälön soveltaminen ja siitä johtuvat epäyhtälöt tavallisille summille. Jos esimerkiksi tiedetään, että summa on riittävän suuri ja siinä olevat alkiot on rajattu ylhäältä ( ), niin voidaan osoittaa, että on monia alkioita, joiden arvo on suhteellisen suuri ja lähellä . Tämä "monet" tarkoittaa jotakin elementtijoukkoa, ja tämä , jos sitä tai sen elementtejä käytetään edelleen todistuksessa, tekee todistuksesta ei-konstruktiivisen, koska siitä on mahdotonta tietää mitään muuta kuin sen olemassaoloa. $\sum \limits _{i=1}^{n}{a_{i}}$ $a_{i}<M$ $M$ $A$ $A$

Dirichlet'n periaatteen kaltaiset pohdinnat ovat todennäköisyyspohjaisen menetelmän aritmeettisen perustan taustalla , jossa lähes kaikki todistukset osoittautuvat ei-konstruktiivisiksi.

Dirichlet-periaatteen käänteistä lausetta äärettömille joukoille voidaan myös käyttää:

Jos äärellisessä määrässä laatikoita on äärettömän monta kania, niin jokaisessa laatikossa on äärellinen määrä kaneja.

Tässä ei esiinny olemassaolon väitettä, mutta se syntyy, jos esimerkiksi tarkastelemme segmenttiä ja siinä olevan funktion arvoja diskreettien laatikoiden sijaan. Jos se konvergoi, niin se suppenee lähes kaikkialla , eli joukolla pisteitä, joissa se ei konvergoi, on mitta nolla. Mutta emme voi sanoa mitään tästä sarjasta, mikä tarkoittaa, että emme voi sanoa mitään pisteistä, joissa sarja lähentyy. Olemme osoittaneet, että sarja konvergoi lähes kaikkialla, mutta missä tarkalleen, ei ole selvää. Tässä piilee epäkonstruktiivisuus. $(0;1)$ $\int \limits _{0}^{1}\left({\sum \limits _{i=1}^{\infty }{f_{i}(x)))\right)dx$ ${\displaystyle \sum \limits _{i=1}^{\infty }{f_{i}(x)))$

Aseta kokoero

Jos , niin . $|A|<|B|$ $\exists x\in B:\ x\not \in A$

Jos muotoilemme tämän uudelleen Dirichlet-periaatteen mukaisesti, saamme seuraavan:

jos osa kaneista on jossakin häkissä, mutta kussakin häkissä on enintään yksi kani, ainakaan yksi kani ei ole missään häkissä. $n+1$ $n$

Yllä kuvatussa esimerkissä sarjaintegraalin kanssa käytettiin juuri tätä tekniikkaa, mutta on huomattava, että tässä tekniikassa ei ole väliä, olivatko sarjat myös rakentavia aiemmin. Vaikka ne olisi määritetty yksiselitteisesti, elementin olemassaolo todistettiin ei-konstruktiivisesti (joukon sisällä ). $A$ $B$ $x$ $B$

Olemassaolon käyttö edellytyksenä

Suurin osa matemaattisista lauseista on muotoiltu ”Jos […], niin […]” -periaatteen mukaisesti. Jos tämän lauseen ensimmäinen osa (premissi) sisältää joitain ehtoja, jotka liittyvät vain tiettyjen ominaisuuksien omaavien elementtien olemassaoloon, niin tällaisen väitteen todistus voi olla rakentava vain siinä mielessä, että se osoittaa selvästi halutun objektin riippuvuuden (olemassaolo). josta todistetaan) kohteesta, jonka olemassaolo oletetaan . Todistuksen konstruktiivisuus tässä mielessä ei kuitenkaan vielä takaa niiden laajempien väitteiden konstruktiivisuutta, joiden todistamiseen tätä käytetään - niiden rakentavuuden varmistamiseksi on myös tarpeen varmistaa todisteiden rakentavuus todisteiden omaisuudesta. olemassaolo oletetaan täällä.

Todistetaan esimerkiksi jokin väite mille tahansa jatkuvalle funktiolle ja jollekin pisteelle (kuten ). Jatkuvuuden määritelmän mukaan . Tästä on helppo päätellä, että . Todistusta tästä voidaan pitää rakentavana, koska voimme arvioida riippuvuuden kannalta . Mutta jos sitten käytämme todistettua seurausta jollekin funktiolle , jonka tiedämme olevan jatkuva, mutta emme tiedä selkeää riippuvuutta (eli jatkuvuus todistetaan ei-konstruktiivisesti), niin saadaan epä- rakentava todiste, koska emme voi palauttaa ja . $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$

Esimerkkejä ei-konstruktiivisista todisteista

Lasketettavuusteoria

Ei-laskettavan joukon olemassaolo on klassinen esimerkki ei-konstruktiivisesta todistuksesta joukkojen kokojen erojen suhteen.

Algoritmin käsitteen formalisointi aikoinaan herätti kysymyksen - onko olemassa luonnollisten lukujen joukkoa, jolle ei ole algoritmia (tarkemmin sanottuna Turingin kone ), joka tarkistaisi mielivaltaisen luvun kuulumisen tähän joukkoon.

Cantorin lauseen mukaan luonnollisten lukujen kaikkien osajoukkojen joukon kardinaalisuus on yhtä suuri kuin jatkumo . Koska mikä tahansa Turingin kone on annettu äärellisellä määrällä symboleja, kaikkien Turingin koneiden joukko on laskettavissa .

Koska jatkumo on suurempi kuin laskettava joukko ja jokainen algoritmi vastaa tiettyä laskettavaa joukkoa, niin tietyn laskettavan funktiojoukon lisäksi muut funktiot osoittautuvat laskemattomiksi. Näiden argumenttien perusteella ei kuitenkaan voida sanoa mitään niiden järjestämisestä, joten tällainen todiste ei ole rakentava.

On huomattava, että mikään ei-konstruktiivinen todiste ei sulje pois toisen, rakentavan todisteen mahdollisuutta . Erityisesti joitakin esimerkkejä ei-laskettavissa olevista joukoista ja funktioista (sekä algoritmisesti ratkaisemattomista ongelmista, jotka voidaan pelkistää niihin) tunnetaan edelleen, katso:

Numeroiden geometria

Olkoon suljettu kupera tilavuuskappale , joka on symmetrinen koordinaattien origon suhteen . Jos otetaan huomioon funktio ${\displaystyle A\subset {\mathbb {R} }^{n))$ ${\displaystyle V(A)>2^{n))$

f(x_{1},\dots ,x_{n})=\#\left\lsulku {(c_{1},\dots ,c_{n})\in {\mathbb {Z} _{ n}}:(2c_{1}+x_{1},\pisteet ,2c_{n}+x_{n})\in A}\oikea\rhaulu

on selvää, että siksi $\int \limits _{0}^{2}\dots \int \limits _{0}^{2}{f(x_{1},\dots ,x_{n})dx_{1}\ pisteet dx_{n}}=V(A)>2^{n}$

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

joten on pisteitä , joiden ero on kokonaislukuhilan parillinen piste . Tästä on helppo päätellä kuperuuden ja symmetrian ominaisuuksien kautta, että on olemassa ainakin yksi muu kokonaislukupiste kuin . On kuitenkin mahdotonta sanoa, mikä tämä kohta on. ${\overline {x}},{\overline {y}}\in A$ $A$ ${\näyttötyyli (0,\pisteet ,0)}$

Todistettua väitettä kutsutaan Minkowskin lauseeksi [1] . Kuvattu todistus ei ole rakentava, koska se käyttää Dirichlet-periaatetta.

Kombinatorinen geometria

Jotkut Danzer-Grünbaum-ongelmaa koskevista todisteista eivät olleet konstruktiivisia todennäköisyyslaskentamenetelmän [2] [3] [4] vuoksi .

Numeroteoria

Weyl-kriteerin avulla voidaan osoittaa, että mille tahansa äärettömälle numerosarjalle, melkein kaikille luvuille , sarja on jakautunut tasaisesti modulo 1 , eli arvojoukolla, jolle näin ei ole, on mitta nolla . Tällainen todiste ei kuitenkaan salli joukkoa poikkeuksia (se riippuu tietysti sekvenssistä ). eli siitä on mahdotonta ymmärtää, onko sekvenssi jakautunut tasaisesti jollekin tietylle annetulle . [5] $a_{1}<a_{2}<\dots <a_{n}<\dots$ $\xi \in (0;1)$ ${\displaystyle {(a_{n}\xi )}_{n=1}^{\infty ))$ ${\displaystyle (a_{n})_{n=1}^{\infty ))$ ${\displaystyle {(a_{n}\xi )}_{n=1}^{\infty ))$ $\xi$

Katso myös

Rakentavaa matematiikkaa

Muistiinpanot

↑ Chandrasekharan, 1968 , s. 136-137.
↑ P. Erdos, Z. Furedi. Suurin kulma n pisteen joukossa d-ulotteisessa euklidisessa avaruudessa // Kombinatorinen matematiikka.--Marseille-Luminy, 1981.--P. 275-283; Pohjois-Hollannin matematiikka. Stud.--75.--Pohjois-Hollanti, Amsterdam, 1983 (pääsemätön linkki) . Haettu 31. maaliskuuta 2018. Arkistoitu alkuperäisestä 28. elokuuta 2018. (määrätön)
↑ D. Bevan, "Pistejoukot, jotka määrittävät vain akuutteja kulmia ja joitain niihin liittyviä väritysongelmia", Electron. J. Combin., 13:1 (2006), 24 s. . Haettu 31. maaliskuuta 2018. Arkistoitu alkuperäisestä 2. toukokuuta 2018. (määrätön)
↑ L. V. Buchok, "Kahdesta uudesta lähestymistavasta arvioiden saamiseksi Danzer-Grunbaumin ongelmassa", Mat. muistiinpanot, 2010, osa 87, numero 4, sivut 519-527" . Haettu 31. maaliskuuta 2018. Arkistoitu alkuperäisestä 12. toukokuuta 2018. (määrätön)
↑ Kuipers, 1963 .

Kirjallisuus

K. Chandrasekharan. Johdatus analyyttiseen lukuteoriaan . – Maailma, 1968.
Lawrence Kuipers, Harold Niederreiter. Sekvenssien tasainen jakautuminen. - Mir, 1963. - 407 s.