Welche Theorien werden unter dem Produkt bewahrt?

Die von Ihnen vorgeschlagene Produktdefinition ist in der Tat die Standarddefinition. Es kann natürlich erweitert werden, um das Produkt zu definieren$\prod_{i\in I} M_i$jeder Familie von Strukturen$(M_i)_{i\in I}$. Hier schließe ich den Fall ein$I = \emptyset$. Dann ist das Produkt die Singleton-Struktur$\{*\}$mit$f(*,\dots,*) = *$für ein beliebiges Funktionssymbol$f$Und$R(*,\dots,*)$für jedes Beziehungssymbol$R$. Wenn ich weiter unten davon spreche, dass Formeln unter Produkten aufbewahrt werden, meine ich damit unter Produkten willkürlicher Strukturfamilien (einschließlich der leeren Familie - aber dazu werde ich weiter unten mehr kommentieren).

Eine einfache (aber nicht optimale, siehe unten) Antwort auf Ihre Frage ist, dass strenge Horn-Formeln unter Produkten erhalten bleiben.

Eine strenge Horn-Grundformel hat die Form$\left(\bigwedge_{i=1}^n \varphi_i(x)\right)\rightarrow \psi(x)$, wo jeder der$\varphi_i(x)$Und$\psi(x)$sind Atomformeln. Wir lassen den Fall zu$n = 0$, also ist jede Atomformel eine grundlegende Hornformel. Eine strenge Horn-Formel wird aus grundlegenden Horn-Formeln von aufgebaut$\land$,$\forall$, Und$\exists$(aber nein$\lor$oder$\lnot$).

Sie können überprüfen, ob die strengen grundlegenden Hornformeln unter Produkten erhalten bleiben, und dann durch Induktion beweisen, dass alle strengen Hornformeln unter Produkten erhalten bleiben. Daraus folgt, wenn$T$ist jede Theorie und$S$ist die Menge aller strengen Horn-Sätze, die durch enthalten sind$T$, dann jedes Produkt von Modellen von$T$ist ein Modell von$S$.

Was macht das Wort "streng" da? Nun, wir können die grundlegende Hornformel und die Hornformel genau auf die gleiche Weise definieren, außer dass wir dies auch zulassen$\psi(x)$die widersprüchliche Formel sein$\bot$. Eine gebräuchlichere (und äquivalente) Definition ist, dass eine grundlegende Hornformel eine der Form ist$\bigvee_{i=1}^n \varphi_i(x)$, wo höchstens einer der$\varphi_i$ist eine Atomformel, und der Rest sind negierte Atomformeln. Der Punkt ist, dass strenge Hornformeln unter beliebigen Produkten erhalten bleiben, während Hornformeln nur unter Produkten nicht leerer Strukturfamilien erhalten bleiben.

Beachten Sie, dass das Axiom der Integralbereiche$\forall x\forall y\,(xy = 0\rightarrow (x = 0\lor y = 0))$ist kein (strenger) Hornsatz, und die Tatsache, dass dieses Axiom nicht unter Produkten erhalten bleibt, beweist, dass es nicht äquivalent zu einem (strengen) Hornsatz ist. Ebenso der Satz$\forall x\exists y\, (xy = 1)$aus der Gruppentheorie ist ein (strenger) Hornsatz, und er ist unter Produkten erhalten, aber der Satz$\forall x \exists y\, (x\neq 0\rightarrow xy = 1)$aus der Feldtheorie ist kein (strenger) Hornsatz (seit$x\neq 0$ist nicht atomar) und wird nicht unter Produkten aufbewahrt.

Das ist alles sehr schön, aber es wirft natürlich die Frage auf: Bleibt ein Satz erster Ordnung genau dann unter Produkten erhalten, wenn er einem strengen Horn-Satz äquivalent ist?

Die Antwort ist nein - strenge Hornsätze bleiben nicht nur unter Produkten erhalten, sondern auch unter der allgemeineren Konstruktion reduzierter Produkte . Und wie bof in den Kommentaren betont, hat Keisler bewiesen, dass ein Satz erster Ordnung genau dann einem strengen Hornsatz entspricht, wenn er unter reduzierten Produkten erhalten bleibt. Dies ist Theorem 6.2.5 in Model Theory von Chang und Keisler (das ich im Folgenden als C&K bezeichnen werde). Was dort tatsächlich bewiesen ist, ist, dass ein Satz genau dann einem Hornsatz entspricht, wenn er unter reduzierten Produkten von Proper aufbewahrt wirdFilter. Wenn man ein reduziertes Produkt durch den falschen Filter nimmt, erhält man eine Singleton-Struktur, genau wie das leere Produkt. Siehe C&K-Übung 6.2.8 für die Version über strenge Hornsätze und beliebige reduzierte Produkte.

