Átlós eljárás

A Wikipédiából, a szabad enciklopédiából

Az átlós eljárás vagy diagonális módszer a matematika egy Cantor által alkalmazott bizonyítási metódusa. Leggyakrabban a rekurzív függvények matematikájában alkalmazzák olyan esetekben, amikor azt szeretnék igazolni, hogy egy univerzális kiszámítási tulajdonsággal rendelkező függvény nem eleme annak a függvényosztálynak, melynek kiszámítására hivatott. Természetesen a módszer a matematika más területein is alkalmazható. Cantor eredetileg arra használta, hogy bebizonyítsa, hogy a valós számok halmazának számossága nagyobb a természetes számok számosságánál.

Az eredeti argumentum[szerkesztés | forrásszöveg szerkesztése]

  • TételCantor tétele a valós számok számosságának nem megszámlálható voltáról – A (0,1) intervallum valós számainak halmaza és a természetes számok halmaza nem azonos számosságú.

Bizonyítás. Indirekten bizonyítunk. Tegyük fel, hogy a (0,1) intervallum összes valós száma felsorolható egyetlen sorozatban. Térjünk át a valós számok tizedestört alakjára, mely egyértelmű, amennyiben feltesszük, hogy az egy helyiérték után "csupa kilencest" tartalmazó tizedestört alakokat azonosítjuk – a szokásos módon – a véges tizedestörtekkel (melyek "csupa nullával" alakíthatók át végtelen számjegylánccá). Például 0,1239999… = 0,124000… Soroljuk fel a (0,1) intervallum valós számait egyetlen (xk) sorozatba (illusztrációként közlünk egy példasorozatot):

x1 = 0 , 5 1 0 5 1 1 0 …
x2 = 0 , 4 2 3 2 0 4 3 …
x3 = 0 , 8 2 4 5 0 2 6 …
x4 = 0 , 2 3 3 0 1 2 6 …
x5 = 0 , 4 1 0 7 2 4 6 …
x6 = 0 , 9 9 3 7 8 3 8 …
x7 = 0 , 0 1 0 5 1 3 5 …

Tekintsük a k-adik valós szám k-adik tizedesjegyét, jelöljük ezt xkk-val!

x1 = 0 , 5 1 0 5 1 1 0 …
x2 = 0 , 4 2 3 2 0 4 3 …
x3 = 0 , 8 2 4 5 0 2 6 …
x4 = 0 , 2 3 3 0 1 2 6 …
x5 = 0 , 4 1 0 7 2 4 6 …
x6 = 0 , 9 9 3 7 8 3 8 …
x7 = 0 , 0 1 0 5 1 3 5

Legyen (yk) az a számjegyekből álló sorozat, melynek k-adik eleme 2, ha xkknem egyenlő kettővel és 1, ha xkk=2. Legyen r az a valós szám, melynek egész része 0, tizedesjegyei pedig az (yk) sorozat elemeiből áll. (Példánkban

r = 0, 2 1 2 2 1 2 2 … )

Világos, hogy az r szám k-adik tizedesjegye különbözik a k-adik valós szám k-adik tizedesjegyétől. r tehát különbözik az összes felsorolt számtól, azaz nem tagja az (xk) sorozatnak. Ám r kétségkívül valós szám, így feltételünk szerint szerepelnie kellene a felsorolásban, azaz ellentmondásra jutottunk.

Az általános módszer[szerkesztés | forrásszöveg szerkesztése]

TételÁtlós eljárás – Legyen A halmaz,

\varrho\subseteq A\times A

reláció és

\varrho\mbox{*}:A\times A\rightarrow \{0,1\}

a ρ reláció karakterisztikus függvénye (azaz az A minden x illetve y elemére ρ*(x,y) = 1, ha x ρ y teljesül és ρ*(x,y) = 0, ha x ρ y nem áll fenn). Legyen továbbá

\mathcal{C}:=\{f_i:A\rightarrow\{0,1\} \mid i\in A\}

olyan függvényrendszer, melynek elemeit a ρ* reláció projekciói előállítanak, azaz minden iA-ra:

\varrho\mbox{*}(i,.)=f_i.

Ekkor a

g:A\rightarrow \{0,1\};\;\; i\mapsto 1-\varrho\mbox{*}(i,i)

diagonális függvényt nem állítja elő a ρ egyetlen projekciója sem, azaz

g\notin \mathcal{C}.

Bizonyítás. g definíciója és C elemeinek tulajdonsága folytán minden iA-ra:

f_i(i)=\varrho\mbox{*}(i,i)\neq 1-\varrho\mbox{*}(i,i)=g(i)

azaz C minden eleme legalább egy értékben (éspedig fi az i-hez tartozó értékben) különbözik g-től, így g nem lehet egyenlő egyetlen C-beli elemmel sem, azaz g nem lehet eleme C-nek. ■

