Teoria Modelelor CURS

TEORIA MODELELORMaster I, Semestrul II 2015

Laurentiu Leustean

1

Logica ca fundament al matematicii

Logica matematica s-a dezvoltat cu scopul de a se depasi criza nfundamentele matematicii de la nceputul secolului XX.

Criza fundamentelor matematiciiI 16 iunie, 1902: scrisoarea lui Bertrand Russell (filozof englez)

catre Gottlob Frege (logician german)

I Paradoxul lui Russel (1902) Sistemul logic al lui Fregeinconsistent

I a declansat criza fundamentelor matematicii (foundations ofmathematics)

Paradoxul lui Russel

Conform teoriei naive a multimilor, orice colectie definibila estemultime.Fie R = {A | A / A}. Atunci R / R R R.

2

Programul lui Hilbert

Programul lui Hilbert (1921)

Sa se formalizeze matematica si sa se stabileasca urmatoarele:

I Matematica este consistenta: un enunt matematic si negatiasa nu pot fi demonstrate simultan.

I Matematica este completa: toate enunturile matematiceadevarate pot fi demonstrate.

I Matematica este decidabila: exista o regula mecanica pentru adetermina daca un enunt matematic dat este adevarat sau fals

3

Programul lui Hilbert

Hilbert a fost convins ca aceste obiective pot fi atinse:

Every mathematical problem must necessarily be susceptible to anexact statement either in the form of an actual answer to thequestion asked, or by the proof of the impossibility of its solution.

Once a logical formalism is established one can expect that asystematic, so-to-say computational, treatment of logic formulas ispossible, which would somewhat correspond to the theory ofequations in algebra.

4

Esecul programului lui Hilbert

Teoremele de incompletitudine ale lui Godel (1931-33)

I Incompletitudinea aritmeticii obisnuite

I Imposibilitatea de a demonstra consistenta teoriei multimilor

Problema de decizie (Entscheidungsproblem)

I Hilbert si Ackermann (1928): Exista un algoritm pentru averifica daca o anumita formula din logica de ordinul ntai esteadevarata?

I Cu alte cuvinte: Este logica de ordinul ntai decidabila?

Church si Turing (1936-37)

Logica de ordinul ntai este nedecidabila.5

Inceputul informaticii

Teorema Church-Turing poate fi vazuta ca nceputul informaticiiteoretice:

I masinile Turing - calculatoare

I -calculul - programare functionala

I funtiile recursive - teoria calculabilitatii - teoria complexitatii

Teza Church-Turing

O functie f : N N este efectiv calculabila daca si numai dacaeste calculabila de o masina Turing.

6

Calculul propozitional PCReamintire: anul I (slideuri Ioana Leustean)

7

Sintaxa PC

8

Limbajul si formulele

Limbajul PC este format din:

I o multime numarabila de variabile propozitionale:Var = {v0, v1, v2, . . . , vn, . . .}

I conectori logici: (unar), (binar)I paranteze: ( , ).

Formulele PC se definesc recursiv astfel:

(F0) orice variabila propozitionala este formula,

(F1) daca este formula, atunci () este formula,(F2) daca si sunt formule, atunci ( ) este formula,(F3) orice formula se obtine aplicand regulile (F0), (F1), (F2) de

un numar finit de ori.

Notatie: Form := multimea formulelor

9

Limbajul si formulele

Exemple: v1 (v2), v1v2 nu sunt formule . ((v1 v2) (v1)), ((v1 v2)) sunt formule. are precedenta cea mai mare parantezele se pun numai atunci cand sunt necesare formula ((v1 v2) (v1)) se scrie (v1 v2) v1Conectori derivati

Pentru si formule oarecare, definim urmatoarele abrevieri: := := ( ) := ( ) ( )

10

Sistemul deductiv

Sistemul deductiv al PC este prezentat n stilul Hilbert.

Axiomele

(A1) ( )(A2) ( ( )) (( ) ( ))(A3) ( ) ( ),unde , si sunt formule ale PC.

Regula de deductie

(MP) (modus ponens),

11

Demonstratie. Teoreme

Definitie

O demonstratie este o secventa de formule 1, . . ., n astfel ncat,pentru fiecare i {1, . . . , n}, una din urmatoarele conditii estesatisfacuta:

I i este axioma,

I i se obtine din formulele anterioare prin MP:exista j , k < i astfel ncat j = k i

k , j = k ii

O formula este teorema daca exista o demonstratie 1, . . ., nastfel ncat n = .

Notatie: `

12

Teoreme ale PC

Pentru orice formula avem ` .Demonstratie

(1) ` ( (( ) )) (( ( )) ( ))(A2) cu , := , :=

(2) ` (( ) )(A1) cu , :=

(3) ` ( ( )) ( )(MP): (1), (2)

(4) ` ( )(A1) cu , :=

(5) ` (MP): (3), (4)

13

Teoreme ale PC

Fie , , formule n PC.

` ( ) (( ) ( ))` ( )` ( )` ` ` ( ) ( )` ( ) ` ( )

14

Deductia din ipoteze

Fie o multime de formule.

Definitie

O -demonstratie (demonstratie din ipotezele ) este o secventade formule 1, . . ., n a.. , pentru fiecare i {1, . . . , n}, una dinurmatoarele conditii este satisfacuta:

I i este axioma sau i ,I i se obtine din formulele anterioare prin MP.

O formula este -teorema daca exista o -demonstratie1, . . ., n a.. n = .

Notatie: ` ` este echivalent cu ` .

15

Reguli de deductie

O regula de deductie are forma

1 ` 1, . . . , n ` n ` .

A demonstra o regula de deductie derivata revine la a deduceconcluzia ` din premizele 1 ` 1, . . ., n ` n.

Exemplu:

` , ` `

16

Semantica PC

17

Evaluare (Interpretare)

Valori de adevar

Multimea valorilor de adevar este L2 := {0, 1} pe care consideramoperatiile de algebra Boole.

Definitie

O evaluare (interpretare) este o functie e : Var {0, 1}.

Teorema

Pentru orice evaluare e : Var {0, 1} exista o unica functiefe : Form {0, 1}

care satisface urmatoarele proprietati:

(e0) fe(v) = e(v) pentru orice v Var ,(e1) fe() = 1 fe() pentru orice Form,(e2) fe( ) = fe() fe() pentru orice , Form.

18

Tautologii. Modele

Definitie

I O evaluare e : Var {0, 1} este model al unei formule daca fe() = 1.

I O formula este satisfiabila daca admite un model.

I O formula este tautologie (valida) daca fe() = 1 pentruorice evaluare e : Var {0, 1}. Notatie: |= .

Fie o multime de formule.

I O evaluare e : Var {0, 1} este model al lui dacafe() = 1 pentru orice .

I este satisfiabila daca are un model e : Var {0, 1}.I este tautologie daca orice model al lui este si model

pentru . Notatie: |= 19

Metoda tabelului

Vrem sa demonstram ca o formula este tautologie: |= Daca v1, . . ., vn sunt variabilele care apar n , atuncicele 2n evaluari posibile e1, . . ., e2n pot fi scrise ntr-un tabel:

v1 v2 . . . vn

e1(v1) e1(v2) . . . e1(vn) fe1()e2(v1) e2(v2) . . . e2(vn) fe2()

......

......

...e2n(v1) e2n(v2) . . . e2n(vn) fe2n ()

Fiecare evaluare corespunde unei linii din tabel.

20

Metoda tabelului

Exemplu:

|= v1 (v2 (v1 v2))v1 v2 v1 (v2 (v1 v2))0 0 10 1 11 0 11 1 1

21

Corectitudine

Teorema de corectitudine (soundness)

Orice -teorema este -tautologie, i.e.

` |= pentru orice Form si Form.

22

Multimi consistente

Definitie

O multime de formule se numeste consistenta daca exista oformula astfel ncat 6` .

Propozitie

este consistenta.Dem. Aratam ca 6` ( ). Presupunem ca ` ( ).Deoarece deductia este corecta, obtinem fe(( )) = 1 oricarear fi e o evaluare. Dar fe(( )) = (fe() fe()) = 0,deci obtinem o contradictie.

Multimea teoremelor este consistenta. Orice multime satisfiabila este consistenta.

23

Multimi inconsistente

Definitie

O multime de formule se numeste inconsistenta daca nu esteconsistenta, i.e. ` oricare Form .

Propozitie

Pentru o multime Form sunt echivalente:I este inconsistenta,

I exista Form a.. ` si ` .

Propozitie

