Eine formale Grenze innerhalb einer gegebenen logischen Sprache oder eines Fragments, jenseits derer zusätzliche semantische Unterscheidungen oder Eigenschaften nicht ausgedrückt werden können, ohne die Sprache zu ändern (Hinzufügen von Quantoren, Prädikaten oder höherordentlichen Merkmalen) oder zusätzliche rechnerische Komplexität in Kauf zu nehmen.

Prinzip

Ausdrucksgrenzen entstehen durch syntaktische Beschränkungen und Invarianzen (z. B. Abschlusseigenschaften oder Bewahrung unter Homomorphismen, Bisimulationen oder Ehrenfeucht-Fraïssé-Ununterscheidbarkeit), die die Sprache daran hindern, bestimmte semantische Konfigurationen zu differenzieren.

Demonstration

Die Prädikatenlogik erster Stufe kann auf endlichen Graphen etwa die Eigenschaft 'Graph ist zusammenhängend' oder 'die Domäne ist endlich' nicht ausdrücken; diese Unfähigkeit ist eine Expressivitätsbarriere, die den Einsatz von transitiver Hülle, Fixpunktlogiken oder zweiter Ordnung erzwingt, wenn man solche Eigenschaften erfassen will.

Fehlanwendung

Eine Expressivitätsbarriere als absolute ontologische Unmöglichkeit zu interpretieren statt als relative Beschränkung bezüglich einer gewählten Syntax oder Modellklasse; oder aus einer Barriere auf algorithmische Härte zu schließen, ohne zwischen deskriptiver und berechenbarer Komplexität zu unterscheiden.

Konsequenz

Die Identifikation einer Expressivitätsbarriere motiviert die Erweiterung der Sprache (Hinzufügen von Operatoren wie transitiver Hülle oder Zähloperatoren) oder die Einschränkung der Modellklasse (Arbeiten auf geordneten Strukturen oder beschränkter Baumweite), und strukturiert Klassifikationssätze und Untergrenzen in der deskriptiven Komplexitätstheorie.

Umkehrung

Das Aufheben oder Lockern syntaktischer Beschränkungen (z. B. Hinzufügen von zweiter Ordnung, Fixpunktoperatoren oder Kardinalitätsprädikaten) kann die Barriere durchbrechen und die zuvor unausdrückbare Eigenschaft definierbar machen; umgekehrt zeigt das Nachweisen einer unüberwindbaren Barriere in einem erweiterten Rahmen tiefere Beschränkungen auf.

Abgrenzung

Expressivitätsbarrieren sind stets relativ zu einer festgelegten Logik, Signatur und Strukturklasse; sie treffen keine Aussagen über die praktische Berechenbarkeit einer Eigenschaft oder über Semantik außerhalb des gewählten formalen Rahmens.

Semantische Spannung

Es besteht Spannung zwischen Ausdruckskraft und Handhabbarkeit: reichere Logiken überwinden Barrieren, erhöhen aber meist die Komplexität, während schwächere Sprachen handhabbar bleiben, aber Barrieren begegnen; außerdem besteht Spannung zwischen Kürze (Prägnanz) und bloßer Ausdrucksfähigkeit.

Synthese

Eine Expressivitätsbarriere markiert den Punkt, an dem eine gewählte formale Sprache ihre diskriminierende Kraft verliert: sie ist eine relative, formale Schranke, bestimmt durch syntaktische Invarianten und Strukturklassenüberlegungen, die anzeigt, ob die Sprache erweitert, die Modelle angepasst oder die Einschränkung akzeptiert werden soll.