Le nombre de symboles non logiques distincts dans la signature d'un langage, comptant typiquement les symboles de fonction, de prédicat et les constantes (en pratique on précise souvent si l'on considère un symbole avec son arité comme une entrée distincte).

Principe

La taille de la signature mesure la richesse du vocabulaire disponible pour former des formules ; elle contraint la variété des atomes et affecte l'expressivité, la combinatoire des structures et la complexité des problèmes de décision.

Démonstration

Une signature Σ = {c (constante), f (fonction unaire), g (fonction binaire), P (prédicat unaire), R (prédicat binaire)} a une taille de signature égale à 5 selon la convention de compter les noms de symboles ; en adoptant la convention qui enregistre l'arité avec les symboles, on obtient également 5.

Mauvaise application

Compter les connecteurs logiques (¬, ∧, →) ou les méta-variables comme symboles de signature, ou omettre de préciser si des arités différentes d'un même nom sont distinctes, conduit à des comparaisons incohérentes de la taille de signature entre langages ou résultats.

Conséquence

Contrôler la taille de la signature est important en théorie des modèles finis et dans les analyses de complexité : des signatures bornées peuvent simplifier les arguments d'énumération et rendre certaines procédures de décision plus réalisables, tandis que des signatures non bornées ou infinies augmentent l'expressivité et la difficulté technique.

Inversion

Le point de vue dual est une signature infinie ou très grande où de nouveaux symboles peuvent être introduits librement ; une telle extension augmente trivialement l'expressivité mais peut rendre caduques certains résultats de classification ou exiger un suivi supplémentaire dans les constructions.

Limite

La taille de la signature se rapporte uniquement au décompte des symboles non logiques du langage formel choisi et exclut les connecteurs logiques, la ponctuation, les variables et les surcoûts d'encodage externes ; le traitement précis de l'arité et de l'équivalence des symboles doit être spécifié pour éviter toute ambiguïté.

Tension sémantique

La taille de la signature est en tension avec des mesures de densité du vocabulaire comme la distribution des arités et la réutilisation des symboles : deux signatures de même taille peuvent différer fortement si l'une a beaucoup de symboles de haute arité et l'autre beaucoup de constantes, offrant des capacités de modélisation différentes.

Synthèse

La taille de signature est le nombre de symboles non logiques distincts disponibles dans un langage (avec une convention précisée pour l'arité) ; c'est une métrique simple de richesse du vocabulaire qui conditionne l'expressivité, la combinatoire et la complexité dans les études logiques.