Pentru Form si Form sunt echivalente:I {} este inconsistenta,I ` .

24

Completitudine

Teorema de completitudine extinsa

Orice multime consistenta este satisfiabila.

Teorema de completitudine (completeness)

-teoremele si -tautologiile coincid, i.e.

` |= pentru orice Form si Form. In particular, ` daca si numai daca |= .Dem. corectitudinea. Presupunem ca 6` . Atunci 6` si {} esteconsistenta. Fie e : Var {0, 1} un model pentru {}.Obtinem fe() = {1} si fe() = 1, deci fe() = 0. Din ipoteza,orice model al lui este si model al lui , deci fe() = 1.Contradictie! 25

LOGICA DE ORDINUL ILimbaj de ordinul I. Structura de ordinul I.

1

Limbaje de ordinul I

ReferencesI Peter G. Hinman, Fundamentals of Mathematical Logic, AK

Peters, 2005

I Donald Monk, Mathematical Logic, Springer, 1976

2


Definitia 1.1

Un limbaj L de ordinul I este format din:I o multime numarabila V = {vn | n N} de variabile;I conectorii si ;I simbolul de egalitate =;

I cuantificatorul universal ;I o multime R de simboluri de relatii;I o multime F de simboluri de functii;I o multime C de simboluri de constante;I o functie aritate ari : F R N \ {0}.I L este unic determinat de cvadruplul := (R,F , C, ari).I se numeste signatura lui L sau vocabularul lui L sau

alfabetul lui L sau tipul de similaritate al lui L3


Fie L un limbaj de ordinul I. Multimea SimL a simbolurilor lui L este

SimL := V {,,=, } R F C

Elementele lui R F C se numesc simboluri non-logice. Elementele lui V {,,=,} se numesc simboluri logice.

Notam variabilele cu x , y , z , v0, v1, . . ., simbolurile de relatii cuP,Q,R . . ., simbolurile de functii cu f , g , h, . . . si simbolurile deconstante cu c , d , e, . . ..

Pentru orice m N \ {0} notam:Fm := multimea simbolurilor de functii de aritate m;Rm := multimea simbolurilor de relatii de aritate m.

4


Definitia 1.2

Multimea ExprL a expresiilor lui L este multimea tuturor sirurilorfinite de simboluri ale lui L.

Expresia vida se noteaza . Fie = 01 . . . k1 o expresie a lui L, unde i SimL pentruorice i .

I Daca 0 i j k 1, atunci expresia i . . . j se numeste(i , j)-subexpresia lui ;

I Spunem ca o expresie apare n daca exista0 i j k 1 a.. este (i , j)-subexpresia lui ;

I Notam cu Var() multimea variabilelor care apar n .

5

Termeni

Definitia 1.3

Multimea TrmL a termenilor lui L este intersectia tuturorcolectiilor de expresii care satisfac urmatoarele proprietati:

I orice variabila este element al lui ;

I orice simbol de constanta este element al lui ;

I daca m 1, f Fm si t1, . . . , tm , atunci ft1 . . . tm .Notatii:

I Termeni: t, s, t1, t2, s1, s2, . . ..

I Var(t) multimea variabilelor care apar n termenul t.

I t(x1, . . . , xn) daca Var(t) {x1, . . . , xn}. Daca Var(t) = , atunci t se numeste termen nchis.

6

Termeni

Multimea TrmL a termenilor lui L este intersectia tuturorcolectiilor de expresii care satisfac urmatoarele proprietati:

I orice variabila este element al lui ;

I orice simbol de constanta este element al lui ;

I daca m 1, f Fm si t1, . . . , tm , atunci ft1 . . . tm .

Propozitia 1.4 (Inductia pe termeni)

Presupunem ca este o multime de expresii care satisface:

I contine variabilele si simbolurile de constante;

I daca m 1, f Fm si t1, . . . , tm , atunci ft1 . . . tm .Atunci TrmL . folosita pentru a demonstra ca toti termenii au o proprietate P:definim ca fiind multimea tuturor expresiilor care satisfac P siaplicam inductia pe termeni pentru a obtine ca TrmL .

7

Termeni

Propozitia 1.5 (Citire unica (Unique readability))

I Orice termen este expresie nevida.

I Daca t este un termen, atunci fie t = vn pentru un n N, fiet = c pentru un c C, fie exista f Fm (m 1) sit1, . . . , tm termeni ai lui L a.. t = ft1 . . . tm.

I Daca f Fm, g Fn sunt simboluri de functii sit1, . . . , tm, s1, . . . , sn sunt termeni astfel ncatft1 . . . tm = gs1 . . . sn, atunci m = n, f = g si ti = si pentruorice i = 1, . . . , n.

demonstratii tehnice: Monk, Mathematical Logic, Springer, 1976

8

Formule

Definitie 1.6

Formulele atomice ale lui L sunt expresiile de forma:I = st, unde s, t sunt termeni;

I Rt1 . . . tm, unde R Rm si t1, . . . , tm sunt termeni.

Definitia 1.7

Multimea FmL a formulelor lui L este intersectia tuturor colectiilorde expresii care satisfac urmatoarele proprietati:

I orice formula atomica este element al lui ;

I este nchisa la , i.e implica ;I este nchisa la , i.e , implica ;I este nchisa la x (pentru orice variabila x), i.e.

implica x pentru orice variabila x . Notatie: Formule: ,, , . . ..

9

Formule

Propozitia 1.8 (Inductia pe formule)

Presupunem ca este o multime de expresii care contine toateformulele atomice si este nchisa la , si x (pentru oricevariabila x). Atunci FmL .

folosita pentru a demonstra ca toate formulele satisfac oproprietate P: definim ca fiind multimea tuturor expresiilor caresatisfac P si aplicam inductia pe formule pentru a obtine caFmL .

10

Formule

Propozitia 1.9 (Citire unica (Unique readability))

I Orice formula este expresie nevida.I Daca este o formula, atunci exact una din urmatoarele

alternative are loc:

(a) == st, unde s, t sunt termeni;(b) = Rt1 . . . tm, unde R Rm si t1, . . . , tm sunt termeni;(c) = , unde este formula;(d) = , unde , sunt formule;(e) = x, unde x este variabila si este formula.

Mai mult, scrierea lui sub una din aceste forme este unica.

demonstratii tehnice: Monk, Mathematical Logic, Springer, 1976

11

Subformule

Definitia 1.10

Fie o formula a lui L. O subformula a lui este orice formula care apare n .

Notatie: SubFmL() := multimea subformulelor lui .

Definitie alternativa

Multimea SubFmL() a subformulelor lui poate fi definita si prininductie dupa formule:

SubFmL() = {}, daca este formula atomica;SubFmL() = {} SubFmL();SubFmL( ) = { } SubFmL() SubFmL();SubFmL(x) = {x} SubFmL().

12

Notatii

De multe ori identificam un limbaj L cu multimea simbolurilor salenon-logice si scriem L = (R,F , C).

I Scriem de multe ori f (t1, . . . , tm) n loc de ft1 . . . tm siR(t1, . . . , tm) n loc de Rt1 . . . tm

I Scriem s = t sau (s = t) n loc de = st

I Scriem ( ) sau n loc de I Scriem ( ) n loc de I Pentru simboluri f de operatii binare scriem t1ft2 n loc de

ft1t2.

I Analog pentru simboluri R de relatii binare: scriem t1Rt2 nloc de Rt1t2.

13

Conectori derivati

Conectorii , , si cuantificatorul existential sunt introdusiprin urmatoarele abrevieri:

:= := ( ) := ( ) ( )x := x. si au precedenta mai mare decat ,, , . are precedenta mai mare decat , , . Astfel x este (x) si nu x( ).

14

L-structura

Definitia 1.11

O L-structura este un cvadruplu

A = (A,FA,RA, CA)

unde

I A este o multime nevida;

I FA = {f A | f F} este o multime de operatii pe A; daca fare aritatea n, atunci f A : An A;

I RA = {RA | R R} este o multime de relatii pe A; daca Rare aritatea n, atunci RA An;

I CA = {cA A | c C}.I A se numeste universul structurii A. Notatie: A = |A|I f A (respectiv RA, cA) se numeste denotatia sau interpretarea

lui f (respectiv R, c) n A. 15

Exemple - Limbajul egalitatii L=

L= = (R,F , C), undeI R = F = C = I acest limbaj este potrivit doar pentru a exprima proprietati ale

egalitatii

I L=-structurile sunt multimile nevide

Exemple de formule:

egalitatea este simetrica:xy(x = y y = x)

universul are cel putin trei elemente:

xyz((x = y) (y = z) (z = x))16

Exemple - Limbajul aritmeticii Lar

Lar = (R,F , C), undeI R = {

Exemple - Limbajul grupurilor LGr

LGr = (R,F , C), undeI R = ;I F = {,1 }; simbol binar, 1 simbol unarI C = {e}.

Scriem LGr = (; ,1 ; e) sau LGr = (,1 , e).Exemple naturale de LGr -structuri sunt grupurile: G = (G , ,1 , e).Prin urmare, G = , 1G =1, eG = e.Pentru a discuta despre grupuri abeliene (comutative), estetraditional sa se foloseasca limbajul LAbGr = (R,F , C), undeI R = ;I F = {+, }; + simbol binar, simbol unar;I C = {0}.

Scriem LAbGr = (+, , 0).18

Exemplu - Limbajul cu un simbol de relatie binar

LR = (R,F , C), undeI R = {R}; R simbol binarI F = C = I L-structurile sunt multimile nevide mpreuna cu o relatie

binara

I Daca suntem interesati de multimi partial ordonate (A,),folosim simbolul n loc de R si notam limbajul cu L.

I Daca suntem interesati de multimi strict ordonate (A,

Interpretare (evaluare)

Fie A o L-structura.Definitia 1.12

O interpretare sau evaluare a (variabilelor) lui L n A este o functiee : V A.In continuare, e : V A este o interpretare a lui L in A.Definitia 1.13 (Interpretarea termenilor)

Prin recursie pe termeni se defineste interpretarea tA(e) A atermenului t sub evaluarea e:

I daca t = v V , atunci tA(e) := e(v);I daca t = c C, atunci tA(e) := cA;I daca t = ft1 . . . tm, atunci tA(e) := f A(tA1 (e), . . . , t

Am (e)).

1

Exemplu - Limbajul aritmeticii Lar

I Lar = (

Interpretarea formulelor

Notatie

Pentru orice variabila x V si orice a A, definim o nouainterpretarea exa : V A prin

exa(v) ={

e(v) daca v 6= xa daca v = x .


(x)A(e) ={

1 daca A(exa) = 1 pentru orice a A0 altfel.

5


Propozitia 1.14

I ( )A(e) = A(e) A(e);I ( )A(e) = A(e) A(e);I ( )A(e) = A(e) A(e);

I (x)A(e) ={

1 daca exista a A a.. A(exa) = 10 altfel.

Dem.:

(x)A(e) = 1 (x)A(e) = 1 (x)A(e) = 1 (x)A(e) = 0 exista a A a.. ()A(exa) = 0 exista a A a.. A(exa) = 1.

6

Relatia de satisfacere

A o L-structura, e : V A o interpretare a lui L n A.Definitia 1.15

I Spunem ca e satisface n A si scriem A [e] daca sinumai daca A(e) = 1.

I Spunem ca e nu satisface n A si scriem A 6 [e] daca sinumai daca A(e) = 0.

Corolarul 1.16I A [e] A 6 [e];I A ( )[e] A [e] implica A [e]

A 6 [e] sau A [e];I A ( )[e] A [e] si A [e];I A ( )[e] A [e] sau A [e];I A ( )[e] A [e] daca si numai daca A [e];I A (x)[e] pentru orice a A, A [exa];I A (x)[e] exista a A a.. A [exa].

Dem.: Exercitiu usor.

7


Lar = (


Lar = (

Semantica

Propozitia 1.24

Pentru orice 1, . . . , n si orice 1 i < n, urmatoarele suntechivalente:

(i) {1, . . . , n} ;(ii) {1 . . . n} ;(iii) 1 . . . n ;(iv) {1, . . . , i} i+1 . . . n .Dem.: Exercitiu.

13

Semantica

Propozitia 1.25

(i) {} este nesatisfiabila.(ii) {} este nesatisfiabila.(iii) Daca este satisfiabila, atunci cel putin una dintre {} si

{} este satisfiabila.Dem.: Exercitiu.

Atentie! Este posibil ca atat cat si sa fie satisfiabile.Exemplu: := x = y n L=.

14

Echivalente si consecinte logice

Propozitia 1.26

Pentru orice formule , si orice variabile x , y ,

x x legile de negare a cuantificatorilorx x

x( ) x x este distributiv fata de x x x( ) este partial distributiv fata de x( ) x x este partial distributiv fata de x( ) x x este distributiv fata de x( ) x x este partial distributiv fata de x( ) x x

x x universul e nevid xx

15

Echivalente si consecinte logice

Propozitia 1.26 (continuare)

xy yx interschimbul cuantificatorilorxy yxyx xy.

Dem.: Exercitiu.

16

Egalitatea

Propozitia 1.27

Pentru orice termeni s, t, u,

I t = t;I s = t t = s;I s = t t = u s = u.

Dem.: Exercitiu.

Propozitia 1.28

Pentru orice m 1, f Fm,R Rm si orice termeniti , ui , i = 1, . . . ,m,

(t1 = u1) . . . (tm = um) ft1 . . . tm = fu1 . . . um (t1 = u1) . . . (tm = um) (Rt1 . . . tm Ru1 . . . um).

Dem.: Exercitiu.17

Tautologii

Notiunile de tautologie si consecinta tautologica se pot aplica siunui limbaj de ordinul ntai. Intuitiv: o tautologie este o formulaadevarata numai pe baza interpretarilor conectivelor ,.Definitia 1.29

O L-evaluare (de adevar) este o functie F : FmL L2 = {0, 1} cuurmatoarele proprietati: pentru orice formule ,,

I F () = 1 F () daca si numai daca F () = 0;I F ( ) = F () F ().

Propozitia 1.30

Pentru orice L-structura A si orice evaluare e : V A, functiaVe,A : FmL {0, 1}, Ve,A() = A(e)

este o L-evaluare.Dem.: Exercitiu usor.

18

Tautologii

Definitia 1.31

I este tautologie daca F () = 1 pentru orice L-evaluare F .I este consecinta tautologica a lui daca pentru oriceL-evaluare de adevar F ,

F () = 1 pentru orice F () = 1.

Propozitia 1.32

I Orice tautologie este valida.

I Daca este consecinta tautologica a lui , atunci .Dem.: Exercitiu.

Exemplu

t = t este valida, dar nu e tautologie.

19

Variabile legate si libere

Definitia 1.33

Fie = 01 . . . n1 o formula a lui L si x o variabila.I spunem ca variabila x apare legata pe pozitia k n daca

x = k si exista 0 i k j n 1 a.. (i , j)-subexpresialui este o subformula a lui de forma x;

I spunem ca x apare libera pe pozitia k n daca x = k , dar xnu apare legata pe pozitia k n ;

I x este variabila legata (bounded variable) a lui dacaexista un k a.. x apare legata pe pozitia k n ;

I x este variabila libera (free variable) a lui daca exista unk a.. x apare libera pe pozitia k n .

Notatie: FV () := multimea variabilelor libere ale lui . O variabila poate fi atat libera cat si legata. Exemplu:

= x(x = y) x = z1

Variabile legate si libere


Multimea FV () a variabilelor libere ale unei formule poate fidefinita si prin inductie pe formule:

FV () = Var(), daca este formula atomica;

FV () = FV ();FV ( ) = FV () FV ();FV (x) = FV () \ {x}.

Notatie: (x1, . . . , xn) daca FV () {x1, . . . , xn}.Definitia 1.34

O formula se numeste enunt (sentence) daca FV () = , i.e. nu are variabile libere.

Notatie: SentL:= multimea enunturilor lui L.2

Interpretarea termenilor - Propozitia 1.35

Propozitia 1.35

Pentru orice L-structura A si orice interpretari e1, e2 : V A,pentru orice termen t,

daca e1(v) = e2(v) pentru orice variabila v Var(t), atuncitA(e1) = tA(e2).

Dem.: Aplicam inductia pe termeni. Avem urmatoarele cazuri: t = v V . Atunci tA(e1) = e1(v) = e2(v) = tA(e2). t = c C. Atunci tA(e1) = tA(e2) = cA.

3

Demonstratia Propozitiei 1.35

t = ft1 . . . tm, cu f Fm,m 1 si t1, . . . , tm sunt termeni.Deoarece Var(ti ) Var(t), rezulta ca pentru orice i = 1, . . . ,m,avem e1(v) = e2(v) pentru orice variabila v Var(ti ).Prin urmare, putem aplica ipoteza de inductie pentru a concluzionaca

tAi (e1) = tAi (e2) pentru orice i = 1, . . . ,m.

Atunci

tA(e1) = f A(tA1 (e1), . . . , tAm (e1)) = f

A(tA1 (e2), . . . , tAm (e2)) = t

A(e2).

4

Interpretarea formulelor - Propozitia 1.36

Propozitia 1.36

Pentru orice L-structura A, orice interpretari e1, e2 : V A,pentru orice formula ,

daca e1(v) = e2(v) pentru orice variabila v FV (), atunciA [e1] A [e2].

Dem.: Aplicam inductia pe formule. Avem urmatoarele cazuri: = t1 = t2.Atunci Var(t1) FV (),Var(t2) FV (), deci putem aplicaPropozitia 1.27 pentru a conclude ca

tA1 (e1) = tA1 (e2), t

A2 (e1) = t

A2 (e2).

Rezulta

A [e1] tA1 (e1) = tA2 (e1) tA1 (e2) = tA2 (e2) A [e2].

5


= Rt1 . . . tm.Atunci Var(ti ) FV () pentru orice i = 1, . . . ,m, deci putemaplica Propozitia 1.27 pentru a conclude ca

tAi (e1) = tAi (e2) pentru orice i = 1, . . . ,m.

Rezulta

A [e1] RA(tA1 (e1), . . . , tAm (e1)) RA(tA1 (e2), . . . , tAm (e2)) A [e2].

= .Deoarece FV () = FV (), putem aplica ipoteza de inductiepentru a conclude ca

A [e1] A [e2].Rezulta

A [e1] A 6 [e1] A 6 [e2] A [e2].6


= .Deoarece FV (),FV () FV (), putem aplica ipoteza deinductie pentru a conclude ca

A [e1] A [e2] si A [e1] A [e2].Rezulta

A [e1] A 6 [e1] sau A [e1] A 6 [e2] sau A [e2] A [e2].

7


= x sie1(v) = e2(v) pentru orice v FV () = FV () \ {x}.

Rezulta ca pentru orice a A,e1xa(v) = e2xa(v) pentru orice v FV ().

Prin urmare, putem aplica ipoteza de inductie pentru interpretarilee1xa, e2xa pentru a conclude ca

pentru orice a A, A [e1xa] A [e2xa].Rezulta

A [e1] pentru orice a A,A [e1xa] pentru orice a A,A [e2xa] A [e2].

8


Notatie

Fie t(x1, . . . , xn) un termen. Scriem

tA[a1, . . . , an]

n loc de tA(e), unde e : V A este o (orice) interpretare a..e(x1) = a1, . . . , e(xn) = an.

Notatie

Fie (x1, . . . , xn) o formula. Scriem

A [a1, . . . , an]

n loc de A [e], unde e : V A este o (orice) interpretare a..e(x1) = a1, . . . , e(xn) = an.

9

Consecinta

Consecinta 1.37

Daca t este un termen nchis si este un enunt, atunci

tA(e1) = tA(e2) si A [e1] A [e2]pentru orice interpretari e1, e2 : V A.

10

Interpretarea enunturilor

Definitia 1.38

Fie un enunt. Spunem ca A este model al lui sau ca esteadevarat n A daca

A [e] pentru o (orice) interpretare e : V A.

Notatie: A Spunem ca este fals n A daca A 6 .Definitia 1.39

Fie o multime de enunturi. Spunem ca A este model al lui daca A pentru orice .Notatie: A

11


Corolarul 1.40

Pentru orice enunturi ,,

I A A 6 ;I A sau A ;I A A implica A

A 6 sau A ;I A A si A ;I A A sau A ;I A A daca si numai daca A ;

Dem.: Aplicatie imediata a Corolarului 1.16.

12


Fie SentL, , enunturi.Corolarul 1.41

(i) daca si numai daca A pentru orice L-structura A;(ii) daca si numai daca orice model al lui este si model al

lui ;

(iii) daca si numai daca orice model al lui este si model allui ;

(iv) este satisfiabila daca si numai daca are un model.

Un enunt este (logic) fals daca este fals n orice structura.

13

Exemple - Enunturi valide si false

Orice limbaj L de ordinul ntai are enunturi valide si enunturi false.Exemplu

x(x = x), A 6 (x = x) pentru orice L-structura A.

Exemplu

Daca L are cel putin un simbol de constanta c , atunci c = c , A 6 (c = c) pentru orice L-structura A.

Notatie

> := x(x = x) := x(x = x)

14

Substitutia

Fie x o variabila a lui L si u termen al lui L.Definitia 1.42

Pentru orice termen t al lui L, definimtx(u) := expresia obtinuta din t prin nlocuirea tuturor

aparitiilor lui x cu u.

Propozitia 1.43

Pentru orice termen t al lui L, tx(u) este termen al lui L.Dem.: Demonstram prin inductie dupa termenul t.

I t = y V . Atunci yx(u) ={y daca y 6= xu daca y = x .

I t = c C. Atunci cx(u) = c .I t = ft1 . . . tm si, conform ipotezei de inductie,

(t1)x(u), . . . , (tm)x(u) sunt termeni. Atunci(ft1 . . . tm)x(u) = f (t1)x(u) . . . (tm)x(u) este termen.

1

Substitutia

I Vrem sa definim analog x(u) ca fiind expresia obtinuta din prin nlocuirea tuturor aparitiilor libere ale lui x cu u.

I De asemenea, vrem ca urmatoarele proprietati naturale alesubstitutiei sa fie adevarate:

x x(u) si x(u) x.

Apar nsa probleme.

Fie := y(x = y) si u := y . Atunci x(u) = y(y = y).Avem

I Pentru orice L-structura A cu |A| 2 si pentru orice a A,A [a]. Deci x este satisfiabila.

I x(u) nu este satisfiabila.

2

Substitutia

Fie x o variabila, u un termen si o formula.

Definitia 1.44

Spunem ca x este libera pentru u n sau ca u este substituibilpentru x n daca pentru orice variabila y care apare n u, nici osubformula a lui de forma y nu contine aparitii libere ale lui x .

Observatie

x este libera pentru u n n oricare din urmatoarele situatii:

I u nu contine variabile;

I nu contine variabile care apar n u;

I nici o variabila din u nu apare legata n ;

I x nu apare n ;

I nu contine aparitii libere ale lui x .

3

Substitutia


Notiunea x este libera pentru u n poate fi definita si prininductie dupa formula astfel:

I daca este formula atomica, atunci x este libera pentru u n;

I daca = , atunci x este libera pentru u n daca sinumai daca x este libera pentru u n ;

I daca = , atunci x este libera pentru u n daca sinumai daca x este libera pentru u atat n cat si n ;

I daca = y, atunci x este libera pentru u n daca sinumai daca

I x nu apare libera n , sauI y nu apare n u si x este libera pentru u n .

4

Substitutia

Fie x o variabila, u termen si o formula a.. x este libera pentruu n .

Definitia 1.45

x(u) := expresia obtinuta din prin nlocuirea tuturoraparitiilor libere ale lui x cu u.

Spunem ca x(u) este o substitutie libera.

Propozitia 1.46

x(u) este formula a lui L.Dem.: Exercitiu.

Notiunea de substitutie libera evita problemele mentionate anteriorsi se comporta cum am astepta.

5

Substitutia

Fie A o L-structura si e : V A.Lema 1.47

Fie x o variabila, u un termen si a = uA(e).(i) Pentru orice termen t, (tx(u))

A(e) = tA(exa).(ii) Pentru orice formula , daca x este libera pentru u n ,

atunciA x(u)[e] A [exa].

Ideea lemei este urmatoarea: a schimba evaluarea e pentru aatribui variabilei x valoarea a A este acelasi lucru cu a nlocui xcu un termen u a carui interpretare sub e este a.

6

Substitutia

Propozitia 1.48

Pentru orice termeni u1 si u2 si orice variabila x ,

(i) pentru orice termen t,

u1 = u2 tx(u1) = tx(u2).(ii) pentru orice formula a.. x este libera pentru u1 si u2 n ,

u1 = u2 (x(u1) x(u2)).Dem.: Fie A o L-structura si e : V A. Presupunem caA (u1 = u2)[e], adica uA1 (e) = uA2 (e) := a A.(i) Conform Lemei 1.47.(i),

(tx(u1))A(e) = tA(exa) = (tx(u2))A(e),

deci A (tx(u1) = tx(u2))[e].(ii) Aplicand Lema 1.47.(ii), obtinem

A x(u1)[e] A [exa] A x(u2)[e].Deci, A (x(u1) x(u2))[e].

7

Substitutia

Propozitia 1.49

Fie o formula si x o variabila.

(i) Pentru orice termen u substituibil pentru x n ,

x x(u), x(u) x.(ii) x , x.(iii) Pentru orice simbol de constanta c,

x x(c), x(c) x.Dem.:

(i) Fie A si e : V A. AtunciA x[e] pentru orice a A, A [exa]

= pentru a = uA(e), A [exa] A x(u)[e] conform Lemei 1.47.(ii).

A doua asertiune rezulta din prima aplicata la .8

Substitutia

Propozitia 1.49

Fie o formula si x o variabila.

(i) Pentru orice termen u substituibil pentru x n ,

x x(u), x(u) x.(ii) x , x.(iii) Pentru orice simbol de constanta c,

x x(c), x(c) x.Dem.: (continuare)

(ii) Aplicam (i) cu u := x .

(iii) Aplicam (i) cu u := c .

9

Substitutia

In general, daca x si y sunt variabile, si x(y) nu sunt logicechivalente: fie Lar , N si e : V N a..e(x) = 3, e(y) = 5, e(z) = 4. Atunci

N (x

Substitutia

Definitia 1.52

este varianta a lui daca este varianta y1, . . . , yk -libera a lui pentru anumite variabile y1, . . . , yk .

Propozitia 1.53

(i) Pentru orice formula , daca este o varianta a lui , atunci ;

(ii) Pentru orice formula si orice termen t, daca variabilele lui tse afla printre y1, . . . , yk si

este varianta y1, . . . , yk -libera alui , atunci x(t) este o substitutie libera.

Dem.: Exercitiu.

13

Axiome logice

Definitia 1.54

Multimea LogAxL FmL a axiomelor logice ale lui L consta din:(i) toate tautologiile;

(ii) pentru orice termeni s, t, u, toate formulele de forma

t = t, s = t t = s, s = t t = u s = u;(iii) pentru orice m 1, f Fm, R Rm si orice termeni

s1, t1, s2, t2, . . . sm, tm, toate formulele de forma

t1 = u1 . . . tm = um ft1 . . . tm = fu1 . . . um,t1 = u1 . . . tm = um (Rt1 . . . tm Ru1 . . . um);

(iv) toate formulele de forma

x(t) x,unde x(t) este o substitutie libera (-axiomele).

Axiomele de la (ii) si (ii) se numesc si axiomele egalitatii.14

Reguli de deductie

Definitia 1.55

Regulile de deductie (sau inferenta) sunt urmatoarele: pentru oriceformule ,,

(i) din si se infera (modus ponens sau (MP)):,

;

(ii) daca x / FV (), atunci din se infera x (-introducerea):

x daca x / FV ().

15

-teoreme

Fie o multime de formule ale lui L.Definitia 1.56

Multimea ThmL() a -teoremelor lui L este intersectia tuturormultimilor de formule care satisfac urmatoarele proprietati:

(i) AxmL ;(ii) ;(iii) este nchisa la regulile de deductie, i.e.

(a) daca , , atunci ;(b) daca si x / FV (), atunci x .

Daca ThmL(), atunci spunem si ca este dedusa dinipotezele .

16

-teoreme

Notatii

`L := este -teoremaThmL := ThmL()`L := `L `L := `L pentru orice .

