Főmenü megnyitása

A Peano-aritmetika elsőrendű nyelveSzerkesztés

Rövidítések
 

A Peano-aritmetika nyelve a következő nem logikai jeleket tartalmazza:

  • A nullának megfelelő konstans jel:  
  • A rákövetkezésnek megfelelő egyváltozós függvényjel: 
  • Az összeadásnak megfelelő kétváltozós műveleti jel:  
  • A szorzásnak megfelelő kétváltozós műveleti jel:  

Peano-féle axiómák és axiómasémákSzerkesztés

  1.   – A nulla semminek sem rákövetkezője.
  2.   – Amiknek a rákövetkezői is azonosak, azok maguk is azonosak. (Azaz   injektív.)
  3.   – A nullával jobbról való összegzés hatástalan. (Azaz a nulla jobb oldali additív neutrális elem.)
  4.   – a rákövetkezővel való összegzés visszavezethető az összeg rákövetkezőjére.
  5.   – A nullával jobbról való szorzás nullát ad.
  6.   – A rákövetkezővel való szorzás visszavezethető a másik tagnak az szorzathoz való még egyszeri hozzáadására.
  7.   – A teljes indukció axiómasémája: Ha a   formula igaz a nullára, továbbá a formula igazsága a rákövetkezés során öröklődik, akkor ez a formula minden számra igaz.

Szokásos definíciók, tételekSzerkesztés

Műveleti tulajdonságokSzerkesztés

Műveleti tulajdonságok tételei
  asszociativitás  
kommutativitás  
  egységelem  
asszociativitás  
kommutativitás  
  disztributivitás  

A Peano-aritmetika 3. axiómája szerint az   -nak van (jobb oldali) nulleleme. Levezethető továbbá a kommutativitás, asszociativitás is, azonban az összes csoportaxióma még nem állítható elő, mivel szinte egy számnak sincs inverze – és ez rendben is van, mivel a negatív számok nem természetes számok.

A szorzásnak megfelelő   -ról is bizonyítható, hogy asszociatív, kommutatív és egységelemes. Inverz itt is csak kivételes esetben van. Egyfajta osztás azonban mégiscsak értelmezhető majd, ez lesz az ún. maradékos osztás, ennek azonban inkább számelméleti, mint algebrai jelentősége lesz.

Fontos tétel továbbá a két műveletet összekötő egyik irányú disztributivitás: A   disztributív az   -ra nézve.

Példa levezetésre: Kommutativitás

 

RendezésSzerkesztés

A gyenge rendezés tételei
  minimális elem  
  reflexív  
  antiszimmetrikus  
  tranzitív  
  lineáris  
  és a    
  és a    

A Peano-aritmetikában definiálható a következő „nem nagyobb, mint”-nek megfelelő kétargumentumú predikátum:

 

Ez egy gyenge lineáris rendezés a természetes számokon, azaz

  • Reflexív: Senki sem nagyobb magánál.
  • Antiszimmetrikus: Ha ketten nem nagyobbak egymásnál, akkor ugyanazok.
  • Tranzitív: Ha három közül a második nem nagyobb az elsőnél, és a harmadik nem nagyobb a másodiknál, akkor a harmadik nem nagyobb az elsőnél sem.
  • Lineáris: Bármely kettő közül valamelyik nem nagyobb a másiknál.

Ezen belül további jellemzők, hogy

  • Alulról korlátos: Van olyan, aki senkinél sem nagyobb.
  • A   minimális eleme: 0 senkinél sem nagyobb.
Szigorú rendezés tételei
  infimum  
  irreflexív  
  antiszimmetrikus  
  tranzitív  
  lineáris  
  és a    
  és a    

A reláció természetesen élesíthető „kisebb, mint”-re:

 

Ez már egy totális szigorú rendezés:

  • Irreflexív: Senki sem kisebb magánál.
  • Antiszimmetrikus: Semelyik kettő közül sem lehet egyszerre mindkettő kisebb a másiknál (ilyenkor ugyanis magánál lenne kisebb, ami tiltott).
  • Tranzitív: Ha három közül a harmadik kisebb a másodiknál, és a második kisebb az elsőnél, akkor a harmadik kisebb az elsőnél is.
  • lineáris: Bármely két különböző elem közül pontosan az egyik kisebb a másiknál.

Ezen belül további jellemzők, hogy

  • A   infimum: 0-nál nincs kisebb.
  • Felülről nem korlátos: Mindennél van nagyobb.