Megjegyzések[szerkesztés | forrásszöveg szerkesztése]

  1. A tétel tulajdonképpen nem meglepő. C számossága – tekintve, hogy A elemivel van indexelve – legfeljebb |A|, míg az összes A-n értelmezett {0,1}-be érkező függvény halmaza 2|A| számosságú, mely a Cantor-tétel következményeként nagyobb számosságú mint |A|. Kell tehát, hogy legyen C elemeitől különböző A-n értelmezett {0,1}-be érkező függvény.
  2. Másrészt viszont figyeljünk fel arra, hogy szemben az |A| < 2|A| egyenlőtlenséggel a tétel „konstruktív” módon igazol egy C-n kívüli függvény létezését, abban az értelemben, hogy megadja a hozzárendelési utasítását is. Ez hasznos lehet abban az esetben, amikor ρ nemcsak halmazelméleti reláció, hanem megfeleltethető valamely formális nyelv egy kétváltozós predikátumának is, így C egy formulaséma elemeit is jelentheti. Ekkor g szintén formalizálható és nem csak mint halmazelméleti függvény létezhet, hanem mint formális nyelvi függvény is. Ezzel a tétel páratlanul erős jelentést nyer és alapjául szolgál a halmazelmélet nyelvfilozófiai problémáit eredményező Löwenheim-Skolem-paradoxonnak.
  3. Az előbb említett konstruktív bizonyítási mód teszi rendkívül erőssé Gödel első nemteljességi tételét is, hiszen elvileg ott is egy számítógép segítségével megkereshető a se nem levezethető, se nem cáfolható G mondat. Az egyetlen probléma az, hogy a mondatot megkereső programhoz nem tudunk egy olyan N természetes számot mondani, melyről kijelenthetjük, hogy a gép legfeljebb N lépésben megtalálja G-t. Adott esetben a program nem áll le véges lépésben, illetve nem lévén felső korlátja N-nek tetszőleges formális nyelv esetén nem tudjuk meddig húzódik el a keresés. (Konkrét elméletben persze ez az N esetleg megtalálható.) Ez azért van, mert a Gödel-tétel bizonyításában szereplő lépésekben ugyan rekurzív függvényekkel van dolgunk, de nem feltétlenül primitív rekurzív függvényekkel. Ez az oka annak, hogy az intuicionista matematikát (és a taiti finit matematikát) a Gödel-tétel hatása nem érinti.

Néhány alkalmazás[szerkesztés | forrásszöveg szerkesztése]

Cantor tétele a valós számok számosságának megszámlálhatatlanságáról[szerkesztés | forrásszöveg szerkesztése]

Ebben a tételben a következő szereposztásban jelentkezik az átlós módszer:

A=\mathbb{N}
\varrho(k,l)\Leftrightarrow "a k-adik valós szám l-edik tizedesjegye egyenlő kettővel"

Az átlós eljárás egy valós számot definiál:

(a g-ből képzett) r = "az a valós szám, melynek k-adik tizedesjegye 2, ha a k-adik valós szám k-adik tizedesjegye nem 2 és 1, ha a k-adik valós szám k-adik tizedesjegye 2"

Primitív rekurzív aritmetikai függvények univerzális függvénye[szerkesztés | forrásszöveg szerkesztése]

A k változós primitív rekurzív függvényekhez nincs k + 1 változós univerzális primitív rekurzív függvény.

Legyenek ugyanis az f_i függvények (i ∈ N) a k változós primitív rekurzív függvények és legyen g olyan k + 1 változós primitív rekurzív függvény, hogy

f_i=g(\,.\,,i)

Definiáljuk a

h:=g(x_1,x_2,x_3, ... ,x_k,x_k)+1\,

függvényt (tehát az utolsó változója helyére ugyanazt kell helyettesíteni, mint az utolsó előtti változójába). Ekkor h egy k változós primitív rekurzív függvény, így g valamely i-vel előállítja a következőképpen:

h=g(\,.\,,i)

Node ekkor az x_k=i helyettesítéssel:

g(x_1,x_2,...,i,i)=h(x_1,x_2,x_3, ... ,i)=g
(x_1,x_2,x_3, ... ,i,i)+1\,

Ami (szerencsére) ellentmondás.

Russell-tétel/Russell-paradoxon[szerkesztés | forrásszöveg szerkesztése]

A sztenderd halmazelmélet szerint egy A nemüres halmaz minden eleme szintén halmaz. Értelmes (sőt alapvető) ekkor az A halmaz feletti

\varrho:=\{(x,y)\in A\times A \mid x\in y\}

reláció, illetve ennek ρ* karakterisztikus függvénye. Szemléletünk számára a ρ* "reláció" projekciói előállítják A azon elemeit, melyek A-beli elemekből állnak. Érdekes következménye ekkor az átlós eljárásnak, hogy létezik A-nak olyan valódi részhalmaza, melyet ρ* projekciói nem állítanak elő (azaz nem csak A-beli elemekből áll):

R=\{x\in A \mid x\notin x\}

Különösen érdekes ez akkor, ha feltételezzük, hogy létezik olyan halmaz, melynek minden halmaz halmaza. Ha A ez az univerzum, akkor az átlós eljárás következményeként egyenesen ellentmondásra jutunk, hiszen ekkor létezne olyan halmaz, mely nem eleme A-nak, azaz az összes halmaz halmazának. Az átlós eljárás tehát a Russell-paradoxon Zermelo-Fraenkel-halmazelméletbeli magyarázatául szolgál.

További információk[szerkesztés | forrásszöveg szerkesztése]