Eine obere Grenze für die Klasse von Eigenschaften oder Strukturen, die eine logische Sprache oder ein Fragment in einem gegebenen syntaktischen oder semantischen Rahmen definieren oder unterscheiden kann; die maximale expressive Reichweite ohne Änderung des formalen Apparats.

Prinzip

Obergrenzen ergeben sich aus der Kombination syntaktischer Bildungsvorschriften, verfügbarer Quantoren und Operatoren sowie semantischer Invarianten: Sie lassen sich oft algebraisch oder spieltheoretisch charakterisieren (z. B. durch Ehrenfeucht-Fraïssé-Spiele, algebraische Varietäten oder Automatenkorrespondenzen).

Demonstration

Auf endlichen Wörtern erfasst die monadische zweite Ordnung (MSO) genau die regulären Sprachen — diese Charakterisierung ist eine Expressivitätsobergrenze für MSO über Wörtern: Keine nichtreguläre Sprache ist in MSO[<] auf endlichen Wörtern definierbar. Ebenso entspricht die erste Ordnung mit Ordnung den sternfreien (aperiodischen) Sprachen und setzt damit eine Obergrenze für FO[<].

Fehlanwendung

Zu behaupten, eine Obergrenze verbiete jede sinnvolle Approximation oder Teilbeschreibung; eine Obergrenze sagt nur Nicht-Definierbarkeit in der gegebenen Sprache aus, nicht die Unmöglichkeit schwächerer oder probabilistischer Charakterisierungen außerhalb dieses Rahmens.

Konsequenz

Eine bekannte Expressivitätsobergrenze erlaubt die Klassifikation von Eigenschaften in definierbare und nicht definierbare Mengen und lenkt die Wahl stärkerer Logiken oder alternativer Modellbeschränkungen; sie stützt Vollständigkeits- und Unausdrückbarkeitsbeweise und verbindet Logik mit Automaten- und Algebracharakterisierungen.

Umkehrung

Die Erweiterung der Sprache (Hinzufügen zweiter Ordnung, höherer Prädikate, Zähloperatoren oder Fixpunktoperatoren) kann die Obergrenze anheben oder entfernen, sodass zuvor nicht definierbare Eigenschaften definierbar werden; umgekehrt zeigt das Nachweisen einer Obergrenze für eine sehr expressive Logik tiefere Beschränkungen an.

Abgrenzung

Eine Obergrenze wird hinsichtlich einer konkreten Logik, Signatur und Strukturklasse bewertet; sie behauptet keine Unmöglichkeit über alle Formalismen hinweg und schließt Betrachtungen zur Prägnanz aus (eine Eigenschaft kann definierbar, aber unpraktisch ausgedrückt sein).

Semantische Spannung

Die Obergrenze steht in Wechselwirkung mit Kürze und Komplexität: Eine Eigenschaft kann unter der Obergrenze liegen (definierbar), aber schwer berechenbar sein, oder oberhalb liegen, dennoch durch Formeln approximierbar sein, die große Anteile ihres Verhaltens erfassen; die Einordnung hinsichtlich einer Obergrenze erfordert qualitative und quantitative Abwägungen.

Synthese

Eine Expressivitätsobergrenze ist die formale maximale Grenze dessen, was die gewählte Logik definieren kann: Sie ist durch syntaktische Beschränkungen und semantische Invarianten bestimmt, oft mittels Spielen oder algebraischer Korrespondenzen fassbar, und gibt Aufschluss darüber, ob die Sprache zu stärken oder Modellannahmen zu ändern sind, um darüber hinauszugehen.