Model teori

Den model teori er en gren af matematisk logik , der beskæftiger sig med konstruktion og klassificering strukturer . Den definerer især modellerne for aksiomatiske teorier , hvor målet er at fortolke de syntaktiske strukturer (udtryk, formler, demonstrationer ...) i matematiske strukturer (sæt af naturlige tal, grupper , universer ...) for at knytte dem til begreber af semantisk karakter (såsom mening eller sandhed).

Historie

Ideen om at fortolke matematiske teorier i strukturer synes ganske tidligt, fra det XVII th  århundrede . Således giver Abbé Buée og Jean-Robert Argand (plan d'Argand), derefter Gauss og Cauchy, en geometrisk model, hvor de komplekse tal , objekter ganske vist bekvemme til beregninger, men på det tidspunkt uden mening, fortolkes som punkter i det euklidiske plan og deres operationer som geometriske transformationer. Men det er utvivlsomt udseendet af ikke-euklidiske geometrier, der var den mest afgørende i fremkomsten af ​​idéen om model. Først baseret på varianter af det parallelle postulat af euklid , fremkom de som et simpelt formelt spil og havde ringe kreditstatus mod den absolutte sandhed i euklidisk geometri. De blev gradvist accepteret fra det øjeblik, vi var i stand til at levere modeller, det vil sige geometriske understøtninger med specifikke fortolkninger af de formelle begreber punkter, linjer, ... gjorde det muligt at fortolke ikke-euklidisk geometri i euklidisk geometri. Således Poincarés giver en model af den hyperbolske plan fra en halvplan af det komplekse plan. Senere vil Hilbert holde en konference i Paris, hvor han vil give en numerisk betydning af alle betingelserne for euklidisk geometri for at demonstrere uafhængigheden af ​​aksiomerne for den euklidiske geometri over for andre aksiomer .

To af pionererne inden for modelteori er Leopold Löwenheim og Thoralf Skolem, der demonstrerer en stærk sætning om eksistensen af ​​modeller af alle slags "størrelser" ( kardinaler ). Men et vigtigt skridt i historien om denne teori er definitionen af ​​sandhed af Alfred Tarski i en artikel med titlen The Concept of Truth in Formalized Languages , offentliggjort i 1933. Tarskis mål er at give en definition af sandhed i overensstemmelse med det daglige sprog og at klarlægge teorien om korrespondance . For at undgå logiske antinomier foreslår han at definere "sand" og "falsk" på et metasprog. For eksempel skelner han propositionen "det sneer" fra at observere, at det faktisk sneer i den virkelige verden. Til dette introducerer Tarski begrebet tilfredsstillelse i den forstand, at propositionen "det sner" kun opfyldes af virkeligheden (som en "model" af formlen) i det tilfælde, hvor det sner. Formålet med dette eksempel er at vise forskellen mellem det sproglige objekt og dets fortolkning, der gør det muligt at bedømme propositionen. For at gøre dette introducerer han den formelle undersøgelse af semantikken i beregningen af ​​predikater .

Det var dog først i 1950'erne og 1960'erne, at modelteori blev en disciplin i sig selv. Blandt dets pionerer var Tarski, RL Vaught og M. Morley. I dag er modelteori en af ​​de vigtigste grene inden for logik .

Grundlæggende begreber i modelteori

Et sprog er et sæt konstanter, funktioner, prædikater og variabler. Formålet med forskning i teorien om modeller er teorier, derfor sæt formler. En model er en sikker struktur, der tilfredsstiller aksiomerne i den pågældende teori. L{\ displaystyle L}L{\ displaystyle L}

Der er to hovedforskningsmetoder i modelteori:

1) Forståelsen af ​​en enestående struktur, som man anser for at give betydningen [for eksempel eller ]. (IKKE,+,∗){\ displaystyle (\ mathbb {N}, +, *)}(R,+,∗){\ displaystyle (\ mathbb {R}, +, *)}

2) Undersøgelsen for at finde karakteristika, der er fælles for et antal strukturer [for eksempel algebraiske strukturer som en ring eller et felt ].