Definitia 1.57

O formula se numeste teorema (logica) a lui L daca `L .

Conventie

Cand L este clar din context, scriem LogAx ,Thm, Thm(), ` ,` , etc..

17

-teoreme

Definitia -teoremelor da nastere la metoda de demonstratie prininductie dupa -teoreme. Demonstram ca orice -teorema are oproprietate P astfel:

(i) demonstram ca orice axioma are proprietatea P;

(ii) demonstram ca orice formula din are proprietatea P;

(iii) demonstram ca daca si au proprietatea P, atunci are proprietatea P;

(iv) demonstram ca daca are proprietatea P si x / FV (),atunci x are proprietatea P.

1

-teoreme

Lema 1.58

Pentru orice multime de formule si orice formule ,, au locurmatoarele proprietati:

(i) daca este axioma logica, atunci ` ;(ii) daca , atunci ` ;(iii) daca ` si ` , atunci ` ;(iv) daca ` si x / FV (), atunci ` x .

2

-teoreme

Lema 1.59

Pentru orice multimi de formule ,, au loc urmatoareleproprietati:

(i) daca , atunci Thm() Thm(), i.e pentru oriceformula , ` implica ` ;

(ii) Thm Thm(), i.e. pentru orice formula , ` implica ` ;

(iii) Thm(Thm()) = Thm(), i.e. pentru orice formula ,Thm() ` daca si numai daca ` ;

