Nem konstruktív bizonyítás

Nem konstruktív bizonyítás ( nem hatékony bizonyítás ) - a matematikai bizonyítások olyan osztálya, amelyek csak egy adott (általában végtelen) halmazban igazolják egy olyan elem létezését, amely kielégíti az adott tulajdonságokat, de nem ad információt az elem egyéb tulajdonságairól, vagyis nem teszi lehetővé sem bemutatását, sem hozzávetőleges leírását . Konstruktívnak nevezzük azokat a bizonyításokat, amelyek egy elem létezését bizonyítják az adott elem megszerzésének módját bemutatva .

Ha a bizonyításban bebizonyosodott egy képlet, amelyben az egyik mennyiség állandó, de értéke nem állítható vissza, akkor ezt a számot hatástalan állandónak nevezzük .

Ezt a fogalmat nem szabad összetéveszteni azzal az esettel, amikor egy állandó (vagy más érdeklődési tárgy) egyszerűen nagyon nehezen fejezhető ki, vagy az ésszerű elvárásokon kívül esik. Például az a bizonyíték, amelyben a Graham-szám szerepel , konstruktív, mert a Graham-szám, bár nagyon nagy, konkrétan leírható.

A nem konstruktív bizonyítások természete

A nem konstruktív bizonyítások általában akkor jönnek létre, ha a bizonyítás során olyan tipikus állításokat és technikákat alkalmaznak, amelyek önmagukban nem konstruktívak. A nem konstruktív bizonyításokat gyakran ellentmondásokkal hajtják végre .

Dirichlet-elv

Sok ilyen bizonyítás a Dirichlet-elv különféle formáin és általánosításain alapul. Önmagában ez az elv

Ha az elemek cellákban helyezkednek el, akkor van egy cella legalább két elemmel $n+1$ $n$

állítja a létezést, de nem engedi megtalálni a kívánt tárgyat.

Ebbe a csoportba tartozik a Markov-egyenlőtlenség és az ebből eredő egyenlőtlenségek közönséges összegekre történő alkalmazása is. Például, ha tudjuk, hogy az összeg elég nagy, és a benne lévő elemek felülről korlátosak ( ), akkor kimutatható, hogy sok olyan elem van, amelynek értéke viszonylag nagy és közel van a -hoz . Ez a "sok" valamilyen elemhalmazt jelent , és ez , ha ezt vagy elemeit tovább használjuk a bizonyításban, a bizonyítást nem építő jellegűvé teszi, mivel nem lehet tudni róla semmit, csak azt, hogy létezik. $\sum \limits _{i=1}^{n}{a_{i}}$ $a_{i}<M$ $M$ $A$ $A$

A Dirichlet-elvhez hasonló megfontolások támasztják alá a valószínűségi módszer aritmetikai alapját , ahol szinte minden bizonyítás nem konstruktív.

A végtelen halmazokra vonatkozó Dirichlet-elv fordított állítása is használható:

Ha véges számú dobozban véges sok nyúl van, akkor minden doboz véges számú nyulat tartalmaz.

Itt a létezés állítása nem merül fel, de fel fog merülni, ha például diszkrét dobozok helyett egy szegmenst és egy függvény értékeit veszünk figyelembe. Ha konvergál, akkor szinte mindenhol konvergál , vagyis annak a pontnak a halmazának, ahol nem konvergál, nulla mértéke van. De erről a halmazról nem mondhatunk semmit, vagyis nem mondhatunk semmit azokról a pontokról, ahol a sorozatok konvergálnak. Bebizonyítottuk, hogy a sorozat szinte mindenhol konvergál, de hogy pontosan hol, az nem világos. Ebben rejlik a konstruktivitástalanság. $(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)))$

Méretkülönbség beállítása

Ha , akkor . $|A|<|B|$ $\exists x\in B:\ x\not \in A$

Ha ezt újrafogalmazzuk a Dirichlet-elv szerint, a következőket kapjuk:

ha a nyulak egy része az egyik ketrecben van, de minden ketrecben legfeljebb egy nyúl van, akkor legalább egy nyúl nincs egy ketrecben sem. $n+1$ $n$

A fentebb leírt példában a sorozatintegrállal csak ezt a technikát alkalmaztuk, de meg kell jegyezni, hogy ennél a technikánál nem mindegy, hogy korábban a halmazok is konstruktívak voltak-e. Még ha egyedileg meghatározottak is voltak, az elem létezése nem konstruktív módon bizonyított (a halmazon belül ). $A$ $B$ $x$ $B$

A létezés előfeltételként való használata

A legtöbb matematikai tétel a „Ha […], akkor […]” elv szerint van megfogalmazva. Ha a mondat első része (premisszája) tartalmaz néhány feltételt, amelyek csak bizonyos tulajdonságokkal rendelkező elemek létezésére vonatkoznak, akkor egy ilyen állítás bizonyítása csak abban az értelemben lehet konstruktív, hogy egyértelműen jelzi a kívánt objektum (létezése) függőségét. amelynek bizonyítása folyamatban van) abból a tárgyból, amelynek létezését feltételezzük . A bizonyítás ilyen értelemben vett konstruktivitása azonban még nem garantálja azon tágabb értelemben vett állítások konstruktivitását, amelyek bizonyítására ezt felhasználják - konstruktivitásának biztosításához biztosítani kell a bizonyítási tulajdonság bizonyításának konstruktivitását is. itt feltételezett létezést.

