EIN NEUER BEWEIS UND EINE VERSCHÄRFUNG FÜR DEN REDUKTIONSTYP ∀∃∀∞(0, 1) MIT EINER ANWENDUNG AUF DIE SPEKTRALE DARSTELLUNG VON PRÄDIKATEN

✍ Scribed by Michael Deutsch; M. Deutsch

• Publisher: John Wiley and Sons
• Year: 1992
• Tongue: English
• Weight: 782 KB
• Volume: 38
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19920380153

✦ Synopsis

Abstract

A simultaneous semantical and syntactical reduction is given for the satisfiability respectively finite satisfiability of first order formulas. We choose ∀∃∀∞(0, 1) as conservative reduction class and allow only formulas out of ∀∃∀∞(0, 1) having a simple set theoretical model if they are satisfiable at all. With the same method we get a spectral representation of any ϱ‐ary enumerable respectively coenumerable predicate by a formula out of ∀∃∀∞(ϱ, 1).