Nicht-definierbare Eigenschaften

Eigenschaften, die sich nicht durch einen FO-Satz ausdrücken lassen:

• Endlichkeit: "Das Universum ist endlich".
• Erreichbarkeit (Reachability): "Es gibt einen Pfad von $s$ nach $t$". (Benötigt Quantifizierung über Pfade beliebiger Länge).
• Parität: "Die Anzahl der Elemente ist gerade" (Kann in FO nicht zählen).
• Zusammenhang: "Der Graph ist zusammenhängend".