Etwas Vorgeschichte: Keislers ursprünglicher Beweis von Theorem 6.2.5 (von 1965) ging von der Kontinuumshypothese (CH) aus. Dies ist der Beweis in Abschnitt 6.2 von C&K. Im selben Jahr eliminierte Galvin die Abhängigkeit von CH, und Abschnitt 6.3 von C&K ist größtenteils einer Darstellung von Galvins Beweis gewidmet. 1971 bewies Shelah bekanntermaßen das, was heute als Keisler-Shelah-Isomorphie-Theorem bekannt ist, und beseitigte die Abhängigkeit von CH aus dem früheren Ergebnis von Keisler, dass zwei Strukturen elementar äquivalent sind, wenn und nur wenn sie isomorphe Ultrakräfte haben. In diesem Artikel behauptete Shelah, dass die gleiche Technik verwendet werden könnte, um einen saubereren Beweis von Theorem 6.2.5 ohne CH zu geben. Aufgabe 6.2.4 in C&K fordert den Leser auf, die Details herauszuarbeiten – und die Aufgabe wurde in Form eines veröffentlichten Aufsatzes von George C.Erhaltungssätze ohne Kontinuumshypothese ).

Um die Geschichte zu vervollständigen, hier noch einige zusätzliche Informationen von Chang und Keisler:

• Es gibt ein Beispiel (Beispiel 6.2.3 in C&K) eines Satzes, der unter (nicht leeren) Produkten bewahrt wird, aber nicht unter willkürlich reduzierten Produkten durch geeignete Filter bewahrt wird (und daher nicht äquivalent zu einem Horn-Satz ist). Das gegebene Beispiel ist die Konjunktion der endlich vielen Axiome für Boolesche Algebren, zusammen mit dem Satz, der behauptet, dass es ein Atom gibt. Dieses Beispiel kann leicht zu einem modifiziert werden, das unter allen Produkten erhalten bleibt, aber nicht mit einem strengen Horn-Satz äquivalent ist, indem "thereexists an atom" durch "$0=1$oder es existiert ein Atom".
• Anscheinend gibt es eine wahre Charakterisierung dieser Sätze erster Ordnung, die unter Produkten aufbewahrt werden. C&K schreiben: "Eine syntaktische Charakterisierung direkter Produktsätze wurde von Weinstein (1965) gegeben. Da seine Charakterisierung sehr kompliziert ist, werden wir sie hier nicht geben." Es muss in der Tat sehr kompliziert sein, denn C&K scheuen sich nicht davor, an anderer Stelle in ihrem Buch extrem technisches Material aufzunehmen! Der Verweis bezieht sich auf Weinsteins Doktorarbeit „Eigenschaften erster Ordnung, bewahrt durch direktes Produkt“. Es scheint schwierig, diese These online aufzuspüren. Vielleicht ist es in der Bibliothek der University of Wisconsin? Wenn jemand, der dies liest, eine Kopie hat oder die Charakterisierung kennt, würde ich gerne wissen, was es ist!
• Schließlich zeigen C&K (Propositionen 6.2.8 und 6.2.9), dass, wenn ein universeller (bzw. existentieller) Satz unter (nicht leeren) Produkten erhalten bleibt, er einem universellen (bzw. existentiellen) Hornsatz entspricht. Und sie geben einen Hinweis, wieder auf Weinsteins These, für das gleiche Ergebnis für$\forall\exists$-Sätze. Dies ist das bestmögliche Ergebnis, da das Gegenbeispiel über Atome in Booleschen Algebren ein ist$\exists\forall$-Satz.

Ich war in der Lage, eine Kopie von Weinsteins Dissertation aufzuspüren (nicht weniger auf Mikrofilm) und ich kann seine Charakterisierung direkter Produktsätze hier reproduzieren. Es ist ziemlich technisch und insofern etwas unbefriedigend, als es sich nicht um eine induktiv definierte Klasse von Formeln handelt (wie die Horn-Sätze und die strengen Horn-Sätze), sondern um eine Klasse, die in Begriffen eines rekursiven Entscheidungsverfahrens definiert ist.

Es gibt ein Argument in Chang und Keisler, dass Sätze, die unter endlichen direkten Produkten bewahrt werden, unter beliebigen direkten Produkten bewahrt werden, also müssen wir wirklich nur die Sätze charakterisieren, die unter endlichen direkten Produkten bewahrt werden.

