Ugrás a tartalomhoz

A matematikai logika alkalmazásszemléletű tárgyalása

Pásztorné Varga Katalin, Várterész Magda, Sági Gábor

Panem Kft.

Chapter 1. Matematikai alapfogalmak

Chapter 1. Matematikai alapfogalmak

Különböző dolgokat (tárgyakat, személyeket, fogalmakat, objektumokat stb.) halmazokba sorolhatunk. Az egy halmazba sorolt dolgok a halmaz elemei. Egy halmazban annak minden eleme egyszer fordul elő. Ha h eleme a H halmaznak, akkor erre a hH, ellenkező esetben pedig a hH jelölést használjuk. Egy halmazt megadhatunk úgy, hogy kapcsos zárójelben felsoroljuk az elemeit. Például {h} az a halmaz, amelynek egyetlen eleme h. Megállapodunk abban, ha egy halmaz elemeit felsorolni ugyan nem lehet, de világosan tudunk utalni rájuk, akkor is használjuk ezt a jelölésmódot. Például a {0,1,2,,n,} halmaz a természetes számok halmaza, amit a továbbiakban N0-lal fogunk jelölni. Ha T egy tulajdonság, és minden dolog vagy T tulajdonságú, vagy épp nem, akkor H azon elemei, melyek T tulajdonságúak, szintén halmazt alkotnak, melyet

{ h H | a h elem T tulajdonságú }

formában adunk meg. A K halmaz a H halmaz részhalmaza, jelölve KH, ha K minden eleme eleme H-nak is. Amikor KH és HK, akkor H és K ugyanazon elemeket tartalmazzák, ilyenkor a két halmazt egyenlőnek nevezzük. A halmazok egyenlőségének definíciója miatt pontosan egy olyan halmaz van, amelyiknek nincs eleme. Ezt a halmazt üres halmaznak nevezzük, és jellel hivatkozunk rá. Két halmaz diszjunkt, ha nincs közös elemük. Egy adott H halmaz összes részhalmazai is halmazt alkotnak, melyet Hhatványhalmazának nevezünk, és P(H)-val jelölünk. A halmazelmélet kezdeti szakaszában úgy gondolták, hogy létezik olyan halmaz, amelynek minden ,,elképzelhető” halmaz eleme. Ez a feltételezés azonban ellentmondáshoz vezetett, amit az irodalomban Russell-féle antinómiának neveznek. Szükségünk lehet tehát arra, hogy olyan összességekről beszéljünk, melyekről nem tudjuk, hogy halmazok. Ezeket az összességeket osztályoknak fogjuk hívni.

Dolgokat nemcsak halmazokba gyűjthetünk, hanem fel is sorolhatunk belőlük néhányat. A (h1,h2,,hn)(n1)n-esben egy-egy elem akár többször is szerepelhet. Ha egy n-esben az elemek sorrendje lényeges, rendezett n-esről beszélünk, és azt mondjuk, hogy i a hi elem pozíciója. Két rendezett n-es Hamming-távolsága azon pozícióik száma, ahol az n-esek elemei különböznek. Két n-est akkor tekintünk egyenlőnek, ha Hamming-távolságuk épp 0.

A H1,H2,,Hn(n1) nemüres halmazok Descartes-szorzatának jelölése

H 1 × H 2 × × H n ,

amin azt a halmazt értjük, melynek a (h1,h2,,hn) (hiHi, i=1,2,,n) rendezett n-esek az elemei. A H1,H2,,Hn halmazok Descartes-szorzatának részhalmazai a H1,H2,,Hn halmazokon értelmezett n-változós relációk. Legyen R a H1,H2,,Hn halmazokon értelmezett n-változós reláció és

( h 1 , h 2 , , h n ) H 1 × H 2 × × H n .

