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
      0 references
      1986
      0 references
      conservative reduction type
      0 references
      interpretation
      0 references
      satisfiability
      0 references
      finite satisfiability
      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

      Identifiers