Twierdzenie Fefermana-Vaughta

Twierdzenie Fefermana-Vaughta w teorii modeli to twierdzenie Solomona Fefermana i Roberta Lawsona Vaughta , które pokazuje, jak w algorytmiczny sposób zredukować teorię pierwszego rzędu produktu struktur pierwszego rzędu do teorii pierwszego rzędu elementów struktura.

Twierdzenie jest uważane za jeden ze standardowych wyników w teorii modeli. Twierdzenie to rozszerza poprzedni wynik Andrzeja Mostowskiego na iloczyny bezpośrednie teorii. Uogólnia (na formuły z dowolnymi kwantyfikatorami) właściwość algebry uniwersalnej , że równości (tożsamości) przenoszą się na iloczyny bezpośrednie struktur algebraicznych ( co jest konsekwencją jednego kierunku twierdzenia Birkhoffa ).

Bezpośredni produkt struktur

sygnaturę logiczną pierwszego rzędu L . Definicja struktur produktowych przyjmuje rodzinę $}$ L dla pewnego ${\ displaystyle \ mathbf {A} _ {$ indeksów I i definiuje strukturę produktu $\ Displaystyle \ mathbf {A} = \ prod _ {i \ in I} \ mathbf {A} _ {i}}$ , która jest również strukturą L , ze wszystkimi zdefiniowanymi funkcjami i relacjami punktowo.

Definicja uogólnia iloczyn bezpośredni w algebrze uniwersalnej na relacyjne struktury pierwszego rzędu, które zawierają nie tylko symbole funkcji, ale także symbole relacji.

$})}$ za $p$ symbolem relacji z w L i $\ Displaystyle a_ {1}, \ ldots, a_ {n} \ in \ Pi _ {i \ in I} \ mathbf {A} _ {i}} są$ elementami kartezjańskiego produkt $}$ interpretację przez r $displaystyle r$ \

${\ Displaystyle \ mathbf {A} \ modele r (a_ {1},\ldots ,a_{p})\iff \forall i\in I,\ \mathbf {A} _{i}\models r(a_{1}(i),\ldots ,a_{p} (I))}$

Kiedy jest $relacją$ funkcjonalną, definicja ta sprowadza się do definicji iloczynu bezpośredniego w algebrze .

Sformułowanie twierdzenia o iloczynach bezpośrednich

$}$$L$$logicznej$ pierwszego rzędu sygnaturze z wolnymi zmiennymi interpretacji zmiennych definiujemy zbiór wskaźników, dla których ja $i}$$displaystyle$${a}} )}$ trzyma się ZA $\ Displaystyle \ mathbf {A} _ {i}}$

${\ Displaystyle ||\ phi ({\ bar {a}}) || = \ {i \ mid \ mathbf {A} _ {i} \ modele \phi ({\bar {a}}(i))\}}$

$alternatywą$ uwagę formułę pierwszego rzędu ze zmiennymi swobodnymi ${\ Displaystyle \ bigvee _ {i = 0} ^ {k-1} \ theta ({\ bar {x}})} wzajemnie$ algorytm obliczania jej równoważnej postaci normalnej gry, która jest sprzecznych formuł.

Twierdzenie Fefermana-Vaughta podaje $} }$ ( Ż ) $({\ bar {x}})$${\ Displaystyle \ phi ({\ bar {a}}$ który redukuje warunek, który spełnia w produkcie do warunku, który zachodzi $}$ interpretacji k ${\ displaystyle k + 1}$ zestawów indeksów: k +

${\ Displaystyle I, ||\ theta _ {0} ({\ bar {a}}) ||, \ ldots, ||\ theta _ {k-1} ({\ bar {a}})||}$

Formuła $zestawu , na przykład$ więc formułą ze zmiennymi $teorii$ pierwszego rzędu algebry Boole'a

Pomysł na dowód

Formułę można skonstruować zgodnie ze strukturą formuły wyjściowej ${\ Displaystyle \ phi ^ {$$*$ . Kiedy jest wolny od kwantyfikatora, to z definicji iloczynu bezpośredniego powyżej następuje ${\ displaystyle \ phi}$

${\ Displaystyle {\ rozpocząć {tablica} {rl} \ mathbf {A} \ modele \ phi ({\ bar {a}}) & \ if \ forall i \ w I. \ \ mathbf {A} _ { i}\models \phi ({\bar {a}}(i))\\&\iff \{i\mid \mathbf {A} _{i}\models \phi ({\bar {a}}( i))\}=I\\&\iff ||\phi ({\bar {a}})||=I\end{tablica}}}$

W konsekwencji możemy przyjąć równość w ${\ Displaystyle \ phi ^ {*} (U$$}$ język algebry boolowskiej zbiorów (odpowiednik ciała zbiorów ).

Rozszerzenie warunku na skwantyfikowane formuły można postrzegać jako formę eliminacji kwantyfikatora , w której kwantyfikacja elementów produktu jest zredukowana do kwantyfikacji na podzbiorach ${\ Displaystyle I}$${\ displaystyle {\ bar {a}}}$ in $\ phi}$ .

Produkty uogólnione

Często interesujące jest rozważenie podstruktury bezpośredniej struktury produktu. Jeśli ograniczenie, które definiuje elementy produktu należące do podstruktury, można wyrazić jako warunek na zbiorach elementów indeksowych, to wyniki można uogólnić.

Przykładem jest podstruktura elementów produktu, które są stałe przy wszystkich, ale nieskończenie wielu indeksach. Załóżmy, że język L $\ displaystyle a}$ stały symbol i rozważmy podstrukturę zawierającą tylko te elementy produktu, ${$ których zestaw jest za

$\ Displaystyle \ {i \ mid {\ textbf {A}} _ {i} \ modele a (i) \ neq c \}}$

jest skończony. Twierdzenie następnie redukuje wartość logiczną w takiej podstrukturze do wzoru $w$ algebrze boolowskiej zbiorów, gdzie pewne zbiory są ograniczone do

Jednym ze sposobów definiowania uogólnionych produktów jest rozważenie tych podstruktur, w których zbiory ${\ Displaystyle ||\ phi (a)||}$ należą do jakiejś algebry Boole'a $Displaystyle$ zbiorów $X \ subseteq I}$ indeksów (podzbiór algebry zbiorów powerset ${ \displaystyle 2^{I}}$ ) i gdzie podstruktura produktu dopuszcza klejenie. Tutaj dopuszczenie sklejenia odnosi się do następującego warunku zamknięcia: jeśli są dwoma elementami produktu i $jest$ elementem algebry Boole'a, to tak samo jest z elementem $Displaystyle X \ in B$${\ displaystyle c}$ zdefiniowane przez „klejenie” $zgodnie$ b $\ displaystyle b}$ z ${\ displaystyle X}$ :

${\ Displaystyle c (i) = \ lewo \ {{\ rozpocząć {tablica} {rl} a (i),&{\mbox{ if }}i\in X\\b(i),&{\mbox{ if }}i\in (I\setminus X)\end{tablica}}\right.}$

Konsekwencje

Twierdzenie Fefermana-Vaughta implikuje rozstrzygalność arytmetyki Skolema , patrząc za pomocą podstawowego twierdzenia arytmetyki na strukturę liczb naturalnych z mnożeniem jako uogólniony iloczyn (potęgę) struktur arytmetycznych Presburgera .