Természetesen definálhatók a szokásos párjaik is:

 

További mindkettőre jellemző tulajdonság még, hogy működnek a szokásos egyenlőtlenség-rendezési szabályok:

  • az egyenlőtlenség mindkét oldalához hozzáadhatunk tetszőleges számot
  • az egyenlőtlenség mindkét oldalát megszorozhatjuk egy (szigorú rendezés esetében nem nulla) számmal.

A rendezések kapcsán Érdemes még megjegyezni a következő formulát:

 

Ezt úgy lehetne mondani, hogy „minden ami nem a nulla, rákövetkezője valaminek”. A rendezés definíciói szerint ezt a következőképpen írhatjuk át:

 

Ez a nagyon egyszerű formula azért érdekes, mert a Peano-aritmetikának vannak olyan gyengébb változatai is, melyekben ez a formula szerepel a teljes indukciós axiómaséma helyén.[1]

Erős indukció és a legkisebb szám elveSzerkesztés

A Peano-aritmetikában bizonyíthatók más bizonyítási módszerek tételei is. Az egyik ilyen az ún. erős indukció (alakja szerint lényegében ez maga a transzfinit indukció, csak ez nem a halmazelmélet). Ez azt mondja, hogy ha egy számra öröklődik egy tulajdonság az összes őt megelőző számról, akkor az minden számra érvényes:

 

Az egyik legfontosabb következménye ennek az ún. legkisebb szám elve, miszerint ha egy tulajdonság igaz minden számra, akkor van legkisebb szám is, amelyre igaz.[2]

 

Ez a halmazelméleti jólrendezés megfogalmazása: Mivel minden ilyen tulajdonságnak egy halmaz fog majd megfelelni a modellben (azok halmaza, amelyekre igaz), ez azt mondja, hogy minden ilyen halmaznak lesz egy legkisebb eleme. A jólrendezettség persze csak másodrendben definiálható tulajdonság, de ez a két formula sem egy bizonyos tétel, hanem mint a teljes indukció, tételsémák.

Ez tehát az az elv, amit akkor használunk, mikor az ún. végtelen leszállásra hivatkozva bizonyítunk. Ez a következőt jelenti: egy indirekt feltevés oda vezet, hogy ha a tulajdonság igaz egy természetes számra, akkor igaz egy nála (szigorúan) kisebb természetes számra is. Ez végtelen leszállásra vezet, azonban tudjuk, hogy a természetes számok jólrendezett számhalmaz. Innen nyerjük az ellentmondást.

Oszthatósági relációSzerkesztés

oszthatósági reláció tételei
reflexivitás  
antiszimmetria  
tranzitivitás  
  egység  
 ,    

Bevezethető egy a  -hez nagyon hasonló reláció, ami csak abban különbözik attól, hogy   helyett   szerepel benne. Ez felelne meg az oszthatóságnak:

 

A  -hez hasonlóan ez is egy parciális rendezés, azaz:

  • Reflexív: Minden osztója önmagának – mivel minden egyszerese önmaga.
  • Antiszimmetrikus: Ha ketten osztói egymásnak, akkor ugyanarról van szó.
  • Tranzitív: Ha három közül az egyik a kettő között van, Akkor az első is osztója a harmadiknak.

De természetesen - mint általában az oszthatóság - nem lineáris.

Maradékos osztásSzerkesztés

Számelméleti szempontból a legfontosabb tétel a maradékos osztásért felelős tétel levezethetősége. Ugyanis ha ez létezik, akkor a (metanyelvi, modellelméleti értelemben vett) számelmélet szerint a Peano-aritmetika modellje egy euklideszi gyűrű, amiről tudható, hogy érvényes benne a számelmélet alaptétele, azaz minden szám lényegében egyértelműen felbontható prímek szorzatára. A számelmélet alaptétele lenne persze a legfontosabb tétel, azonban ez elsőrendben nem megfogalmazható, így a Peano-aritmetikában (az eddig látottnál is) bonyolultabb minden.

Ez a maradékos osztásért felelős tétel azt mondja ki, hogy a maradékos osztás létezik és egyértelmű:

 

Ez alapján bevezethetünk egy relációt:

 

Ebből a fenti függvényszerű tulajdonság miatt származtatható egy függvény is. Ezt a függvényt a   alakban fogjuk használni, és ezt úgy lesz érdemes kiolvasni, hogy „az  -et az  -nal maradékosan osztva   a maradék”.

     

