Die Anzahl der unterschiedlichen nicht-logischen Symbole in der Signatur einer Sprache, üblicherweise die Funktionssymbole, Prädikatsymbole und Konstantensymbole zählend (je nach Konvention wird ein Symbol zusammen mit seiner Arität als eigene Einheit betrachtet).

Prinzip

Die Signaturgröße misst den Wortschatz, der zum Bilden von Formeln verfügbar ist; sie begrenzt die Vielfalt atomarer Formeln und beeinflusst damit Ausdrucksstärke, die Kombinatorik von Strukturen und die Komplexität von Entscheidungsproblemen.

Demonstration

Eine Signatur Σ = {c (Konstante), f (unäre Funktion), g (binäre Funktion), P (unäres Prädikat), R (binäres Prädikat)} hat nach der Zählkonvention 5 Symbole; unter einer Konvention, die Symbol-Aritäts-Paare zählt, bleibt sie 5, sofern die Aritäten mit den Symbolen festgehalten werden.

Fehlanwendung

Logische Junktoren (¬, ∧, →) oder Metavariablen als Signatursymbole zu zählen oder nicht zu klären, ob unterschiedliche Aritäten desselben Namens verschieden gezählt werden, führt zu inkonsistenten Vergleichen der Signaturgröße zwischen Sprachen oder Ergebnissen.

Konsequenz

Die Kontrolle der Signaturgröße ist in der endlichen Modelltheorie und in Komplexitätsanalysen wichtig: Begrenzte Signaturen vereinfachen Zählargumente und machen manche Entscheidungsverfahren praktikabler, während unbeschränkte oder unendliche Signaturen die Ausdrucksstärke und technische Komplexität erhöhen.

Umkehrung

Die duale Sicht ist eine unendliche oder sehr große Signatur, in der neue Symbole frei eingeführt werden; eine solche Erweiterung erhöht die Ausdrucksstärke trivial, kann jedoch gewisse Klassifikationsergebnisse entwerten oder zusätzlichen administrativen Aufwand bei Konstruktionen erfordern.

Abgrenzung

Die Signaturgröße bezieht sich nur auf die Anzahl nicht-logischer Symbole in der gewählten formalen Sprache und schließt logische Junktoren, Interpunktion, Variablen und externen Kodierungsaufwand aus; die genaue Behandlung von Arität und Symboläquivalenz muss angegeben werden, um Mehrdeutigkeiten zu vermeiden.

Semantische Spannung

Die Signaturgröße steht im Spannungsfeld zu Maßen wie der Dichte des Vokabulars, etwa Verteilung der Aritäten und Wiederverwendung von Symbolen: Zwei Signaturen gleicher Größe können stark variieren, wenn die eine viele hoch-arity Symbole und die andere viele Konstanten hat, was zu unterschiedlichen Modellierungsmöglichkeiten führt.

Synthese

Die Signaturgröße ist die Anzahl der unterschiedlichen nicht-logischen Symbole in einer Sprache (mit einer festgelegten Konvention zur Arität); sie ist ein einfaches Maß für Wortschatzreichtum, das Ausdrucksstärke, Kombinatorik und Komplexität in logischen Untersuchungen mitbestimmt.