Eliminarea cuantificatoarelor

În  logica matematică , sau mai precis în teoria modelelor, eliminarea cuantificatorilor  este acțiunea constând în găsirea unei  formule fără cuantificator echivalentă cu o formulă dată care conține eventual  cuantificatori în teoria considerată a unui anumit limbaj.

Astfel, dacă luăm în considerare teoria  corpurilor reale închise , limbajul acestei teorii este L = {+, •, <, 0,1} unde +, • sunt două simboluri funcționale ale ariității 2, <este un simbol de relație binară, și 0,1 sunt două simboluri constante, formula L ∃ x  ( ax² +  bx  +  c  = 0) este echivalentă cu formula L  în teorie, deoarece în această teorie  ax² +  bx  +  c  = 0 admite o rădăcină dacă și numai dacă  a , b și c sunt toate zero, sau a este zero, dar b este diferit de zero, sau un non-zero și este pozitiv. (la=0∧b=0∧vs.=0)∨(la=0∧b≠0)∨(la≠0∧¬(b2-4lavs.<0)){\ displaystyle (a = 0 \ land b = 0 \ land c = 0) \ lor (a = 0 \ land b \ not = 0) \ lor (a \ not = 0 \ land \ lnot (b ^ {2} -4ac <0))}b2-4lavs.{\ displaystyle b ^ {2} -4ac}

Definiții

Fie L un limbaj și T o teorie L, spunem că T admite eliminarea cuantificatoarelor dacă pentru orice L-formula F, există o L-formula G fără un cuantificator astfel încât . Cu alte cuvinte, o teorie T a limbajului L admite eliminarea cuantificatorilor dacă orice formulă a limbajului L este echivalentă cu o formulă fără cuantificator în această teorie. T⊨F↔G{\ displaystyle T \ models F \ leftrightarrow G}

Interesul în eliminarea cuantificatorilor

Formulele fără variabile sunt adesea mai ușor de decis; algoritmul de eliminare cuantificator poate fi, prin urmare, utilizat ca procedură de decizie pentru această teorie. Într-o teorie decisivă care admite eliminarea cuantificatorilor, există un algoritm care prin acceptarea unei formule dă întotdeauna o formulă fără cuantificator. Singura problemă este eficiența algoritmului.

De asemenea, ne permite să înțelegem mai bine seturile definibile într-o teorie.

Unele criterii pentru eliminarea cuantificatorilor

Criteriul 1

Fie o teorie L. T{\ displaystyle T}

Să presupunem că pentru orice formulă L fără un cuantificator există o formulă L fără un cuantificator astfel încât . F(v¯,w){\ displaystyle F ({\ bar {v}}, w)}G(v¯){\ displaystyle G ({\ bar {v}})}T⊨∃wF(v¯,w)↔G(v¯){\ displaystyle T \ models \ există wF ({\ bar {v}}, w) \ leftrightarrow G ({\ bar {v}})}

Apoi, T admite eliminarea cuantificatorilor.

Dovadă

Fie o formulă L. Arătăm prin inducție asupra complexității că există o formulă L fără cuantificator astfel încât . F(X1,X2,...,Xnu){\ displaystyle F (x_ {1}, x_ {2}, ..., x_ {n})}F{\ displaystyle F}G{\ displaystyle G}T⊨F↔G{\ displaystyle T \ models F \ leftrightarrow G}

Dacă atunci să întrebăm . Să presupunem că proprietatea este adevărată pentru toate formulele de complexitate strict mai mici decât . Dacă există trei cazuri: fie , fie prin ipoteză de inducție există fără un cuantificator care să fie echivalent cu , este suficient să se stabilească ; adică , atunci prin ipoteză de inducție există și fără cuantificator astfel încât și , și am stabilit ; sau , prin ipoteză de inducție, există fără un cuantificator astfel încât , și prin ipoteză, există fără un cuantificator astfel încât , să punem . |F|=0{\ displaystyle | F | = 0}G=F{\ displaystyle G = F}nu{\ displaystyle n}|F|=nu{\ displaystyle | F | = n}F: =¬H1{\ displaystyle F: = \ l nu H_ {1}}H2{\ displaystyle H_ {2}}H1{\ displaystyle H_ {1}}H2{\ displaystyle H_ {2}}G: =¬H2{\ displaystyle G: = \ l nu H_ {2}}F: =H1∧H2{\ displaystyle F: = H_ {1} \ land H_ {2}}H3{\ displaystyle H_ {3}}H4{\ displaystyle H_ {4}}T⊨H1↔H3{\ displaystyle T \ models H_ {1} \ leftrightarrow H_ {3}}T⊨H2↔H4{\ displaystyle T \ models H_ {2} \ leftrightarrow H_ {4}}G: =H3∧H4{\ displaystyle G: = H_ {3} \ land H_ {4}}F: =∃XH1{\ displaystyle F: = \ există xH_ {1}}H2{\ displaystyle H_ {2}}T⊨∃XH1↔∃XH2{\ displaystyle T \ models \ există xH_ {1} \ leftrightarrow \ există xH_ {2}}H3{\ displaystyle H_ {3}}T⊨∃XH2↔H3{\ displaystyle T \ models \ există xH_ {2} \ leftrightarrow H_ {3}}G: =H3{\ displaystyle G: = H_ {3}}

Exemplu: DLO

