Eliminación de cuantificadores para la teoría de relaciones de equivalencia.

Question

Deje $\mathcal{L}=\{\sim\}$ $\Sigma_\infty$ el conjunto de axiomas que indica que:

(i) $\sim$ es una relación de equivalencia
(ii) Cada clase de equivalencia es infinito
(iii) hay infinitamente muchas clases de equivalencia

Esto es suficiente para mostrar que todos los $\mathcal{L}$ fórmula $\exists y\varphi(x,y)$ $\Sigma_\infty$- equivalente a un cuantificador libre $\psi(x)$ donde $x=(x_1,\ldots,x_n)$ son distintas variables, y $\varphi(x,y)$ es una conjunción de literales. Ya es bastante trivial al $\varphi(x,y)$ tiene un conjunto de la forma $x_i=y$, podemos asumir que tenemos que reducir $$\exists y (\bigwedge_{i\in I} x_i\not=y\wedge\bigwedge_{j\in J}x_j\sim y\wedge\bigwedge_{h\in H}\neg (x_j\sim y))$$ Mi pregunta es si o no la condición siguiente se tiene:

$$\Sigma_\infty\vdash\exists y (\bigwedge_{i\in I} x_i\not=y\wedge\bigwedge_{j\in J}x_j\sim y\wedge\bigwedge_{h\in H}\neg (x_j\sim y))\leftrightarrow(\bigwedge_{j\in J,h\in H}\neg(x_i\sim x_j)\wedge\bigwedge_{j,j'\in J}x_j\sim x_{j'})$$ No puedo pensar en una razón por la que no, pero estoy un poco preocupado acerca de ignorar la información acerca de la falta de elementos idénticos en la que no fue reducida fórmula.

Answer 1

La equivalencia se mantiene porque las clases de equivalencia son infinitas. Si tiene$(x_1,…,x_n)$ de manera tal que se mantiene el RHS, el conjunto$\{x_j \mid j\in J\}$ es finito. Si no está vacío, hay un elemento$y$ tal que$y\sim x_j$ para$j\in J$ y$y\neq x_j$. Si el conjunto está vacío, la existencia de$y$ está implícita por el hecho de que hay infinitas clases de equivalencia, por lo que puede elegir un$y$ que no sea$\sim$ - equivalente a cualquier$x_h,h\in H$.