Pruébalo: Imposible expresar "Hay al menos 7 objetos" cuantificando sobre sólo 6 variables

Question

[ACTUALIZACIÓN: Un comentario en esta entrada ( ¿Es legítimo cuantificar dos veces una variable? me llevó a un pdf de un libro sobre la Teoría de Modelos Finitos de Libkin, y el tema aquí parece estar conectado con el concepto general de FO-inexpresividad. El capítulo 3 sobre los juegos de Erhrenfeucht-Fraisse parece contener información relevante, pero es mucho más que una introducción. También he encontrado la frase "Beth Definability Theorem", que parece estar relacionada (cf. https://encyclopediaofmath.org/wiki/Beth_definability_theorem ). Teniendo en cuenta todo esto, dudo que Barwise y Etchemendy esperen que alguien de la audiencia de su libro de texto persiga esta cuestión con éxito por su cuenta...)

La pregunta #14.8 en Lenguaje, Pruebas y Lógica por Barwise & Etchemendy dice:

"Es imposible expresar la frase Hay al menos siete objetos utilizando sólo = y las seis variables disponibles en [el programa informático que acompaña a la obra] El mundo de Tarski, sin importar cuántos cuantificadores se utilicen. Intente demostrar esto [Advertencia: Esto es cierto, pero es muy difícil de demostrar]"

Espero sólo una pista -- NO una solución (al menos no inmediatamente...)-- ya que lo más cercano que pude encontrar aquí fue este post( Definibilidad de primer orden de estructuras de al menos $n$ elementos ), y las búsquedas posteriores sobre la definibilidad/tamaño de las estructuras de primer orden condujeron a cuestiones mucho más complicadas.

No quiero saturar el tablero con especulaciones infructuosas, así que me limitaré a exponer brevemente un par de estrategias con las que estaba jugando:

Método general: Prueba por contradicción -- Supongamos que podemos expresar la frase objetivo con sólo 6 variables, llámese $\phi$

Idea 1: Reconocer que la frase objetivo puede expresarse con 6 o 7 variables cuantificadas, y tratar de derivar una contradicción a partir del posible tipo/orden del cuantificador

Idea 2: Tratar de demostrar que asumiendo $\phi$ permite expresar "Hay al menos 6 objetos" con sólo 5 variables. Induce hasta "Hay un objeto" sin variables. Inténtelo reconociendo que cada variable aparece sólo un número finito de veces en $\phi$ . Así que elige, digamos, $x_1$ y en todos los casos sustituirlo por $x_2$ excepto cuando un "=" ya tiene $x_2$ en él, en cuyo caso sustitúyalo por $x_3$ .

Idea 3: Considerar la estructura algebraica de, y la relación entre, conjuntos de wffs que expresan la propiedad "al menos n objetos", donde cada conjunto contiene sólo wffs con un número fijo de variables.

¿Alguno de estos esbozos parece la dirección correcta, o estoy completamente desorientado?

Answer 1

Hay formas más sencillas de hacerlo, pero sugiero que se investiguen los juegos de Ehrenfeucht-Fraïssé, ya que son una buena forma de intuir la expresividad de la lógica de primer orden. El libro Linear Orderings de Rosenstein tiene una buena introducción.

Dos jugadores, Spoiler y Duplicator, se turnan para elegir elementos de dos estructuras A y B.

A su vez $i$ , Spoiler va primero y escoge cualquier elemento de cualquiera de las dos estructuras. Duplicator entonces escoge un elemento de la otra estructura para emparejarlo. Llama a estos $a_i$ y $b_i$ independientemente de quién haya elegido qué.

Si en algún momento hay una fórmula básica (que no implique lógica booleana o cuantificadores, por lo que en su caso sólo implica $=$ ) que es cierto para el $a_i$ pero no es cierto que el correspondiente $b_i$ Entonces el Duplicador pierde.

Si el Duplicador puede evitar perder por turno $n$ entonces todas las fórmulas con $n$ las variables que son verdaderas en una estructura son verdaderas en la otra. Duplicator puede aprovechar esta similitud para no perder.

Por el contrario, si Spoiler tiene una estrategia para ganar en $n$ se convierte, hay una fórmula con $n$ variables que es cierto en una estructura pero no en la otra. Spoiler puede explotar esta diferencia para ganar.

Si quieres acotar el número de variables $(\leq n)$ y permiten cuantificar sobre la misma variable varias veces, es necesario acotar el número de $a_i$ y $b_i$ ( $\leq n$ ), pero permiten que Spoiler mueva el turno anterior $a_j$ ( $b_j$ ) a la que Duplicator responde reposicionando el correspondiente $b_j$ ( $a_j$ ).