Azt mondjuk, hogy R igaz a (h1,h2,,hn) rendezett n-esre, vagy hogy a h1,h2,,hn elemek R relációban vannak, ha (h1,h2,,hn)R. Ha pedig (h1,h2,,hn)R, azt mondjuk, hogy R hamis a (h1,h2,,hn) rendezett n-esre, vagy azt, hogy a h1,h2,,hn elemek nincsenek R relációban. Gyakran foglalkozunk olyan n-változós relációkkal, ahol a H1,H2,,Hn halmazok egyenlőek. Ilyen esetben, a H×H××H szorzatot Hn-nel jelölve, a H halmazokon értelmezett n-változós relációról beszélünk, ami Hn valamely részhalmaza. Az ilyen reláció változóinak számát a reláció aritásának nevezzük. Fontos szerepet játszanak a H halmazon értelmezett kétváltozós vagy binér relációk. Ilyenkor gyakran a (h1,h2)RH2 jelölés helyett azt írjuk röviden, hogy h1Rh2. Azt mondjuk, hogy az R binér reláció

  • reflexív, ha minden hH-ra hRh;

  • irreflexív, ha egyetlen hH-ra sem igaz, hogy hRh;

  • szimmetrikus, ha minden h1,h2H-ra, melyre h1Rh2, fennáll h2Rh1 is;

  • antiszimmetrikus, ha minden h1,h2H-ra, melyre h1Rh2 és h2Rh1, az is igaz, hogy h1=h2;

  • aszimmetrikus, ha egyetlen h1,h2H-ra sem teljesül egyszerre h1Rh2 és h2Rh1;

  • tranzitív, ha minden h1,h2,h3H-ra, melyre h1Rh2 és h2Rh3, teljesül h1Rh3 is;

  • dichotom, ha minden h1,h2H-ra vagy h1Rh2, vagy h2Rh1;

  • trichotom, ha minden h1,h2H-ra vagy h1Rh2, vagy h2Rh1, vagy pedig h1=h2.

A reflexív, szimmetrikus és tranzitív relációkat ekvivalenciarelációknak nevezzük. Ha R ekvivalenciareláció a H halmazon, akkor h1Rh2 esetén azt mondjuk, hogy h1 és h2ekvivalensek egymással. Könnyen látható, hogy egy hH objektummal ekvivalens H-beli elemek halmazában bármely két elem ekvivalens egymással. Az ilyen halmazok az ekvivalenciareláció ekvivalenciaosztályai. Egy H-n értelmezett ekvivalenciareláció ekvivalenciaosztályai nemüres, páronként diszjunkt halmazok, és H minden eleme eleme valamely ekvivalenciaosztálynak.

A reflexív, antiszimmetrikus és tranzitív relációkat gyönge[1] rendezési relációknak nevezzük. A H; pár, ahol H nemüres halmaz, pedig egy gyönge rendezési reláció H-n, gyönge részbenrendezett halmaz. A H;gyönge teljesen rendezett, ha a reláció dichotom is. A H; gyönge rendezett halmaz esetén definiálható egy új reláció: h1h2 pontosan akkor, ha h1h2, de nem igaz, hogy h1=h2. Ez a reláció irreflexív, aszimmetrikus és tranzitív. Az ilyen relációkat erős rendezési relációknak nevezzük, a H; párt pedig erős részbenrendezett halmaznak. A H;erős teljesen rendezett, ha a reláció trichotom is. Ha most a H; erős rendezett halmaz esetén definiálunk egy új relációt úgy, hogy h1h2 pontosan akkor, ha vagy h1h2, vagy h1=h2, az új rendezéssel H gyönge rendezett halmaz lesz. Ezért egy adott rendezett halmaz esetén szabadon fogjuk használni mind a gyönge, mind az erős rendezést, ahogy épp kényelmesebb. Emellett feltételezzük, hogy az átmenet az egyik rendezésből a másikba a fent leírt módon történik. Legyen h1,h2 a H; gyönge részbenrendezett halmaz két tetszőleges eleme. A h1,h2 elemek legnagyobb alsó korlátja vagy infimuma olyan inf {h1,h2}H, melyre

  • inf   { h 1 , h 2 } h 1 , inf {h1,h2}h2, és

  • minden hH-ra, melyre hh1 és hh2, fennáll hinf {h1,h2} is.