Arătăm că (Dense Linear Ordering) admite eliminarea cuantificatorilor prin verificarea condiției criteriului 1. Cu alte cuvinte, să fie o formulă fără cuantificator, să căutăm o formulă fără cuantificator astfel încât . DLO{\ displaystyle DLO}F(X1,...,Xnu,y){\ displaystyle F (x_ {1}, \ ldots, x_ {n}, y)}G(X1,...,Xnu){\ displaystyle G (x_ {1}, \ ldots, x_ {n})}DLO⊨F↔G{\ displaystyle DLO \ models F \ leftrightarrow G}

F{\ displaystyle F}este fără cuantificator, deci este echivalent cu o formulă în formă disjunctivă în care sunt formule atomice (sau negarea lor) ale limbajului . De parcă și numai dacă pentru un anumit , este echivalent cu o formulă a formei în care sunt formule atomice (sau negarea lor) ale limbajului . F{\ displaystyle F}⋁eu⋀jLAeu,j(X1,...,Xnu,y){\ displaystyle \ bigvee _ {i} \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}LAeu,j{\ displaystyle A_ {i, j}}DLO{\ displaystyle DLO}DLO⊨⋁eu⋀jLAeu,j(X1,...,Xnu,y){\ displaystyle DLO \ models \ bigvee _ {i} \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}DLO⊨⋀jLAeu,j(X1,...,Xnu,y){\ displaystyle DLO \ models \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}eu{\ displaystyle i}F{\ displaystyle F}⋀euLAeu(X1,...,Xnu,y){\ displaystyle \ bigwedge _ {i} A_ {i} (x_ {1}, ..., x_ {n}, y)}LAeu{\ displaystyle A_ {i}}DLO{\ displaystyle DLO}

Ca , , , și , se poate presupune că sunt de forma: sauDLO⊨¬(X<y)↔(y<X∨X=y){\ displaystyle DLO \ models \ lnot (x <y) \ leftrightarrow (y <x \ lor x = y)}DLO⊨¬(X=y)↔(X<y∨y<X){\ displaystyle DLO \ models \ lnot (x = y) \ leftrightarrow (x <y \ lor y <x)}DLO⊨X=X↔⊤{\ displaystyle DLO \ models x = x \ leftrightarrow \ top}DLO⊨X<X↔⊥{\ displaystyle DLO \ models x <x \ leftrightarrow \ bot}DLO⊨H∧⊤↔H{\ displaystyle DLO \ models H \ land \ top \ leftrightarrow H}LAeu{\ displaystyle A_ {i}}y=Xeu,Xeu=Xj,y<Xeu,Xeu<y,Xeu<Xj{\ displaystyle y = x_ {i}, x_ {i} = x_ {j}, y <x_ {i}, x_ {i} <y, x_ {i} <x_ {j}}⊥.{\ displaystyle \ bot.}

Dacă există , cum ar fi atunci , atunci este adecvat. Să presupunem că pentru orice . eu{\ displaystyle i}LAeu=⊥{\ displaystyle A_ {i} = \ bot}DLO⊨⋀euLAeu(X1,...,Xnu,y)↔⊥{\ displaystyle DLO \ models \ bigwedge _ {i} A_ {i} (x_ {1}, ..., x_ {n}, y) \ leftrightarrow \ bot}G: =⊥{\ displaystyle G: = \ bot}LAeu≠⊥{\ displaystyle A_ {i} \ not = \ bot}eu{\ displaystyle i}

Dacă există asemenea, atunci este potrivit. Deci, putem presupune că nu este forma pentru tot . eu{\ displaystyle i}y=Xeu{\ displaystyle y = x_ {i}}G: =F[Xeu/y]{\ displaystyle G: = F [x_ {i} / y]}LAeu{\ displaystyle A_ {i}}y=Xeu{\ displaystyle y = x_ {i}}eu{\ displaystyle i}

Deci sunt de forma :, sau . LAeu{\ displaystyle A_ {i}}Xeu=Xj,y<Xeu,Xeu<y{\ displaystyle x_ {i} = x_ {j}, y <x_ {i}, x_ {i} <y}Xeu<Xj{\ displaystyle x_ {i} <x_ {j}}

Deci, unde sunt de formă sau , și sunt de formă sau . ⋀euLAeu(X1,...,Xnu,y): =⋀eu∈EuLAeu∧⋀j∈JLAj{\ displaystyle \ bigwedge _ {i} A_ {i} (x_ {1}, ..., x_ {n}, y): = \ bigwedge _ {i \ in I} A_ {i} \ land \ bigwedge _ {j \ in J} A_ {j}}LAeu{\ displaystyle A_ {i}}Xeu=Xj{\ displaystyle x_ {i} = x_ {j}}Xeu<Xj{\ displaystyle x_ {i} <x_ {j}}LAj{\ displaystyle A_ {j}}y<Xeu{\ displaystyle y <x_ {i}}Xeu<y{\ displaystyle x_ {i} <y}

Avem asta . Deci avem două cazuri: ⋀j∈JLAj: =⋀j∈SXj<y∧⋀j∈Ty<Xj{\ displaystyle \ bigwedge _ {j \ in J} A_ {j}: = \ bigwedge _ {j \ in S} x_ {j} <y \ land \ bigwedge _ {j \ in T} y <x_ {j} }

• Dacă , atunci este bine.S∩T≠∅{\ displaystyle S \ cap T \ not = \ emptyset}G: =⊥{\ displaystyle G: = \ bot}

• În caz contrar, dacă sau , atunci este adecvat deoarece ordinea este fără terminații.S=∅{\ displaystyle S = \ emptyset}T=∅{\ displaystyle T = \ emptyset}G: =⊤{\ displaystyle G: = \ top}

