Monadische Logik

Question 1

Was ist MSO?

Answer 1

Monadische Logik zweiter Stufe.

Diese ist eine Erweiterung von FO, welche FO um Quantoren über einstellige Relationssymbole (d.h. Mengenvariablen) erweitert. Aus einer Formel psi können neue Formeln der Form ex.X.psi bzw. f.A.X.psi gebildet werden, mit der Bedeutung “es gibt eine Teilmenge X des Universums, so dass psi”, bzw. “für alle Teilmengen X des Universums gilt psi”