Blandt de vigtige sætninger i modelteori spiller tre en hovedrolle, fordi de giver de generelle betingelser for, at en teori har en model:

(i) Kompaktitetssætningen for første ordens logik, (formulering 1 og 2 er ækvivalente):

1) Enten ; er en formel. Der findes et endeligt sæt sådan, at . x⊨φ{\ displaystyle X \ modeller \ varphi}φ{\ displaystyle \ varphi}xende⊆x{\ displaystyle X _ {\ text {end}} \ subseteq X}xende⊨φ{\ displaystyle X _ {\ text {end}} \ modeller \ varphi}

2) Hvis en bestemt del af et sæt formler Γ har en model, så har Γ en model.

(ii) Gödel's fuldstændighedssætning sikrer, at det klassiske førsteordenslogik er det omvendte: hver ikke-modstridende teori har mindst en model. Det lukker forskning, der går tilbage til (iii) Löwenheim-Skolems sætning om, at enhver teori (på et tælleligt sprog af første orden), som har en uendelig model, også har en model for enhver uendelig kardinalitet .

Modeller af klassisk propositionel beregning

I propositionel beregning af klassisk logik er der ingen eksistentielle eller universelle kvantificeringsanordninger. Formlerne består af atomare propositioner, der er knyttet iterativt af logiske stik. En model består i at definere en sandhedsværdi (sand eller falsk) for hver atomær propositionelle variabel. Vi kan derefter udlede sandheden eller falskheden i en hvilken som helst kompleks formel.

Kompleksiteten af ​​en formel måles ved det maksimale antal indlejrede operatører. For eksempel i den eller og ingen er indlejrede inden i hinanden. Men nej og ikke og er ikke. Dette forslag er af kompleksitet 2, fordi det højst har to indlejrede operatører. (¬P)∨(Q∧R){\ displaystyle (\ lnot P) \ lor (Q \ land R)} ∨{\ displaystyle \ lor} ¬{\ displaystyle \ lnot} ∧{\ displaystyle \ land}

Formler med kompleksitet 0 er atomformler. Det er den valgte model, der definerer deres sandhedsværdi.

Antag, at sandheden og falskheden i alle kompleksitetsformler er blevet defineret. Lad os vise, hvordan vi definerer sandheden og falskheden af ​​kompleksitetsformler . Enten en formel af kompleksitet , opnået fra formlen eller formlerne og af kompleksiteten eller mindre, ved hjælp af et logisk stik. Sandheden eller falskheden om og er derfor allerede defineret. ikke{\ displaystyle n}ikke+1{\ displaystyle n + 1}P{\ displaystyle P}ikke+1{\ displaystyle n + 1}Q{\ displaystyle Q}R{\ displaystyle R}ikke{\ displaystyle n}Q{\ displaystyle Q}R{\ displaystyle R}

a)  : Hvis det er sandt, er det falsk ved definition af negation. Hvis det er falsk, er det sandt af samme grund. P=¬Q{\ displaystyle P = \ lnot Q}Q{\ displaystyle Q}P{\ displaystyle P}Q{\ displaystyle Q}P{\ displaystyle P}

b)  : Hvis og begge er sande, så er det også falsk i alle andre tilfælde. P=(Q∧R){\ displaystyle P = (Q \ land R)}Q{\ displaystyle Q}R{\ displaystyle R}P{\ displaystyle P}P{\ displaystyle P}

c)  : Hvis og begge er falske, så er det også sandt i alle andre tilfælde. P=(Q∨R){\ displaystyle P = (Q \ lor R)}Q{\ displaystyle Q}R{\ displaystyle R}P{\ displaystyle P}P{\ displaystyle P}

d)  : Hvis er sandt og er falsk, er det falsk, men er sandt i alle andre tilfælde. P=(Q→R){\ displaystyle P = (Q \ til R)}Q{\ displaystyle Q}R{\ displaystyle R}P{\ displaystyle P}P{\ displaystyle P}