A h1,h2 elemek legkisebb felső korlátja vagy szuprémuma ezzel szemben olyan sup {h1,h2}H, melyre

  • h 1 sup   { h 1 , h 2 } , h2sup {h1,h2}, és

  • minden hH-ra, melyre h1h és h2h, fennáll sup {h1,h2}h is.

Nem biztos, hogy egy gyönge részbenrendezett halmaz bármely két elemének létezik legnagyobb alsó, illetve legkisebb felső korlátja, de ha igen, akkor legfeljebb egy legnagyobb alsó és legfeljebb egy legkisebb felső korlátja van. Evidens, hogy ha h1h2, akkor a h1,h2 elemeknek létezik legnagyobb alsó, illetve legkisebb felső korlátja, és az előbbi épp h1, az utóbbi pedig h2. Egy olyan gyönge részbenrendezett halmazt, melyben bármely két elemnek van legnagyobb alsó és legkisebb felső korlátja, hálónak nevezünk. Egy U alaphalmaz részhalmazainak P(U) halmaza például a gyönge rendezési relációval háló.

Jelöljük most a H1,H2,,Hn halmazok Descartes-szorzatát H-val. A H,K halmazokon értelmezett F reláció H-ból K-ba képező n-változós függvény, ha minden hH-hoz legfeljebb egy olyan kK van, amelyre (h,k)F. Egy H-ból K-ba képező függvényre a továbbiakban az F:HK jelölést használjuk. Ha FH-ból az igazságértékek {igaz,hamis} halmazába képez, logikai függvénynek fogjuk nevezni. Tetszőleges RH reláció is felfogható mint logikai függvény, ugyanis legyen (h,igaz)F pontosan akkor, amikor R igaz h-ra, és (h,hamis)F pedig amikor R hamis h-ra. A nem logikai függvényekre – megkülönböztetésül – matematikai függvényként fogunk hivatkozni. Gyakran találkozunk olyan F:HK függvényekkel is, amikor Hi=K, (i=1,2,,n). Az ilyen függvények az n-változós műveletek, és a művelet logikai, ha K={igaz,hamis}, egyébként pedig matematikai. Az n-változós logikai műveleteket szokták n-változós Boole-függvényeknek is nevezni.

Egy tetszőleges F:HK függvény esetén azon H-beli elemek halmazát, melyekre van olyan kK, hogy (h,k)F, az F függvény értelmezési tartományának nevezzük és Dom (F)-fel jelöljük. Ily módon F minden hDom (F) elemhez egy jól meghatározott kK elemet rendel, amit F(h)-val jelölhetünk, és az F függvény h helyen felvett helyettesítési értékének, vagy a h elem képének nevezünk, h-t pedig az F(h)ősképének hívjuk. Az {F(h)|hDom (F)} halmaz az Fértékkészlete, vagy képtere, és Rng (F) jelöléssel hivatkozunk rá. Természetesen Rng (F)K. Az F függvény

  • szürjektív, ha Rng (F)=K;

  • injektív, ha minden olyan h1,h2H-ra, melyre h1h2, fennáll az is, hogy F(h1)F(h2);

  • bijektív vagy kölcsönösen egyértelmű, ha szürjektív és injektív.

Ha F injektív függvény, akkor a Rng (F) képtér minden k eleméhez egyértelműen hozzá tudjuk rendelni az ősképét. Ily módon egy újabb függvényt nyerhetünk, amelynek értelmezési tartománya Rng (F), képtere pedig Dom (F). Ez a függvény az Finverze, és F1-gyel jelöljük.

Gyakran találkozunk olyan függvényekkel, melyek értelmezési tartománya valamely nN0-ra a {0,1,,n} halmaz, vagy maga a természetes számok halmaza. Ha egy ilyen függvény i helyen felvett értékét si-vel jelöljük, akkor s0,s1,,sn, illetve s0,s1, formában adhatjuk meg őket. Ezeket a függvényeket véges, illetve végtelen sorozatoknak szoktuk nevezni.

