Átlós eljárás

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

• Tétel – Cantor 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 (x_k) sorozatba (illusztrációként közlünk egy példasorozatot):

x₁ = 0 , 5 1 0 5 1 1 0 …

x₂ = 0 , 4 2 3 2 0 4 3 …

x₃ = 0 , 8 2 4 5 0 2 6 …

x₄ = 0 , 2 3 3 0 1 2 6 …

x₅ = 0 , 4 1 0 7 2 4 6 …

x₆ = 0 , 9 9 3 7 8 3 8 …

x₇ = 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 x_k^k-val!

x₁ = 0 , 5 1 0 5 1 1 0 …

x₂ = 0 , 4 2 3 2 0 4 3 …

x₃ = 0 , 8 2 4 5 0 2 6 …

x₄ = 0 , 2 3 3 0 1 2 6 …

x₅ = 0 , 4 1 0 7 2 4 6 …

x₆ = 0 , 9 9 3 7 8 3 8 …

x₇ = 0 , 0 1 0 5 1 3 5 …

…

Legyen (y_k) az a számjegyekből álló sorozat, melynek k-adik eleme 2, ha x_k^knem egyenlő kettővel és 1, ha x_k^k=2. Legyen r az a valós szám, melynek egész része 0, tizedesjegyei pedig az (y_k) 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 (x_k) 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

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

$\varrho \subseteq A\times A$

reláció és

$\varrho \text{*}:A\times A\to \{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á

$𝒞:=\{f_i:A\to \{0,1\}\mid i\in A\}$

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

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

Ekkor a

$g:A\to \{0,1\};i\mapsto 1-\varrho \text{*}(i,i)$

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

$g\notin 𝒞.$

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

$f_i(i)=\varrho \text{*}(i,i)\ne 1-\varrho \text{*}(i,i)=g(i)$

azaz C minden eleme legalább egy értékben (éspedig f_i 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

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

Cantor tétele a valós számok számosságának megszámlálhatatlanságáról

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

$A=\mathbb{N}$

$\varrho (k,l)\iff$ "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

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 ellentmondás.

Russell-tétel/Russell-paradoxon

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

• A végtelenen túl, YOUPROOF
• Az Encyclopaedia of Mathematics Diagonal process szócikke
• A MathWorld Cantor Diagonal Method szócikke
• Georg Cantor, Uber ein elementare Frage der Mannigfaltigkeitslehre, in Deutsche Mathematiker-Vereinigung (1890-1) és az angol fordítás. Az első cikk, melyben az átlós eljárás egy bizonyítás alapja.