En sand formel i enhver model siges at være universelt gyldig (især en tautologi er en). Hvis formlen har atomære propositionelle variabler, er det faktisk tilstrækkeligt at verificere sandheden af ​​formlen i de mulige modeller, der giver de forskellige sandhedsværdier til atomforslagene for at bevise, at denne formel er en tautologi. Antallet af modeller, der er endelige, det skyldes, at beregningen af ​​propositionerne kan afgøres: der findes en algoritme, der gør det muligt at afgøre, om en formel er en tautologi eller ej. ikke{\ displaystyle n}2ikke{\ displaystyle 2 ^ {n}}ikke{\ displaystyle n}

Desuden fastslår sætningen af ​​fuldstændigheden af ​​propositionens beregning ækvivalensen mellem at være en tautologi og at være bevisbar i et passende fradragssystem.

Eksempler

Lad os vise, at ( Peirces lov ) er en tautologi ved hjælp af regel d). Hvis det er sandt, så er det at være af formen sandt. Hvis det er falsk, er det sandt, er falsk og er sandt. ((P→Q)→P)→P{\ displaystyle ((P \ til Q) \ til P) \ til P}P{\ displaystyle P}((P→Q)→P)→P{\ displaystyle ((P \ til Q) \ til P) \ til P}R→P{\ displaystyle R \ til P}P{\ displaystyle P}P→Q{\ displaystyle P \ til Q}(P→Q)→P{\ displaystyle (P \ til Q) \ til P}((P→Q)→P)→P{\ displaystyle ((P \ til Q) \ til P) \ til P}

At være sand i enhver model, er en tautologi. Det er derfor også bevises ved hjælp af fradrag systemer, for eksempel naturlig deduktion . ((P→Q)→P)→P{\ displaystyle ((P \ til Q) \ til P) \ til P}

På den anden side er det ikke beviseligt. Faktisk, i en model hvor er falsk, er også falsk. (P→Q)→P{\ displaystyle (P \ til Q) \ til P}P{\ displaystyle P}(P→Q)→P{\ displaystyle (P \ til Q) \ til P}

Modeller til beregning af prædikater

I beregningen af første ordens prædikater af klassisk logik gælder de anvendte prædikater for variabler. For at definere en model er det derfor nødvendigt at introducere et sæt, hvis elementer vil fungere som værdier, der skal tildeles variablerne. Hvad angår propositionel beregning, begynder vi med at definere sandheden eller falskheden af ​​atomformler i et givet domæne, inden vi gradvist definerer sandheden eller falskheden af ​​sammensatte formler. Man kan således ved successive stadier definere sandheden af ​​alle de komplekse formler af logikken i den første orden sammensat ud fra de grundlæggende symboler i en teori.

For at en erklæring, der bruger et sæt symboler defineret af et sprog, betragtes som sand, dvs. at være i stand til at sige, at det er et sætning, er det nødvendigt og tilstrækkeligt, at alle strukturer tilfredsstiller staterne. L{\ displaystyle {\ mathcal {L}}}L{\ displaystyle {\ mathcal {L}}}

En formel er atomær, når den ikke indeholder logiske operatorer (negation, sammenhæng, eksistens ...). Atomic betyder her ikke, at en formel kun indeholder et symbol, men kun at det indeholder et enkelt grundlæggende prædikatsymbol. De andre navne, den indeholder, er objektnavne, og de kan være meget komplekse. At en formel er atomær betyder, at den ikke indeholder en underformel. Dette er en logisk atomicitet.

Fortolke atomformler i en model

En førsteordens sprogfortolkning er en struktur defineret af følgende elementer.

• En uforsigtig sæt U, teoriens univers. Hvert objektnavn (konstant), der er nævnt på sproget, har et tilknyttet element af U.
• Hvert grundlæggende unary (ét sted) predikat, der er nævnt på sproget, er forbundet med en del af U, udvidelsen af ​​dette predikat. Det er det sæt værdier, som vi beslutter at predikatet er sandt for. Med hvert grundlæggende binære prædikat, der er nævnt på sproget, er der knyttet en del af det cartesiske produkt U × U, det er sættet med alle de par, hvor prædikatet er sandt. Det samme gælder for ternære prædikater eller for højere aritet.
• Hver unary operator nævnt på sproget er forbundet med en funktion fra U i U. Med hver binær operator nævnt på sproget er en funktion fra U × U i U. Ligeledes for operatører med højere aritet.