• În caz contrar, deoarece ordinea este densă, așa este adecvat.DLO⊨⋀j∈JLAj↔⋀eu∈S,j∈TXeu<Xj{\ displaystyle DLO \ models \ bigwedge _ {j \ in J} A_ {j} \ leftrightarrow \ bigwedge _ {i \ in S, j \ in T} x_ {i} <x_ {j}}G: =⋀eu∈EuLAeu∧⋀eu∈S,j∈TXeu<Xj{\ displaystyle G: = \ bigwedge _ {i \ in I} A_ {i} \ land \ bigwedge _ {i \ in S, j \ in T} x_ {i} <x_ {j}}

Criteriul 2

Fie o teorie L. T{\ displaystyle T}

Să presupunem că pentru orice formulă L fără cuantificator , dacă și sunt două modele ale , este o substructură comună a și , elemente ale setului de bază al , și există astfel încât , atunci există în domeniul astfel încât . F(X1,X2,...,Xnu,y){\ displaystyle F (x_ {1}, x_ {2}, ..., x_ {n}, y)}M{\ displaystyle M}NU{\ displaystyle N}T{\ displaystyle T}LA{\ displaystyle A}M{\ displaystyle M}NU{\ displaystyle N}la1,la2,...,lanu{\ displaystyle a_ {1}, a_ {2}, ..., a_ {n}}LA{\ displaystyle A}b∈M{\ displaystyle b \ în M}M⊨F(la1,la2,...lanu,b){\ displaystyle M \ models F (a_ {1}, a_ {2}, ... a_ {n}, b)}vs.{\ displaystyle c}NU{\ displaystyle N}NU⊨F(la1,la2,...,lanu,vs.){\ displaystyle N \ models F (a_ {1}, a_ {2}, ..., a_ {n}, c)}

Deci, admite eliminarea cuantificatoarelor. T{\ displaystyle T}

Dovadă

Să arătăm conversația (dovada directă este mai delicată). Fie o formulă L fără cuantificator. Să , să fie două modele de , o structură comună și , precum și elemente de . Să presupunem că . Apoi, eliminând cuantificatorii, există o formulă L fără un cuantificator astfel încât , și . Cu toate acestea, așa cum este o substructură a și este fără cuantificator, este echivalent cu , echivalent, în același mod, cu , deci în cele din urmă . F(X1,...,Xnu,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}M{\ displaystyle M}NU{\ displaystyle N}T{\ displaystyle T}LA{\ displaystyle A}M{\ displaystyle M}NU{\ displaystyle N}la1,la2,...lanu{\ displaystyle a_ {1}, a_ {2}, ... a_ {n}}LA{\ displaystyle A}M⊨∃yF(la1,la2,...lanu,y){\ displaystyle M \ models \ există yF (a_ {1}, a_ {2}, ... a_ {n}, y)}G(X1,...,Xnu){\ displaystyle G (x_ {1}, ..., x_ {n})}T⊨∃yF(X1,...,Xnu,y)↔G(X1,...,Xnu){\ displaystyle T \ models \ există yF (x_ {1}, ..., x_ {n}, y) \ leftrightarrow G (x_ {1}, ..., x_ {n})}M⊨G(la1,...,lanu){\ displaystyle M \ models G (a_ {1}, ..., a_ {n})}LA{\ displaystyle A}M{\ displaystyle M}G(X1,...,Xnu){\ displaystyle G (x_ {1}, ..., x_ {n})}M⊨G(la1,...,lanu){\ displaystyle M \ models G (a_ {1}, ..., a_ {n})}LA⊨G(la1,...,lanu){\ displaystyle A \ models G (a_ {1}, ..., a_ {n})}NU⊨G(la1,...,lanu){\ displaystyle N \ models G (a_ {1}, ..., a_ {n})}NU⊨∃yF(la1,la2,...lanu,y){\ displaystyle N \ models \ există yF (a_ {1}, a_ {2}, ... a_ {n}, y)}

Exemplu: DAG

Arătăm că teoria grupului abelian divizibil fără torsiune ( ) admite eliminarea cuantificatorilor arătând că îndeplinește condiția criteriului 2. DLAG{\ displaystyle DAG}

Luați în considerare o formulă fără cuantificator. Fie , două grupuri abeliene divizibile torsional, un subgrup comun al și , astfel încât . Mai întâi arătăm că există un subgrup comun de și astfel încât este un subgrup de , și apoi arătăm că înainte de a încheia. F(X1,...,Xnu,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}M{\ displaystyle M}NU{\ displaystyle N}G{\ displaystyle G}M{\ displaystyle M}NU{\ displaystyle N}(la1,...,lanu)∈Gnu,h∈M{\ displaystyle (a_ {1}, ..., a_ {n}) \ în G ^ {n}, h \ în M}M⊨F(la1,...,lanu,h){\ displaystyle M \ models F (a_ {1}, ..., a_ {n}, h)}H{\ displaystyle H}M{\ displaystyle M}NU{\ displaystyle N}G{\ displaystyle G}H{\ displaystyle H}H⊨∃XF(la1,...,lanu,X){\ displaystyle H \ models \ există xF (a_ {1}, ..., a_ {n}, x)}