Legyen F:HnH a H nemüres halmazon értelmezett n-változós művelet. A változók száma a művelet aritása. Tetszőleges hiH(i=1,2,,n) elemekre hi-k a művelet operandusai és F(h1,h2,,hn) a művelet eredménye. Az egy-, illetve kétváltozós, azaz unér, illetve binér műveletek esetén a művelet jelölésére betű helyett gyakran egyéb jelet használunk (pl. +, , , stb.). Ilyenkor a binér műveleti jeleket az operandusok közé szoktuk írni; tehát ha binér művelet H-n, akkor tetszőleges h1,h2H-ra a művelet eredményét h1h2-vel jelöljük. A H-n értelmezett binér művelet lehet

  • asszociatív, ha minden h1,h2,h3H-ra (h1h2)h3=h1(h2h3);

  • kommutatív, ha minden h1,h2H-ra h1h2=h2h1;

  • idempotens, ha minden hH-ra hh=h.

Egy H;M pár, ahol M a H-n értelmezett műveletek egy halmaza, algebrai struktúra. H a struktúra alaphalmaza vagy univerzuma, az M-beli műveletek a struktúra alapműveletei. Ha M véges, elemeit felsorolással is megadhatjuk, ilyenkor a struktúrát a következő módon jelöljük: H;F1,F2,,Fk. Azokat a struktúrákat, melyeknek egy kétváltozós alapművelete van, grupoidoknak nevezzük. Ha ez a művelet asszociatív, akkor a struktúra félcsoport, ha még kommutatív is, kommutatív félcsoport. Ha a H; félcsoportban van olyan eH elem, hogy eh=he=h teljesül minden hH-ra, akkor e a félcsoport neutrális eleme. Egy félcsoportban legfeljebb egy neutrális elem van. Legyen a H; félcsoportban e neutrális elem. Ha a hH elemhez van olyan h*H, hogy h*h=hh*=e, akkor h*-ot hinverzének nevezzük. Az inverz, ha létezik, egyértelmű. A csoport olyan félcsoport, amelyben van neutrális elem, és minden elemnek van inverze. Ha a csoport alapművelete még kommutatív is, Abel-csoportról beszélünk.

Legyenek és kétváltozós műveletek H-n. Azt mondjuk, hogy disztributív-ra nézve, ha minden h1,h2,h3H-ra

( h 1 h 2 ) h 3 = ( h 1 h 3 ) ( h 2 h 3 ) és h 3 ( h 1 h 2 ) = ( h 3 h 1 ) ( h 3 h 2 )

A H;, struktúra gyűrű, ha H; Abel-csoport, H; félcsoport, és disztributív -ra nézve. A H; Abel-csoportot a gyűrű additív csoportjának, a H; félcsoportot a gyűrű multiplikatív félcsoportjának nevezzük. A gyűrű kommutatív, ha a multiplikatív félcsoportja kommutatív. Az additív csoport neutrális elemét a gyűrű nullelemének nevezzük. Ha 0 a H;, gyűrű nulleleme, tetszőleges hH-ra 0h=h0=0. A H;, gyűrű test, ha H; csoport, ahol HH-nak a nullelemtől különböző elemeit tartalmazza. Ez a csoport a test multiplikatív csoportja. A multiplikatív csoport neutrális elemét a test egységelemének nevezzük. A test kommutatív, ha a multiplikatív csoportja kommutatív.

A hálókat az előbb mint olyan gyönge részbenrendezett halmazokat definiáltuk, amelyekben bármely két elemnek van legkisebb felső és legnagyobb alsó korlátja. A hálónak alkalmas definíciója az is, amikor a h1,h2H által egyértelműen meghatározott sup {h1,h2} és inf {h1,h2} elemeket mint a h1 és h2 operandusokkal végrehajtott és binér műveletek eredményét tekintjük. Ugyanis ha a H;, struktúrában a és műveletek kommutatívak, asszociatívak, idempotensek és egymásra nézve abszorptívak, azaz minden h1,h2H-ra