Zuerst einige Notationen. Gegebene Formeln$\varphi_0$,$\varphi_1$, Und$\varphi$, wir schreiben$\varphi_0 \times \varphi_1 \Rightarrow \varphi$um das immer zu meinen$M \models \varphi_0(a_1,\dots,a_n)$Und$N \models \varphi_1(b_1,\dots,b_n)$, Dann$M \times N \models \varphi((a_1,b_1),\dots,(a_n,b_n))$. Für jeden Satz von Formeln$S$, wir schreiben

• $\neg S$für die Menge der Negationen von Elementen von$S$,
• $\exists x S$für den Satz von Formeln der Form$\exists x \varphi$für$\varphi \in S$(für die jeweilige Variable$x$),
• $\forall x S$für den Satz von Formeln der Form$\forall x \varphi$für$\varphi \in S$,
• $\bigvee S$für die Menge endlicher Disjunktionen von Elementen von$S$(einschließlich der leeren Disjunktion$\top$),
• $\bigwedge S$für die Menge endlicher Konjunktionen von Elementen von$S$(einschließlich der leeren Konjunktion$\bot$), Und
• $\bigwedge^\ast S$für die Menge aller maximal konsistenten Konjunktionen von Elementen von$S$.

Im Fall von$\bigvee S$Und$\bigwedge S$, nehmen wir an, dass wir eine feste vernünftige Konvention zum Auflisten dieser Formeln haben, um Redundanzen zu vermeiden. (Zum Beispiel könnten wir verlangen, dass die Disjunkte/Konjunkte in einer festen lexikografischen Reihenfolge ohne Wiederholungen aufgelistet werden.) Insbesondere wann$S$ist endlich, wir wollen$\bigvee S$Und$\bigwedge S$endlich sein, und wir wollen die Karten$S \mapsto \bigvee S$Und$S \mapsto \bigwedge S$berechenbar sein.

Nehmen Sie außerdem an, dass wir wählen$\bigwedge^\ast S$so dass$\bigwedge^\ast S \subseteq \bigwedge S$. Eine Sache, die zu beachten ist, ist, dass es keine rechnerische Methode gibt, um dies zu bestimmen$\bigwedge^\ast S$als Teilmenge von$\bigwedge S$.

Lassen$(v_n)_{n< \omega}$sei eine Aufzählung unserer Variablen. Gegeben sei eine endliche Menge atomarer Formeln$S$, definieren wir die folgenden endlichen Mengen atomarer Formeln:

• $S_0 = \bigvee \bigwedge (S \cup \neg S)$.
• $S_{n+1} = \bigvee \bigwedge \exists v_n S_n$, Wenn$n$ist gerade.
• $S_{n+1} = \bigvee \bigwedge \forall v_n S_n$, Wenn$n$ist ungerade.
• $S^\ast_0 = \bigvee \bigwedge^\ast (S \cup \neg S)$.
• $S^\ast_{n+1} = \bigvee \bigwedge^\ast \exists v_n S^\ast_n$, Wenn$n$ist gerade.
• $S^\ast_{n+1} = \bigvee \bigwedge^\ast \forall v_n S^\ast_n$, Wenn$n$ist ungerade.

Einige Dinge zu beachten:

• Der Ablauf$S_n$ist einheitlich berechenbar als Funktion von$S$, aber die Reihenfolge$S^\ast_n$wird es normalerweise nicht sein.
• Wir werden immer haben$S^\ast_n \subseteq S_n$für jeden$n<\omega$.
• Jede Formel entspricht einer Formel in$S^\ast_n$für einige$S$und einige$n$. Erst recht bedeutet dies, dass jede Formel einer Formel in entspricht$S_n$für einige$S$und einige$n$.

Weinstein bewies das folgende Lemma:

Lemma. Lassen$F$eine endliche autonome Menge von abgeschlossenen Formeln sein$\wedge$Und$\vee$bis zur Äquivalenz. Lassen$u$eine beliebige Variable sein und lassen$\varphi_0$,$\varphi_1$, Und$\varphi$Formeln sein$\bigvee\bigwedge\exists u F$. Folgende Bedingung$(\ast)$reicht aus, um dies sicherzustellen$\varphi_0 \times \varphi_1 \Rightarrow \varphi$.

$(\ast)$Für jedes Disjunkt$\psi_0$von$\varphi_0$und jedes Disjunkt$\psi_1$von$\varphi_1$, es gibt einen Disjunkt$\psi$von$\varphi$so dass für jede Konjunktion$\exists u \chi$von$\psi$, es gibt Konjunktionen$\exists u \chi_0$von$\psi_0$Und$\exists u \chi_1$von$\psi_1$so dass$\chi_0 \times \chi_1 \Rightarrow \chi$.

