Una relación que compara dos lenguajes o formalismos formales en la que uno se considera al menos tan expresivo como el otro cuando puede definir o simular toda propiedad, clase de estructuras o predicado definible en el segundo.

Principio

La expresividad se mide por la definibilidad o la simulación fiel: L1 es al menos tan expresivo como L2 si existe una codificación o interpretación sistemática que lleve cada propiedad definible en L2 a una propiedad definible en L1; típicamente esto induce un preorden (reflexivo, transitivo) entre lenguajes.

Demostración

La lógica proposicional es estrictamente menos expresiva que la lógica de primer orden porque hay propiedades de primer orden (por ejemplo, “existen dos elementos distintos”) que no pueden expresarse proposicionalmente; del mismo modo, muchas lógicas modales son menos expresivas que el fragmento de lógica de primer orden obtenido por la traducción estándar de fórmulas modales a fórmulas de primer orden sobre marcos.

Aplicación incorrecta

Confundir expresividad relativa con decidibilidad, complejidad o concisión; por ejemplo, concluir que por ser más expresivo un lenguaje debe ser indecidible, o equiparar expresividad con la brevedad de las fórmulas.

Consecuencia

Si un lenguaje es al menos tan expresivo como otro, se pueden transferir teoremas meta, resultados de definibilidad y algunas distinciones semánticas mediante la codificación; esto orienta la elección de formalismo para especificación y análisis.

Inversión

La relación inversa señala in-expresividad estricta: L1 es menos expresivo que L2 cuando existen propiedades definibles en L2 que ninguna codificación en L1 puede capturar, mostrando brechas cualitativas entre lenguajes.

Límite

Se aplica a lenguajes formales y formalismos con una noción clara de definibilidad o satisfacción; no compara directamente rendimiento de implementación, complejidad de búsqueda de pruebas o concisión pragmática salvo que estos formen parte explícita del criterio de definibilidad.

Tensión semántica

Compite con nociones como decidibilidad y concisión: un lenguaje más expresivo puede sacrificar decidibilidad o requerir fórmulas más largas, por lo que la expresividad debe compensarse con consideraciones algorítmicas y prácticas.

Síntesis

La expresividad relativa es el preorden sobre formalismos inducido por la existencia de codificaciones o simulaciones sistemáticas que preservan la definibilidad; identifica cuándo un lenguaje puede capturar fielmente los recursos descriptivos de otro y señala los compromisos con la decidibilidad y la complejidad.