( h 1 h 2 ) h 1 = h 1 és ( h 1 h 2 ) h 1 = h 1 ,

akkor H-n rendezési relációt értelmezhetünk a következő módon:

h 1 h 2 pontosan akkor , ha h 1 h 2 = h 1 , ( vagy h 1 h 2 = h 2 ) .

Ekkor H; háló, amelyben tetszőleges h1,h2H legnagyobb alsó korlátja h1h2 és legkisebb felső korlátja h1h2.

Egy U alaphalmaz esetén említettük, hogy a P(U); gyönge részbenrendezett halmaz háló. Vezessünk most be műveleteket P(U)-n. A H és a KP(U)-beli halmazok uniója vagy egyesítése alatt azt a HK-val jelölt halmazt értjük, amely pontosan azokat az elemeket tartalmazza, melyek a H és a K közül legalább az egyik halmaznak elemei, metszetén vagy közös részén pedig azt a HK-val jelölt halmazt, melynek elemei H-nak is és K-nak is elemei. Könnyen belátható, hogy a bevezetett műveletek kommutatívak, asszociatívak, idempotensek és egymásra nézve abszorptívak, tehát a P(U);, struktúra háló.

Ha két halmaz között van bijekció, akkor a két halmazt mennyiségileg egybevágónakekvivalensnek – tekintjük. Ez a viszony halmazok között reflexív, szimmetrikus és tranzitív. Minden halmazhoz egyértelműen úgy fogunk egy jelet rendelni, melyet a halmaz számosságának nevezünk, hogy az egymással mennyiségileg egybevágó halmazokhoz ugyanazt, az egymással mennyiségileg nem egybevágó halmazokhoz pedig különböző jelet rendelünk. Egy ilyen hozzárendelés nem függvény, hisz egy függvény értelmezési tartománya halmaz. Az ilyen hozzárendelést operációnak nevezzük. Megjegyezzük, hogy a számosságoperáció létezik ugyan, de létezése nem nyilvánvaló, hanem bizonyításra szorul.

Tetszőleges nN0 természetes számra jelölje n_ a {0,1,,n1} halmazt (n=0 esetén 0_ legyen ). Az n_ elemeinek száma n. A H halmazt végesnek tekintjük, és számosságaként rendeljük hozzá n-t, ha van olyan nN0, melyre n_ és H mennyiségileg egybevágó. Ha n és m különböző természetes számok, n_ és m_ mennyiségileg nem egybevágóak. Továbbá N0 egyetlen nN0-ra sem egybevágó mennyiségileg az n_ halmazzal, tehát N0 nem véges, azaz végtelen. Ha egy H halmaz mennyiségileg egybevágó N0-lal, akkor H-t megszámlálhatóan végtelen számosságúnak mondjuk és ezt 0-lal jelöljük. A véges és megszámlálhatóan végtelen halmazok közös neve: megszámlálható halmazok. Belátható az is, hogy P(N0) végtelen, de mennyiségileg nem egybevágó N0-lal. A P(N0)-lal mennyiségileg egybevágó halmazok nem megszámlálhatóak, azt mondjuk, hogy kontinuum számosságúak. Mivel egy halmaz és hatványhalmaza mennyiségileg sosem egybevágó, de a hatványhalmaz egy részhalmazával (pl. az összes egyelemű részhalmazainak halmazával) igen, kézenfekvő a hatványhalmazhoz rendelt számosságot nagyobbnak tekinteni, és így azt kaptuk, hogy bármely halmaznál van nagyobb számosságú halmaz.

