Rekurzív

Az Unciklopédiából


Senilissimus prof. könyvének fülszövege[szerkesztés]

Egy idős tudós, aki a rekurzív gondolkodásról írt könyveket és egy kicsit már szenilis volt a könyvesboltban nézegette az új könyveket. Az egyik nagyon megtetszett neki és ezt gondolta:

– Pont egy ilyen könyvet akartam én is írni.

Megnézte a könyv hátulján lévő ajánló sorokat és meglepetésére ott ezt olvasta:

Legutóbb mikor a könyvesboltban az új könyveket nézegettem, kezembe akadt ez a könyv. Nagyon megtetszett és akkor azt gondoltam, pont ilyen könyvet akartam én is írni. Megnéztem a könyv hátulján lévő ajánló sorokat és meglepetésemre, pont ezeket a sorokat olvastam ott. Gyorsan megfordítottam a könyvet és a címlapján megláttam a saját nevem. Hoppá! Ezt a könyvet én írtam! - kiáltottam.

Ekkor az író gyorsan megfordította a könyvet és a címlapján meglátta a saját nevét. – Hoppá! Ezt a könyvet én írtam! – kiáltott fel.

Legközelebb, mikor bement a kiadójába a szerkesztő megkérdezte tőle:

– A következő könyvének hátlapjára is ugyanazt az ajánló szöveget írjuk, mint az eddigiekre?

– Nem – mondta az tudós – Most írjuk helyette ezt. – és átadta a szerkesztőnek ezt a papírlapot.

Forrás[szerkesztés]

Forrás: kömal fórum; viccek topik; 61. hozzászólás.

Tallózás Senilissimus prof. könyvéből[szerkesztés]

A rekurzív bizonyítás 1. egzisztenciatétele[szerkesztés]

1. tétel: Bizonyítsuk be, hogy van olyan bizonyítás, ami önrekurzív, azaz hivatkozik önmagára !

Bizonyítás:

  1. Tegyük fel indirekte, hogy egy bizonyítás sem önrekurzív.
  2. Akkor tehát ez a bizonyítás sem lenne az.
  3. De az, mert a 2. pontban hivatkozik magára.
  4. Ez ellentmondás.
  5. Tehát van olyan bizonyítás, ami önrekurzív. Q.E.D.

Nagyszerű, de természetes módon felmerül a kétely: hátha a fenti, meglehetősen erőltetett bizonyítás jelenti az egyetlen példát a rekurzív gondolkodás alkalmazhatóságára. Nem így van, amint azt a következő tétel is mutatja:

A rekurzív bizonyítás 2. egzisztenciatétele[szerkesztés]

2. tétel: Létezik még egy bizonyítás a fentin kívül, ami rekurzív.

Bizonyítás:

  1. Tegyük fel indirekte, hogy nem.
  2. Ekkor a fenti az egyetlen rekurzív bizonyítás.
  3. Tehát jelen a bizonyítás nem rekurzív.
  4. De az, hiszen a 3. pontban hivatkozik magára.
  5. Ismét ellentmondásra jutottunk. Ezért létezik még rekurzív bizonyítás, ami eltér a fentitől.
  6. Q.E.D.

A rekurzív bizonyítás 3., 4., s.í.t. egzisztenciatétele[szerkesztés]

- Az Olvasóra hagyjuk.

Irreflexív rekurzió[szerkesztés]

A fenti bizonyítások közös jellemzője, hogy tkp. saját maguk létét bizonyítják. Ezáltal persze nem lesznek túl érdekes objektumok. Felmerül a kérdés, létezik-e olyan rekurzív bizonyítás, amiből következik valami másnak a léte is, mint az illető rekurzív bizonyítás?

Definíció: Egy rekurzív egzisztenciabizonyítást reflexívnek nevezünk, ha egy bizonyítási osztály nemürességét saját megkonstruálódásával bizonyítja, úgy értve, hogy hogy az osztály nemürességét úgy bizonyítja, hogy példaként saját magát mutatja fel, mint ami ez osztályba tartozik. Ellenkező esetben, ha az illető bizonyítás nem tartozik abba az osztályba, amelynek ürességét igazolja, akkor irreflexív bizonyításról beszélünk.