Außerdem, wenn$\varphi_0$Und$\varphi_1$sind Elemente von$\bigvee \bigwedge^\ast \exists u F$, Dann$(\ast)$ist notwendig und ausreichend für$\varphi_0 \times \varphi_1 \Rightarrow \varphi$halten.

Schließlich gelten die obigen Aussagen für alle Instanzen von$\exists$Ersetzt mit$\forall$.

Die Definition autonomer Mengen findet sich bei Chang und Keisler. Relevant ist hier nur, dass unsere Sets$S_n$sind alle autonom.

Dieses Lemma motiviert die Definition des folgenden primitiven rekursiven Prädikats:$R(\varphi_0,\varphi_1,\varphi)$gilt genau dann wenn$\varphi_0$,$\varphi_1$, Und$\varphi$gehören zu einigen gemeinsamen$S_n$Und

• Wenn$n$Ist$0$, Dann$\varphi_0 \times \varphi_1 \Rightarrow \varphi$;
• Wenn$n$ist dann seltsam$(\ast\ast)$für jedes Disjunkt$\psi_0$von$\varphi_0$und jedes Disjunkt$\psi_1$von$\varphi_1$, es gibt einen Disjunkt$\psi$von$\varphi$so dass für jede Konjunktion$\exists v_{n-1} \chi$von$\psi$es gibt Konjunktionen$\exists v_{n-1} \chi_0$von$\psi_0$Und$\exists v_{n-1} \chi_1$von$\psi_1$so dass$R(\chi_0,\chi_1,\chi)$hält;
• Wenn$n$ist dann gleichmäßig und positiv$(\ast\ast)$hält mit$\forall$anstatt$\exists$.

Dies ist ein berechenbares Prädikat, weil wir nehmen können$S$die Menge der in unseren Formeln vorkommenden atomaren Formeln, und wir brauchen nur zu prüfen$n$das ist ungefähr so ​​groß wie die Quantorenränge unserer Formeln.

Das Lemma besagt das$R(x,y,z)$erfüllt folgendes:

• Für alle$\varphi_0$,$\varphi_1$, Und$\varphi$in einigen$S_n$, Wenn$R(\varphi_0,\varphi_1,\varphi)$hält dann$\varphi_0 \times \varphi_1 \Rightarrow \varphi$.
• Für alle$\psi_0$,$\psi_1$, Und$\psi$in einigen$S^\ast_n$, Wenn$\psi_0 \times \psi_1 \Rightarrow \psi$, Dann$R(\psi_0,\psi_1,\psi)$hält.

Insbesondere bedeutet dies, dass ein Satz$\chi$bleibt unter binären direkten Produkten (und damit endlichen direkten Produkten und auch beliebigen direkten Produkten) genau dann erhalten, wenn es logisch äquivalent zu einem Satz ist$\varphi$in einigen$S_n$so dass$R(\varphi,\varphi,\varphi)$hält.

Eine Formel (erster Ordnung) bleibt durch direkte Faktoren erhalten , wenn sie in einem direkten Produkt gilt$A\times B$, es gilt auch in den Faktoren$A$Und$B$. Keisler gab eine Art komplizierte syntaktische Charakterisierung von Formeln, die durch direkte Faktoren erhalten bleiben: Keisler, HJ, Eigenschaften, die unter direkten Faktoren erhalten wurden. Mitteilungen der American Mathematical Society, vol. 10 (1963), p. 302. Zusammenfassung 63T–169.

Betrachten Sie nun Formeln der Form

$$Q[(\varphi_1\to\alpha_1)\land(\varphi_2\to\alpha_2)\land\cdots\land(\varphi_n\to\alpha_n)]\tag1$$ wo jeweils$\alpha_i$ist jeweils eine atomare Formel$\varphi_i$ist eine durch direkte Faktoren erhaltene Formel, und$Q$ist ein Quantorenpräfix. Formeln des Formulars$(1)$sind allgemeiner als Hornformeln und bleiben durch direkte Produkte erhalten. Ich glaube, es wurde von jemandem (Weinstein? Keisler?) vermutet, dass jede Formel, die durch direkte Produkte erhalten bleibt, einer Formel der Form entspricht$(1)$. Wenn dies zutrifft, würde dies in Kombination mit Keislers Charakterisierung von durch Faktoren erhaltenen Formeln eine syntaktische Charakterisierung von durch Produkte erhaltenen Sätzen ergeben.