A H; erős részbenrendezett halmaz egy 0H elemét null-, vagy legkisebb elemnek hívjuk, ha minden ettől az elemtől különböző hH elemre, 0h teljesül. Hasonlóan, egy 1H elem egység-, vagy legnagyobb elem, ha minden ettől különböző hH elemre fennáll, hogy h1. A H; erős részbenrendezett halmaz egy hminH eleme minimális elem, ha nem létezik hH úgy, hogy hhmin, illetve egy hmaxH eleme maximális elem, ha nem létezik hH úgy, hogy hmaxh. Egy legkisebb elem egyúttal minimális elem, egy legnagyobb elem pedig maximális elem. Nem minden erős részbenrendezett halmaznak van legkisebb, illetve legnagyobb eleme, de ha van, akkor legfeljebb egy legkisebb és egy legnagyobb eleme van. Továbbá minden véges, erős részbenrendezett halmaznak van minimális, illetve maximális eleme, és ilyen elem több is lehet. A Zorn-lemma szerint ha minden KH rendezett részhalmaznak van alsó korlátja, azaz van olyan hKH, melyre hKk tetszőleges hK-tól különböző kK esetén, akkor van H-nak minimális eleme. A H; erős részbenrendezett halmaz jólrendezett, ha minden nemüres részhalmazának van legkisebb eleme. Egy jólrendezett halmaz nyilván teljesen rendezett is.

Legyenek H;H és K;K jólrendezett halmazok. Az F:HK függvény rendezéstartó, ha minden h1Hh2 esetén F(h1)KF(h2). Ha két jólrendezett halmaz között van bijektív rendezéstartó függvény, akkor azt mondjuk, hogy hasonlóak. Ez a viszony a jólrendezett halmazok között reflexív, szimmetrikus és tranzitív. Egy olyan operációt, ami hasonló jólrendezett halmazokhoz ugyanolyan, nem hasonlóakhoz pedig különböző jeleket rendel, rendszámnak nevezünk. Nyilván két hasonló halmaz mennyiségileg egybevágó, tehát számosságuk egyenlő. Mivel bármely két, ugyanannyi elemből álló rendezett véges halmaz egyúttal jólrendezett és hasonló egymáshoz, legyen a rendszámuk a számosságuk. Végtelen jólrendezett halmazra példa N0 a szokásos rendezéssel; ennek és az összes hozzá hasonló halmaznak a rendszámát ω-val jelöljük. Legyen a H;H és a K;K jólrendezett halmazok rendszáma rendre α és β. Ha van olyan a H-hoz hasonló KK halmaz, hogy minden k1K és k2Kk1 esetén k2K is igaz, akkor azt mondjuk, hogy az α rendszám kisebb, mint a β.

Vegyünk egy α rendszámú H;H jólrendezett halmazt, és rakjunk H-ba egy új, mondjuk a k elemet, és legyen minden hH elemre hk. Az így kapott H;H rendezett halmaz szintén jólrendezett, de nem hasonló az eredetihez. Ha H elemeinek száma épp nN0 lenne, akkor az előbbiek miatt rendszáma is n, és H elemeinek száma és rendszáma is n+1. Általában is, ha egy α rendszámú rendezett halmazt egy legnagyobb elemmel bővítünk, jelöljük az új rendezett halmaz rendszámát α+1-gyel. Az α+1 alakú rendszámokat rákövetkező rendszámoknak nevezzük. Azokat a 0-tól különböző rendszámokat, melyek nem rákövetkező rendszámok, limesz rendszámoknak hívjuk. Egy nemüres H;H jólrendezett halmaz rendszáma akkor rákövetkező, ha van legnagyobb eleme, és akkor limesz, ha nincs. Tehát ω limesz rendszám, ω+1 ennek rákövetkezője, majd sorra jönnek egymás rákövetkezői: ω+2, ω+3, …, ω+n, …. A második limesz rendszám ω+ω, vagy másképp jelölve ω2. Ezt a rendszámot rendeljük a két ω rendszámú halmaz ,,egymásután helyezésével” kapott jólrendezett halmazhoz és a hozzá hasonló jólrendezett halmazokhoz. Ezután újra rákövetkező rendszámok jönnek: ω2+1, ω2+2, …, ω2+n, …. Hasonlóan folytatva a gondolatmenetet kapjuk az ωm+n rendszámokat, melyek azon jólrendezett halmazok rendszámai, melyek mω rendszámú jólrendezett halmaz ,,egymásután helyezésével” és ezután n új elem hozzáadásával adódó jólrendezett halmazhoz hasonlóak. Majd újabb limesz rendszám következik: ωω, amit ω2-tel jelölhetünk. Következetesen haladva tovább kapjuk az