Să arătăm că există un subgrup comun de și astfel încât este un subgrup de : Să setăm . Definim o relație de echivalență pe de dacă și numai dacă . Să pozăm . Notam clasa a . Definim prin pozare . H{\ displaystyle H}M{\ displaystyle M}NU{\ displaystyle N}G{\ displaystyle G}H{\ displaystyle H}X: ={(g,nu):g∈G,nu∈NU∗}{\ displaystyle X: = \ {(g, n): g \ în G, n \ in \ mathbb {N} ^ {*} \}}∼{\ displaystyle \ sim}X{\ displaystyle X}(g,nu)∼(h,m){\ displaystyle (g, n) \ sim (h, m)}mg=nuh{\ displaystyle mg = nh}H=X/∼{\ displaystyle H = X / \ sim}((g,nu)){\ displaystyle ((g, n))}∼ {\ displaystyle \ sim ~}(g,nu){\ displaystyle (g, n)}+:H2→H{\ displaystyle +: H ^ {2} \ rightarrow H}(((g,nu)),((h,m)))=((mg+nuh,mnu)){\ displaystyle (((g, n)), ((h, m))) = ((mg + nh, mn))}

+{\ displaystyle +}este bine definit: Să avem așa cum(g′,nu′)∈((g,nu)) et (h′,m′)∈((h,m)).{\ displaystyle (g ', n') \ in ((g, n)) \ și \ (h ', m') \ in ((h, m)).}((g′,nu′))+((h′,m′))=((m′g′+nu′h′,m′nu′)).{\ displaystyle ((g ', n')) + ((h ', m')) = ((m'g '+ n'h', m'n ')).}m′nu′(mg+nuh)=m′nu′mg+m′nu′nuh=m′mnu′g+nu′num′h=mnum′g′+mnunu′h=mnu(mg′+nu′h),((m′g′+nu′h′,m′nu′))=((mg+nuh,mnu)){\ displaystyle m'n '(mg + nh) = m'n'mg + m'n'nh = m'mn'g + n'nm'h = mnm'g' + mnn'h = mn (mg ' + n'h), ((m'g '+ n'h', m'n ')) = ((mg + nh, mn))}

(H,+){\ displaystyle (H, +)}este un grup: Să avem ; ((g,nu)),((h,m)),((k,l))∈H.{\ displaystyle ((g, n)), ((h, m)), ((k, l)) \ în H.}((0,1))+((g,nu))=((g,nu)){\ displaystyle ((0,1)) + ((g, n)) = ((g, n))}

((-g,nu))+((g,nu))=((0,nunu))=((0,1)){\ displaystyle ((-g, n)) + ((g, n)) = ((0, nn)) = ((0,1))};

(((g,nu))+((h,m)))+((vs.,l))=((g,nu))+(((h,m))+((vs.,l))){\ displaystyle (((g, n)) + ((h, m))) + ((c, l)) = ((g, n)) + (((h, m)) + ((c, l)))}

(H,+){\ displaystyle (H, +)}este fără torsiune: Să Prin urmare , avem De aceea Astfel , deoarece este fără torsiune. ((g,nu))∈H,m∈NU∗ tels qtue m((g,nu))=((0,1)).{\ displaystyle ((g, n)) \ in H, m \ in \ mathbb {N} ^ {*} \ such \ that \ m ((g, n)) = ((0,1)).}((mg,nu))=((0,k)).{\ displaystyle ((mg, n)) = ((0, k)).}kmg=(km)g=0{\ displaystyle kmg = (km) g = 0}g=0{\ displaystyle g = 0}M{\ displaystyle M}

(H,+){\ displaystyle (H, +)} este divizibil: Let ((g,nu))∈H. Onu la m((g,mnu))=((g,nu)).{\ displaystyle ((g, n)) \ în H. ​​\ On \ a \ m ((g, mn)) = ((g, n)).}

(H,+){\ displaystyle (H, +)} este abelian: Let ((g,m)),((h,nu))∈H. Onu la ((g,m))+((h,nu))=((nug+mh,mnu))=((mh+nug,mnu))=((h,nu))+((g,m)){\ displaystyle ((g, m)), ((h, n)) \ în H. ​​\ On \ a \ ((g, m)) + ((h, n)) = ((ng + mh, mn )) = ((mh + ng, mn)) = ((h, n)) + ((g, m))}

Monstronii definiți de este un homomorfism injectiv ; f:G→H{\ displaystyle f: G \ rightarrow H}f(g)=((g,1)){\ displaystyle f (g) = ((g, 1))}f(0)=((0,1)){\ displaystyle f (0) = ((0,1))}

{\ displaystyle \ quad}fi atunci ; g,h∈G,{\ displaystyle g, h \ în G,}f(g+h)=((g+h,1))=((g,1))+((h,1))=f(g)+f(h){\ displaystyle f (g + h) = ((g + h, 1)) = ((g, 1)) + ((h, 1)) = f (g) + f (h)}

{\ displaystyle \ quad}fie dacă și numai dacăg,h∈G, g=h{\ displaystyle g, h \ în G, \ g = h}((X,1))=((y,1)).{\ displaystyle ((x, 1)) = ((y, 1)).}

Să arătăm că este definit prin bine definit și este un omomorfism injectiv: h:H→M{\ displaystyle h: H \ rightarrow M}h((g,nu))=g/nu{\ displaystyle h ((g, n)) = g / n}

h{\ displaystyle h}este bine definit: Fie atunci . Prin urmare(k,m)∈((g,nu)),{\ displaystyle (k, m) \ in ((g, n)),}mg=nuk{\ displaystyle mg = nk}f(g,nu)=g/nu=(mg)/mnu=(nuk/mnu)=k/m.{\ displaystyle f (g, n) = g / n = (mg) / mn = (nk / mn) = k / m.}

h{\ displaystyle h}este un omomorfism injectiv ; h(((0,1)))=0/1=0{\ displaystyle h (((0,1))) = 0/1 = 0}

{\ displaystyle \ quad}fi ,((g,m)),((k,nu))∈H{\ displaystyle ((g, m)), ((k, n)) \ în H}h(((g,m))+((k,nu)))=h(((nug+mk,mnu)))=(nug+mk)/(mnu)=g/m+k/nu=h(((g,m)))+h(((k,nu)));{\ displaystyle h (((g, m)) + ((k, n))) = h ((((ng + mk, mn))) = (ng + mk) / (mn) = g / m + k / n = h (((g, m))) + h (((k, n)));}

{\ displaystyle \ quad}fi , dacă , atunci , deci , prin urmare ; dacă , atunci((g,m)),((k,nu))∈H{\ displaystyle ((g, m)), ((k, n)) \ în H}((g,m))=((k,nu)){\ displaystyle ((g, m)) = ((k, n))}nug=mk{\ displaystyle ng = mk}mnu(g/m)=mnu(k/nu){\ displaystyle mn (g / m) = mn (k / n)}g/m=k/nu{\ displaystyle g / m = k / n}g/m=k/nu{\ displaystyle g / m = k / n}nug=num(g/m))=num(k/nu)=mk.{\ displaystyle ng = nm (g / m)) = nm (k / n) = mk.}