Sættet U eller fortolkningen, som det er en del af, er en model for en teori, når alle aksiomerne i denne teori er sande med hensyn til denne fortolkning.

Brugen af ​​ordet, model, er undertiden mangfoldig. Nogle gange betegner det sættet U, undertiden sættet med ægte atomformler, undertiden fortolkningen. Når vi siger en model af en teori, antager vi ofte, at det er sandt. Men vi siger også, at en teori er forkert i en model.

Definitionen af ​​rigtigheden af ​​komplekse formler

Så snart man har en fortolkning af en teori, kan sandheden af ​​alle formler, der kun nævner konstanterne, prædikaterne og de grundlæggende operatorer, defineres. Vi starter med atomformler og fortsætter rekursivt til mere komplekse formler.

Vi tager de regler, der er defineret i afsnittet vedrørende propositionelle beregningsmodeller, og vi definerer de to yderligere regler, der vedrører den universelle og eksistentielle kvantificeringsenhed.

e)  : Hvis en af formlerne opnået ved at erstatte en del af U for alle de gratis forekomster af i fortolkningen af er falsk så er falsk, ellers, hvis ikke har andre frie variable end , er sandt. P=∀xQ{\ displaystyle P = \ forall x \; Q}x{\ displaystyle x}Q{\ displaystyle Q}P{\ displaystyle P}Q{\ displaystyle Q}x{\ displaystyle x}P{\ displaystyle P}

f)  : Hvis en af ​​formlerne opnået ved at erstatte et element af U for alle de gratis forekomster af i fortolkningen af er sandt, er det ellers sandt, hvis det ikke har andre gratis variabler end , er det falsk. P=∃xQ{\ displaystyle P = \ eksisterer x \; Q}x{\ displaystyle x}Q{\ displaystyle Q}P{\ displaystyle P}Q{\ displaystyle Q}x{\ displaystyle x}P{\ displaystyle P}

e) og f) gør det muligt at definere sandheden og falskheden af ​​alle de lukkede formler, det vil sige uden frie variabler.

Sandhed og falskhed af alle de komplekse formler uden gratis variabler i førsteordens logik kan derfor bestemmes i en given model.

En sand formel i enhver model kaldes en logisk lov eller sætning. Hvad angår propositionel beregning, angiver Gödel's fuldstændighedssætning ækvivalensen mellem logisk lov og påviselig formel i et passende fradragssystem. Dette resultat er bemærkelsesværdigt i betragtning af det faktum, at i modsætning til beregningen af ​​propositioner er antallet af modeller, der kan overvejes, generelt uendeligt. Desuden er beregningen af ​​prædikater i modsætning til beregningen af ​​propositioner ikke afgørende.

Eksempler

Formlen er en logisk lov. Overvej faktisk en ikke-uforsigtig U-model. Der er derefter to muligheder. ∃x∀y(R(x)→R(y)){\ displaystyle \ eksisterer x \; \ forall y \; (R (x) \ til R (y))}

• Eller vi tildeler den sande værdi til R ( y ), når y tildeles en værdi i U , og i dette tilfælde tildeler vi x enhver værdi i U. Implikationen er så sand for alle y i U, derfor er også sand i U og x, der også betegner et element i U, er sandt i U.R(x)→R(y){\ displaystyle R (x) \ til R (y)}∀y(R(x)→R(y)){\ displaystyle \ forall y \; (R (x) \ til R (y))}∃x∀y(R(x)→R(y)){\ displaystyle \ eksisterer x \; \ forall y \; (R (x) \ til R (y))}
• Eller vi tildeler værdien falsk til R ( y ) for mindst en y i U. Lad os betegne dette element med x . Så for alle y i U, er sandt, derfor er sandt i U, og derfor er også sandt.R(x)→R(y){\ displaystyle R (x) \ til R (y)}∀y(R(x)→R(y)){\ displaystyle \ forall y \; (R (x) \ til R (y))}∃x∀y(R(x)→R(y)){\ displaystyle \ eksisterer x \; \ forall y \; (R (x) \ til R (y))}

