Á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.

Tartalomjegyzék

1 Az eredeti argumentum
2 Az általános módszer
- 2.1 Megjegyzések
3 Néhány alkalmazás
4 Külső hivatkozások

[szerkesztés] 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. ■

[szerkesztés] Az általános módszer

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 i ∈ A-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 i ∈ A-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 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. ■

[szerkesztés] Megjegyzések

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

[szerkesztés] 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

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"

[szerkesztés] 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 primtí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.

[szerkeszté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ítnak 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.

[szerkesztés] Külső hivatkozások

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.

Kategóriák: Halmazelmélet | Logika

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Átlós eljárás

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

Tartalomjegyzék

[szerkesztés] Az eredeti argumentum

[szerkesztés] Az általános módszer

[szerkesztés] Megjegyzések

[szerkesztés] 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] Primitív rekurzív aritmetikai függvények univerzális függvénye

[szerkesztés] Russell-tétel/Russell-paradoxon

[szerkesztés] Külső hivatkozások

Views

Navigáció

részvétel

Keresés

Más nyelveken