Tétel: Létezik irreflexív rekurzív bizonyítás.

Bizonyítás:

  1. Tegyük fel indirekte, hogy nem létezik.
  2. Ekkor jelen bizonyítás reflexív, azaz belőle legfeljebb csak önmaga léte következik.
  3. Ezáltal viszont nem igaz a fenti tétel, hogy létezik irreflexív bizonyítás.
  4. Tehát jelen bizonyítás eddigi részére szorítkozva, ez vagy nem is bizonyítás (hiszen nem bizonyítja a tételt), vagy nem reflexív.
    1. Ha nem bizonyítás, akkor kell hogy legyen egy hamis mondata. De minden eddigi mondatunk vagy indirekt feltevés, vagy feltételes logikai következtetés. Ha a feltevések igazak, akkor a konklúziók is, vagyis hamis mondat csak úgy lehet, ha az egyik feltevés hamis. Tehát nem-bizonyítás csak úgy lehet, ha az egyik indirekt feltevés hamis. Két ilyen van, az egyik: hogy nem létezik irreflexív bizonyítás, ha ez hamis, kész vagyunk (és így ez mégis csak egy bizonyítás), van irreflexív bizonyítás. A másik: hogy ez nem is bizonyítás. Ha ez hamis, akkor mégis csak bizonyítás, és így jelen bizonyítás nem reflexív (3. miatt), tehát irreflexív.
    2. Semmilyen módon nem lehet tehát, hogy ez nem egy bizonyítás. Ergo, ez egy bizonyítás, és ekkor az indirekt feltevésből következően, nem reflexív, hanem irreflexív.
    3. De ha nem reflexív, akkor ellentmondunk 2.-nek, amely következik 1.-ből. Ergo, nem marad más, minthogy 1. hamis. Az ellenmondásra vezető indirekt feltevést megcáfoltuk: létezik irreflexív bizonyítás.

Érdekesség, hogy elvileg lehetetlen, hogy a fenti tételt konstruktív úton bizonyítsuk, mert ha a tételt, az irreflexív bizonyítás (IB) létét úgy bizonyítanánk, hogy megkonstruálunk egy K irreflexív bizonyítást, akkor ez egy olyan bizonyítás lenne, amely a saját osztályának nemürességét bizonyítaná, tehát definíció szerint reflexív lenne. Ergo nem is bizonyítaná, hogy létezik irreflexív bizonyítás, azaz nem lenne bizonyítás. Ez azt jelenti, hogy a fenti, konstruktív bizonyítás bizony reflexív, hisz ha irreflexív lenne, akkor eleme lenne az általa bizonyított osztálynak, azaz reflexív és nem irreflexív bizonyítás lenne.

A rekurzív végtelenség tétele[szerkesztés]

3. tétel: A rekurzív bizonyítások halmaza végtelen.

  1. Tegyük fel indirekte, hogy nem. Ekkor létezik az összes rekurzív bizonyítások véges S= s1,s2,...,sr sorozata, ahol r természetes szám.
  2. Tekintsük a következő A1 állítást: "Jelen bizonyítás tagja S-nek". Ez igaz állítás, mert a 2. pontban hivatkoztunk jelen bizonyításra.
  3. Tekintsük a következő, A2 állítást: "Az az állítás, hogy jelen bizonyítás tagja S-nek, igaz". Ez az állítás igaz 3. miatt, az 1., 2. és 3. állítások közösen anak rekurzív bizonyítása.
  4. Tekintsük a következő, A3 állítást: „Az az állítás, hogy az az állítás, hogy jelen bizonyítás tagja S-nek, igaz, igaz.” Ez az állítás igaz 4. miatt, az 1., 2., 3., és 4. állítások közösen annak rekurzív bizonyítása.
  5. S.í.t. haladunk, így egy végtelen An állítássorozatot kapunk, és jelen bizonyítás pontjai 1.-től n+1-ig az An n.-edik állítás bizonyítása.
  6. Így egy végtelen rekurzív bizonyítássorozat adódik.
  7. Ez ellentmond az indirekt feltételnek. Ergo, az hamis.
  8. Ergo, a rekurzív bizonyítások valóban végtelen sokan vannak.- Q.E.D.