I begge tilfælde er formlen sand. Når du er vilkårlig, gælder formlen i enhver model og kan også bevises ved hjælp af et system for fradrag.

På den anden side er formlen ikke påviselig. Det er tilstrækkeligt at tage et sæt U med to elementer a og b som model for at indstille P og Q ( a ) sandt og Q ( b ) falsk. er falsk i U, mens det er sandt (med x = a ). Det følger, at der er falsk i U. Formlen, der kan forfalskes, er ikke en sætning. ∃x(P→Q(x))→(P→∀xQ(x)){\ displaystyle \ eksisterer x (P \ til Q (x)) \ til (P \ til \ for alle xQ (x))}P→∀xQ(x){\ displaystyle P \ to \ forall xQ (x)}∃x(P→Q(x)){\ displaystyle \ eksisterer x (P \ til Q (x))}∃x(P→Q(x))→(P→∀xQ(x)){\ displaystyle \ eksisterer x (P \ til Q (x)) \ til (P \ til \ for alle xQ (x))}

Kategorisitet

Vi siger om en teori, at det er kategorisk, hvis alle dets modeller er isomorfe (to modeller ? og ? 'er isomorfe, hvis der er en binativ homomorfisme fra M til M' ). En kategorisk teori vil derfor virkelig karakterisere strukturen, hvis love den siger. Men teorierne fra den første orden kan ikke være kategoriske, så snart de har en uendelig model i henhold til kompaktitetssætningen , mere præcist ifølge sætningerne i Lowenheim-Skolem . En førsteordens teori, der har uendelige modeller, kan dog være komplet, dvs. alle dens modeller opfylder de samme udsagn. For eksempel har teorien om tætte samlede ordrer uden ender, som er en komplet teori , for modeller (ℚ, <) og (ℝ, <), som har de samme sætninger (angivet på ordens sprog alene!) Uden at være isomorfe, da de ikke engang er ækvipotente .

De eneste kategoriske førsteordens teorier er teorier, der kun har modeller for en given endelig kardinalitet (betingelsen er selvfølgelig ikke tilstrækkelig).

En forestilling, der er mere relevant for førsteordens teorier, er den af κ- kategoricitet, for en bestemt uendelig kardinal κ  : en teori siges at være κ -kategorisk, når alle dens modeller af uendelig kardinal κ (i betydningen kardinalitetsdomæne) er isomorfe. For eksempel kan vi vise, at teorien om endeløse tætte lineære ordrer er ℵ₀-kategorisk: alle dens modeller for tællbar kardinalitet er isomorf til (ℚ, <).

Første ordre axiomatized Peano aritmetik er ikke ℵ₀-kategorisk: det har så- kaldt ikke-standardiserede modeller , som ikke er isomorf til standardmodellen af naturlige tal, men kan være tælleligt.

Vi kan kun betragte andenordens aritmetik som kategorisk, hvis vi kun betragter fulde modeller: en klasse af modeller, der ikke kan tilfredsstillende karakteriseres aksiomatisk. Hvis denne teori gør det muligt at karakterisere naturlige heltal, er det relativt for eksempel til teorien om sæt (det vil sige til en model deraf). For Henkins semantik, der indrømmer fuldstændighed og kompaktitetssætninger, er andenordens aritmetik , som alle andenordens teorier , ikke kategorisk.

Karakterisering af klasser af L-strukturer

Lad K være en ikke-klasse klasse af L-strukturer. Kan vi karakterisere K ved et sæt udsagn?

- Vi siger, at en klasse af L-strukturer er EC ( elementær klasse ), hvis der findes et endeligt sæt Γ af udsagn, således at K = Mod (Γ) (dette betyder, at alle klasser af L-strukturer i K er nøjagtigt alle modeller af Γ)- Vi siger, at en klasse af L-strukturer er EC Δ ( elementær klasse i bredere forstand ), hvis der findes et sæt Γ af udsagn (ikke nødvendigvis endelige), således at K = Mod (Γ)