Például bizonyítsunk be valamilyen állítást bármely folytonos függvényre és valamilyen pontra (például ). A folytonosság definíciója szerint . Ebből könnyű arra következtetni, hogy . Ennek bizonyítása konstruktívnak tekinthető, hiszen a függőség szempontjából értékelhetünk . Ha azonban ezután a bizonyított következményt használjuk valamilyen függvényre , amelyről tudjuk, hogy folytonos, de nem ismerünk egyértelmű függőséget (vagyis a folytonosság nem konstruktív módon bizonyított), akkor egy nem- konstruktív bizonyíték, mivel nem tudjuk helyreállítani és . $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})|<\varepszilon$ $\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$

Példák nem konstruktív bizonyításra

Kiszámíthatóság elmélet

A nem kiszámítható halmaz létezése a halmazok méretbeli különbsége szempontjából a nem konstruktív bizonyítás klasszikus példája.

Az algoritmus fogalmának formalizálása egy időben felvetette a kérdést: van-e természetes számok halmaza, amelyre nincs olyan algoritmus (pontosabban egy Turing-gép ), amely ellenőrzi, hogy egy tetszőleges szám ebbe a halmazba tartozik-e.

Cantor tétele szerint a természetes számok összes részhalmazának számossága egyenlő a kontinuummal . Mivel bármely Turing-gépet véges számú szimbólum ad meg, az összes Turing-gép halmaza megszámlálható .

Mivel a kontinuum nagyobb, mint egy megszámlálható halmaz, és minden algoritmus egy bizonyos kiszámítható halmaznak felel meg, ezért egy bizonyos megszámlálható függvényhalmaz mellett más függvények is kiszámíthatatlannak bizonyulnak. Ezen érvek alapján azonban semmi sem mondható el az elrendezésükről, így egy ilyen bizonyítás nem építő jellegű.

Meg kell jegyezni, hogy egyetlen nem építő jellegű bizonyítás sem zárja ki egy másik, konstruktív bizonyítás lehetőségét . Különösen a nem kiszámítható halmazokra és függvényekre (valamint a rájuk redukálható algoritmikusan eldönthetetlen problémákra) ismert néhány példa, lásd:

Számok geometriája

Legyen adott egy zárt konvex térfogattest , amely szimmetrikus a koordináták origójára nézve . Ha figyelembe vesszük a függvényt ${\displaystyle A\subset {\mathbb {R} }^{n))$ ${\displaystyle 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},\pontok ,2c_{n}+x_{n})\in A}\jobbra\rkapcsos zárójel

nyilvánvaló, hogy ezért $\int \limits _{0}^{2}\dots \int \limits _{0}^{2}{f(x_{1},\dots ,x_{n})dx_{1}\ pontok dx_{n}}=V(A)>2^{n}$

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

tehát vannak olyan pontok, amelyek különbsége az egész rács páros pontja . A konvexitás és a szimmetria tulajdonságain keresztül ebből könnyen kikövetkeztethető, hogy a -n kívül van legalább egy egész pont . Azt azonban nem lehet megmondani, hogy pontosan mi ez a pont. ${\overline {x}},{\overline {y}}\in A$ $A$ $(0,\pontok ,0)$

A bizonyított állítást Minkowski tételének nevezzük [1] . A leírt bizonyítás nem építő jellegű, mivel a Dirichlet-elvet használja.

Kombinatorikus geometria

A Danzer-Grünbaum problémával kapcsolatos bizonyítások egy része a valószínűségi módszer alkalmazása miatt [2] [3] [4] nem volt konstruktív .

Számelmélet

A Weyl-kritérium segítségével kimutatható, hogy tetszőleges végtelen számsorozatnál, szinte minden számnál a sorozat egyenletes eloszlású modulo 1 , vagyis annak az értékhalmaznak, amelyre nem ez a helyzet, nulla mértéke van . Egy ilyen bizonyítás azonban nem tesz lehetővé kivételek halmazát (ez nyilvánvalóan a sorrendtől függ ). vagyis nem lehet megérteni belőle, hogy a sorozat egyenletes eloszlású -e valamilyen adott adott esetén . [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$

Lásd még

Konstruktív matematika

Jegyzetek

↑ Chandrasekharan, 1968 , p. 136-137.
↑ P. Erdos, Z. Furedi. A legnagyobb szög n pont között a d-dimenziós euklideszi térben // Kombinatorikus matematika.--Marseille-Luminy, 1981.--P. 275-283; Észak-Hollandia matematika. Stud.--75.--North-Holland, Amszterdam, 1983 (elérhetetlen link) . Letöltve: 2018. március 31. Az eredetiből archiválva : 2018. augusztus 28.. (határozatlan)
↑ D. Bevan, "Csak akut szögeket meghatározó pontok és néhány kapcsolódó színezési probléma", Electron. J. Combin., 13:1 (2006), 24 p. . Letöltve: 2018. március 31. Az eredetiből archiválva : 2018. május 2. (határozatlan)
↑ L. V. Buchok, „A Danzer-Grunbaum probléma becsléseinek két új megközelítéséről”, Mat. jegyzetek, 2010, 87. kötet, 4. szám, 519-527 . oldal . Letöltve: 2018. március 31. Az eredetiből archiválva : 2018. május 12. (határozatlan)
↑ Kuipers, 1963 .

Irodalom

K. Chandrasekharan. Bevezetés az analitikus számelméletbe . – Világ, 1968.
Lawrence Kuipers, Harold Niederreiter. A sorozatok egyenletes eloszlása. - Mir, 1963. - 407 p.