ω m a m + ω m 1 a m 1 + + ω a 1 + a 0

alakú rendszámokat, majd folytathatjuk ωω, ωω+1, … stb. Láttuk, hogy véges jólrendezett halmazok rendszámai a természetes számok. A végtelen jólrendezett halmazok rendszámait pedig a természetes számok általánosításának tekintjük és transzfinit számoknak nevezzük.

Később hivatkozni fogunk a transzfinit indukció elvére: Tegyük fel, hogy T olyan rendszámtulajdonság, ami ha minden α-nál kisebb rendszámra igaz, akkor α-ra is igaz. Ekkor T minden rendszámra igaz.

Szükség esetén alkalmazni fogjuk a transzfinit rekurzió elvét is: Ha adott operáció, akkor pontosan egy olyan rendszámokon értelmezett G operáció van, melyre teljesül, hogy minden α rendszámra

G ( α ) = ( { G ( β ) | β α } ) .

Tehát a G operáció α-beli helyettesítési értéke korábbi helyettesítési értékeitől ,, módon” függ. Ilyenkor azt mondjuk, hogy G-t transzfinit rekurzióval származtattuk -ből.

A fák ebben a könyvben több összefüggésben is elő fognak fordulni. Fának fogunk nevezni egy H; párt (és azt mondjuk, hogy hh esetén h megelőzi h-t), ha

  • irreflexív reláció a H halmazon,

  • H -ban van legelső elem (azaz olyan hH, melyre nincs hH, hogy hh lenne),

  • minden ettől az elemtől különböző hH-hoz pontosan egy olyan hH elem van, hogy hh és

  • a H-beli elemek minden olyan h0,h1,h2, sorozata véges, melyre teljesül, hogy hi+1hi.

H elemeit a fa csúcsainak, legnagyobb elemét a fa gyökerének, azokat a csúcsokat pedig, amelyek nem nagyobbak a reláció szerint egyetlen H-beli csúcsnál sem, a fa leveleinek hívjuk. Mélységi számnak vagy szintszámnak nevezzük azt a m:HN0 függvényt[2], amely a gyökérhez 0-t rendel, és minden hh esetén m(h)=m(h)+1. Egy fa véges vagy végtelen aszerint, hogy a H halmaz véges vagy végtelen. Ha hh, a (h,h) rendezett párt h-ból h-be vezető (irányított) élnek nevezzük. Azt is mondjuk, hogy hszülőjeh-nek, illetve hgyermekeh-nak. Egy fa végesen generált, ha minden csúcsának véges számú gyermeke van. Találkozni fogunk olyan végesen generált fákkal is, melyben minden nem levél csúcsnak pontosan két gyermeke van. Ezeket a fákat bináris fáknak nevezzük.

Egy h-ból h-be vezető út csúcsoknak olyan h0,h1,h2,,hn sorozata, melyre h0=h, hn=h, és hihi+1i=0,1,,(n1)-re, és egy ilyen út hosszan. Ha h-ból h-be vezet út, azt is mondhatjuk, hogy hőseh-nek, illetve hutódah-nak. A fa egy ága csúcsoknak olyan h0,h1,h2, sorozata, melyre h0 a fa gyökere, és hihi+1i=0,1,. A fa ágai lehetnek végtelenek, és persze végesek is. König lemmája szerint egy végesen generált végtelen fának van végtelen ága.

A közös szülővel rendelkező csúcsokat egymás testvéreinek nevezzük. Bevezethetünk egy a testvérek sorrendjét kijelölő t relációt is a fán. A t reláció irreflexív H-n, és ha egy h csúcsnak n1 gyermeke van, ezek egyértelműen olyan h1,h2,,hn sorozatba rendezhetők, melyre hihi+1 minden i=1,,n1, és azt mondjuk, hogy hi a h csúcs i-edik gyermeke. A H;,t fát rendezett fának nevezzük.