La fel, există și un homomorfism injectiv al in . Astfel ne putem identifica cu un subgrup comun care conține din și . H{\ displaystyle H}NU{\ displaystyle N}H{\ displaystyle H}G{\ displaystyle G}M{\ displaystyle M}NU{\ displaystyle N}

Să arătăm că : H⊨∃XF(la1,la2,...,lanu,X){\ displaystyle H \ models \ există xF (a_ {1}, a_ {2}, ..., a_ {n}, x)}

F(X1,...,Xnu,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}este o formulă fără cuantificator, deci este echivalentă cu o formulă sub formă disjunctivă: unde sunt formule atomice sau negații ale formulelor atomice ale limbajului. Când este satisfăcut, există așa cum este satisfăcut. ⋁eu⋀jLAeu,j(X1,...,Xnu,y){\ displaystyle \ bigvee _ {i} \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}LAeu,j{\ displaystyle A_ {i, j}}⋁eu⋀jLAeu,j(X1,...,Xnu,y){\ displaystyle \ bigvee _ {i} \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}eu0{\ displaystyle i_ {0}}⋀jLAeu0,j(X1,...,Xnu,y){\ displaystyle \ bigwedge _ {j} A_ {i_ {0}, j} (x_ {1}, ..., x {n}, y)}

La fel ca în limbă, singurul simbol predicat este simbolul și singurul simbol funcțional este , o formulă atomică în acest limbaj este de forma în care . Asa de={\ displaystyle =}+{\ displaystyle +}∑eu=1nu(meu,jXeu+mjy=0){\ displaystyle \ sum _ {i = 1} ^ {n} (m_ {i, j} x_ {i} + m_ {j} y = 0)}meu,j,mj∈NU{\ displaystyle m_ {i, j}, m_ {j} \ in \ mathbb {N}}⋀jLAeu0,j(X1,...,Xnu,y): =(⋀j∈S(∑eu=1numeu,jXeu+mjy=0)∧⋀j∈T(∑eu=1numeu,jXeu+mjy≠0).){\ displaystyle \ bigwedge _ {j} A_ {i_ {0}, j} (x_ {1}, ..., x_ {n}, y): = (\ bigwedge _ {j \ în S} (\ sum _ {i = 1} ^ {n} m_ {i, j} x_ {i} + m_ {j} y = 0) \ land \ bigwedge _ {j \ in T} (\ sum _ {i = 1} ^ {n} m_ {i, j} x_ {i} + m_ {j} y \ not = 0).)}

Dacă există așa ceva , atunci așa , pentru că G este un grup distinct. Deci . j∈S{\ displaystyle j \ in S}mj≠0{\ displaystyle m_ {j} \ not = 0}M⊨F(la1,...,lanu,b){\ displaystyle M \ models F (a_ {1}, ..., a_ {n}, b)}b=∑eu=1numeu,j(-laeu)mj∈G{\ displaystyle b = {\ frac {\ sum _ {i = 1} ^ {n} m_ {i, j} (- a_ {i})} {m_ {j}}} \ în G}b∈H{\ displaystyle b \ in H}

În caz contrar, întrucât H nu are torsiune, deci este infinit, pentru că altfel pentru orice . Așa cum totul este terminat, există un element care satisface⋀jLAeu0,j(X1,...,Xnu,y): =⋀j∈T(∑eu=1numeu,jXeu+mjy≠0).{\ displaystyle \ bigwedge _ {j} A_ {i_ {0}, j} (x_ {1}, ..., x_ {n}, y): = \ bigwedge _ {j \ in T} (\ sum _ {i = 1} ^ {n} m_ {i, j} x_ {i} + m_ {j} y \ not = 0).}H{\ displaystyle H}X∈H,|H|X=0{\ displaystyle x \ în H, | H | x = 0}j∈T,{w∈H|∑eu=1numeu,jlaeu+mjy=0}{\ displaystyle j \ in T, \ {w \ in H | \ sum _ {i = 1} ^ {n} m_ {i, j} a_ {i} + m_ {j} y = 0 \}}H{\ displaystyle H}⋀j∈T(∑eu=1numeu,jlaeu+mjy≠0).{\ displaystyle \ bigwedge _ {j \ in T} (\ sum _ {i = 1} ^ {n} m_ {i, j} a_ {i} + m_ {j} y \ not = 0).}

