Nicelik belirteçlerinin ortadan kaldırılması
Olarak matematiksel mantık , ya da daha doğrusu modeli teoride, niceleyicilerin ortadan kaldırılması bir bulmakta oluşan eylemdir formüle muhtemelen içeren belirli bir formüle nicelik eşdeğeri olmayan nicelik belirli bir dil olarak teorik olarak.
Dolayısıyla, kapalı gerçek alanlar teorisini ele alırsak, bu teorinin dili L = {+, •, <, 0,1} olup, burada +, • arity 2'nin iki fonksiyon sembolüdür, <bir ikili ilişki sembolüdür, ve 0,1 iki sabit semboldür, L formülü ∃ x ( ax² + bx + c = 0) teoride L formülüne eşdeğerdir , çünkü bu teoride ax² + bx + c = 0 bir kök kabul eder ve sadece bir , b ve c her sıfır ya da bir sıfır, ancak b sıfır olmayan, ya da bir sıfırdan farklı olması ve pozitiftir.
(-de=0∧b=0∧vs=0)∨(-de=0∧b≠0)∨(-de≠0∧¬(b2-4-devs<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-4-devs{\ displaystyle b ^ {2} -4ac}
Tanımlar
L bir dil ve T a L-teorisi olsun, deriz ki, eğer herhangi bir L-formülü F için, niceleyici olmayan bir L-formülü G varsa, T niceleyicilerin ortadan kaldırılmasını kabul eder . Başka bir deyişle, L dilinin herhangi bir formülü bu teoride nicelik belirteci olmayan bir formüle denk ise, L dilinin bir T teorisi niceleyicilerin ortadan kaldırılmasını kabul eder.
T⊨F↔G{\ displaystyle T \ modelleri F \ leftrightarrow G}
Nicelik belirteçleri ortadan kaldırmaya yönelik ilgi
Değişken içermeyen formüllere karar vermek genellikle daha kolaydır; niceleyici eleme algoritması bu nedenle bu teori için bir karar prosedürü olarak hizmet edebilir . Nicelik belirteçlerinin ortadan kaldırıldığını kabul eden karar verilebilir bir teoride, bir formülü kabul ederek her zaman nicelik belirteçsiz bir formül veren bir algoritma vardır. Tek sorun, algoritmanın verimliliğidir.
Aynı zamanda bir teorideki tanımlanabilir kümeleri daha iyi anlamamıza izin verir.
Nicelik belirteçleri ortadan kaldırmak için bazı kriterler
1. Kriter
L-teorisi olalım .
T{\ displaystyle T}
Nicelik belirteci olmayan herhangi bir L formülü için nicelik belirteci olmayan bir L formülü olduğunu varsayalım, öyle ki .
F(v¯,w){\ displaystyle F ({\ çubuğu {v}}, w)}G(v¯){\ displaystyle G ({\ bar {v}})}T⊨∃wF(v¯,w)↔G(v¯){\ displaystyle T \ modeller \ var wF ({\ bar {v}}, w) \ leftrightarrow G ({\ bar {v}})}
Ardından, T, niceleyicilerin ortadan kaldırıldığını kabul eder.
Kanıt
Olsun , bir L-formül. Karmaşıklığı tümevarımla gösteriyoruz, öyle ki niceleyici olmayan bir L formülü var .
F(x1,x2,...,xdeğil){\ displaystyle F (x_ {1}, x_ {2}, ..., x_ {n})}F{\ displaystyle F}G{\ displaystyle G}T⊨F↔G{\ displaystyle T \ modelleri F \ leftrightarrow G}
Öyleyse soralım . Özelliğin tüm karmaşıklık formülleri için kesinlikle daha küçük olduğunu varsayalım . Eğer , üç durum varsa: ya , o zaman, tümevarım hipotezi ile eşdeğer bir nicelik belirteci olmadan vardır , ayarlamak yeterlidir ; yani , o zaman tümevarım hipotezi yoluyla vardır ve niceleyici olmadan öyle ki ve , biz koyarız ; veya , tümevarım hipotezi ile, öyle bir nicelik belirteci olmadan var olur ki ve hipotezle, ortaya koyduğumuz bir nicelik belirteci olmadan var olur .
|F|=0{\ displaystyle | F | = 0}G=F{\ displaystyle G = F}değil{\ displaystyle n}|F|=değil{\ displaystyle | F | = n}F: =¬H1{\ displaystyle F: = \ l değil H_ {1}}H2{\ displaystyle H_ {2}}H1{\ displaystyle H_ {1}}H2{\ displaystyle H_ {2}}G: =¬H2{\ displaystyle G: = \ l değil 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 \ modelleri H_ {1} \ leftrightarrow H_ {3}}T⊨H2↔H4{\ displaystyle T \ modelleri H_ {2} \ leftrightarrow H_ {4}}G: =H3∧H4{\ displaystyle G: = H_ {3} \ land H_ {4}}F: =∃xH1{\ displaystyle F: = \ var xH_ {1}}H2{\ displaystyle H_ {2}}T⊨∃xH1↔∃xH2{\ displaystyle T \ modeller \ var xH_ {1} \ leftrightarrow \ var xH_ {2}}H3{\ displaystyle H_ {3}}T⊨∃xH2↔H3{\ displaystyle T \ modeller \ var xH_ {2} \ leftrightarrow H_ {3}}G: =H3{\ displaystyle G: = H_ {3}}
Örnek: DLO
(Yoğun Doğrusal Sıralama) 'nın kriter 1'in koşulunu yerine getirerek niceleyicilerin ortadan kaldırılmasını kabul ettiğini gösteriyoruz . Diğer bir deyişle, nicelik belirteci olmayan bir formül olalım, nicelik belirteci olmayan bir formül arayalım öyle ki .
DLÖ{\ displaystyle DLO}F(x1,...,xdeğil,y){\ displaystyle F (x_ {1}, \ ldots, x_ {n}, y)}G(x1,...,xdeğil){\ displaystyle G (x_ {1}, \ ldots, x_ {n})}DLÖ⊨F↔G{\ displaystyle DLO \ modelleri F \ leftrightarrow G}
F{\ displaystyle F}nicelik belirteci yoktur, bu nedenle dilin atomik formüllerinin (veya bunların olumsuzlamalarının) olduğu ayrık formdaki bir formüle eşdeğerdir . Olarak , ancak ve ancak bir kesin , şeklinde bir formüle eşdeğerdir dilinin atom formüller (veya bunların DEĞİL) vardır .
F{\ displaystyle F}⋁ben⋀jATben,j(x1,...,xdeğil,y){\ displaystyle \ bigvee _ {i} \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}ATben,j{\ displaystyle A_ {i, j}}DLÖ{\ displaystyle DLO}DLÖ⊨⋁ben⋀jATben,j(x1,...,xdeğil,y){\ displaystyle DLO \ modelleri \ bigvee _ {i} \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}DLÖ⊨⋀jATben,j(x1,...,xdeğil,y){\ displaystyle DLO \ modelleri \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}ben{\ displaystyle i}F{\ displaystyle F}⋀benATben(x1,...,xdeğil,y){\ displaystyle \ bigwedge _ {i} A_ {i} (x_ {1}, ..., x_ {n}, y)}ATben{\ displaystyle A_ {i}}DLÖ{\ displaystyle DLO}
Gibi , , , ve , bir varsayabiliriz biçimdedir: yaDLÖ⊨¬(x<y)↔(y<x∨x=y){\ Displaystyle DLO \ modelleri \ lnot (x <y) \ leftrightarrow (y <x \ lor x = y)}DLÖ⊨¬(x=y)↔(x<y∨y<x){\ Displaystyle DLO \ modelleri \ lnot (x = y) \ leftrightarrow (x <y \ lor y <x)}DLÖ⊨x=x↔⊤{\ displaystyle DLO \ modelleri x = x \ leftrightarrow \ top}DLÖ⊨x<x↔⊥{\ displaystyle DLO \ modelleri x <x \ leftrightarrow \ bot}DLÖ⊨H∧⊤↔H{\ displaystyle DLO \ modelleri H \ land \ top \ leftrightarrow H}ATben{\ displaystyle A_ {i}}y=xben,xben=xj,y<xben,xben<y,xben<xj{\ displaystyle y = x_ {i}, x_ {i} = x_ {j}, y <x_ {i}, x_ {i} <y, x_ {i} <x_ {j}}⊥.{\ displaystyle \ bot.}
Yoksa gibi o zaman , daha sonra uygun. Her şey için bunu varsayalım .
ben{\ displaystyle i}ATben=⊥{\ displaystyle A_ {i} = \ bot}DLÖ⊨⋀benATben(x1,...,xdeğil,y)↔⊥{\ displaystyle DLO \ modelleri \ bigwedge _ {i} A_ {i} (x_ {1}, ..., x_ {n}, y) \ leftrightarrow \ bot}G: =⊥{\ displaystyle G: = \ bot}ATben≠⊥{\ displaystyle A_ {i} \ not = \ bot}ben{\ displaystyle i}
Böyle bir şey varsa o zaman uygundur. Böylece her şeyin şekli olmadığını varsayabiliriz .
ben{\ displaystyle i}y=xben{\ displaystyle y = x_ {i}}G: =F[xben/y]{\ displaystyle G: = F [x_ {i} / y]}ATben{\ displaystyle A_ {i}}y=xben{\ displaystyle y = x_ {i}}ben{\ displaystyle i}
Yani şu biçimdedir:, veya .
ATben{\ displaystyle A_ {i}}xben=xj,y<xben,xben<y{\ displaystyle x_ {i} = x_ {j}, y <x_ {i}, x_ {i} <y}xben<xj{\ displaystyle x_ {i} <x_ {j}}
Yani nerede formun olan veya ve form olan veya .
⋀benATben(x1,...,xdeğil,y): =⋀ben∈benATben∧⋀j∈JATj{\ displaystyle \ bigwedge _ {i} A_ {i} (x_ {1}, ..., x_ {n}, y): = \ bigwedge _ {i \ in I} A_ {i} \ land \ bigwedge _ {j \ in J} A_ {j}}ATben{\ displaystyle A_ {i}}xben=xj{\ displaystyle x_ {i} = x_ {j}}xben<xj{\ displaystyle x_ {i} <x_ {j}}ATj{\ displaystyle A_ {j}}y<xben{\ displaystyle y <x_ {i}}xben<y{\ displaystyle x_ {i} <y}
Biz buna sahibiz . Yani iki vakamız var:
⋀j∈JATj: =⋀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} }
- Eğer , o zaman iyidir.S∩T≠∅{\ displaystyle S \ cap T \ not = \ emptyset}G: =⊥{\ displaystyle G: = \ bot}
- Aksi takdirde eğer veya , o zaman uygundur çünkü siparişin sonu yoktur.S=∅{\ displaystyle S = \ emptyset}T=∅{\ displaystyle T = \ emptyset}G: =⊤{\ displaystyle G: = \ top}
- Aksi takdirde sıra yoğun olduğu için uygundur.DLÖ⊨⋀j∈JATj↔⋀ben∈S,j∈Txben<xj{\ displaystyle DLO \ models \ bigwedge _ {j \ in J} A_ {j} \ leftrightarrow \ bigwedge _ {i \ in S, j \ in T} x_ {i} <x_ {j}}G: =⋀ben∈benATben∧⋀ben∈S,j∈Txben<xj{\ displaystyle G: = \ bigwedge _ {i \ I} A_ {i} \ land \ bigwedge _ {i \ in S, j \ in T} x_ {i} <x_ {j}}
2. Kriter
L - teorisi olalım .
T{\ displaystyle T}
Nicelik olmadan herhangi bir L-formül varsayalım , eğer ve iki modelleri , bir ortak alt olan ve , taban kümenin elemanları ve vardır , öyle ki , daha sonra vardır alanı içinde bu şekilde .
F(x1,x2,...,xdeğil,y){\ displaystyle F (x_ {1}, x_ {2}, ..., x_ {n}, y)}M{\ displaystyle M}DEĞİL{\ displaystyle N}T{\ displaystyle T}AT{\ displaystyle A}M{\ displaystyle M}DEĞİL{\ displaystyle N}-de1,-de2,...,-dedeğil{\ displaystyle a_ {1}, a_ {2}, ..., a_ {n}}AT{\ displaystyle A}b∈M{\ displaystyle b \ M olarak}M⊨F(-de1,-de2,...-dedeğil,b){\ displaystyle M \ modelleri F (a_ {1}, a_ {2}, ... a_ {n}, b)}vs{\ displaystyle c}DEĞİL{\ displaystyle N}DEĞİL⊨F(-de1,-de2,...,-dedeğil,vs){\ displaystyle N \ modelleri F (a_ {1}, a_ {2}, ..., a_ {n}, c)}
Öyleyse, niceleyicilerin ortadan kaldırıldığını kabul edin.
T{\ displaystyle T}
Kanıt
Sohbeti gösterelim (doğrudan ispat daha hassastır). Nicelik belirteci olmayan bir L formülü olsun. Let olmak iki modelleri , ortak bir alt yapı ve ve elemanları . Varsayalım ki . Daha sonra niceleyicileri ortadan kaldırarak, niceleyici olmayan bir L-formülü vardır , öyle ki , ve . Bununla birlikte, nicelleştiricinin bir altyapısı olduğu ve nicelleştirici olmadığı gibi , eşdeğerdir, aynı şekilde eşdeğerdir , dolayısıyla nihayet .
F(x1,...,xdeğil,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}M{\ displaystyle M}DEĞİL{\ displaystyle N}T{\ displaystyle T}AT{\ displaystyle A}M{\ displaystyle M}DEĞİL{\ displaystyle N}-de1,-de2,...-dedeğil{\ displaystyle a_ {1}, a_ {2}, ... a_ {n}}AT{\ displaystyle A}M⊨∃yF(-de1,-de2,...-dedeğil,y){\ displaystyle M \ modeller \ var yF (a_ {1}, a_ {2}, ... a_ {n}, y)}G(x1,...,xdeğil){\ displaystyle G (x_ {1}, ..., x_ {n})}T⊨∃yF(x1,...,xdeğil,y)↔G(x1,...,xdeğil){\ displaystyle T \ modeller \ var yF (x_ {1}, ..., x_ {n}, y) \ leftrightarrow G (x_ {1}, ..., x_ {n})}M⊨G(-de1,...,-dedeğil){\ displaystyle M \ modelleri G (a_ {1}, ..., a_ {n})}AT{\ displaystyle A}M{\ displaystyle M}G(x1,...,xdeğil){\ displaystyle G (x_ {1}, ..., x_ {n})}M⊨G(-de1,...,-dedeğil){\ displaystyle M \ modelleri G (a_ {1}, ..., a_ {n})}AT⊨G(-de1,...,-dedeğil){\ displaystyle A \ modelleri G (a_ {1}, ..., a_ {n})}DEĞİL⊨G(-de1,...,-dedeğil){\ displaystyle N \ modelleri G (a_ {1}, ..., a_ {n})}DEĞİL⊨∃yF(-de1,-de2,...-dedeğil,y){\ displaystyle N \ modeller \ var yF (a_ {1}, a_ {2}, ... a_ {n}, y)}
Örnek: DAG
Burulmasız bölünebilir değişmeli grup teorisinin ( ) ölçüt 2'nin koşulunu sağladığını göstererek niceleyicilerin ortadan kaldırıldığını kabul ettiğini gösteriyoruz.
DATG{\ displaystyle DAG}
Nicelik belirteci olmayan bir formül düşünün . Let olabilir, iki kıvrımlı bölünebilir değişmeli gruplar, ortak bir alt-grubu ve , bu şekilde . Önce ortak bir alt grubu olduğunu ve bunun bir alt grubu olduğunu gösteriyoruz, sonra bunu sonuçlandırmadan önce gösteriyoruz .
F(x1,...,xdeğil,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}M{\ displaystyle M}DEĞİL{\ displaystyle N}G{\ displaystyle G}M{\ displaystyle M}DEĞİL{\ displaystyle N}(-de1,...,-dedeğil)∈Gdeğil,h∈M{\ displaystyle (a_ {1}, ..., a_ {n}) \ G ^ {n} içinde, h \ M olarak}M⊨F(-de1,...,-dedeğil,h){\ displaystyle M \ modelleri F (a_ {1}, ..., a_ {n}, h)}H{\ displaystyle H}M{\ displaystyle M}DEĞİL{\ displaystyle N}G{\ displaystyle G}H{\ displaystyle H}H⊨∃xF(-de1,...,-dedeğil,x){\ displaystyle H \ modeller \ var xF (a_ {1}, ..., a_ {n}, x)}
Şunun ortak bir alt grubunun var olduğunu ve bunun bir alt grubu olduğunu gösterelim: Hadi belirleyelim . Biz bir denklik ilişkisi tanımlamak üzerinde tarafından ancak ve ancak . Hadi poz verelim . Bize göstermek Let ait -sınıf . Poz vererek tanımlıyoruz .
H{\ displaystyle H}M{\ displaystyle M}DEĞİL{\ displaystyle N}G{\ displaystyle G}H{\ displaystyle H}X: ={(g,değil):g∈G,değil∈DEĞİL∗}{\ displaystyle X: = \ {(g, n): g \ G'de, n \ matematikte \ mathbb {N} ^ {*} \}}∼{\ displaystyle \ sim}X{\ displaystyle X}(g,değil)∼(h,m){\ displaystyle (g, n) \ sim (h, m)}mg=değilh{\ displaystyle mg = nh}H=X/∼{\ displaystyle H = X / \ sim}((g,değil)){\ displaystyle ((g, n))}∼ {\ displaystyle \ sim ~}(g,değil){\ displaystyle (g, n)}+:H2→H{\ displaystyle +: H ^ {2} \ rightarrow H}(((g,değil)),((h,m)))=((mg+değilh,mdeğil)){\ displaystyle (((g, n)), ((h, m))) = ((mg + nh, mn))}
+{\ displaystyle +}iyi tanımlanmış geçerli: Let Biz bu var 'i(g′,değil′)∈((g,değil)) et (h′,m′)∈((h,m)).{\ displaystyle (g ', n') \ in ((g, n)) \ ve \ (h ', m') \ in ((h, m)).}((g′,değil′))+((h′,m′))=((m′g′+değil′h′,m′değil′)).{\ displaystyle ((g ', n')) + ((h ', m')) = ((m'g '+ n'h', m'n ')).}m′değil′(mg+değilh)=m′değil′mg+m′değil′değilh=m′mdeğil′g+değil′değilm′h=mdeğilm′g′+mdeğildeğil′h=mdeğil(mg′+değil′h),((m′g′+değil′h′,m′değil′))=((mg+değilh,mdeğil)){\ 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, +)}bir gruptur: Let Biz ;
((g,değil)),((h,m)),((k,l))∈H.{\ Displaystyle ((g, n)), ((h, m)), ((k, l)) \ H. içinde}((0,1))+((g,değil))=((g,değil)){\ displaystyle ((0,1)) + ((g, n)) = ((g, n))}
((-g,değil))+((g,değil))=((0,değildeğil))=((0,1)){\ displaystyle ((-g, n)) + ((g, n)) = ((0, nn)) = ((0,1))};
(((g,değil))+((h,m)))+((vs,l))=((g,değil))+(((h,m))+((vs,l))){\ displaystyle (((g, n)) + ((h, m))) + ((c, l)) = ((g, n)) + (((h, m)) + ((c, l)))}
(H,+){\ displaystyle (H, +)}torsiyon-ücretsizdir: Let Bu nedenle sahip nedenle Böylece çünkü torsiyon-serbesttir.
((g,değil))∈H,m∈DEĞİL∗ tels qsene m((g,değil))=((0,1)).{\ displaystyle ((g, n)) \ H, m \ in \ mathbb {N} ^ {*} \ böyle \ m ((g, n)) = ((0,1)).}((mg,değil))=((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, +)} bölünebilir: Let ((g,değil))∈H. Ödeğil -de m((g,mdeğil))=((g,değil)).{\ Displaystyle ((g, n)) \ H. \ Üzerinde \ bir \ m ((g, mn)) = ((g, n)).}
(H,+){\ displaystyle (H, +)} değişmeli: Let ((g,m)),((h,değil))∈H. Ödeğil -de ((g,m))+((h,değil))=((değilg+mh,mdeğil))=((mh+değilg,mdeğil))=((h,değil))+((g,m)){\ Displaystyle ((g, m)), ((h, n)) \ H. \ üzerinde \ bir \ ((g, m)) + ((h, n)) = ((ng + mh, mn) )) = ((mh + ng, mn)) = ((h, n)) + ((g, m))}
Tarafından tanımlandığı gibi canavarlar, enjekte edici bir homomorfizmdir ;
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}olması daha sonra ;
g,h∈G,{\ displaystyle g, h \ G cinsinden}}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}olmak ancak ve ancakg,h∈G, g=h{\ displaystyle g, h \ G cinsinden, \ g = h}((x,1))=((y,1)).{\ displaystyle ((x, 1)) = ((y, 1)).}
Bize bu gösterelim tarafından tanımlanan iyi tanımlanmış ve bir injektif homomorfizma:
h:H→M{\ displaystyle h: H \ rightarrow M}h((g,değil))=g/değil{\ displaystyle h ((g, n)) = g / n}
h{\ displaystyle h}iyi tanımlanmıştır: Öyleyse . Bu nedenle(k,m)∈((g,değil)),{\ displaystyle (k, m) \ içinde ((g, n)),}mg=değilk{\ displaystyle mg = nk}f(g,değil)=g/değil=(mg)/mdeğil=(değilk/mdeğil)=k/m.{\ displaystyle f (g, n) = g / n = (mg) / mn = (nk / mn) = k / m.}
h{\ displaystyle h}enjekte edici bir homomorfizmdir ;
h(((0,1)))=0/1=0{\ displaystyle h (((0,1))) = 0/1 = 0}
{\ displaystyle \ quad}olmak ,((g,m)),((k,değil))∈H{\ displaystyle ((g, m)), ((k, n)) \ H içinde}h(((g,m))+((k,değil)))=h(((değilg+mk,mdeğil)))=(değilg+mk)/(mdeğil)=g/m+k/değil=h(((g,m)))+h(((k,değil)));{\ 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}olabilir , eğer , daha sonra , bu nedenle , bu nedenle ; eğer öyleyse((g,m)),((k,değil))∈H{\ displaystyle ((g, m)), ((k, n)) \ H içinde}((g,m))=((k,değil)){\ displaystyle ((g, m)) = ((k, n))}değilg=mk{\ displaystyle ng = mk}mdeğil(g/m)=mdeğil(k/değil){\ displaystyle mn (g / m) = mn (k / n)}g/m=k/değil{\ displaystyle g / m = k / n}g/m=k/değil{\ displaystyle g / m = k / n}değilg=değilm(g/m))=değilm(k/değil)=mk.{\ displaystyle ng = nm (g / m)) = nm (k / n) = mk.}
Aynı şekilde, bir de injective homomorphism vardır . Böylece , ve içeren ortak bir alt grupla özdeşleşebiliriz .
H{\ displaystyle H}DEĞİL{\ displaystyle N}H{\ displaystyle H}G{\ displaystyle G}M{\ displaystyle M}DEĞİL{\ displaystyle N}
Bunu gösterelim :
H⊨∃xF(-de1,-de2,...,-dedeğil,x){\ displaystyle H \ modeller \ var xF (a_ {1}, a_ {2}, ..., a_ {n}, x)}
F(x1,...,xdeğil,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}nicelik belirteci olmayan bir formüldür, bu nedenle ayrık formdaki bir formüle eşdeğerdir: burada atomik formüller veya dilin atomik formüllerinin olumsuzlukları. Ne zaman memnun olduğunu, bu Varlığından olarak karşılanmaktadır.
⋁ben⋀jATben,j(x1,...,xdeğil,y){\ displaystyle \ bigvee _ {i} \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}ATben,j{\ displaystyle A_ {i, j}}⋁ben⋀jATben,j(x1,...,xdeğil,y){\ displaystyle \ bigvee _ {i} \ bigwedge _ {j} A_ {i, j} (x_ {1}, ..., x_ {n}, y)}ben0{\ displaystyle i_ {0}}⋀jATben0,j(x1,...,xdeğil,y){\ displaystyle \ bigwedge _ {j} A_ {i_ {0}, j} (x_ {1}, ..., x {n}, y)}
Dilde olduğu gibi, tek yüklem sembolü semboldür ve tek fonksiyon sembolü ise , bu dilde bir atomik formülün bulunduğu formdadır . Yani={\ displaystyle =}+{\ displaystyle +}∑ben=1değil(mben,jxben+mjy=0){\ displaystyle \ toplamı _ {i = 1} ^ {n} (m_ {i, j} x_ {i} + m_ {j} y = 0)}mben,j,mj∈DEĞİL{\ displaystyle m_ {i, j}, m_ {j} \ in \ mathbb {N}}⋀jATben0,j(x1,...,xdeğil,y): =(⋀j∈S(∑ben=1değilmben,jxben+mjy=0)∧⋀j∈T(∑ben=1değilmben,jxben+mjy≠0).){\ displaystyle \ bigwedge _ {j} A_ {i_ {0}, j} (x_ {1}, ..., x_ {n}, y): = (\ bigwedge _ {j \ in S} (\ toplam _ {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).)}
Eğer böyle bir şey varsa , o zaman olduğu için , çünkü G, bölünebilir bir gruptur. Yani .
j∈S{\ displaystyle j \ S’de}mj≠0{\ displaystyle m_ {j} \ not = 0}M⊨F(-de1,...,-dedeğil,b){\ displaystyle M \ modelleri F (a_ {1}, ..., a_ {n}, b)}b=∑ben=1değilmben,j(--deben)mj∈G{\ displaystyle b = {\ frac {\ toplamı _ {i = 1} ^ {n} m_ {i, j} (- a_ {i})} {m_ {j}}} \ G}b∈H{\ displaystyle b \ H'de}
Aksi takdirde, H torsiyonsuz olduğu için sonsuzdur, çünkü her şey için aksi halde . Her şey bittiğinde olduğu gibi , tatmin edici bir unsur var⋀jATben0,j(x1,...,xdeğil,y): =⋀j∈T(∑ben=1değilmben,jxben+mjy≠0).{\ displaystyle \ bigwedge _ {j} A_ {i_ {0}, j} (x_ {1}, ..., x_ {n}, y): = \ bigwedge _ {j \, T} (\ toplam _ {i = 1} ^ {n} m_ {i, j} x_ {i} + m_ {j} y \ not = 0).}H{\ displaystyle H}x∈H,|H|x=0{\ displaystyle x \ H, | H | x = 0}j∈T,{w∈H|∑ben=1değilmben,j-deben+mjy=0}{\ displaystyle j \ T'de, \ {w \ H'de | \ toplamı _ {i = 1} ^ {n} m_ {i, j} a_ {i} + m_ {j} y = 0 \}}H{\ displaystyle H}⋀j∈T(∑ben=1değilmben,j-deben+mjy≠0).{\ displaystyle \ bigwedge _ {j \ T içinde} (\ toplamı _ {i = 1} ^ {n} m_ {i, j} a_ {i} + m_ {j} y \ not = 0).}
Yorum , bir alt gruptur , bir memnun unsuru vardır , bu nedenle,H{\ displaystyle H}DEĞİL{\ displaystyle N}DEĞİL{\ displaystyle N}⋀j∈T(∑ben=1değilmben,j-deben+mjy≠0){\ displaystyle \ bigwedge _ {j \ T} (\ toplamı _ {i = 1} ^ {n} m_ {i, j} a_ {i} + m_ {j} y \ not = 0)}DEĞİL⊨∃F(-de1,...,-dedeğil,y){\ displaystyle N \ modeller \ var F (a_ {1}, ..., a_ {n}, y)}
3. Kriter
Let bir L - teori şekilde olmalıdır
T{\ displaystyle T}
Hepsi için 1. , tek vardır ve bir monomorfizm herkes için böyle ve monomorfizm , vardır öyle ki .
AT⊨T∀{\ displaystyle A \ modelleri T _ {\ forall}}K⊨T{\ displaystyle K \ modelleri T}ben:AT→K{\ Displaystyle ı: A \ sağ K}DEĞİL⊨T{\ displaystyle N \ modelleri T}j:AT→DEĞİL{\ displaystyle j: A \ rightarrow N}h:K→DEĞİL{\ displaystyle h: K \ rightarrow N}j=h∘ben{\ displaystyle j = h \ circ i}
2. Eğer iki model ise ve o zaman herhangi bir L-formülü için altyapıysa ve etki alanındaki her şey, içinde karşılanan böyle bir alanda mevcutsa , o zaman da içerdedir .
M,DEĞİL{\ displaystyle M, N}T{\ displaystyle T}M{\ displaystyle M}DEĞİL{\ displaystyle N}F(x1,...,xdeğil,w){\ displaystyle F (x_ {1}, ..., x_ {n}, w)}-de1,-de2,...,-dedeğil{\ displaystyle a_ {1}, a_ {2}, \ ldots, a_ {n}}M{\ displaystyle M}b{\ displaystyle b}DEĞİL{\ displaystyle N}F(-de1,-de2,...,-dedeğil,b){\ displaystyle F (a_ {1}, a_ {2}, ..., a_ {n}, b)}DEĞİL{\ displaystyle N}M{\ displaystyle M}
Öyleyse, niceleyicilerin ortadan kaldırıldığını kabul edin.
T{\ displaystyle T}
Kanıt
Nicelik belirteci olmayan bir L formülü olsun. Orada Varsayalım ki iki modelleri , ortak bir alt ve , elemanlar ve bir elemanın bu şekilde . Bizim var olduğunu gösterelim içinde öyle ki daha sonra kriter 1 ile sonuçlandırmak:
F(x1,...,xdeğil,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}M,DEĞİL{\ displaystyle M, N}T{\ displaystyle T}AT{\ displaystyle A}M{\ displaystyle M}DEĞİL{\ displaystyle N}-de1,-de2,...,-dedeğil{\ displaystyle a_ {1}, a_ {2}, ..., a_ {n}}AT{\ displaystyle A}b{\ displaystyle b}M{\ displaystyle M}M⊨F(-de1,-de2,...,-dedeğil,b){\ displaystyle M \ modelleri F (a_ {1}, a_ {2}, ..., a_ {n}, b)}vs{\ displaystyle c}DEĞİL{\ displaystyle N}DEĞİL⊨F(-de1,-de2,...,-dedeğil,vs){\ displaystyle N \ modelleri F (a_ {1}, a_ {2}, ..., a_ {n}, c)}
As ve bir altyapı olduğunu , biz buna sahip . 1) hipotezine göre , ' nin bir uzantısı olan herkes için' nin bir altyapısı olacak şekilde vardır . Bu nedenle, bir alt olan ve .
M⊨T{\ displaystyle M \ modelleri T}AT{\ displaystyle A}M{\ displaystyle M}AT⊨T∀{\ displaystyle A \ modelleri T _ {\ forall}}K⊨T{\ displaystyle K \ modelleri T}Q⊨T{\ displaystyle Q \ modelleri T}AT{\ displaystyle A}K{\ displaystyle K}Q{\ displaystyle Q}K{\ displaystyle K}M{\ displaystyle M}DEĞİL{\ displaystyle N}
Yana nicelik olmayan bir formül, bir alt olan ve Nicelik olmayan formüller alt yapısı ile korunur, bunu sahiptir . Aynı .
M⊨F(-de1,-de2,...,-dedeğil,b),F{\ displaystyle M \ modelleri F (a_ {1}, a_ {2}, ..., a_ {n}, b), F}K{\ displaystyle K}M{\ displaystyle M}K⊨∃xF(-de1,-de2,...,-dedeğil,x){\ displaystyle K \ modeller \ var xF (a_ {1}, a_ {2}, ..., a_ {n}, x)}DEĞİL⊨∃xF(-de1,-de2,...,-dedeğil,x){\ displaystyle N \ modeller \ var xF (a_ {1}, a_ {2}, ..., a_ {n}, x)}
Böylece , niceleyicilerin ortadan kaldırılmasıyla kabul edilen kriter 2 ile sonuçlandırıyoruz .
T{\ displaystyle T}
Örnek: Cebirsel olarak kapalı alan
Cebirsel olarak kapalı alanlar teorisini not ediyoruz . Göstermek için nicelik itiraf ortadan kaldırılması, öncelikle bir biçimde göstermek cebirsel kapalı alanların teorisinin evrensel sonuçlarından ayrılmaz halkaları teoridir. Ve sonra, sonuca varmak için Kriter 3'ün koşullarını karşıladığını gösteriyoruz .
ATVSF{\ displaystyle ACF}ATVSF{\ displaystyle ACF}ATVSFU{\ displaystyle ACFU}ATVSF{\ displaystyle ACF}
Bunun integral halkalar teorisi olduğunu gösterelim: Let bir integral halka olalım . Izin vermek kesir alanının cebirsel alan-uzantısı olsun . Bunun bir modeline sahibiz . Bir birebir homomorfizması olduğundan fraksiyonunun alanında ve fraksiyonunun alan bir birebir homomorfizması olduğu de , bunu anlamak bir alt halka olup . Yani . Ya . Özellikle . Halkalar teorisinin üstelik tüm aksiyomlar içinde olduğu için , ayrılmaz bir halkadır.
ATVSFU{\ displaystyle ACFU}AT{\ displaystyle A}K{\ displaystyle K}AT{\ displaystyle A}K{\ displaystyle K}ATVSF{\ displaystyle ACF}AT{\ displaystyle A}AT{\ displaystyle A}AT{\ displaystyle A}K{\ displaystyle K}AT{\ displaystyle A}K{\ displaystyle K}AT⊨ATVSFU{\ displaystyle A \ modelleri ACFU}B⊨ATVSFU{\ displaystyle B \ modelleri ACFU}B⊨∀x∀y((x≠0∧y≠0)→(x.y≠0)){\ Displaystyle B \ modelleri \ forall x \ forall y ((x \ not = 0 \ land y \ not = 0) \ rightarrow (xy \ not = 0))}ATVSFU{\ displaystyle ACFU}B{\ displaystyle B}
Bize bu gösterelim Izin: kriter 3 tatmin ilk koşulu modeli . ayrılmaz bir halkadır. Izin vermek kesir alanının cebirsel genişleme alanı olsun . Izin vermek bir alt halkası olan böyle bir model olalım . Şöyle bir içeren vücut olup , bu nedenle, bir fraksiyon gövdesi içeren . Ve cebirsel olarak kapalı olduğu için, tanımı gereği, cebirsel genişleme alanını içerir .
ATVSF{\ displaystyle ACF}B{\ displaystyle B}ATVSFU{\ displaystyle ACFU}B{\ displaystyle B}VS{\ displaystyle C}B{\ displaystyle B}D{\ displaystyle D}ATVSF{\ 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}
Bize göstermektedir izin edelim: kriteri 3 tatmin ikinci durum böyle bir alt olup , nicelik olmayan bir L-formül, etki unsurları . Diyelim ki böyle bir etki alanının bir öğesi var . Bize bir olduğunu göstereyim etki unsuru şekilde . nicelik belirteci olmayan bir formüldür, bu nedenle atomik formüllerin veya atomik formüllerin olumsuzluklarının olduğu ayrık formdaki bir formüle eşdeğerdir . ancak ve ancak belirli bir süre için . Bu nedenle, genelliği kaybetmeden, F'nin atomik formüllerin veya atomik formüllerin olumsuzluklarının olduğu formun bir formülü olduğunu varsayabiliriz . Ve ACF'nin dili halka dilidir, atomik bir formül P'nin bir polinom olduğu formdadır . bir polinomdur . Bu yüzden mevcut içinde öyle ki . İki vakamız var:
ATVSF{\ displaystyle ACF}M,DEĞİL⊨ATVSF{\ displaystyle M, N \ ACF modelleri}M{\ displaystyle M}DEĞİL{\ displaystyle N}F(x1,...,xdeğil,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}-de1,...,-dedeğil{\ displaystyle a_ {1}, ..., a_ {n}}M{\ displaystyle M}b{\ displaystyle b}DEĞİL{\ displaystyle N}DEĞİL⊨F(-de1,-de2,...,-dedeğil,b){\ displaystyle N \ modelleri F (a_ {1}, a_ {2}, ..., a_ {n}, b)}vs{\ displaystyle c}M{\ displaystyle M}M⊨F(-de1,...,-dedeğil,vs){\ displaystyle M \ modelleri F (a_ {1}, ..., a_ {n}, c)}F(x1,...,xdeğil,y){\ displaystyle F (x_ {1}, ..., x_ {n}, y)}⋁ben⋀jATbenj(x1,...,xdeğil,y){\ displaystyle \ bigvee _ {i} \ bigwedge _ {j} A_ {ij} (x_ {1}, ..., x_ {n}, y)}ATbenj(x1,...,xdeğil,y){\ displaystyle A_ {ij} (x_ {1}, ..., x_ {n}, y)}DEĞİL⊨F(x1,...,xdeğil,y){\ displaystyle N \ modelleri F (x_ {1}, ..., x_ {n}, y)}DEĞİL⊨⋀jATbenj(x1,...,xdeğil,y){\ displaystyle N \ modeller \ bigwedge _ {j} A_ {ij} (x_ {1}, ..., x_ {n}, y)}ben{\ displaystyle i}⋀benATben(x1,...,xdeğil,y){\ displaystyle \ bigwedge _ {i} A_ {i} (x_ {1}, ..., x_ {n}, y)}ATben(x1,...,xdeğil,y){\ displaystyle Ai (x_ {1}, ..., x_ {n}, y)}AT(x1,...,xdeğil){\ displaystyle A (x_ {1}, ..., x_ {n})}P(x1,...,xdeğil)=0{\ displaystyle P (x_ {1}, ..., x_ {n}) = 0}Z[X1,X2,...,Xdeğil]{\ displaystyle \ mathbb {Z} [X_ {1}, X_ {2}, ..., X_ {n}]}F(-de1,...,-dedeğil,X){\ displaystyle F (a_ {1}, ..., a_ {n}, X)}M[X]{\ displaystyle M [X]}P1,P2,...,Pdeğil,Q1,Q2,...,Qm{\ displaystyle P_ {1}, P_ {2}, ..., P_ {n}, Q_ {1}, Q_ {2}, ..., Q_ {m}}M[X]{\ displaystyle M [X]}F(-de1,...,-dedeğil,X)=⋀ben=1değilPben(X)=0∧⋀j=1mQj(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}
Sıfır olmayan bir polinom varsa , o zaman her şeye sahip olduğumuza göre, özellikle sahibiz . M, N'nin cebirsel olarak kapalı bir alt alanı olduğu ve b, N'nin alanının bir elemanı olduğu için, b'nin M'nin alanının bir elemanı olduğunu gördük.
Pk{\ displaystyle P_ {k}}DEĞİL⊨Pben(b)=0{\ displaystyle N \ modelleri P_ {i} (b) = 0}ben{\ displaystyle i}DEĞİL⊨Pk(b)=0{\ displaystyle N \ modelleri P_ {k} (b) = 0}
Değilse, o zaman . Let köklerinin kümesini Hepsi bu için . Bunun her şey için sonlu olduğunu ve bunun sonsuz olduğunu biliyoruz , bu nedenle öyle varolur . Yani M'nin etki alanında öyle ki var .
F(-de1,...,-dedeğil,X)=⋀j=1mQj(X)≠0{\ displaystyle F (a_ {1}, ..., a_ {n}, X) = \ bigwedge _ {j = 1} ^ {m} Q_ {j} (X) \ not = 0}Sj{\ displaystyle S_ {j}}Qj(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=1mQj(vs)≠0{\ displaystyle \ bigwedge _ {j = 1} ^ {m} Q_ {j} (c) \ not = 0}vs{\ displaystyle c}M⊨F(-de1,...,-dedeğil,vs){\ displaystyle M \ modelleri F (a_ {1}, ..., a_ {n}, c)}
Örnekler
Nicelik belirteçlerinin ortadan kaldırıldığını kabul eden teorilere örnekler:
Tüm bu teoriler tam model (in) .
Sonuç
Tamlık modeli
Nicelik belirteçlerinin ortadan kaldırıldığını kabul eden bir teori olalım . Izin vermek alt yapısı olan böyle iki model olsun . Izin vermek bir -formül ve içindeki değişkenlerin bir ataması . Nicelik ortadan kaldırarak, bir vardır bir nicelik olmaksızın aşağıdaki formüle eşdeğerdir olarak . Sadece ve ancak ancak ve ancak ve ancak eğer var . İçine kanonik enjeksiyon enjekte edici bir homomorfizm olduğundan ve bu nicelik belirteci olmayan bir formül olduğundan, buna sadece ve ancak sahip oluruz . Sadece ve ancak olduğu sonucuna varıyoruz . Öyleyse temel bir alt yapıdır . Yani modeli tamamlama (tanım gereği) 'dir.
T{\ displaystyle T}L{\ displaystyle L}M,DEĞİL{\ displaystyle M, N}T{\ displaystyle T}M{\ displaystyle M}DEĞİL{\ 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 \ modelleri F [s]}M⊨G[s]{\ displaystyle M \ modelleri G [s]}DEĞİL⊨F[s]{\ displaystyle N \ modelleri F [s]}DEĞİL⊨G[s]{\ displaystyle N \ modelleri G [s]}M{\ displaystyle M}DEĞİL{\ displaystyle N}G{\ displaystyle G}M⊨G[s]{\ displaystyle M \ modelleri G [s]}DEĞİL⊨G[s]{\ displaystyle N \ modelleri G [s]}M⊨F[s]{\ displaystyle M \ modelleri F [s]}DEĞİL⊨F[s]{\ displaystyle N \ modelleri F [s]}M{\ displaystyle M}DEĞİL{\ displaystyle N}T{\ displaystyle T}
Notlar ve referanslar
-
(inç) Philipp Rothmaler, Model Teorisine Giriş , CRC Press ,2000( çevrimiçi okuyun ) , s. 141.
-
(in) Jeanne Ferrante ve Charles Rackoff , " Sıralı gerçek toplamanın birinci dereceden teorisi için bir karar prosedürü " , SIAM J. on Computing , cilt. 4, n o 1,Mart 1975, s. 69-76 ( DOI 10.1137 / 0204006 ).
-
(in) Aaron R. Bradley ve Zohar Manna , The Calculus of Computation: Doğrulama Uygulamalı Karar Prosedürleri , Berlin, Springer ,Ekim 2007, 366 s. ( ISBN 978-3-540-74112-1 ).
-
(inç) Rüdiger Loos ve Volker Weispfenning , " Doğrusal niceleme eliminasyonunun uygulanması " , The Computer Journal , Cilt. 36, n o 5,1993, s. 450-462 ( DOI 10.1093 / comjnl / 36.5.450 , çevrimiçi okuyun [PDF] ).
Ayrıca görün
İlgili Makaleler
Kaynakça
-
Jean-Louis Krivine ve Georg Kreisel , Matematiksel mantığın unsurları (modeller teorisi) , Paris, Dunod, 1966, bölüm. 4, pdf
- Jean-François Pabion, Matematiksel mantık , bölüm VI “ Nicelik belirteçlerinin ortadan kaldırılması” s. 191-210, Hermann, Paris 1976 ( ISBN 2-7056 5830-0 )
- René David, Karim Nour, Christophe Raffalli, gösterimin mantık-teorisine giriş , 2. baskı, Dunod
- David Marker, Model Teorisi: Giriş , Springer
- René Cori, Daniel Lascar, Matematiksel mantık 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;">