En EC-klasse er derfor også EC Δ .

Ved at forsøge at karakterisere klasserne af endelige L-strukturer (dvs. hvis univers indeholder et endeligt antal elementer), opdager vi grænserne for den ekspressive kraft af førsteordens logik: det er umuligt i første orden at karakterisere Afslut. Her er demonstrationen:

(For beviset er følgende sætning nødvendig: Hvis et sæt udsagn har endelige modeller af vilkårligt stor størrelse (dvs. for alle n findes der en model, hvis univers har mindst n elementer), så har den en uendelig model). Lad K f være klassen af ​​endelige L-strukturer. Antag, at K f er EF Δ . Så der findes Γ et sæt udsagn, således at K f = Mod (Γ). Således har models modeller af begrænset størrelse vilkårligt store (fordi K f indeholder alle de klasser af L-strukturer, hvis domæne er endelig), derfor har the sætningen Γ en uendelig model. Modsigelse, fordi Mod (by) efter hypotese er klassen for alle endelige L-strukturer. Så K f er ikke EC Δ , så a fortiori ikke EC.

Modeller af intuitionistisk logik

De hidtil præsenterede modeller er modeller af klassisk logik . Men der er andre logik, for eksempel den intuitionistiske logik, som er en logik, der bygger demonstrationerne ud fra lokalerne. Der er en teori om modeller til denne logik, Kripke-modellerne med en fuldstændighedssætning: en formel kan bevises i intuitionistisk logik, hvis og kun hvis det er sandt i enhver Kripke-model.

Disse modeller gør det f.eks. Muligt at besvare følgende spørgsmål. Enten en lukket formel: F{\ displaystyle F}

• Eller er ikke en sætning af klassisk logik. For at vise dette er det tilstrækkeligt at udstille en klassisk model, der annullerer formlen;F{\ displaystyle F}
• Eller er en sætning af klassisk logik. For at vise det er det tilstrækkeligt at demonstrere det i et system til deduktion af klassisk logik. Der er derefter to underafsager:F{\ displaystyle F}

Eller er også en sætning af intuitionistisk logik. For at vise det er det tilstrækkeligt at demonstrere det i et intuitionistisk system for deduktion (eller at vise, at det er sandt i alle Kripkes modeller);F{\ displaystyle F}F{\ displaystyle F} Eller det kan ikke påvises i intuitionistisk logik. For at vise dette er det tilstrækkeligt at give en Kripke-model, der annullerer formlen.F{\ displaystyle F}

Sådan kan vi demonstrere, at:

(¬∀xF(x))→(∃x¬F(x)){\ displaystyle (\ lnot \ forall x \; F (x)) \ to (\ exist x \; \ lnot F (x))} er en sætning af klassisk logik, men ikke af intuitionistisk logik; (¬∃xF(x))→(∀x¬F(x)){\ displaystyle (\ lnot \ eksisterer x \; F (x)) \ til (\ forall x \; \ lnot F (x))} er en sætning af intuitionistisk logik (og også af klassisk logik).

Kripkes modeller bruges også til at give modeller til modalogik .

Eksempler på anvendelse af modellerne

Vi har allerede givet anvendelser af modellerne:

• tilfredsstille eller tværtimod falske en formel (for eksempel skelne en formel, der er sand i klassisk logik, men falsk i intuitionistisk logik: formlen er sand i enhver klassisk model, men der er en model i intuitionistisk logik, der forfalsker den);
• bevise, at en teori eller et system af aksiomer ikke er modstridende ved at udstille en model, der tilfredsstiller alle aksiomerne.

Med hensyn til aksiomasystemer griber modellerne også ind for at vise aksiomernes uafhængighed mellem dem eller for at etablere en modsigelse af et aksiomatisk system ved at stole på ikke-modsigelsen af ​​et andet system (dette kaldes derefter ”Relativ konsistens”). Lad os give nogle eksempler.