Comentariul este un subgrup de , există un element de satisfăcut , prin urmare,H{\ displaystyle H}NU{\ displaystyle N}NU{\ displaystyle N}⋀j∈T(∑eu=1numeu,jlaeu+mjy≠0){\ displaystyle \ bigwedge _ {j \ in T} (\ sum _ {i = 1} ^ {n} m_ {i, j} a_ {i} + m_ {j} y \ not = 0)}NU⊨∃F(la1,...,lanu,y){\ displaystyle N \ models \ există F (a_ {1}, ..., a_ {n}, y)}

Criteriul 3

Să fie o teorie L astfel încât T{\ displaystyle T}

1. Pentru toți , există unul și un monomorfism astfel încât pentru toți și monomorfism , există astfel încât . LA⊨T∀{\ displaystyle A \ models T _ {\ forall}}K⊨T{\ displaystyle K \ models T}eu:LA→K{\ displaystyle i: A \ rightarrow K}NU⊨T{\ displaystyle N \ models T}j:LA→NU{\ displaystyle j: A \ rightarrow N}h:K→NU{\ displaystyle h: K \ rightarrow N}j=h∘eu{\ displaystyle j = h \ circ i}

2. Dacă sunt două modele ale și este o structură de atunci pentru orice formulă L și orice în domeniul lui , dacă există în domeniul a ceea ce este satisfăcut în , atunci este și în . M,NU{\ displaystyle M, N}T{\ displaystyle T}M{\ displaystyle M}NU{\ displaystyle N}F(X1,...,Xnu,w){\ displaystyle F (x_ {1}, ..., x_ {n}, w)}la1,la2,...,lanu{\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n}}M{\ displaystyle M}b{\ displaystyle b}NU{\ displaystyle N}F(la1,la2,...,lanu,b){\ displaystyle F (a_ {1}, a_ {2}, ..., a_ {n}, b)}NU{\ displaystyle N}M{\ displaystyle M}

Deci, admite eliminarea cuantificatoarelor. T{\ displaystyle T}

Dovadă

Fie o formulă L fără cuantificator. Să presupunem că există două modele de , o substructură comună a și , elemente și un element de astfel încât . Să arătăm că există în așa fel încât și apoi să încheiem prin criteriul 1: F(X1,...,Xnu,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}M,NU{\ displaystyle M, N}T{\ displaystyle T}LA{\ displaystyle A}M{\ displaystyle M}NU{\ displaystyle N}la1,la2,...,lanu{\ displaystyle a_ {1}, a_ {2}, ..., a_ {n}}LA{\ displaystyle A}b{\ displaystyle b}M{\ displaystyle M}M⊨F(la1,la2,...,lanu,b){\ displaystyle M \ models F (a_ {1}, a_ {2}, ..., a_ {n}, b)}vs.{\ displaystyle c}NU{\ displaystyle N}NU⊨F(la1,la2,...,lanu,vs.){\ displaystyle N \ models F (a_ {1}, a_ {2}, ..., a_ {n}, c)}

Deoarece și asta este o substructură a , avem asta . Prin ipoteza 1) există astfel încât pentru tot ceea ce este o extensie a , este o substructură a . Prin urmare, este substructura și a . M⊨T{\ displaystyle M \ models T}LA{\ displaystyle A}M{\ displaystyle M}LA⊨T∀{\ displaystyle A \ models T _ {\ forall}}K⊨T{\ displaystyle K \ models T}Î⊨T{\ displaystyle Q \ models T}LA{\ displaystyle A}K{\ displaystyle K}Î{\ displaystyle Q}K{\ displaystyle K}M{\ displaystyle M}NU{\ displaystyle N}

Deoarece este o formulă fără cuantificator, este o substructură a și formulele fără cuantificatori sunt păstrate de substructură, avem asta . La fel . M⊨F(la1,la2,...,lanu,b),F{\ displaystyle M \ models F (a_ {1}, a_ {2}, ..., a_ {n}, b), F}K{\ displaystyle K}M{\ displaystyle M}K⊨∃XF(la1,la2,...,lanu,X){\ displaystyle K \ models \ există xF (a_ {1}, a_ {2}, ..., a_ {n}, x)}NU⊨∃XF(la1,la2,...,lanu,X){\ displaystyle N \ models \ există xF (a_ {1}, a_ {2}, ..., a_ {n}, x)}

Astfel încheiem cu criteriul 2 admis prin eliminarea cuantificatorilor. T{\ displaystyle T}

Exemplu: câmp închis algebric

Observăm pentru teoria câmpurilor închise algebric. Pentru a demonstra că eliminarea cuantificatorilor admite, arătăm mai întâi setul de consecințe universale ale teoriei câmpurilor închise algebric este teoria inelelor integrale. Și apoi, arătăm că îndeplinește condițiile criteriului 3 de încheiat. LAVSF{\ displaystyle ACF}LAVSF{\ displaystyle ACF}LAVSFU{\ displaystyle ACFU}LAVSF{\ displaystyle ACF}

