Ugrás a tartalomhoz

Átlós eljárás

Ellenőrzött
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]
  • 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]

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

reláció és

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á

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

.

Ekkor a

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

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

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]
  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]

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

[szerkesztés]

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

"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]

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ü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

Definiáljuk a

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:

Node ekkor az helyettesítéssel:

Ami ellentmondás.

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

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):

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]