(iv) daca ` , atunci Thm() Thm(), i.e. pentru oriceformula , ` implica ` .

Dem.: Exercitiu.

3

-demonstratii

Definitia 1.60

O -demonstratie (demonstratie din ipotezele ) este o secventade formule 1, . . ., n a.. pentru fiecare i {1, . . . , n}, una dinurmatoarele conditii este satisfacuta:

(i) i este axioma;

(ii) i ;(iii) exista k, j < i a.. k = j i ;(iv) exista j < i si x V , , formule a.. x / FV (),

j = si i = x .O -demonstratie se va numi simplu demonstratie.

4

-demonstratii

Definitia 1.61

Fie o formula. O -demonstratie a lui sau demonstratie a lui din ipotezele este o -demonstratie 1, . . ., n a.. n = . Inacest caz, n se numeste lungimea -demonstratiei.

Propozitia 1.62

Fie o multime de formule si o formula. Atunci ` daca sinumai daca exista o -demonstratie a lui .

Dem.: Exercitiu.

5

Proprietati sintactice

Propozitia 1.63

Pentru orice multimi de formule si orice formula , ` daca sinumai daca exista o submultime finita a lui a.. ` .Dem.: Fie , finita a.. ` . Aplicand Lema1.59.(i) obtinem ca ` . Presupunem ca ` . Conform Propozitiei 1.62, are o-demonstratie 1, . . ., n = . Fie

:= {1, . . . , n}.

Atunci este finita, si 1, . . ., n = este o-demonstratie a lui , deci ` .

6

Teorema tautologiei

Definitia 1.64

Doua formule si se numesc tautologic echivalente dacaF () = F () pentru orice L-evaluare F .

Exemplu

1 (2 . . . (n ) . . .) si (1 . . . n) sunttautologic echivalente.

Propozitia 1.65

Fie n 1 si 1, . . . , n, formule. Urmatoarele sunt echivalente:(i) este consecinta tautologica a formulelor 1, . . . , n;

(ii) 1 (2 . . . (n ) . . .) este tautologie;(iii) (1 . . . n) este tautologie.Dem.: Exercitiu.

7

Teorema tautologiei

Teorema tautologiei 1.66

Daca este consecinta tautologica a formulelor 1, . . . , n si ` 1, . . . , ` n, atunci ` .Dem.: Aplicam Propozitia 1.65 pentru a obtine ca := 1 (2 . . . (n ) . . .) este tautologie. Deoarecetautologiile sunt axiome ale lui L, rezulta ca ` . Aplicand acumipoteza si de n ori faptul ca multimea -teoremelor este nchisa lamodus ponens, obtinem ca ` .

8

Teorema deductiei

Teorema deductiei 1.67

Fie {} o multime de formule si un enunt. Atunci {} ` daca si numai daca ` .

Dem.: (1) ` ipoteza(2) {} ` Lema 1.59.(i)(3) {} ` Lema 1.58.(ii)(4) {} ` (MP): (2), (3).

9

Teorema deductiei



Dem.: (continuare) Prin inductie dupa {}-teoreme. Fie

:= { | ` }. Fie o axioma sau o formula din . Atunci

(1) ` (2) ` ( ) tautologie(3) ` (MP): (1), (2).

Asadar . Fie = . Atunci = este tautologie, deci ` . Asadar .

10

Teorema deductiei



Dem.: (continuare) Demonstram acum ca este nchisa la modus ponens.Presupunem ca , , i.e. ` si ` ( ).Trebuie sa aratam ca , deci ca ` .Afirmatia 1: este consecinta tautologica a formulelor , ( ).Dem.: Fie F o L-evaluare de adevar a..F ( ) = F ( ( )) = 1. Avem urmatoarele cazuri:

(i) F () = 0. Atunci F ( ) = 1.(ii) F () = 1. Atunci F () = 1 si F ( ) = 1, deci F () = 1.

Rezulta ca F ( ) = 1.Conform Teoremei tautologiei, rezulta ca ` .

11

Teorema deductiei



Dem.: (continuare) Demonstram acum ca este nchisa la -introducere.Presupunem ca , i.e. ` ( ). Fie x / FV ().Trebuie sa aratam ca x , deci ca ` (x ) .Afirmatia 2: 1 (2 3) este consecinta tautologica aformulei 2 (1 3).Dem.: Exercitiu.

Obtinem ` ( ) Teorema tautologiei ` x ( ) -introducerea ( enunt, deci x / FV ( )) ` (x ) Teorema tautologiei

12

Inchiderea universala

Definitia 1.68

Fie o formula a.. FV () = {x1, . . . , xn}. Inchiderea universalaa lui este enuntul

:= x1 . . . xn.Notatie: Daca este o multime de formule, := { | }.Observatie

enunt = = ; multime de enunturi = = .

Propozitia 1.69

Daca este multime de enunturi, atunci pentru orice ,

.Dem.: Exercitiu.

13

Teorema de corectitudine

Teorema de corectitudine (soundness) 1.70

Pentru orice multime de formule si orice formula ,

` .

In particular, daca este multime de enunturi, atunci