Să arătăm că este teoria inelelor integrale: Fie un inel integral. Fie câmp algebric-extensie a câmpului fracției de . Avem că este un model de . Deoarece există un morfism injectiv de în domeniul fracțiune , și există un morfism injectiv a domeniului fracțiunii de la , deducem că este un subinel al . Deci . Fie . În special ,. Deoarece, în plus, sunt toate axiomele teoriei inelelor , este un inel integral. LAVSFU{\ displaystyle ACFU}LA{\ displaystyle A}K{\ displaystyle K}LA{\ displaystyle A}K{\ displaystyle K}LAVSF{\ displaystyle ACF}LA{\ displaystyle A}LA{\ displaystyle A}LA{\ displaystyle A}K{\ displaystyle K}LA{\ displaystyle A}K{\ displaystyle K}LA⊨LAVSFU{\ displaystyle A \ models ACFU}B⊨LAVSFU{\ displaystyle B \ models ACFU}B⊨∀X∀y((X≠0∧y≠0)→(X.y≠0)){\ displaystyle B \ models \ forall x \ forall y ((x \ not = 0 \ land y \ not = 0) \ rightarrow (xy \ not = 0))}LAVSFU{\ displaystyle ACFU}B{\ displaystyle B}

Să arătăm că prima condiție a criteriului 3 îndeplinește: Fie un model de . este un inel integral. Fie câmpul de extensie algebrică al câmpului fracțional al lui . Fie un model de astfel de, care este un sub-inel de . Așa cum este un corp care conține , prin urmare conține fracțiunea corpului . Și întrucât este închis algebric, conține, prin definiție, câmpul de extensie algebrică a . LAVSF{\ displaystyle ACF}B{\ displaystyle B}LAVSFU{\ displaystyle ACFU}B{\ displaystyle B}VS{\ displaystyle C}B{\ displaystyle B}D{\ displaystyle D}LAVSF{\ displaystyle ACF}B{\ displaystyle B}D{\ displaystyle D}D{\ displaystyle D}B{\ displaystyle B}D{\ displaystyle D}B{\ displaystyle B}D{\ displaystyle D}D{\ displaystyle D}VS{\ displaystyle C}B{\ displaystyle B}

Să arătăm că a doua condiție a criteriului 3 îndeplinește: Fie astfel încât este o substructură a , o formulă L fără cuantificator, elemente din domeniul lui . Să presupunem că există un element al domeniului astfel încât . Să arătăm că există un element al domeniului astfel încât . este o formulă fără cuantificator, deci este echivalentă cu o formulă în formă disjunctivă în care sunt formule atomice sau negații ale formulelor atomice. dacă și numai dacă pentru o anumită . Prin urmare, putem presupune, fără pierderea generalității, că F este o formulă a formei în care sunt formule atomice sau negații ale formulelor atomice. Iar limbajul ACF este limbajul inelar, o formulă atomică are forma în care P este un polinom al lui . este un polinom al . Deci există în așa fel încât . Avem două cazuri: LAVSF{\ displaystyle ACF}M,NU⊨LAVSF{\ displaystyle M, N \ models ACF}M{\ displaystyle M}NU{\ displaystyle N}F(X1,...,Xnu,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}la1,...,lanu{\ displaystyle a_ {1}, ..., a_ {n}}M{\ displaystyle M}b{\ displaystyle b}NU{\ displaystyle N}NU⊨F(la1,la2,...,lanu,b){\ displaystyle N \ models F (a_ {1}, a_ {2}, ..., a_ {n}, b)}vs.{\ displaystyle c}M{\ displaystyle M}M⊨F(la1,...,lanu,vs.){\ displaystyle M \ models F (a_ {1}, ..., a_ {n}, c)}F(X1,...,Xnu,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}⋁eu⋀jLAeuj(X1,...,Xnu,y){\ displaystyle \ bigvee _ {i} \ bigwedge _ {j} A_ {ij} (x_ {1}, ..., x_ {n}, y)}LAeuj(X1,...,Xnu,y){\ displaystyle A_ {ij} (x_ {1}, ..., x_ {n}, y)}NU⊨F(X1,...,Xnu,y){\ displaystyle N \ models F (x_ {1}, ..., x_ {n}, y)}NU⊨⋀jLAeuj(X1,...,Xnu,y){\ displaystyle N \ models \ bigwedge _ {j} A_ {ij} (x_ {1}, ..., x_ {n}, y)}eu{\ displaystyle i}⋀euLAeu(X1,...,Xnu,y){\ displaystyle \ bigwedge _ {i} A_ {i} (x_ {1}, ..., x_ {n}, y)}LAeu(X1,...,Xnu,y){\ displaystyle Ai (x_ {1}, ..., x_ {n}, y)}LA(X1,...,Xnu){\ displaystyle A (x_ {1}, ..., x_ {n})}P(X1,...,Xnu)=0{\ displaystyle P (x_ {1}, ..., x_ {n}) = 0}Z[X1,X2,...,Xnu]{\ displaystyle \ mathbb {Z} [X_ {1}, X_ {2}, ..., X_ {n}]}F(la1,...,lanu,X){\ displaystyle F (a_ {1}, ..., a_ {n}, X)}M[X]{\ displaystyle M [X]}P1,P2,...,Pnu,Î1,Î2,...,Îm{\ displaystyle P_ {1}, P_ {2}, ..., P_ {n}, Q_ {1}, Q_ {2}, ..., Q_ {m}}M[X]{\ displaystyle M [X]}F(la1,...,lanu,X)=⋀eu=1nuPeu(X)=0∧⋀j=1mÎj(X)≠0{\ displaystyle F (a_ {1}, ..., a_ {n}, X) = \ bigwedge _ {i = 1} ^ {n} P_ {i} (X) = 0 \ wedge \ bigwedge _ {j = 1} ^ {m} Q_ {j} (X) \ not = 0}