Prím-, Felbonthatatlan- és RelatívPrím predikátumSzerkesztés

A szokásos értelemben beszélhetünk irreducibilis, vagy más néven felbonthatatlan számról,

 

illetve prímszámról,

 

továbbá relatív prímségről is:

 

Ezekkel kapcsolatos tételek:

  • a   a legkisebb felbonthatatlan:
 
  • Mindenkit oszt egy felbonthatatlan:
 
  • Pontosan akkor relatív prím két szám, ha nincs közös felbonthatatlan osztójuk.
 
  • Relatív prímeknek van szomszédos többszörösük.
 
  • Minden felbonthatatlan szám prímszám.
 

MonuszSzerkesztés

Az összeadásnak a kivonás lenne az inverze, azonban mint tudjuk ez a természetes számok közt nem létezik. Szokás azonban mégis bevezetni egy öszvérműveletet, amit (mínusz helyett) mónusznak hívnak. Ez a kivonásféleség a következőképp működik: a szokásos kivonást adja, ha amúgyis elvégezhető lenne a kivonás, és  -t ad olyankor, mikor az egész számok köréből ismert kivonás negatív eredményt ad.

Ehhez mindenekelőtt az szükséges, hogy ez függvényszerű legyen, amit akövetkező tétel garantál:

 

Ezért ha vesszük a következő relációt,

 

Akkor a tétel értelmében csinálhatunk belőle függvényt:

 

Korlátos kvantorokSzerkesztés

A szokásos kvantifikációkat szokás gyengíteni, méghozzá a következőképpen:

 

Ahol is   és   különböző változók kell legyenek.

Ezt a fajta kvantifikációt korlátos kvantifikációnak nevezzük. Egy formulát pedig korlátos formulának nevezünk akkor, ha benne minden kvantor korlátos.

Aritmetikai hierarchiaSzerkesztés

Az aritmetika formulahalmazában azon formuláknak, melyek prenex alakjában váltakoznak a kvantorok, létezik egy érdekes formulahalmaz-sorozat, egy hierarchia, amit a következőképpen definiálunk (rekurzívan):

Bázis: A  -formulák és  -formulák nem mások, mint a korlátos formulák.
Rekurzió:
 
 

Tehát az   szám tulajdonképpen azt jelöli, hogy hány kvantor van a váltakozó kvantorú formulában. A   és   pedig azt jelöli, hogy egzisztenciális vagy univerzális kvantorral kezdődik-e a váltakozó kvantorokból álló formula.

Adódik, hogy egy   formula pontosan akkor  -formula, ha   egy  -beli formula.

Az egyszerre   és   formulákat   formuláknak nevezzük. Adódik, hogy   zárt negálásra.

A modell alaphalmazának azon részhalmazait, melyek egy szabad változós  -formulák extenziói,   halmaznak nevezzük, amelyek pedig egy szabad változós  -formulák extenziói,   halmaznak, nevezzük.

A   és   jelölések egyébként régies jelölései a kvantoroknak, amik pedig arra utalnak, hogy az univerzálisan kvantifikált állítás tulajdonképpen sok állítás konjunkciója (amit a boole-algebrák nyelvén szorzással szokás jelölni), az egzisztenciálisan kvantifikált állítás pedig sok állítás diszjunkciója, amit ugyanitt összeadással szokás jelölni). Hogy miért is használunk mégis kvantorokat és nem küszöböljük ki őket ezekkel a logikai konstansokkal, az azért van, mert a 'sok' végtelent is jelenthet – végtelen hosszú formuláink pedig nincsenek.

Innen látszódik is, hogy a fent definiált korlátos kvantorok egyáltalán nem is 'igazi kvantorok', hiszen a korlátján belül végesen felsorolhatók. Ezt mondja tulajdonképpen az, hogy a következő formulák tételei a Peano-aritmetikának:

 
 

További információkSzerkesztés

ForrásokSzerkesztés

  • George Boolos. The Logic of Provability. New York: Cambridge University Press (1993). ISBN 0-521-48325-5 
  • Petr Hájek, Pavel Pudlák. Metamathematics of First-Order Arithmetic. Berlin Heidelberg: Springer-Verlag (1993). ISBN 0-387-50632-2 

JegyzetekSzerkesztés

  1. George Boolos The Logic of Provability, i. m. 2 fejezet, 49. old.
  2. George Boolos The Logic of Provability, i. m. 2 fejezet, 23. old.