` .Dem.: Prin inductie dupa -teoreme (exercitiu).

14

Multimi consistente

Definitia 1.71

O multime de formule se numeste consistenta daca exista oformula astfel ncat 6` . se numeste inconsistenta daca nu este consistenta, i.e. ` pentru orice formula .

Propozitia 1.72

Pentru orice multime de formule, urmatoarele sunt echivalente:

(i) este inconsistenta;

(ii) pentru orice formula , ` si ` ;(iii) exista o formula a.. ` si ` .Dem.: Exercitiu.

15

Multimi consistente

Propozitia 1.73

Pentru orice multime de formule, urmatoarele sunt echivalente:

(i) este inconsistenta;

(ii) are o submultime finita inconsistenta.

Dem.: (ii)(i) Exercitiu imediat.(i)(ii) Presupunem ca este inconsistenta. Atunci exista a.. ` si ` . Aplicand Propozitia 1.63 , obtinem submultimifinite 1,2 ale lui a.. 1 ` si 2 ` . Fie := 1 2.Atunci este submultime finita a lui care este inconsistenta.Un rezultat echivalent:

Propozitia 1.74

O multime de formule este consistenta daca si numai daca oricesubmultime finita a lui este consistenta.

16

Multimi consistente

Propozitia 1.75

Fie o multime de formule si un enunt.

(i) ` {} este inconsistenta.(ii) ` {} este inconsistenta.Dem.: (i) ` = {} ` si {} ` = {} este inconsistenta.

(1) {} ` {} este inconsistenta(2) ` Teorema deductiei(3) ` ( ) tautologie(4) ` (MP): (2),(3)

(ii) Exercitiu.

17

Cardinalul unui limbaj

Fie L = (R,F , C) un limbaj de ordinul ntai.Definitia 1.76

Cardinalul lui L este prin definitie

L := |R F C|.

I L este finit daca L este finit.I L este numarabil daca L = |N| = 0.I L este cel mult numarabil daca L este finit sau numarabil.

Propozitia 1.77

