El número de símbolos no lógicos distintos en la firma de un lenguaje, contando típicamente símbolos de función, predicado y constantes (a menudo tratando un símbolo con su aridad como una entrada distinta según la convención).

Principio

El tamaño de la firma mide la riqueza de vocabulario disponible para construir fórmulas; limita la variedad de fórmulas atómicas y, por tanto, afecta la expresividad, la combinatoria de estructuras y la complejidad de problemas de decisión.

Demostración

Una firma Σ = {c (constante), f (función unaria), g (función binaria), P (predicado unario), R (predicado binario)} tiene tamaño de firma 5 bajo la convención de contar nombres de símbolos; según la convención de contar pares símbolo-aridad sigue siendo 5 si las aridades se registran con los símbolos.

Aplicación incorrecta

Contar conectivos lógicos (¬, ∧, →) o metadatos como símbolos de la firma, o no fijar si diferentes aridades del mismo nombre son distintas, conduce a comparaciones inconsistentes del tamaño de firma entre lenguajes o resultados.

Consecuencia

Controlar el tamaño de la firma es importante en teoría de modelos finitos y en análisis de complejidad: firmas acotadas pueden simplificar argumentos de enumeración y hacer más factibles algunos procedimientos de decisión, mientras que firmas no acotadas o infinitas aumentan la expresividad y la dificultad técnica.

Inversión

La visión dual es una firma infinita o muy grande donde se introducen símbolos libremente; esa expansión puede aumentar trivialmente la expresividad pero puede anular ciertos resultados de clasificación o requerir contabilidad adicional en construcciones.

Límite

El tamaño de la firma se refiere únicamente al conteo de símbolos no lógicos en el lenguaje formal elegido y excluye conectivos lógicos, puntuación, variables y sobrecarga de codificación externa; el tratamiento preciso de la aridad y la equivalencia de símbolos debe definirse para evitar ambigüedad.

Tensión semántica

El tamaño de la firma compite con medidas de densidad del vocabulario como la distribución de aridades y la reutilización: dos firmas del mismo tamaño pueden diferir mucho si una tiene muchos símbolos de alta aridad y la otra muchas constantes, ofreciendo distintas capacidades de modelado.

Síntesis

El tamaño de la firma es el recuento de símbolos no lógicos distintos disponibles en un lenguaje (con una convención especificada para la aridad), y sirve como una medida simple de riqueza de vocabulario que condiciona la expresividad, la combinatoria y la complejidad en estudios lógicos.