Ein Neuer Beweis und Eine Verschärfung für den Konservativen Reduktionstyp ∀∃∀∃∞(0, 1) (Q3718679)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3948224
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Ein Neuer Beweis und Eine Verschärfung für den Konservativen Reduktionstyp ∀∃∀∃∞(0, 1) |
scientific article; zbMATH DE number 3948224 |
Statements
Ein Neuer Beweis und Eine Verschärfung für den Konservativen Reduktionstyp ∀∃∀∃∞(0, 1) (English)
0 references
1986
0 references
conservative reduction type
0 references
interpretation
0 references
satisfiability
0 references
finite satisfiability
0 references
0.8549379110336304
0 references
0.8490803241729736
0 references
0.8114107251167297
0 references
0.7988190054893494
0 references
Es sei \({\mathfrak M}\) der kleinste Mengenbereich mit \(\emptyset \in {\mathfrak M}\) und \(x\in {\mathfrak M}\wedge y\in {\mathfrak M}\Rightarrow \{x\}\in {\mathfrak M}\wedge x\cup y\in {\mathfrak M}\). Es heißt \(U\subseteq {\mathfrak M}\) transitiv, gdw. \(u\in v\wedge v\in U\Rightarrow u\in U\). Ferner sei E die zweistellige Prädikatenvariable des Reduktionstyps \(\forall \exists \forall \exists^{\infty}(0,1)\) von Gurevich. Eine Interpretation I von E auf \({\mathfrak M}\) heiße \(\in\)-ähnlich, wenn auf \({\mathfrak M}\) für \(x\neq y\) gilt xI(E)y\(\Leftrightarrow x\in y\). Es wird ohne Benutzung der Methoden von Gurevich oder anderer Methoden bzw. Sätze der Reduktionstheorie bewiesen: Zu jeder Formel \(\alpha\) der PLI kann man eine Formel \(\beta\in \forall \exists \forall \exists^{\infty}(0,1)\) angeben mit 1.) \(\alpha\) ist erfüllbar \(\Leftrightarrow\) \(\beta\) ist erfüllbar \(\Leftrightarrow\) \(\beta\) ist auf \({\mathfrak M}\) durch eine \(\in\)-ähnliche Interpretation von E erfüllbar, 2.) \(\alpha\) ist endlich erfüllbar \(\Leftrightarrow\) \(\beta\) ist endlich erfüllbar \(\Leftrightarrow\) \(\beta\) ist auf einer endlichen transitiven Teilmenge von \({\mathfrak M}\) durch eine \(\in\)- ähnliche Interpretation von E erfüllbar.
0 references