A matematikai logika vagy metamatematika egy fegyelem a matematika végén bevezetett a XIX th században, amely adják objektum a tanulmány a matematika, mint a nyelv .
A matematikai logika alapvető tárgyai a matematikai állításokat reprezentáló képletek , a matematikai érvelést képviselő levezetések vagy formális demonstrációk, valamint olyan szemantika vagy modellek vagy értelmezések olyan szerkezetekben, amelyek általános matematikai "jelentést" adnak a képleteknek (sőt néha a bemutatóknak is) ).) mint bizonyos invariánsok: például a predikátumok kiszámításának képleteinek értelmezése lehetővé teszi számukra az igazság értékének hozzárendelését .
A matematikai logika a XIX . Század végén született meg, a logika a kifejezés filozófiai értelmében; ez az egyik út, amelyet az akkori matematikusok feltártak annak érdekében, hogy megoldják az alapok válságát, amelyet a matematika összetettsége és a paradoxonok megjelenése okoz . Kezdetét két új ötlet találkozása jelzi:
A matematikai logika a matematika formális kezelésének első próbálkozásain alapszik, Leibniz és Lambert ( XVII . Század vége - XVIII . Század eleje) következtében. Különösen Leibniz vezette be a modern matematikai jelölések nagy részét (kvantorok, integrációs szimbólumok használata stb.). A matematikai logikáról azonban csak a XIX . Század közepéig lehet beszélni George Boole (és kisebb mértékben Augustus De Morgan munkáival) munkájával, amely bevezeti az igazság kiszámítását, ahol a logikai kombinációk, például a kötőszó, a diszjunkció és az implikáció az egészek összeadásához vagy szorzásához hasonló műveletek, de az igaz hamis és igaz értékeket (vagy 0 és 1) tartalmazzák; ezeket a logikai műveleteket az igazságtáblák határozzák meg .
Boole számításai azt a látszólag paradox gondolatot közvetítették, amely azonban látványosan gyümölcsözőnek bizonyult, hogy a matematika nyelvét matematikailag meg lehet határozni, és a matematikusok vizsgálati tárgyává válhat. Ez azonban még nem tette lehetővé az alapvető problémák megoldását. Következésképpen számos matematikus megpróbálta kiterjeszteni a matematikai érvelés általános kereteire, és láttuk a formalizált logikai rendszerek megjelenését ; az elsők egyike Frege- nek köszönhető a XX . század fordulóján .
A 1900 folyamán egy nagyon híres előadást a Nemzetközi Matematikai Kongresszus Párizsban, David Hilbert javasolt egy listát a 23 legfontosabb megoldatlan problémák a matematika idején. A második az aritmetika koherenciája volt , vagyis a finitista demonstráció azt jelenti, hogy a számtani axiómák nem ellentmondanak egymásnak.
A Hilbert programja a század első negyedében számos logikai munkát vonzott, ideértve a matematika axiómarendszereinek fejlesztését: az aritmetika Peano-axiómáit , Zermelo- féle Skolem és Fraenkel kiegészítette az elméleti halmazokat, valamint Whitehead és Russell az matematikai formalizációs program, a Principia Mathematica . Ez az az időszak is, amikor megjelennek a modellelmélet alapelvei: az elmélet modelljének fogalma , Löwenheim-Skolem tétel .
1929-ben Kurt Gödel doktori disszertációjában bemutatja teljességi tételét, amely kimondja a matematika formalizálásának sikerességét : a matematikai érvelés elvileg formalizálható az predikátumok kiszámításakor . Ezt a tételt figyelemre méltó előrelépésként fogadták Hilbert programjának megoldása felé , de egy évvel később Gödel bebizonyította az (1931-ben megjelent) hiányosságtételt, amely vitathatatlanul megmutatta a program végrehajtásának lehetetlenségét.
Ez a negatív eredmény azonban nem állította meg a matematikai logika fejlődését. Az 1930-as években megérkezett az angol és amerikai logikusok új generációja, nevezetesen Alonzo Church , Alan Turing , Stephen Kleene , Haskell Curry és Emil Post , akik nagyban hozzájárultak az algoritmus fogalmának meghatározásához és az elmélet kidolgozásához. algoritmikus komplexitás ( kiszámíthatósági elmélet , algoritmusok komplexitásának elmélete ). A bizonyítási elmélet Hilbert Gerhard Gentzen munkájával tovább bővült, amely a relatív koherencia első demonstrációját hozta létre, és így osztályozási programot indított el axiomatikus elméletekként.
A leglátványosabb eredménye a háború utáni időszak miatt a Paul Cohen , aki bemutatja a kényszerítve módszer a függetlenségét a kontinuum hipotézis a halmazelmélet, így megoldva Hilbert 1 st probléma. De a matematikai logika is forradalom alatt áll a számítástechnika megjelenése miatt; A Curry-Howard levelezés felfedezése , amely a hivatalos bizonyításokat az egyház lambda-kalkulusához köti, és a bizonyítékokhoz számítási tartalmat ad, hatalmas kutatási programot indít el.
A logika legfőbb érdeke a matematika más területeivel való kölcsönhatása és az általuk elért új módszerek. Ebből a szempontból a legfontosabb eredményeket a modellek elmélete adja, amelyet néha inkább az algebra, mint a logika egyik ágának tekintenek; a modellelmélet különösen a csoportelméletre és a kombinatorikára vonatkozik ( Ramsey-elmélet ).
Más nagyon produktív kölcsönhatások is léteznek: a halmazelmélet fejlődése szorosan kapcsolódik a méréselmélethez, és egy teljes értékű matematikai mezőt, leíró halmazelméletet eredményezett . A számíthatóság elmélete az elméleti számítástechnika egyik alapja.
A XX . Század vége óta láttuk, hogy a bizonyítási elmélet a kategóriaelmélethez kapcsolódik, és ily módon elkezdik kölcsönhatásba lépni az algebrai topológiával . Másrészt a lineáris logika megjelenésével egyre szorosabb kapcsolatot tart fenn a lineáris algebrával , még a nem kommutatív geometriával is . Újabban a (in) típusok homotóp elmélete gazdag kapcsolatot teremtett a logika (a típusok elmélete) és a matematika (a homotópia elmélete) között, amelyeknek csak a kezdeteit láthatjuk.
A matematika logikai rendszerekben való formalizálása, amely különösen Whitehead és Russell munkáját ösztönözte, a matematikai logika fejlesztésének egyik nagy motivációja volt. A speciális számítógépes eszközök, automatikus demonstrálók , szakértői rendszerek és korrektív asszisztensek megjelenése új érdeklődést váltott ki a program iránt. Különösen a bizonyítási asszisztenseknek van több alkalmazásuk a matematikában.
Először a XX . Század végén és a XXI . Század elején két ősi sejtést oldottak meg a számítógép segítségével számos eset feldolgozására: a négyszínű tétel és a Kepler-sejtés . A számítógép ilyen használata által felvetett kétségek motiválták a bemutatók formalizálását és teljes ellenőrzését.
Másrészt matematikai formalizációs programokat dolgoztak ki bizonyíték-asszisztensek segítségével annak érdekében, hogy egy teljesen formalizált matematikai anyagot állítsanak elő; a matematika szempontjából egy ilyen korpusz megléte különösen érdekes lehet az algoritmikus feldolgozás lehetővé tételéhez, például a minták szerinti kereséshez: keresse meg az összes tételt, amelyet a prímszám tételből levezetnek, a Riemann-féle zéta függvényre vonatkozó összes tételt stb.
Néhány fontos eredmény született az 1930-as években:
Más fontos megállapításokra a XX . Század második felében került sor .
A logikai rendszer vagy a dedukciós rendszer egy három rendszerből álló formális rendszer . Az első kettő meghatározza a szintaxisát , a harmadik a szemantikáját :
A képletek és a dedukciók fő jellemzője, hogy véges objektumok ; ráadásul a képletek és következtetések mindegyike rekurzív , vagyis rendelkezésre áll egy algoritmus, amely meghatározza, hogy az adott objektum helyes képlet vagy a rendszer helyes következtetése. A logika tanulmányozását a képletek és kifejezések szempontjából szintaxisnak nevezzük .
A szemantika azonban elkerüli a kombinatorikát azáltal, hogy végtelen tárgyakra hív (általában). Először az igazság "meghatározására" használták. Például a propozíciók számításakor a képleteket például egy logikai algebra elemei értelmezik .
A figyelmeztetés itt rendben van, mert Kurt Gödel ( Alfred Tarski követi ) hiányosság-tételével megmutatta a matematikai matematikai szigorúság matematikai igazolásának lehetetlenségét. Ezért célszerűbb a szemantikát metaforának tekinteni: a képleteket - szintaktikai tárgyakat - egy másik világba vetítik. Ezt a technikát - amely tárgyakat egy nagyobb világba sodor, hogy érveljen velük kapcsolatban - gyakran alkalmaznak a matematikában, és hatékony.
A szemantika azonban nem csak az igazság "meghatározásáról" szól. Például a denotációs szemantika nem képletek, hanem dedukciók értelmezése, amelyek célja a számítási tartalmuk megragadása .
A klasszikus és az intuitionista logikában az axiómák két típusát különböztetjük meg : a logikai axiómákat, amelyek tisztán logikai tulajdonságokat fejeznek ki, mint például ( a kizárt harmadik elve , érvényes a klasszikus logikában, de az intuitionista logikában nem), és az objektumokat meghatározó logikán kívüli axiómák. például Peano axiómái meghatározzák az aritmetika egész számát, míg Zermelo-Fraenkel axiómái a halmazokat . Amikor a rendszernek extra logikai axiómái vannak, axiomatikus elméletről beszélünk. A tanulmány a különböző modellek azonos axiomatikus elmélet tárgya a elméletének modellek .
Két dedukciós rendszer lehet ekvivalens abban az értelemben, hogy pontosan ugyanazok a tételek vannak. Ezt az ekvivalenciát az egyik levonásának a másik levonásában történő fordításával igazoljuk. Például a predikátumok kiszámításához három (legalább) háromféle ekvivalens dedukciós rendszer létezik : Hilbert-stílusú rendszerek , természetes dedukció és a szekvenciák kalkulusa . Néha hozzáadjuk a Fitch stílusát, amely a természetes dedukció egyik változata, amelyben a bizonyításokat lineáris módon mutatják be.
Míg a számelmélet a számok tulajdonságait mutatja be, a logika mint matematikai elmélet fő jellemzőjét megjegyezzük: "bemutatja" a dedukciós rendszerek tulajdonságait, amelyekben az objektumok "tételek". Van tehát egy kettős szint, amelyben nem szabad eltévednünk. A dolgok tisztázása érdekében a dedukciós rendszerek tulajdonságait megfogalmazó "tételeket" néha " metateorémáknak " nevezik . Az általunk vizsgált dedukciós rendszert „elméletnek”, a rendszert pedig, amelyben metateorémákat állítunk és igazolunk, „metateóriának”.
A dedukciós rendszerek alapvető tulajdonságai a következők:
A korrekció A javítás kimondja, hogy a tételek minden modellben érvényesek. Ez azt jelenti, hogy a következtetési szabályok jól illenek ezekhez a modellekhez, más szóval, hogy a dedukció rendszere helyesen formalizálja az érvelést ezekben a modellekben. a koherencia A dedukció rendszere koherens (az egyik a következetes anglikizmust is használja ), ha beismer egy modellt, vagy mi felel meg ugyanannak a dolognak, ha nem enged meg egyetlen képletet sem bemutatni. Akkor beszélünk egyenletességi koherenciáról is, amikor a rendszer elfogad egy nem triviális modellt, vagyis legalább két elemet tartalmaz. Ez azt állítja, hogy a rendszer nem teszi lehetővé egyenlet bizonyítását. a teljesség Meghatározása egy modellcsaládhoz kapcsolódik. A dedukció rendszere teljes a modellcsalád vonatkozásában, ha bármely tétel, amely a család minden modelljében érvényes, tétel. Röviden: egy rendszer akkor teljes, ha minden érvényes bizonyítható.A teljességgel kapcsolatos dedukciós rendszerek másik tulajdonsága a maximális konzisztencia . A dedukciós rendszer maximálisan következetes, ha egy új axióma hozzáadása, amely maga nem tétel, következetlenné teszi a rendszert.
Az "ilyen és ilyen rendszer teljes megvalósítása egy ilyen modellcsalád számára" állítása tipikus példa a metatéma.
Ebben az összefüggésben az igazság intuitív fogalma két formális fogalmat eredményez: érvényességet és bizonyíthatóságot. A helyesség, a koherencia és a teljesség három tulajdonsága meghatározza, hogy ezek a fogalmak miként kapcsolhatók össze, remélve, hogy így azonosítható az igazság, a logikus keresése.
Az állítások matematikai tényeket kifejező képletek , vagyis olyan tulajdonságok, amelyek nem függenek egyetlen paramétertől sem, és amelyek ezért csak igazak vagy hamisak lehetnek, például "3 a 4 többszöröse" (az "n értéke a 4-szeres többszöröse , ami igaz vagy hamis, az n ) paraméter értékétől függően, vagy "a Riemann-zéta függvény nem triviális nulláinak mindegyikének valódi része van 1/2" .
Az elemi tételeket, amelyeket propozíciós változóknak nevezünk , összekötők segítségével kombinálva összetett képletek jönnek létre. A propozíciók úgy értelmezhetők, hogy minden propozíciós változót propozícióval helyettesítünk. Például a (P ∧ ¬P) ⇒ Q állítás értelmezése lehet "ha 3 páros és 3 páratlan, akkor 0 = 1" .
A csatlakozókat a klasszikus logikában értelmezéssel mutatjuk be .
A disszjunkció A szétválasztás a két tétel P és Q jelentése a javaslat jegyezni P ∨ Q vagy „ P vagy Q ”, ami igaz, ha legalább az egyik két tétel igaz; ezért csak akkor hamis, ha a két állítás hamis. A tárgyalás A tagadás egy állítás P , a javaslat megjegyezte ¬ P , vagy „nem P ”, ami igaz, ha P hamis; ezért hamis, amikor P igaz.Ebből a két csatlakozóból más hasznos csatlakozókat vagy rövidítéseket készíthetünk:
Az együttállás A összefüggésben a két tétel P és Q jelentése a következő állítás: ¬ ((¬ P ) ∨ (¬ Q )) azaz nem ((nem P ) vagy (nem Q )) Ezt P ∧ Q vagy „ P és Q ” jelöli, és csak akkor igaz, ha P és Q igaz; és ezért hamis, ha a két állítás egyike hamis. A következmény A következtetés az Q által P jelentése az állítást (¬ P ) ∨ Q , jelöljük „ P ⇒ Q ” vagy „ P azt jelenti, Q ”, és amely hamis csak akkor, ha a P egy igazi javaslat és Q hamis. Egyenértékűség A logikai ekvivalencia a P és Q jelentése a javaslat (( P ⇒ Q ) ∧ ( Q ⇒ P )) ((( P azt jelenti, Q ) és ( Q magában P ))), jelöljük " P ⇔ Q ", ahol ( P egyenértékű a Q ), és amely csak akkor igaz, ha a két állítás P és Q azonos igazság érték. Az exkluzív ill A kizárólagos vagy vagy kizárólagos diszjunkcióját a P és Q jelentése a javaslat P ⊻ Q (néha szintén jelöljük P ⊕ Q vagy akár a P | Q vagy áramkör tervezők ), amely megfelel a ( P ∨ Q ) ∧ ¬ ( P ∧ Q ), hogy a franciául mondani: vagy P, vagy Q , de nem mindkettő egyszerre. A P és Q kizárása vagy P ⇔ ¬ Q, vagy ismét ¬ ( P ⇔ Q ) felel meg . Ez az állítás csak akkor igaz, ha P és Q eltérő igazságértékekkel rendelkezik.Az úgynevezett „ klasszikus ” propozíciószámítás jellemzője, hogy az összes állítást két összekötőből lehet kifejezni: például ∨ és ¬ ( vagy pedig nem ). De más választási lehetőségek is lehetségesek, például ⇒ (implikáció) és ⊥ (hamis). Csak egy csatlakozót használhat, a Sheffer szimbólumot «| ( Henry M. Sheffer , 1913), tervezője "stroke" -nak nevezte, és most Nand- nak hívják, és az áramköri tervezők megjegyzik ; csak a Nor csatlakozót használhatjuk (megjegyezve ), amint azt Charles Sanders Peirce (1880) megjegyezte, anélkül, hogy közzétennénk. Röviden, a klasszikus logikában egyetlen csatlakozó elegendő az összes logikai művelet elszámolásához.
A predikátum kalkuláció kiterjeszti a propozíciós számítást, lehetővé téve a paraméterektől függő képletek írását; ehhez az predikátumok kiszámítása bevezeti a változók fogalmát , a függvények és relációk szimbólumait , a kifejezéseket és a kvantorokat ; a kifejezéseket a változóknak a függvény szimbólumokkal történő egyesítésével, az elemi képleteket a relációs szimbólumok kifejezésekre történő alkalmazásával kapjuk.
A predikátumok kiszámításának tipikus képlete: "∀ a , b (( p = a . B ) ⇒ (( a = 1) ∨ ( b = 1)))", amely egész számokban értelmezve kifejezi, hogy a p paraméter prímszám (vagy 1). Ez a képlet két függvényszimbólumot (a pontot, az egész számok szorzatával értelmezett bináris függvényt és az "1" szimbólumot, a 0-ary függvényt, vagyis konstansot) és egy relációs szimbólumot használ (az egyenlőségre). A változók a , b és p , a kifejezések a . b és 1, az elemi képletek pedig „ p = a . b "," a = 1 "és" b = 1 ". A változók a és b jelentése mennyiségileg , de nem a variábilis P , amely a képlet függ.
A predikátumok kiszámításának számos változata létezik; a legegyszerűbb, az első rend kiszámítása predikátumokat jelent , a változók ugyanolyan típusú objektumokat képviselnek, például a fenti képletben a 3 a , b és p változó egész számokat fog képviselni. A másodrendű predikátumok kiszámításakor kétféle változó létezik: az objektumok változói, a predikátumok pedig mások , vagyis az objektumok közötti kapcsolatok. Például másodrendű aritmetikában változókat használunk egész számok, mások pedig egész számok halmazához. Folyamatos hierarchia és 3 -én rend 3 változó típusok tárgyak közötti kapcsolatokat tárgyak közötti kapcsolatok kapcsolatok, stb
A predikátumok kiszámításának elengedhetetlen művelete a szubsztitúció, amely abból áll, hogy egy képletben az x változó összes előfordulását egy a kifejezéssel helyettesítjük , így új képletet kapunk; például ha a p változót az n kifejezéssel helyettesítjük ! + 1 a fenti képletben az „∀ a , b (( n ! + 1 = a . B ) ⇒ (( a = 1) ∨ ( b = 1)))” képletet kapjuk (amely kifejezi, hogy a n plusz 1 egész szám prímszám).
Ha P jelentése általános képletű függően paraméter X és egy egy olyan kifejezés, a szerelvény kapjuk, hogy a x által egy a P egy olyan formula, amely lehet írni a P [ a / X ] vagy ( a | x ) P , vagy más variációk ezen jelölések közül. és az úgynevezett általános képletű történő helyettesítésével kapott x által egy a P .
Egy x paraméter kiemeléséhez , amelytől a P képlet függ , megírjuk P { x } formában ; akkor van a P { van } a javaslat ( a | x ) P .
Megpróbálhatjuk megtalálni azokat a helyettesítéseket, amelyek igazolják a képletet; a probléma különösen érdekes az úgynevezett egyenletképletek esetében, vagyis a t (x) = t '(x) alakban . Az elmélet, amely arra törekszik, hogy megoldja az ilyen egyenletek keretében a matematikai logika úgynevezett egyesítése .
A kvantorok az állítmányok kiszámításának specifikus szintaktikai összetevői. A propozíciós csatlakozókhoz hasonlóan ezek is lehetővé teszik, hogy új formulákat építsen fel a régiekből, de ehhez a változók használatára támaszkodnak.
Vagy a P predikátum számításának képlete . Ezután létrehozunk egy új, úgynevezett egzisztenciális képletet, amelyet ∃ x P- vel jelölünk, és amely így olvasható: „létezik x olyan, hogy P”. Tegyük fel, hogy P csak x-től függ " . A javaslat ∃ x P igaz, ha létezik legalább egy tárgy egy (a tartomány tekinthető, az, ahol x „változó” ) úgy, hogy, amikor az egyik helyettesítő egy az x a P érünk egy igazi ajánlatot. A P képletet tulajdonságnak tekintjük, és ∃ x P igaz, ha van egy objektum ezzel a tulajdonsággal.
A ∃ jelet egzisztenciális kvantornak nevezzük .
Hasonlóképpen fel lehet építeni P-ből egy said x P jelölésű univerzális képletet , amely "minden x P-re " vagy bármi más x P-re vonatkozik . Ez azt jelenti, hogy az érintett területen az összes objektum (amelyet x kijelölhet) rendelkezik a P által leírt tulajdonsággal .
A ∀ jelet univerzális kvantornak nevezzük .
A klasszikus logikában az univerzális és az egzisztenciális kvantorokat egymáshoz viszonyítva tagadással definiálhatjuk, mert:
∀ x P egyenértékű ¬ ∃x ¬P és ∃x P egyenértékű ¬ ∀ x ¬ PValójában "hamis, hogy bármely objektumnak van egy adott tulajdonsága" azt jelenti, hogy "van legalább egy, amely nem rendelkezik ezzel a tulajdonsággal".
A kvantorok használata Elemi tulajdonságokLegyen P és Q két állítás, és x egy határozatlan objektum.
Legyen P propozíció, x és y pedig meghatározatlan objektum.
Ha A képlet, ahol az x változó nem jelenik meg szabadon , akkor:
De szintén :
Az egyenlőséget képviselő "=" relációs szimbólum kissé sajátos státusszal rendelkezik a logikai szimbólumok (összekötők, kvantorok) és a nem logikus szimbólumok (relációk, függvények) határán. Az a = b képlet azt jelenti, hogy a és b ugyanazt az objektumot jelképezik (vagy hogy a és b ugyanazon objektum különböző jelölései), és így olvasható: " a egyenlő b-vel ".
A klasszikus modellelmélet az egyenlőségű predikátumszámítás részeként alakul ki leggyakrabban, vagyis a figyelembe vett elméletek egyenlőek: az egyenlő viszonyt alkalmazzák az elmélet aláírásának szimbólumai mellett .
A dedukció szempontjából az egyenlőséget az alábbiakban ismertetett axiómák irányítják, lényegében kifejezve, hogy két egyenlő objektumnak ugyanazok a tulajdonságai vannak (és másodrendű logikában , hogy fordítva igaz).
A „=” tagadása a „≠” összefüggés, amelyet a ≠ b csak akkor határoz meg, ha ¬ ( a = b ).
Az egyenlőség axiómái az elsőrendű logikábanA reláció = lét reflexív, szimmetrikus és tranzitív, azt mondjuk, hogy a kapcsolat = egy ekvivalencia reláció .
E két utóbbi tulajdonságok ösztönösen kifejezni, hogy a = a legfinomabb az egyenértékűség kapcsolatok.
Meghatározás másodrendű logikábanA másodrendű logikában egyszerűbben definiálhatjuk az egyenlőséget:
Más szavakkal, két tárgy akkor és csak akkor egyenlő, ha ugyanazokkal a tulajdonságokkal rendelkeznek (a megkülönböztethetetlenek azonosságának elve, amelyet Leibniz mondott )
Nem említjük itt a matematika logikai részterületein szereplő angol referenciakönyveket, amelyek a bizonyítási elmélet , a modellelmélet , a halmazelmélet vagy a kiszámíthatóság .
Szinte az összes referenciamű angol nyelven készült, azonban vannak francia nyelvű referenciamunkák is, például az alábbiak: