Una cota superior sobre la clase de propiedades o estructuras que un lenguaje lógico o fragmento puede definir o distinguir dentro de un marco sintáctico o semántico dado; el alcance expresivo máximo disponible sin cambiar el aparato formal.

Principio

Los techos proceden de la combinación de reglas sintácticas, cuantificadores y operadores disponibles, y de invariantes semánticos: a menudo pueden caracterizarse por medios algebraicos o de teoría de juegos (p. ej., mediante juegos de Ehrenfeucht-Fraïssé, variedades algebraicas o correspondencias con autómatas).

Demostración

En palabras finitas, la lógica monádica de segundo orden (MSO) captura exactamente los lenguajes regulares: esa caracterización es un techo de expresividad para MSO sobre palabras: ninguna lengua no regular es definible en MSO[<] sobre palabras finitas. De modo análogo, la lógica de primer orden con orden corresponde a los lenguajes sin estrella (aperiódicos), estableciendo un techo para FO[<].

Aplicación incorrecta

Afirmar que un techo impide cualquier aproximación útil o descripción parcial; un techo sólo indica no definibilidad en el lenguaje dado, no la imposibilidad de caracterizaciones más débiles o probabilísticas fuera de ese marco.

Consecuencia

Un techo de expresividad conocido permite clasificar propiedades en definibles y no definibles y guía la elección de lógicas más fuertes o restricciones alternativas en los modelos; respalda pruebas de completitud e inexpressabilidad y conecta la lógica con autómatas y caracterizaciones algebraicas.

Inversión

Extender el lenguaje (añadiendo características de segundo orden, predicados de mayor aridad, conteo u operadores de punto fijo) puede levantar o eliminar el techo de modo que propiedades antes no definibles pasan a ser definibles; a la inversa, probar un techo para una lógica muy expresiva indica límites profundos ligados a invariantes semánticos.

Límite

Un techo se evalúa respecto a una lógica concreta, firma y clase de estructuras; no afirma imposibilidad a través de todos los formalismos y excluye preocupaciones sobre concisión (una propiedad puede ser definible pero requerir fórmulas imprácticas).

Tensión semántica

El techo interactúa con nociones de concisión y complejidad: una propiedad puede estar por debajo del techo (ser definible) pero ser intratable desde su definición, o estar por encima y aun así aproximable por fórmulas que capturan gran parte de su comportamiento; clasificar propiedades respecto a un techo implica compensaciones cualitativas y cuantitativas.

Síntesis

Un techo de expresividad es la frontera formal máxima de lo que un lenguaje elegido puede definir: está determinado por restricciones sintácticas y invariantes semánticos, comúnmente capturados por juegos o correspondencias algebraicas, e indica si conviene fortalecer el lenguaje o alterar supuestos sobre los modelos para ir más allá.