Expresando elementos infinitos cada clase de equivalencia en la lógica de primer orden.

Question

Yo estaba pasando por algunos de FO-lógica de ideas para mi la lógica de examen y de revisión, se encontró con algunos problemas...

Las relaciones de equivalencia puede ser expresado en FO-lógica por el conjunto de axiomas:

$\{\forall x Rxx, \forall x \forall y(Rxy \rightarrow Ryx), \forall x \forall y \forall z (Rxy \wedge Ryz \rightarrow Rxz)\}$ donde $R$ es una relación de congruencia

¿Cómo podemos entonces expresar el requisito adicional de que cada clase de equivalencia tiene un número infinito de elementos? Creo que este sistema axiomático es infinito, pero sin embargo axiomatizable.

Un requisito similar sería que un universo infinitamente muchas clases de equivalencia. ¿Cómo nos va generalmente acerca de la formulación de un sistema axiomático para tales expresiones?

Answer 1

Suponemos que su sistema es el habitual de la lógica de primer orden con igualdad.

Para $n\ge 2$, vamos a $S_n$ ser la frase que dice $\forall x\exists y_1\exists y_2\cdots \exists y_n\phi(x,y_1,y_2,\dots, y_n)$. Aquí $\phi$ es la conjunción de (i) las fórmulas de $R(x,y_i)$ donde $i$ rangos de los enteros de $1$ a $n$ y (ii) las fórmulas de la forma $\lnot(y_i=y_j)$, para todos los $i,j$ donde $1\le i\lt j\le n$.

La adición de todos los $S_n$ a su sistema de axiomas de las fuerzas de todas las clases de equivalencia para tener infinidad de elementos.

Obligando a una infinidad de clases de equivalencia es más simple. Deje $T_n$ ser la frase que dice que el $\exists x_1\exists x_2\cdots \exists x_n\psi(x_1,x_2,\dots,x_n)$. Aquí $\psi$ es la conjunción de todas las $\lnot R(x_i,x_j)$ donde $i,j$ rangos de todas las $1\le i\lt j\le n$. La adición de $T_n$ para todos los $n\ge 2$ fuerzas de la existencia de una infinidad de clases de equivalencia.