¿Por qué son imposibles los modelos de igualdad?

Question

Sea $\mathcal{L}$ un lenguaje de primer orden. Definimos una estructura de $\mathcal{L}$ como una tupla que consiste en:

1. Universo $M$ (implícitamente entendido como aquel sobre el cual variarán las variables de $\mathcal{L}$)
2. Una asignación de cada uno de los símbolos de función $f$ de aridad $k$ de $\mathcal{L}$ a alguna función de aridad $k$ $f^\mathcal{M}$ sobre $M$
3. Una asignación de cada uno de los predicados de aridad $k$ $P$ de $\mathcal{L}$ a alguna relación de aridad $k$ $P^\mathcal{M}$ sobre $M$. Si $\mathcal{L}$ contiene el predicado $=$, entonces $=^\mathcal{M}$ siempre es la verdadera relación de igualdad sobre $M$ (es decir, la relación de equivalencia cuyas clases de equivalencia son precisamente los subconjuntos unitarios de $M$).

Definimos una estructura débil de $\mathcal{L}$ como una estructura de $\mathcal{L}$ sin la condición de que $=^\mathcal{M}$ sea la verdadera relación de igualdad (es decir, puede ser cualquier relación binaria sobre $M$).

Mi pregunta se refiere al siguiente fragmento de Logical Foundations of Proof Complexity de Cook y Nguyen.

¿Existen enunciados $\mathcal{E}$ (axiomas para la igualdad) tales que una estructura débil M satisface $\mathcal{E}$ si y solo si M es una estructura (correcta)? Es fácil ver que no existe tal conjunto $\mathcal{E}$ de axiomas, porque siempre podemos inflar un punto en un modelo débil a un conjunto de puntos equivalentes.

El libro luego define un conjunto de axiomas de "igualdad" (que, en línea con el fragmento anterior, realmente solo pueden requerir que $=^\mathcal{M}$ sea una relación de equivalencia):

Los primeros tres axiomas son los axiomas usuales de relación de equivalencia, y los axiomas EA4 y EA5 requieren que las funciones y relaciones, respectivamente, asignadas por $\mathcal{M}$ respeten las clases de equivalencia de $=^\mathcal{M}$.

Entiendo cómo se cumple la afirmación citada en el caso en que $\mathcal{E}$ sea este conjunto de axiomas EA1-5 que definen una relación de equivalencia. Claramente, cualquier lista potencial de axiomas que requiera que $=^\mathcal{M}$ sea verdadera igualdad necesitaría contener tales axiomas, ya que la verdadera igualdad es una relación de equivalencia después de todo. Sin embargo, no estoy completamente convencido de que no exista algún conjunto adicional de axiomas que podríamos agregar a EA1-5 que realmente sí requerirían que se true equality.

¿Cómo se demuestra que para cualquier $\mathcal{E}$ y estructura débil $\mathcal{M}$, no es el caso que $\mathcal{M}$ satisfaga $\mathcal{E}$ si y solo si $=^\mathcal{M}$ es la verdadera igualdad?

Answer 1

Los esquemas axiomáticos EA4 y EA5 te dicen que los valores de los símbolos de función y los símbolos de predicado no distinguen entre operandos que son $=$-equivalentes. Por lo tanto, tus axiomas adicionales no tienen forma de distinguir entre elementos $=$-equivalentes en un modelo. Para demostrar esto formalmente, procede como sugiere la cita de tu libro: dado un modelo débil, $\cal M$, selecciona un elemento $x$ en el universo de $\cal M$ y extiende el universo de $\cal M$ para incluir un nuevo elemento $x'$ y extiende la interpretación de los símbolos de función y predicado para tratar a $x'$ de manera idéntica a $x$.

Answer 2

El argumento es como citaste: "siempre podemos inflar un punto en un modelo débil a un conjunto de puntos equivalentes". Esto no depende de nada acerca de $\mathcal L$ o los axiomas elegidos. Agrega una copia $x'$ de un punto $x$ a $\mathcal M$ y extiende las interpretaciones de símbolos para que se comporten de manera idéntica en $x$ y $x'$. Ahora, para cualquier símbolo de relación binaria $R$, tenemos que $\mathcal M$ satisface $xRx'$ si y solo si satisface $xRx$. Pero $x\ne x'$ mientras que $x=x$, entonces $R$ no corresponde a una verdadera igualdad.