A fákat gyakran szemléltetjük úgy, hogy a csúcsokat egyszerű geometriai objektumokkal (pont, kör, négyzet stb.) jelöljük. Ha pedig a h csúcs megelőzi h-t (azaz hh), akkor a h csúcsot jelölő objektumból a h csúcsot jelölő objektumba irányuló nyilat rajzolunk. Például legyenek a fa csúcsai {h0,h1,h2,h3,h4,h5}, az élek

{ ( h 0 , h 1 ) , ( h 0 , h 2 ) , ( h 1 , h 3 ) , ( h 1 , h 4 ) , ( h 2 , h 5 ) } .

Ennek a fának a grafikus reprezentációja az alábbi ábrán látható.

Szimbólumoknak tetszőleges nemüres halmazát ábécének, elemeit betűknek nevezzük. Egy ábécé elemeiből álló véges sorozatok a szavak. Egy szó, azaz egy betűsorozat leírásakor nem szoktunk a betűk közé vesszőt írni, tehát például v0v1vn egy szó, ahol v0,v1,,vn az ábécé betűi és nN0. Az egyetlen betűt sem tartalmazó sorozat az üres szó, melynek jelölése λ. A v0v1vn szó kezdőszeletei azok a v0v1vi szavak, melyre in. A v0v1vi szó pedig valódi kezdőszelete a v0v1vn szónak, ha in. Egy V ábécé elemeiből alkotott szavak halmazát V*-gal szokás jelölni. V* elemei az egymás után írásra, azaz a konkatenációra nézve egységelemes félcsoportot alkotnak, ahol az egységelem éppen λ.

A V ábécé feletti (formális) nyelv az ábécé szavainak, V*-nak egy tetszőleges L részhalmaza. A nyelvbe tartozó szavakat a nyelv kifejezéseinek fogjuk nevezni. Fontos kérdés egyrészt, hogyan lehet megadni egy nyelv kifejezéseit. Ha vannak olyan szabályok, melyek megmondják, mely szavak a nyelv kifejezései, akkor ezek összességét a nyelv szintaxisának vagy nyelvtanának nevezzük. Másik fontos kérdés egy nyelvvel kapcsolatban az, hogy mi a nyelv egy-egy kifejezésének a jelentése. A kifejezések jelentését definiáló szabályok halmaza a nyelv szemantikája vagy jelentéstana.

Egy olyan feladatot, amely megoldása egy eldöntendő kérdésre adott (igen-nem) válasz, eldöntésproblémának, a módszert, aminek a segítségével a választ megadjuk döntési eljárásnak nevezzük. Izgalmas kérdés ezzel kapcsolatban az, hogy az eldöntésproblémák egy adott – rendszerint végtelen – osztálya esetén van-e olyan univerzális döntési eljárás, melynek segítségével a problémaosztály minden problémája effektív módon megoldható, azaz eldönthető. Világos, hogy először definiálni kell az effektív eldönthetőség, vagy másképp az effektív kiszámíthatóság fogalmát. Ehhez meg kell keresni az elemi lépéseket, és meg kell határozni ezek egymás utáni alkalmazásának lehetséges módjait. Az 1930-as években több – egymással lényegében egyenértékű – definíciót is adtak az effektív kiszámíthatóság fogalmára. Az egyik az eggyel való továbbszámlálás képességét veszi alapul (rekurzív függvények elmélete), egy másik egy ideális számítógéppel, a Turing-géppel való kiszámíthatóságra épít, később az ún. normál algoritmusok elméletét is kidolgozták. Ezeknek a fogalmaknak a bevezetésére terjedelmi okok miatt nem térünk ki, részletes tárgyalásuk a [21,22,43] könyvekben megtalálható.



[1] [57], 160. oldal.

[2] Vannak mélyebb fák is.