I geometri er Euclids V - postulat uafhængig af de øvrige geometriaksiomer. Faktisk er den euklidiske geometri på den ene side en model, hvor dette postulat er sandt. På den anden side er Poincaré-halvplanet en model for hyperbolsk geometri , hvor dette postulat er falsk. I denne model består universet (det hyperbolske plan) af punkterne i det øverste åbne euklidiske halvplan . Linjerne i det hyperbolske plan er sæt af ligninger eller . {(x,y)|y>0}{\ displaystyle \ {(x, y) \; | \; y> 0 \}}x=på{\ displaystyle x = a}(x-på)2+y2=R2{\ displaystyle (xa) ^ {2} + y ^ {2} = R ^ {2}}

I dette univers, hvis vi giver os selv en linje og et punkt uden for denne linje, er der en uendelig række, der passerer gennem punktet og ikke secant til den første linje.

I dette eksempel ser vi, at vi kan bygge en model af den nye teori (det hyperbolske plan og dets linjer) ved hjælp af en model af den gamle (i det euklidiske plan: halvplanet og dets halvlinjer) linjer. og halvcirkler). Hvis vi antager "kohærens" eller "konsistens" af euklidisk geometri, har vi fastslået den for hyperbolsk geometri.

Denne brug af modeller til at vise den relative konsistens af en teori er meget almindelig. Overvej for eksempel sætteori , betegnet ZF. Lad os også overveje teorien, betegnet ZFC, der består af ZF, som vi tilføjer det valgte aksiom . Vi kan vise, at hvis ZF ikke er modstridende, så er ZFC også. Faktisk (takket være Gödel's fuldstændighedssætning) antager vi, at der findes en model af ZF. Vi er så i stand til i denne model at associere til enhver ordinal α et sæt F α, så:

• den klasse L ”union” af alle F α opfylder alle aksiomer ZF;
• det F α er constructible ved transfinite induktion , i den forstand, at F α defineres fra F β , for β <α;
• hvis vi definerer rækkefølgen af ​​en y af L som den mindste ordinal α således at y hører til F α , så til enhver ikke-fri x af L "kan vi associere" et element af x af minimal orden, som vi betegner med f ( x ).

Vi har derefter defineret en "funktion" f fra L til L (eller mere præcist, en funktionel klasse ) tilfredsstillende . Med andre ord er f en "funktion af valg" i L , således at L ikke kun tilfredsstiller ZF, men også valgets aksiom. L er derfor en model af ZFC. ∀x≠∅,f(x)∈x{\ displaystyle \ forall x \ neq \ varnothing, f (x) \ in x}

Stadig i en model for ZF, hvis vi satte og for enhver helt tal , (sæt af dele af ), derefter foreningen af alle definerer en model, som opfylder alle aksiomer ZF undtagen aksiom uendelighed . Dette beviser (stadig under den antagelse, at ZF ikke er modstridende), at dette sidste aksiom ikke kan afledes fra de andre aksiomer. R0=∅{\ displaystyle R_ {0} = \ varnothing}ikke{\ displaystyle n}Rikke+1=P(Rikke){\ displaystyle R_ {n + 1} = {\ mathcal {P}} (R_ {n})}Rikke{\ displaystyle R_ {n}}Rikke{\ displaystyle R_ {n}}ikke{\ displaystyle n}

Omega-stabilitetsteorien

Et af målene med modelteori er at foreslå en karakterisering og klassificering af teorier, især matematiske teorier, på baggrund af de egenskaber, som deres modeller har (for at bruge Shelahs formel er det generelle program at konstruere en "klassificeringsteori") .

Stabilitet er i denne henseende en væsentlig egenskab (for prolegomenaen og udviklingen af ​​stabilitetsteorien henvises især til Morleys og Shelahs arbejde). Især for de komplette teorier på et tælleligt sprog kan man være interesseret i egenskaben at være -stabil (man læser "omega-stabil"). ω{\ displaystyle \ omega}

Vi skal først introducere visse begreber. Vi kalder en 1-type et sæt formler med v en variabel, der er tilfredsstillende i strukturen, det vil sige sådan, at for enhver formel, der hører til og med strukturen, T teorien, en opgave af variabler. Bemærk, at begrebet type kan generaliseres: for en n-type betragter vi sæt formler med v en tuple. Vi kan specificere den forrige definition ved at overveje 1-typerne på et sæt A: formlerne kan omfatte parametre, der hører til A. Vi siger, at 1-typen t er komplet, hvis vi har en eller anden form for sproget . Σ(v){\ displaystyle \ Sigma (v)}T∪Σ{\ displaystyle T \ cup \ Sigma}M⊨ψ(v)[på]{\ displaystyle M \ models \ psi (v) [a]}ψ(v){\ displaystyle \ psi (v)}Σ(v){\ displaystyle \ Sigma (v)}M⊨T[på]{\ displaystyle M \ modeller T [a]}M{\ displaystyle M}på{\ displaystyle a}Σ(v){\ displaystyle \ Sigma (v)}Σ(v){\ displaystyle \ Sigma (v)}ψ(v){\ displaystyle \ psi (v)}ψ(v)∈t{\ displaystyle \ psi (v) \ in t}¬ψ(v)∈t{\ displaystyle \ neg \ psi (v) \ in t}

Derfor er en teori -stabil, hvis der for hver model af teorien (for hvert sæt A inkluderet i universet) højst findes et tælleligt antal komplette 1-typer (på A). Intuitivt betyder det, at teorien præsenterer en form for enkelhed, fordi den ikke har et for stort antal typer, sidstnævnte kan let klassificeres: vi finder en forestilling, der ligner den grundlæggende i et vektorrum. Derudover skal omega-stabilitet sættes i relation til forestillingen om utallig kategori; vi søger derefter at give mening til ideen om en unik og kortfattet karakterisering af en teori (se afsnittet afsat til kategorisitet). ω{\ displaystyle \ omega}

Eksempel  Ifølge Macintyre sætning (1971), teorien om algebraisk lukkede områder er -stabil (beviset er baseret på Hilbert 's grundlag sætning, og derfor udvalgsaksiomet).ω{\ displaystyle \ omega}

Egenskaben for stabilitet kan generaliseres som følger: en teori T i et L-sprog er stabil, hvis der findes en kardinal, så der for enhver model af T af kardinalitet er mindre end eller lig med , der højst er et antal 1-fulde typer . κ≥|L|{\ displaystyle \ kappa \ geq | L |}κ{\ displaystyle \ kappa}κ{\ displaystyle \ kappa}

Noter og referencer

1. Adrien-Quentin Buee, Memoir om imaginære mængder , Royal Society of London, 1806.
2. Oversat i samlingen Logik, semantik, metamatematik , Armand Colin 1972, s. 157-269.
3. Se afsnit 5.1 i Hodges, Wilfrid og Scanlon, Thomas, "First-order model Theory", The Stanford Encyclopedia of Philosophy (Efterår 2013 Edition), Edward N. Zalta (red.), URL = < https: // plato. stanford.edu/archives/fall2013/entries/modeltheory-fo/ >.
4. Noter af kurset "Modelteori" leveret af A. Arana som en del af Master 1 LOPHISC 2016/2017 University Paris I Panthéon-Sorbonne.
5. https://ncatlab.org/nlab/show/stability+in+model+theory .

Se også

Relaterede artikler

• Beregning af prædikater
• Beregning af forslag
• Naturligt fradrag
• Skolemisering
• Klassisk logik
• Intuitionistisk logik
• Minimal logik
• Ikke-standard model
• Kripke semantik
• Denotational semantik
• Type (modelteori)
• Stabil teori  (in)

Eksternt link

Formelt semantik-kursus

Bibliografi

• Daniel Lascar, teorien om modeller i få ulykker , Cassini, 2009, ( ISBN  978-2-84225-137-6 )
• (en) CC Chang og H. Jerome Keisler , Model Theory , Amsterdam / New York / New York, NY, USA, Elsevier , coll.  "Logikstudier og matematikens fundament",1990, 3 e  ed. ( 1 st  ed. 1973) ( ISBN  978-0-444-88054-3 , læse online ). Referencebog om emnet, da den blev offentliggjort.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">