Definierbarkeit in der Prädikatenlogik Flashcards
(10 cards)
Definition: Relation ist elementar definierbar (Skript Seite 75)
Eine Relation teilmenge A^r auf dem Universum einer tau-Struktur A~ ist (elementar) definierbar in A~, wenn R = psi^(A~) für eine Formel psi element FO(tau). Eine Funktion f: A^r -> A heisst elementar definierbar, wenn ihr Graph R_f elementar definierbar ist. (Der Graph ist eine Relation).
Insbesondere ist also eine Konstante a elementar definierbar, wenn eine Formel phi(x) element FO(tau) existiert, so dass A~ |= phi(a) und A~ |= nicht(phi(b)) für alle b != a.
Wir sagen, a ist termdefinierbar in A~, wenn ein Grundterm t element T(tau) existiert (also a als Konstante c, oder Ziel einer Funktion auf einer Konstanten f(c) =a in der Signatur vorhanden ist), so dass t^(A~) = a. Jede termdefinierbare Konstante ist insbesondere elementar definierbar durch eine Formel der form x=t.
Definition Isomorphismus (Skript Seite 78)
A~ und B~ seien tau-Strukturen. Ein Isomorphismus von A~ nach B~ ist eine bijektive Abbildung pi: A -> B, so dass folgende Bedingungen erfüllt sind:
(1) Für jedes n-stellige Relationssymbol R element tau und alle a1, …, an element A gilt:
(a1, … , an) element R^A~ gdw. (pi a1, …, pi an) element R^B~
(2) Für jedes n-stellige Funktionssymbol f element tau und alle a1, …, an element A gilt:
pi f^A~(a1, …, an) = f^B~(pi a1, …, pi an)
Lemma 3.9 Isomorphielemma (Skript Seite 79)
Sei pi: A~ -~> B~ ein Isomorphismus von tau-Strukturen. Dann gilt für alle psi(x1, …, xn) element FO(tau) und alle a1, …, an element A:
A~ |= psi(a1, …, an) gdw. B~ |= psi(pi a1, …, tau an)
Lemma 3.10 über Automorphismen und expandierte Strukturen (Skript Seite 80)
Sei pi ein Automorphismus einer tau-Struktur A~, und sei psi element FO(tau). Dann ist pi auch ein Automorphismus der expandierten Struktur (A~, psi^A~)
(psi~A~ ist elementar definierbar in A~. Kann benutzt werden in Beweisen zur elementaren Definierbarkeit. Z.b. wähle expandierte Struktur, wo psi elementar definierbar ist, aber ein Automorphismus im Redukt der Struktur kein Automorphismus in der expandierten Struktur mehr ist)
Definition Theorie (Skript 81)
Eine Theorie ist eine erfüllbare Menge T teilmenge FO(tau) von Sätzen, die unter |= abgeschlossen ist, d.h. es gilt für alle tau-Sätze psi mit T |= psi, dass psi element T.
Eine Theorie T ist vollständig, wenn für jeden Satz psi element FO(tau) entweder psi element T oder (nicht psi) element T gilt.
Sei A~ eine tau-Struktur. Was ist die Theorie von A~? (Skript 81)
Die Theorie von A~ ist Th(A~) := {psi : A~|= psi}.
Th(A~) ist vollständig. Die Theorie einer tau-Modellklasse K ist Th(K) = “DURCHSCHNITT aller A~ element K” (Th(A~))
Definition 3.13: elementar äquivalent (Skript 82)
Zwei tau-Strukturen A~, B~ sind elementar äquivalent, wenn Th(A~) = Th(B~), d.h. wenn für alle tau-Sätze psi gilt:
A~ |= psi gdw. B~ |= psi
Lemma 3.14: zusammenhang vollständige Theorie und elementare Äquivalenz (Skript 82)
Eine Theorie ist genau dann vollständig, wenn alle ihre Modelle elementar äquivalent sind.
Definition 3.15: Quantorenrang (Skript 82)
Der Quantorenrang qr(psi) einer Formel psi ist definiert durch:
1) qr(psi) = 0 für quantorenfreie psi,
2. ) qr( nicht psi) = qr(psi)
3. ) qr(psi * phi) = max( qr(psi), qr(phi)), wobei * beliebiger Junktor
4. ) qr(eEx.x. psi) - qr(fA.x. psi) = qr(psi) + 1
Der Quantorenrang ist also die maximale Schachtelungstiefe von Quantoren in der gegebenen Formel.
Definition 3.17: m- äquivalent (Skript 82)
Zwei tau-Strukturen A~, B~ sind m-äquivalent, wenn für alle tau-Sätze psi mit qr(psi) <= m gilt:
A~ |= psi gdw. B~ |= psi