Parciálisan és totálisan rekurzív bizonyítások[szerkesztés]

Definíció: Az A és B bizonyítások konjunkciójának (logikai összegének vagy soros kapcsolásának) nevezzük az A és B által bizonyított állítások konjunkciójának bizonyítását. Hasonlóan értelmezhető tetszőleges sok bizonyítás, bizonyítások tetszőleges U halmazának +U-val jelölt összege is.

Példa: legyen A' az az állítás, hogy "Peti lement a boltba tegnap", B' pedig, hogy "Peti zenét hallgatott tegnap." Ekkor az A' és B' állítások A'+B'-vel jelölt konjunkciója pedig az az állítás, hogy "Peti lement a boltba tegnap és zenét is hallgatott tegnap." Ha A az A', B a B' állítás bizonyítása, akkor az A+B bizonyítást úgy kapjuk, hogy előbb bebizonyítjuk A'-t, majd bebizonyítjuk B'-t, majd vesszük a két bizonyítás állításainak összességét. Vagyis A+B bizonyítása az A' meg a B' bizonyítását kitevő mondatok összesített halmaza.

Definíció: Egy rekurzív bizonyítást totálisan rekurzívnak nevezzük, ha valamely mondata úgy rekurzív, hogy igazságának teljesüléséhez szükséges a bizonyítás mindegyik más mondatára is, azaz a bizonyítás mondatainak összességére hivatkoznia. Nem elég csak a mondatok egy valódi részhalmazára visszahivatkozni. ellenkező esetben a rekurzív bizonyítást parciálisan rekurzívnak nevezzük.


Egy feltételezett bizonyítás totalitásához három feltételt kell ellenőrizni:

  1. a "bizonyítás" egy bizonyítás, azaz olyan mondathalmaz, melynek minden mondata igaz (utóbbit konkrét esetben nem szükséges bizonyítani, csak a végességet); kivéve természetesen azokat, melyeket indirekte teszünk fel és cáfolunk.
  2. a "bizonyítás" rekurzív, azaz tartalmaz önhivatkozó vagy kölcsönösen egymásra hivatkozó mondatokat;
  3. a "bizonyítás", mint rekurzív mondathalmaz, totálisan rekurzív.

Hogy ez a fogalom értelmes, azt a következő tétel biztosítja:

Tétel: Létezik véges (ti. véges sok mondatból álló), totálisan rekurzív bizonyítás.

Bizonyítás:

  1. Tekintsük a fenti állítás bizonyítását, azaz jelen, "T" jelűre keresztelt bizonyítást (ez létezik, minthogy itt van megkonstruálva). Ez rekurzív jelen, T bizonyítás 1. pontja miatt, amely jelen mondatban hivatkozik T-re; de mivel van legalább egy másik mondata is (a 2.) és az nem hivatkozik az 1.-esre (akkor is igaz, ha a jelen, 1.-es esetleg nem), nem feltétlenül totális. Tehát a fentemlített három feltétel közül a második teljesül.
  2. Ezen bizonyítás valóban véges mondathalmaz (mert a 3. mondattal befejeződik), tehát ha totálisan rekurzív, akkor végesen totálisan rekurzív.
  3. Legyen e bizonyítás összes mondata T := (S1,S2,S3). Ha T nem lenne totálisan rekurzív, akkor egyik mondata sem lenne olyan, hogy T-re mint egészre, az összes mondat konjunkciójára hivatkozna. Mármost melyik állítás az igaz: U: "T egyik mondata sem ilyen", vagy nem-U: "T egyik mondata ilyen"? Az első állítás semmiképp sem lehet igaz, mert ez olyan mondat, ami T összes mondatára hivatkozik, tehát ellentmond önmagának, mert ha igaz lenne, az U mondat olyan mondat lenne, ami cáfolata lenne saját magának, U-nak. tehát nem-U az igaz. Tehát T egyik mondata (mégpedig nem-U), éppen olyan, mint amilyen mondat létét a nem-U mondat állítja. Ergo, a fentebb említett három feltételből a harmadik, a totalitás, teljesül.
  4. Q.E.D.

Lásd még[szerkesztés]