Dacă există un polinom diferit de zero, atunci, deoarece avem pentru toate , avem în special . Deoarece M este un subcâmp închis algebric al lui N și b este un element al domeniului lui N, avem că b este un element al domeniului lui M. Pk{\ displaystyle P_ {k}}NU⊨Peu(b)=0{\ displaystyle N \ models P_ {i} (b) = 0}eu{\ displaystyle i}NU⊨Pk(b)=0{\ displaystyle N \ models P_ {k} (b) = 0}

Dacă nu, atunci . Să fie setul de rădăcini pentru toți . Știm că este finit pentru orice și că este infinit, de aceea există în așa fel încât . Deci există în domeniul M astfel încât . F(la1,...,lanu,X)=⋀j=1mÎj(X)≠0{\ displaystyle F (a_ {1}, ..., a_ {n}, X) = \ bigwedge _ {j = 1} ^ {m} Q_ {j} (X) \ not = 0}Sj{\ displaystyle S_ {j}}Îj(X){\ displaystyle Q_ {j} (X)}j{\ displaystyle j}Sj{\ displaystyle S_ {j}}j{\ displaystyle j}M{\ displaystyle M}vs.{\ displaystyle c}|M|-⋃j=1mSj{\ displaystyle | M | - \ bigcup _ {j = 1} ^ {m} S_ {j}}⋀j=1mÎj(vs.)≠0{\ displaystyle \ bigwedge _ {j = 1} ^ {m} Q_ {j} (c) \ not = 0}vs.{\ displaystyle c}M⊨F(la1,...,lanu,vs.){\ displaystyle M \ models F (a_ {1}, ..., a_ {n}, c)}

Exemple

Exemple de teorii care admit eliminarea cuantificatorilor:

• câmpuri reale închise ( teorema Tarski-Seidenberg  (en) , algoritm algebric de descompunere cilindrică  (en) );
• câmp algebric închis al nespecificată sau fix caracteristice (de exemplu , prin intermediul bazelor Gröbner și teorema extensiei);
• teoria liniară a raționalelor sau realelor (algoritmi Ferrante și Rackoff , Loos și Weispfenning  (de) );
• teoria liniară a numerelor întregi, cunoscută și sub numele de aritmetica lui Presburger .

Toate aceste teorii sunt atât de complete  (în) .

Rezultat

Model de completitudine

Fie o teorie care admite eliminarea cuantificatorilor. Fie două modele de astfel de, care este o substructură a . Fie o formulă și o atribuire a variabilelor din . Prin eliminarea cuantificatorilor, există o formulă fără un cuantificator care este echivalentă cu în . Avem doar dacă și numai dacă și numai dacă și numai dacă . Deoarece injecția canonică a în este un homomorfism injectiv și este o formulă fără cuantificator, avem asta dacă și numai dacă . Concluzionăm că dacă și numai dacă . La fel este o substructură elementară a . La fel și modelul complet (prin definiție). T{\ displaystyle T}L{\ displaystyle L}M,NU{\ displaystyle M, N}T{\ displaystyle T}M{\ displaystyle M}NU{\ displaystyle N}F{\ displaystyle F}L{\ displaystyle L}s{\ displaystyle s}M{\ displaystyle M}L{\ displaystyle L}G{\ displaystyle G}F{\ displaystyle F}T{\ displaystyle T}M⊨F[s]{\ displaystyle M \ models F [s]}M⊨G[s]{\ displaystyle M \ models G [s]}NU⊨F[s]{\ displaystyle N \ models F [s]}NU⊨G[s]{\ displaystyle N \ models G [s]}M{\ displaystyle M}NU{\ displaystyle N}G{\ displaystyle G}M⊨G[s]{\ displaystyle M \ models G [s]}NU⊨G[s]{\ displaystyle N \ models G [s]}M⊨F[s]{\ displaystyle M \ models F [s]}NU⊨F[s]{\ displaystyle N \ models F [s]}M{\ displaystyle M}NU{\ displaystyle N}T{\ displaystyle T}

Note și referințe

1. (în) Philipp Rothmaler, Introducere în teoria modelelor , CRC Press ,2000( citiți online ) , p.  141.
2. (în) Jeanne Ferrante și Charles Rackoff , „  A procedure procedure for the first order theory of real addition with order  ” , SIAM J. on Computing , voi.  4, n o  1,Martie 1975, p.  69-76 ( DOI  10.1137 / 0204006 ).
3. (în) Aaron R. Bradley și Zohar Manna , Calculul calculului: proceduri de decizie cu cereri de verificare , Berlin, Springer ,octombrie 2007, 366  p. ( ISBN  978-3-540-74112-1 ).
4. (în) Rüdiger Loos și Volker Weispfenning , "  Aplicarea eliminării cuantificate liniare  " , The Computer Journal , Vol.  36, nr .  5,1993, p.  450-462 ( DOI  10.1093 / comjnl / 36.5.450 , citiți online [PDF] ).

Vezi și tu

Articole similare

• Skolemizarea
• Teorema lui Herbrand

Bibliografie

• Jean-Louis Krivine și Georg Kreisel , Elemente de logică matematică (teoria modelelor) , Paris, Dunod, 1966, cap. 4, pdf
• Jean-François Pabion, Logica matematică , capitolul VI „Eliminarea cuantificatorilor” pp. 191-210, Hermann, Paris 1976 ( ISBN  2-7056 5830-0 )
• René David, Karim Nour, Christophe Raffalli, Introducere în teoria-logică a demonstrației , ediția a II-a, Dunod
• David Marker, Teoria modelului: o introducere , Springer
• René Cori, Daniel Lascar, Mathematical logic 2 , Dunod

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