|FmL| ={0 daca L este finitL altfel.

18

Teorema de completitudine

Teorema de completitudine (prima forma) 1.78

Orice multime consistenta de enunturi este satisfiabila. Maimult, are un model de cardinalitate |FmL|.

Teorema de completitudine (a doua forma) 1.79

Pentru orice multime de enunturi si orice enunt ,

` .Dem.: Teorema de corectitudine. Presupunem ca 6` . Atunci, conform Propozitiei 1.75.(i), {} este consistenta. Aplicam Teorema de completitudine(prima forma) pentru a conclude ca {} are un model A.Deoarece A si , obtinem ca A este model al lui {}.In particular, A si A , ceea ce este o contradictie.

19

Teorema de compacitate

Propozitia 1.80

O multime de enunturi este satisfiabila daca si numai daca esteconsistenta.

Dem.: Exercitiu usor. Conform Teoremei de completitudine (prima forma).Teorema de compacitate 1.81

O multime de enunturi este satisfiabila daca si numai daca oricesubmultime finita a sa este satisfiabila.

Dem.: Se aplica Propozitia 1.80 si Propozitia 1.74.

1

CAPITOLE DE TEORIA MODELELOR

2

Homomorfisme, izomorfisme

Generalizare a notiunii de homomorfism de la algebra:

Definitia 2.1

Fie A, B doua L-structuri, A = |A|, B = |B| si h : A B ofunctie. Spunem ca h este homomorfism si scriem h : A B daca:

(i) pentru orice m 1, R Rm si orice elemente a1, . . . , am A,

RA(a1, . . . , am) RB(h(a1), . . . , h(am))

(ii) pentru orice m 1, f Fm, si orice elemente a1, . . . , am A,

h(f A(a1, . . . , am)) = f B(h(a1), . . . , h(am))

(iii) pentru orice c C, h(cA) = cB.3


Definitia 2.2

Un homomorfism h : A B se numeste izomorfism daca h estebijectiv.Notatie: h : A ' B.

Definitia 2.3

L-structurile A si B se numesc izomorfe daca exista h : A ' B.

Exemplu

I L = (


Fie A, B doua L-structuri, A = |A|, B = |B| si h : A B.Oricarei evaluari e : V A a lui L n A i se asociaza o evaluare alui L n B: h e : V B, (h e)(v) = h(e(v)).Definitia 2.4

(i) Spunem ca h respecta un termen t daca pentru orice evaluaree : V A,

h(tA(e)) = tB(h e).(ii) Spunem ca h respecta o formula daca pentru orice evaluare

e : V A,

A [e] B [h e].Propozitia 2.5

Orice homomorfism h : A B respecta toti termenii.Dem.: Exercitiu. Prin inductie dupa termeni.

5


I Fie t(x1, . . . , xn) un termen. Atunci h respecta t pentruorice a1, . . . , an A,

h(tA[a1, . . . , an]) = tB[h(a1), . . . , h(an)].

I Fie (x1, . . . , xn) o formula. Atunci h respecta pentruorice a1, . . . , an A,

A [a1, . . . , an] B [h(a1), . . . , h(an)].

Exemplu

L = (


Propozitia 2.6

Fie A, B doua L-structuri. Orice izomorfism h : A ' B respectatoate formulele.

Dem.: (continuare) = x. AtunciA [e] pentru orice a A, A [exa]

pentru orice a A, B [h exa]conform ipotezei de inductie pentru

pentru orice a A, B [(h e)xh(a)]deoarece h exa = (h e)xh(a)

pentru orice b B, B [(h e)xb]deoarece h este surjectiv

B [h e].9

Elementar echivalenta

Definitia 2.7

Doua L-structuri A si B se numesc elementar echivalente (scriemA B) daca pentru orice enunt ,

A B .

Propozitia 2.8

Pentru orice A si B, daca A ' B, atunci A B.Dem.: Fie h : A ' B un izomorfism. Pentru orice enunt , avemA pentru o (orice) evaluare e : V A, A [e]

pentru o (orice) evaluare e : V A, B [h e] B .

Vom vedea ca n general nu este adevarata implicatia reciproca:A B NU implica A ' B.

10

Teorii

Notatie: Pentru orice multime de enunturi , notam

Mod() := clasa modelelor lui .

Notam Mod(1, . . . , n) n loc de Mod({1, . . . , n}).Observatie

Pentru orice multimi de enunturi , si orice enunt ,

(i) Mod() Mod().(ii) = Mod() Mod().(iii) este satisfiabila Mod() 6= .

Definitia 2.9

O multime de enunturi se numeste completa daca pentru oriceenunt ,

sau .11

Teorii

Definitia 2.10

O L-teorie este o multime T de enunturi ale lui L care este nchisala consecinta semantica, i.e.:

pentru orice enunt , T = T .

Observatie: O L-teorie T este completa pentru orice enunt, T sau T .Testul lui Vaught 2.11

Fie L un limbaj cel mult numarabil si T o L-teorie consistenta.Presupunem ca

(i) T nu are modele finite;

(ii) orice doua modele numarabile ale lui T sunt izomorfe.

Atunci T este completa.

12

Teorii

Definitia 2.12

Pentru orice multime de enunturi , teoria generata de estemultimea

Th() := { | este enunt si }.Spunem ca este o multime de axiome pentru Th().

1

Teorii

Propozitia 2.13

Pentru orice multimi de enunturi ,,

(i) Mod() = Mod(Th()).

(ii) Th() este o teorie.

(iii) = Th() Th().(iv) este teorie = Th().(v) Th() este cea mai mica teorie T a.. T .(vi) Th() = { | este enunt valid} este inclusa n orice teorie.Dem.: Exercitiu usor.

2

Teorii

Daca T este teorie si K := Mod(T ) este clasa modelelor lui T ,spunem si ca T axiomatizeaza K.

I O teorie are o infinitate de multimi de axiome.

I O teorie prezentata ca Th() se numeste teorie axiomaticasau teorie prezentata axiomatic.

I Orice teorie poate fi prezentata axiomatic, dar sunteminteresati de multimi de axiome care satisfac anumite conditii.

Definitia 2.14

O teorie T este finit axiomatizabila dacaT = Th() pentru omultime de enunturi finita .

3

Teorii

Definitia 2.15

Pentru orice L-structura A, teoria lui A este:

Th(A) := { | este enunt si A }.

Propozitia 2.16

Pentru orice L-structura A, Th(A) este o teorie completaconsistenta

Dem.: Exercitiu usor.

Propozitia 2.17

Pentru orice L-structuri A si B, A B Th(A) = Th(B).Dem.: Exercitiu usor.

4

Teorii

Propozitia 2.18

Fie T o teorie consistenta. Urmatoarele sunt echivalente:

(i) T este completa.

(ii) Pentru orice model A al lui T , Th(A) = T .(iii) Orice doua modele ale lui T sunt elementar echivalente.

Dem.: (i)(ii) Fie A model al lui T . Evident. Pentru orice enunt Th(A), daca / T , atunci T(deoarece T este completa), deci A , ceea ce contrazicefaptul ca A .(ii)(iii) Fie A,B modele ale lui T . Atunci T = Th(A) = Th(B).Aplicam Propozitia 2.17 pentru a obtine ca A B.(iii)(i) Fie un enunt. Presupunem ca T 6 . Atunci exista unmodel A al lui T a.. A 6 , deci A . Aplicand (iii), obtinemca B pentru orice model al lui T . Asadar, T .

5

Teorii

K este o clasa nevida de L-structuriDefinitia 2.19

Teoria lui K este multimea Th(K) := AK Th(A).Propozitia 2.20

(i) Fiecare A K este model al lui Th(K).(ii) Daca K are cel putin doua elemente A si B care nu sunt

elementar echivalente, atunci Th(K) nu este o teoriecompleta.

Dem.: Exercitiu.

Definitia 2.21

K este axiomatizabila daca K = Mod() pentru o multime deenunturi .

6

Exemple

Pentru orice n 2, notam urmatorul enunt cu n:

x1 . . . xn((x1 = x2) (x1 = x3) . . . (xn1 = xn)),

pe care l scriem mai compact astfel:

n = x1 . . . xn

1i


I L= = (, , )I L=-structurile sunt A = (A), unde A este multime nevida.

Fie A = (A),B = (B) doua L=-structuri.I h : A B h : A B.I h : A ' B h : A B este bijectie.I A ' B |A| = |B|.

9


Propozitia 2.24

Fie A = (A) o L=-structura finita si n = |A|. Atunci enuntul =ncaracterizeaza A pana la izomorfism, i.e.: pentru oriceL=-structura B = (B),

A ' B B =n.Dem.: B =n |B| = n A ' B.Propozitia 2.25

Pentru orice L=-structuri finite A,B, A ' B A B.Dem.: Conform Propozitiei 2.8. Presupunem ca A B si fie n = |A|. Atunci A =n, deciB =n. Se aplica acum propozitia precedenta.

10


Propozitia 2.26

Pentru orice n 1 si orice multime finita A cu n elemente,

Th(=n) = Th(A), unde A = (A).

In particular, Th(=n) este o teorie completa.Dem.: Deoarece A =n, avem ca A Th(=n). Prinurmare, Th(=n) Th(A). Fie Th(A), i.e. A . Vrem sa aratam ca Th(=n),i.e. =n . Fie B = (B) a.. B =n. Atunci A ' B, conformPropozitiei 2.24. Rezulta ca A B, prin urmare B .

11


Propozitia 2.27

Th({n | n 1}) este completa.Dem.: Fie T := Th({n | n 1}). Conform Propozitiei 2.23,A = (A) este model a lui T A este multime infinita.Prin urmare, T este consistenta si nu are modele finite.

In plus, daca A = (A),B = (B) sunt doua modele numarabile alelui T , atunci |A| = |B| = 0, deci A ' B.Putem aplica Testul lui Vaught pentru a conclude ca T estecompleta.

12


Corolarul 2.28

Pentru orice multime infinita A ,

Th({n | n 1}) = Th(A), unde A = (A).Dem.: Deoarece Th({n | n 1}) este completa, putem aplicaPropozitia 2.18.(ii).

Corolarul 2.29

Pentru orice multimi infinite A si B, L=-structurile A = (A),B = (B) sunt elementar echivalente.Dem.: Aplicam Propozitia 2.18.(iii).

13

Exemple - Teoria relatiilor de echivalenta

I L = (, , ) = ()I L-structurile sunt A = (A,), unde este relatie binara.

Consideram urmatoarele enunturi:

(REFL) := x(xx)(SIM) := xy(xy yx)

(TRANZ ) := xyz(xy yz xz)Definitie

Teoria relatiilor de echivalenta este

T := Th((REFL), (SIM), (TRANZ )).

I T este finit axiomatizabila;I Fie K clasa structurilor (A,), unde este relatie de

echivalenta pe A.I K = Mod(T ), deci T axiomatizeaza K.I Spunem si ca T axiomatizeaza clasa relatiilor de echivalenta.

14

Exemple - Teoria relatiilor de echivalenta

Daca adaugam axioma:xy(x 6= y xy z(zx (z = x z = y))),

obtinem teoria relatiilor de echivalenta cu proprietatea ca oriceclasa de echivalenta are exact doua elemente.

15

Exemple - Teoria ordinii partiale

I L = (, , ) = ()I L-structurile sunt A = (A,), unde este relatie binara.

Consideram urmatoarele enunturi:

(REFL) := x(xx)(ANTISIM) := xy(xy yx x = y)

(TRANZ ) := xyz(xy yz xz)Definitie

Teoria ordinii partiale este

T := Th((REFL), (ANTISIM), (TRANZ )).

I T este finit axiomatizabila;I modelele lui T sunt multimile partial ordonate.I T axiomatizeaza clasa relatiilor de ordine partiala.

16

Exemple - Teoria ordinii stricte

I L

Schimbarea limbajelor

Definitia 2.30

Fie L = (RL,FL, CL; ariL) si L+ = (RL+ ,FL+ , CL+ ; ariL+) doualimbaje. Spunem ca L+ este extensie a lui L sau ca L estesublimbaj al lui L+ daca

RL RL+ ; FL FL+ ; CL CL+si ariL este restrictia lui ariL+ la simbolurile nelogice ale lui L.Notatie: L L+

Definitia 2.31

Spunem ca L+ este o extensie prin constante a lui L dacaRL = RL+ ; FL = FL+ ; CL CL+ .

Exemple

L= L pentru orice limbaj L L


Corolarul 2.35

Pentru orice L L+ si orice multime de enunturi a lui L,ThL() = SenL ThL+().Dem.: Exercitiu usor.

Corolarul 2.36

Pentru orice L L si orice L-structuri A,B,(i) A ' B = A L ' B L.(ii) A B = A L B L.Dem.: Exercitiu usor.

25


Definitia 2.37

Fie L un limbaj, A o L-structura si X A.(i) LX este extensia lui L obtinuta adaugand, pentru orice

a X , un nou simbol de constanta a.Spunem ca a este un nume pentru a.

(ii) AX este LX -extensia lui A obtinuta definind pentru oricea X , aAX = a.

Observatia 2.38

Pentru orice formula a lui L cu FV () = {x1, . . . , xn} si pentruorice a1, . . . , an A, fie (a1, . . . , an) enuntul din LA obtinut din prin nlocuirea lui xi cu ai , i = 1, . . . , n. Atunci

A [a1, . . . , an] AA (a1, . . . , an).Dem.: Exercitiu usor.

1

Lema constantelor

Lema constantelor 2.39

Fie L un limbaj, {} FmL si c un simbol de constanta din Lcare nu apare n {}. Atunci

x(c) x.Dem.: este imediata, deoarece x x(c). Fie (A, e) un model a lui , i.e. A o L-structura sie : V A a.. A [e] pentru orice .Vrem sa demonstram ca (A, e) este model al lui x, i.e. pentruorice a A, A [exa].Fie a A arbitrar. Fie L sublimbajul lui L obtinut prin eliminareasimbolului c , A := A L si fie Aa L-extensia lui A n care ceste interpretat cu a (i.e. cAa = a).Deoarece {} FmL , rezulta din Propozitia 2.33 ca pentruorice ,

A [e] A [e] Aa [e].2

Lema constantelor

Lema constantelor 2.39

Fie L un limbaj, {} FmL si c un simbol de constanta din Lcare nu apare n {}. Atunci

x(c) x.Dem.: (continuare)Asadar (Aa, e) este model al lui si deoarece x(c), avem ca

Aa x(c)[e].Deoarece cAa = a, putem aplica Lema 1.47.(ii) pentru a obtine ca

Aa [exa].Aplicand din nou Propozitia 2.33, rezulta

Aa [exa] A [exa] A [exa].Am demonstrat astfel ca pentru orice a A, A [exa], deci ca(A, e) este model al lui x.

3

Elementar echivalenta implica izomorfism - L finit

Propozitia 2.40

Fie L un limbaj finit. Pentru orice L-structura finita A, exista unenunt A care caracterizeaza A pana la izomorfism, i.e.: pentruorice L-structura B,

A ' B B A.Dem.: (Nu se cere la examen) Fie A o L-structura finita cu nelemente a1, . . . , an. Consideram enuntul

A := x1x2 . . . xn

1i


Propozitia 2.40

Fie L un limbaj finit. Pentru orice L-structura finita A, exista unenunt A care caracterizeaza A pana la izomorfism, i.e.: pentruorice L-structura B, A ' B B A.Dem.: (continuare)

(i) daca s este un simbol de constanta c si cA = ai , atunci

s := xi = c .

(ii) daca s este un simbol de relatie R de aritate m, atunci

s :=

(ai1 ,...,aim )RARxi1 . . .Rxim

(ai1 ,...,aim )/RA

Rxi1 . . .Rxim .

(iii) daca s este un simbol de operatie f de aritate m, atunci

s :=

fA(ai1 ,...,aim )=aj

fxi1 . . . xim = xj .

5


Propozitia 2.40

Fie L un limbaj finit. Pentru orice L-structura finita A, exista unenunt A care caracterizeaza A pana la izomorfism, i.e.: pentruorice L-structura B, A ' B B A.Dem.: (continuare) Fie B o L-structura. Atunci B satisface A exista b1, . . . , bn B a..(i) pentru orice 1 i < j n, bi 6= bj si pentru orice b B,

b {b1, . . . , bn}. Prin urmare B = {b1, . . . , bn}.(ii) B s [b1, . . . , bn] B = {b1, . . . , bn} si functia h : A B, h(ai ) = bi este

izomomorfism de la A la B.Propozitia 2.41

Fie L un limbaj finit. Pentru orice L-structuri finite A,B, A ' B A B.Dem.: Exercitiu usor.

6

Elementar echivalenta implica izomorfism - L arbitrar

Teorema 2.42

Pentru orice limbaj L, orice L-structura finita A si oriceL-structura B,

A B A ' B.Dem.: evidenta, conform Propozitiei 2.8. Presupunem prin reducere la absurd ca A 6' B. Fie A = |A|,B = |B| si n = |A|. Atunci A =n, deci B =n, deoarece =neste enunt si A B. Deci, B este finita, cu n elemente.Rezulta ca numarul functiilor bijective f : A B este finit.Conform presupunerii, nicio bijectie f : A B nu este izomorfism,deci nu e homorfism. Asadar, pentru orice f , exista un simbol Sf allui L a.. f nu transporta interpretarea lui Sf de la A la B.Fie L sublimbajul finit al lui L ale carui simboluri ne-logice suntexact aceste simboluri Sf . Notam A = A L, B = B L. Eclar ca A 6' B. Rezulta ca A 6 B (conform Propozitiei 2.40)si ca A 6 B (conform Corolarului 2.36.(ii)). Contradictie.

7

Teorema de compacitate

Fie L un limbaj de ordinul ntai. Reamintim Teorema decompacitate:

O multime de enunturi este satisfiabila daca si numai daca oricesubmultime finita a sa este satisfiabila.

I A, B sunt L-structuri: A = |A|, B = |B|.I Cardinalul unei L-structuri A este prin definitie |A|.I A este finita (numarabila, cel mult numarabila) daca A este

finita (numarabila, cel mult numarabila).

8

Teorema de compacitate - aplicatii

Propozitia 2.43

Clasa L-structurilor finite nu este axiomatizabila, i.e. nu exista omultime de enunturi a..

(*) pentru orice L-structura A, A A este finita.Dem.: Presupunem prin reducere la absurd ca exista SenLa.. (*) are loc. Fie

:= {n | n 1}.Demonstram ca este satisfiabila folosind Teorema decompacitate. Fie 0 o submultime finita a lui . Atunci

0 {n1 , . . . ,nk} pentru un k N.Fie A o L-structura finita a.. |A| max{n1, . . . , nk} (de ceexista?). Atunci A ni pentru orice i = 1, . . . , k si A deoarece A este finita.

9


Propozitia 2.43

Clasa L-structurilor finite nu este axiomatizabila, i.e. nu exista omultime de enunturi a..

(*) pentru orice L-structura A, A A este finita.Dem.: (continuare)Aplicand Teorema de compacitate, rezulta ca

= {n | n 1}.are un model B.Deoarece B , B este finita.Deoarece B {n | n 1}, rezulta (conform Propozitiei 2.23) caB este infinita.Am obtinut o contradictie.

Corolarul 2.44

Clasa multimilor nevide finite nu este axiomatizabila n L=. 10


Propozitia 2.45

Clasa L-structurilor infinite este axiomatizabila, dar nu este finitaxiomatizabila.Dem.: Notam cu KInf clasa L-structurilor infinite.Conform Propozitiei 2.23, pentru orice L-structura A,

A KInf A este infinita A {n | n 1}.Prin urmare,

KInf = Mod({n | n 1})deci e infinit axiomatizabila.

11


Propozitia 2.45

Clasa L-structurilor infinite este axiomatizabila, dar nu este finitaxiomatizabila.Dem.: (continuare) Presupunem ca KInf este finit axiomatizabila,deci exista

:= {1, . . . , n} SenL a.. KInf = Mod().Fie := 1 . . . n. Atunci KInf = Mod().Rezulta ca pentru orice L-structura A,

A este finita A / KInf A 6 A .Asadar, clasa L-structurilor finite este axiomatizabila, ceea cecontrazice Propozitia 2.43.

Corolarul 2.46

Clasa multimilor infinite nu este finit axiomatizabila n L=.12


Propozitia 2.47

Fie o multime de enunturi ale lui L cu proprietatea(*) pentru orice m N, are un model de cardinal m.

Atunci are un model infinit.Dem.: Fie

:= {n | n 1}.Demonstram ca este satisfiabila folosind Teorema decompacitate. Fie 0 o submultime finita a lui . Atunci

0 {n1 , . . . ,nk} pentru un k N.Fie m := max{n1, . . . , nk}. Conform (*), are un model A a..|A| m. Atunci A ni , deci A 0.Aplicand Teorema de compacitate, rezulta ca are un model B.Prin urmare, B este un model infinit al lui .

13


Propozitia 2.48

Daca un enunt este adevarat n orice L-structura infinita, atunciexista m N a.. este adevarat n orice L-structura de cardinal m.Dem.: Presupunem ca nu e adevarat. Fie := {}. Atuncipentru orice m N, are un model de cardinal m. AplicandPropozitia 2.47, rezulta ca are un model infinit A. Prin urmare,A 6 , ceea ce contrazice ipoteza.

14


Propozitia 2.49

Fie o multime de enunturi cu proprietatea ca

(*) pentru orice m N, are un model de cardinal m.Atunci

(i) are un model infinit.

(ii) Clasa modelelor finite ale lui nu este axiomatizabila.

(iii) Clasa modelelor infinite ale lui este axiomatizabila, dar nueste finit axiomatizabila.

Dem.: Exercitiu.

15

Aplicatie a Teoremei de compacitate - multimi bine ordonate

Definitia 2.50

Fie A o multime nevida. O relatie de buna ordonare pe A este orelatie de ordine totala < pe A cu proprietatea ca orice submultimenevida a lui A are minim.Spunem ca (A,

Teoria Ramsey

Teoria Ramsey este o ramura a combinatoricii, a carei temaprincipala este:

Complete disorder is impossible. (T.S. Motzkin)

O structura mare, oricat de haotica ar fi, contine substructuri curegularitati.

Problema tipica

O anumita structura este partitionata ntr-un numar finit de clase.Ce tip de substructura ramane intacta n cel putin una din clase?

I Rezultatele din teoria Ramsey sunt foarte puternice, deoareceele sunt generale, se obtin presupunand ipoteze foarte slabe.

I Graham, Rothschild, Sperner, Ramsey Theory, 1990.

1

Teoria Ramsey

Se dau o multime X si o colectie G de submultimi bune ale lui X .Fie r N, r 1.Definitia 2.52

O r -colorare a lui X este o functie c : X {1, 2, . . . , r}. Pentrux X , c(x) este culoarea lui x . O submultime A X se numestemonocromatica daca toate elementele din A au aceeasi culoare.

Definitia 2.53

O familie de multimi C1, . . . ,Cr se numeste partitie a lui X dacaX = ri=1Ci si Ci Cj = pentru orice i 6= j {1, . . . , n}.Urmatoarele sunt echivalente:I Pentru orice partitie X = ri=1Ci a lui X , exista i {1, . . . , r}

si G G a.. G Ci .I Pentru orice r -colorare a lui X exista o multime G G

monocromatica. 2

Teoria Ramsey

Teorema Schur (1916)

Fie r N, r 1 si N = ri=1Ci o partitie a lui N. Atunci existai {1, . . . , r} a..

{x , y , x + y} Ci pentru x , y N.

X = N, G = {x , y , x + y | x , y N}.

Versiunea cu colorari: Pentru orice r -colorare a lui N existax , y N a.. multimea {x , y , x + y} este monocromatica.

3

Teoria Ramsey

Teorema van der Waerden (1927)

Fie r N, r 1 si N = ri=1Ci o partitie a lui N. Pentru oricek N exista i {1, . . . , r} a.. Ci contine progresii aritmetice delungime k .

I rezultat central n teoria RamseyI una din cele trei perle n teoria numerelor Khintchin (1948)I demonstratie combinatoriala prin inductie dubla dupa r si k .

X = N, G = multimea progresiilor aritmetice de lungime k .

Versiunea cu colorari: Orice colorare finita a lui N contine progresiiaritmetice monocromatice de lungime finita arbitrara.

4

Teoria Ramsey

Y multime, k N, k 1. Notam cu [Y ]k multimea submultimilorlui Y cu k elemente:

[Y ]k = {A Y | |A| = k}.Putem sa ne gandim la [Y ]2 ca fiind multimea muchiilor grafuluicomplet peste Y .

Teorema Ramsey 2.54

Fie Y o multime infinita, k, r N \ {0} si [Y ]k = ri=1Ci o partitiea lui [Y ]k . Atunci exista i {1, . . . , r} si o submultime infinita Ba lui Y a.. [B]k Ci .I rezultat structural general, nu depinde de proprietatile

aritmetice ale lui N;I articolul lui Ramsey: On a problem of formal logic (1930);I teorema lui Ramsey a fost popularizata de Erdos si Szekeres,

care au redescoperit-o ntr-un articol clasic din 1935.5

Teoria Ramsey

Teorema Ramsey - versiunea cu colorari 2.55

Fie Y o multime infinita si k , r N \ {0}. Pentru orice r -colorare alui [Y ]k , exista o submultime infinita B a lui Y a.. [B]k estemonocromatica.

Versiune echivalenta


Fie k , r N \ {0}. Pentru orice r -colorare a lui [N]k , exista osubmultime infinita B a lui N a.. [B]k este monocromatica.

Consecinta: Principiul cutiei - varianta infinita (InfinitePigeonhole Principle)

Fie Y o multime infinita si r N \ {0}. Pentru orice r -colorare alui Y , exista o submultime infinita monocromatica B a lui Y .

6

Teoria Ramsey


Fie k , r N \ {0}. Pentru orice r -colorare a lui [N]k , exista osubmultime infinita B a lui N a.. [B]k este monocromatica.

Notam [n] := {1, . . . , n} si [n]k = {A [n] | |A| = k}.Teorema Ramsey finitara 2.57

Fie k , r N \ {0}. Pentru orice m N, exista n N a.. pentruorice r -colorare a lui [n]k exista o submultime D [n] de cardinalm cu proprietatea ca [D]k este monocromatica.

I Generalizare a Principiului cutiei (Pigeonhole Principle): Dacaavem r cutii si r + 1 obiecte, atunci cel putin ntr-o cutie vorfi doua obiecte. Daca coloram r + 1 obiecte cu r culori,atunci exista doua obiecte care au aceeasi culoare.

I Pentru k, r ,m date, notam cel mai mic n cu proprietatea demai sus cu R(k , r ,m). Atunci R(1, r , 2) = r + 1.

7

Aplicatie a Teoremei de compacitate - Teorema Ramsey finitara

Vom demonstra folosind Teorema de compacitate ca TeoremaRamsey implica Teorema Ramsey finitara.Pentru simplitate, consideram r = 2, k = 2.

Teorema Ramsey finitara 2.58

Pentru orice m N, exista n N a.. pentru orice 2-colorare a lui[n]2 exista o submultime D [n] de cardinal m a.. [D]2 estemonocromatica.Dem.: Presupunem prin reducere la absurd ca teorema nu are loc.Atunci exista M N cu urmatoarea proprietate:

(*) pentru orice n N exista o 2-colorare a lui [n]2 a..[n] nu are submultimi D de cardinal M cu proprietatea ca

[D]2 este monocromatica.

In continuare, fixam M ca mai sus.8



Pentru orice m N, exista n N a.. pentru orice 2-colorare a lui[n]2 exista o submultime D [n] de cardinal m a.. [D]2 estemonocromatica.Dem.: (continuare)Pentru orice multime nevida D,

I oricarei 2-colorari c a lui [D]2, i asociem relatia binara Rc peD definita astfel:

Rc = {(a, b) D2 | c({a, b}) = 1}.

I oricarei relatii binare R pe D i asociem 2-colorarea cR a lui[D]2 definita astfel: pentru orice {a, b} D,

cR({a, b}) = 1 (a, b) R.9



Pentru orice m N, exista n N a.. pentru orice 2-colorare a lui[n]2 exista o submultime D [n] de cardinal m a.. [D]2 estemonocromatica.Dem.: (continuare) Fie L limbajul de ordinul ntai care continesimbolurile de constanta {cn | n 1} si un simbol U de relatiebinara. Pentru orice n M, definim un enunt n din L cuurmatoarea proprietate: pentru orice A = (A, {cAn | n 1},UA),A n cAi 6= cAj pentru orice i 6= j {1, . . . , n}

si pentru orice D {cA1 , ..., cAn } de cardinal M,[D]2 nu este monocromatica relativ la 2-colorarea cUA .

n =

1i



Pentru orice m N, exista n N a.. pentru orice 2-colorare a lui[n]2 exista o submultime D [n] de cardinal m a.. [D]2 estemonocromatica.Dem.: (continuare) Fie

C = {cBn | n N} B.

Deoarece B , avem ca cBn 6= cBm pentru n 6= m. Prin urmare,|C | = |N| = 0. Aplicand Teorema Ramsey 2.56 pentru multimeainfinita C si 2-colorarea cUB a lui [B]

2 (deci si a lui [C ]2), rezultaca C are o submultime infinita D a.. [D]2 este monocromatica.Deoarece D este infinita, exista N a.. multimeaDN := D {cB1 , . . . , cBN} are cardinal M. Cum [DN ]2 [D]2 estemonocromatica, am obtinut o contradictie cu faptul ca B N .

13

Aritmetica

Consideram limbajul L = (+, , S , 0), unde +, sunt simboluri deoperatii binare, S este simbol de operatie unara si 0 este simbol deconstanta.

Pentru orice n N, definim prin inductie L-termenul (n) astfel:

(0) = 0, (n + 1) = S(n).

Fie L-structura N = (N,+, , S , 0). Atunci (n)N = n pentruorice n N. Prin urmare, N = {(n)N | n N}.

Definitia 2.59

O L-structura A se numeste non-standard daca exista a A a..a 6= (n)A pentru orice n N. Un astfel de element a se numesteelement non-standard.

1

Aritmetica

Teorema 2.60

Exista un model non-standard al teoriei Th(N ).Dem.: Fie c un simbol de constanta nou, L+ = L {c} si

= Th(N ) {((n) = c) | n N}.Demonstram ca este satisfiabila folosind Teorema decompacitate. Fie 0 o submultime finita a lui ,

0 Th(N ) {((n1) = c), . . . ,((nk) = c)}.Fie n0 > max{n1, . . . , nk}. Consideram L+-extensia N+ a lui Ndefinita astfel: cN+ := n0. Atunci N+ 0.Aplicand Teorema de compacitate, rezulta ca are un model

A = (A,+A, A, SA, 0A, cA).Rezulta ca a := cA este element non-standard al lui A.

2

Forma normala prenex

Definitia 2.61

O formula care nu contine cuantificatori se numeste libera decuantificatori (quantifier-free).

Definitia 2.62

O formula este n forma normala prenex daca

= Q1x1Q2x2 . . .Qnxn ,

unde n N, Q1, . . . ,Qn {, }, x1, . . . , xn sunt variabile si este formula libera de cuantificatori. Formula se numestematricea lui si Q1x1Q2x2 . . .Qnxn este prefixul lui .

Exemple de formule n forma normala prenex:

I Formulele universale: = x1x2 . . . xn , unde este liberade cuantificatori

I Formulele existentiale: = x1x2 . . . xn , unde estelibera de cuantificatori 3


Fie o formula si t1, . . . , tn termeni care nu contin variabile din .Notam cu x1,...,xn(t1, . . . , tn) formula obtinuta din substituindtoate aparitiile libere ale lui x1, . . . , xn cu t1, . . . , tn respectiv.

Notatii: c = , c = .Teorema de forma normala prenex 2.63

Pentru orice formula exista o formula n forma normalaprenex a.. si FV () = FV ().Dem.: Aplicam inductia pe formule. Avem urmatoarele cazuri: este formula atomica. Atunci := . = si, conform ipotezei de inductie, exista o formula = Q1x1 . . .Qnxn0 n forma normala prenex a.. siFV () = FV (). Definim

:= Qc1 x1 . . .Qcnxn0.

Atunci este n forma normala prenex, = siFV () = FV () = FV () = FV (). 4


Teorema de forma normala prenex 2.63

Pentru orice formula exista o formula n forma normalaprenex a.. si FV () = FV ().Dem.: (continuare) = si, conform ipotezei deinductie, exista formulele n forma normala prenex

= Q1x1 . . .Qnxn0, = S1z1 . . . Smzm0

a.. , FV () = FV (), si FV () = FV ().Notam cu V0 multimea tuturor variabilelor care apar n

sau .Fie (resp. ) varianta V0-libera a lui (resp. ). Atunci

= Q1y1 . . .Qnyn0, = S1w1 . . . Smwm0,

unde y1, . . . , yn,w1, . . . ,wm sunt variabile care nu apar n V0,0 = 0x1,...,xn(y1, . . . , yn) si 0 = 0z1,...,zm(w1, . . . ,wm).

5


Teorema de forma normala prenex 2.63

Pentru orice formula exista o formula n forma normalaprenex a.. si FV () = FV ().Dem.: (continuare) Conform Propozitiei 1.53, si .De asemenea, FV () = FV () si FV () = FV (). Definim

:= Qc1 y1 . . .QcnynS1w1 . . . Smwm (0 0).

Atunci este n forma normala prenex, FV () = FV () si

(a se vedea (S3.1)) = .

= x si, conform ipotezei de inductie, exista o formula nforma normala prenex a.. si FV () = FV ().Definim := x.

6

Scufundari

Fie L = (R,F , C) un limbaj de ordinul ntai, A, B douaL-structuri, A = |A|,B = |B|.Definitia 2.64

Un homomorfism h : A B se numeste scufundare daca h esteinjectiv.Notatie: h : A 0 B.

Propozitia 2.65

O functie h : A B este scufundare h : A B respectatoate formulele libere de cuantificatori.Dem.: Exercitiu.

7

Substructuri

Fie A, B doua L-structuri a.. A B si A,B : A B, (a) = ainjectia canonica.

Definitia 2.66

Spunem ca A este substructura a lui B sau ca B este extensie a luiA daca A,B este scufundare.Notatie: A B.Prin urmare, A B (i) pentru orice m 1, R Rm si orice elemente a1, . . . , am A,

RA(a1, . . . , am) RB(a1, . . . , am)(ii) pentru orice m 1, f Fm si orice elemente a1, . . . , am A,

f A(a1, . . . , am) = f B(a1, . . . , am)

(iii) pentru orice c C, cA = cB.8

Substructuri

Exemplu

L = (R), unde R simbol de relatie binara. Atunci (N,

Substructuri

Fie f : Mn M si 6= S M. Spunem ca S este nchisa la fdaca pentru orice a1, . . . , an S , f (a1, . . . , an) S .Propozitia 2.67

Fie B o L-structura si 6= X |B|. Urmatoarele sunt echivalente:(i) X este domeniul unei substructuri (unice) a lui B;(ii) X este nchisa la f B pentru orice f F si cB X pentru

orice c C.Dem.: Exercitiu usor.

Corolarul 2.68

Daca F = C = , atunci orice submultime nevida a lui |B| estedomeniul unei substructuri unice a lui B.

1

Substructuri

Daca o submultime X a lui |B| nu satisface conditia (ii) dinPropozitia 2.67, atunci X nu este domeniul unei substructuri a luiB, dar exista o submultime a lui |B| care contine pe X si care estedomeniul unei substructuri a lui B.Propozitia 2.69

Fie B o L-structura si X |B|. Daca X 6= sau C 6= , atunciexista o substructura X B a lui B cu urmatoarele proprietati:(i) X | X B |.(ii) X B D pentru orice substructura D a lui B a.. X |D|.Dem.: Definim:

A0 = X {cB | c C} 6= An+1 = An {f B(a1, . . . , am) | m 1, f Fm, a1, . . . , am An}

A =nN

An.

2

Substructuri

Propozitia 2.69

Fie B o L-structura si X |B|. Daca X 6= sau C 6= , atunciexista o substructura X B a lui B cu urmatoarele proprietati:(i) X | X B |.(ii) X B D pentru orice substructura D a lui B a.. X |D|.Dem.: (continuare) Se verifica usor ca A este cea mai micamultime care contine X {cB | c C} si este nchisa la toatefunctiile f B pentru f F . Atunci X B este unica substructura alui B cu domeniul A.Definitia 2.70

X B se numeste substructura lui B generata de X .

Observatia 2.71

Daca X este cel mult numarabila si L este este cel mult numarabil,atunci si X B este cel mult numarabila. 3

Substructuri

Propozitia 2.72

Fie B o L-structura. Daca L are cel putin un simbol de constanta,atunci

| B | = {tB | t este termen nchis al lui L}.Dem.: Exercitiu.

Exemple

I L = (S , 0), N = (N,S , 0). Atunci | B | = N, deciB = N .

I L = (0), N = (N, 0). Atunci B = ({0}, 0).

4

Substructuri elementare

Fie A, B doua L-structuri.Propozitia 2.73

Presupunem ca A B. Atunci A B pentru orice formulalibera de cuantificatori si orice evaluare e : V A,

A [e] B [e].Dem.: Exercitiu.

Definitia 2.74

Spunem ca A este substructura elementara a lui B sau ca B esteextensie elementara a lui A daca(i) A B;(ii) pentru orice formula si orice evaluare e : V A,

A [e] B [e].Notatie: A B.

5


Propozitia 2.75

Daca A B, atunci A B si A B.Dem.: Exercitiu usor.

Exemplu

Fie L = (), A = (N \ {0},) si B = (N,). Atunci A B siA ' B (de ce?), dar A B.Consideram formula = y(xy). Atunci

A [1], dar B 6 [1].i.e. 1 este cel mai mic element n A, dar nu n B.Consideram formula = y(yx (x = y)). Atunci

B [1], dar A 6 [1].i.e. 1 are un predecesor n B, dar nu n A.

6


Urmatorul rezultat este un instrument foarte util pentru ademonstra ca o substructura este elementara.

Propozitia 2.76 (Criteriul lui Tarski)

Presupunem ca A B si ca pentru orice formula , orice evaluaree : V A si orice variabila x ,

B x[e] exista a A a.. B [exa].Atunci A B.Dem.: (Nu se cere la examen) Demonstram prin inductie dupaformule ca pentru orice formula ,

(*) pentru orice evaluare e : V A, A [e] B [e].Avem urmatoarele cazuri: este formula atomica. Atunci (*) rezulta din faptul ca A Bsi Propozitia 2.73. Pasii de inductie pentru si sunt imediati.

7


Propozitia 2.76 (Criteriul lui Tarski)

Presupunem ca A B si ca pentru orice formula , orice evaluaree : V A si orice variabila x ,

B x[e] exista a A a.. B [exa].Atunci A B.Dem.: (continuare) = x. Atunci x.

B [e] B x[e] B 6 x[e] pentru orice a A, B 6 [exa]

din ipoteza

pentru orice a A, B [exa] pentru orice a A, A [exa]

din ipoteza de inductie

A [e].8

Teorema Lowenheim-Skolem n jos

Putem enunta acum unul din rezultatele centrale ale teorieimodelelor.

Teorema Lowenheim-Skolem n jos 2.77

Pentru orice limbaj cel mult numarabil L, orice L-structura B siorice submultime cel mult numarabila X B, exista o L-structuracel mult numarabila A a.. X A si A B.

Corolarul 2.78

Pentru orice limbaj cel mult numarabil L si orice multime deenunturi, daca are un model, atunci are un model cel multnumarabil.Dem.: Exercitiu.

9



Pentru orice limbaj cel mult numarabil L, orice L-structura B siorice submultime cel mult numarabila X B, exista o L-structuracel mult numarabila A a.. X A si A B.Dem.: Pentru orice formula si variabila y definim oconstanta/functie Skolem F,y .

Daca formula y este enunt, atunci F,y este un element al lui Bdefinit astfel:

I Daca B y, atunci multimea S1 := {b B | B [b]}este nevida. F,y este un element arbitrar al lui S1.

I Daca B 6 y, atunci F,y este un element arbitrar al lui B.Ca urmare, B y = B [F,y ].

10



Pentru orice limbaj cel mult numarabil L, orice L-structura B siorice submultime cel mult numarabila X B, exista o L-structuracel mult numarabila A a.. X A si A B.Dem.: (continuare) Daca FV (y) = {x1, . . . , xk}, k 1, atuncidefinim F,y : B

k B astfel: pentru orice b1, . . . , bk B,I Daca B y[b1, . . . , bk ], atunci multimea

S2 := {b B | B [b1, . . . , bk , b]} este nevida.F,y (b1, . . . , bk) este un element arbitrar al lui S2.

I Daca B 6 y[b1, . . . , bk ], atunci F,y (b1, . . . , bk) este unelement arbitrar al lui B.

Ca urmare,

B y[b1, . . . , bk ] B [b1, . . . , bk ,F,y (b1, . . . , bk)].11



Pentru orice limbaj cel mult numarabil L, orice L-structura B siorice submultime cel mult numarabila X B, exista o L-structuracel mult numarabila A a.. X A si A B.Dem.: (continuare) Extindem constructia lui X B (a se vedeaPropozitia 2.69) nchizand-o si la constantele si functiile Skolem.Fie A cea mai mica submultime a lui B care:

I contine X {cB | c CL} {F,y | y enunt};I este nchisa la f B pentru orice f FL;I este nchisa la functiile Skolem F,y , cand y nu este enunt.

Obtinem ca A este domeniul unei substructuri unice A a lui B.Deoarece L este cel mult numarabil, A este cel mult numarabila.Aplicand Criteriul lui Tarski 2.76, rezulta imediat ca A B.

12

Teoria Modelelor CURS

Documents

Transcript of Teoria Modelelor CURS