La insatisfacción del principio de encasillamiento

Question

Hola quiero una sugerencia sobre cómo resolver este problema.

Demuestra que la fórmula:

$A_{pigeon} = \forall x \exists y (Pxy \wedge y \neq c) \wedge \forall x,y,z (x = y \vee not Pyz \vee not Pxz)$

No es satisfacible en ningún universo finito (no vacío). Ah, y c es una constante.

Tengo entendido que tengo que dar un ejemplo concreto para poder demostrarlo, pero no estoy del todo seguro. Si tengo que demostrar esto de forma más general, ¿alguien puede dar alguna pista o técnica para abordar este problema? Gracias por cualquier consejo.

Answer 1

Denotemos $x_1,\dots,x_n$ los elementos del universo $U$ con $c=x_1$ . La segunda parte de la frase nos dice que si $Pxz$ y $Pyz$ entonces $x=y$ para cualquier $x,y,z$ . Esto significa que podemos pensar en $P$ como una función parcial $f:U\to U$ , asignando el segundo argumento al primero.

La primera parte nos dice que para todos los $x$ hay $y\neq c$ tal que $f(y)=x$ . Esto significa dos cosas:

1)todo se alcanza por $f$ .

2) $c$ no tiene imagen por $f$ .

Es fácil ver que hay una contradicción: si $c$ no tiene imagen, entonces sólo $n-1$ elementos pueden ser alcanzados, contradiciendo 1).

Observe que $\mathbb N$ es un contraejemplo que satisface $A_{pigeon}$ con $c=0$ y $Pxy$ siendo " $x+1=y$ ".