Demostrar que la fórmula es válido en algunos infinito de la estructura, pero no en todos los finitos de estructuras

Question

Dada la fórmula. $$[\forall x \exists y P(x,y) ]\;\land [\forall x \forall y (P(x,y) \to \lnot P(y,x))] \;\land [\forall x \forall y \forall z ((P(x,y) \land (P(y,z)) \to P(x,z)))]$$

Primero de todo, traté de encontrar algún (infinito) de interpretación, donde esta fórmula se convierte en verdad. Mientras buscaba en esta fórmula, me di cuenta de que la segunda parte es anti-simétrica relación, y la tercera parte es la transitividad. Así que inmediatamente pensé acerca de la elección de P como un orden parcial sobre los números naturales.

Deje $M = \mathbb{N}$$P(x,y) := x < y$.

Si elijo $y = x + 1$ en la primera parte, entonces la fórmula se evalúa en T

OK, si todo está bien, hasta este momento, entonces vamos a tratar de demostrar que la declaración es idéntica F para cualquier finito de interpretación.

Estoy atascado por un par de horas en la segunda parte. Tenía una idea ciegamente a cambiar el nombre de cada uno de los sub-fórmula por alguna letra, y tratar de demostrarlo mediante cálculo proposicional métodos (prueba por contradicción o simplemente a través de las tablas de verdad). Pero el primero que se $\forall x \exists y P(x,y)$, lo que implica la $\exists$ cuantificador que me confunde.

¿Qué me he perdido aquí? Hacer auto estudio del material es muy consumible cuando usted está atascado. Una respuesta con una explicación detallada será muy valiosa.

Gracias.

Answer 1

La idea es la siguiente : $P$ se interpreta como una relación es transitiva y antisimétrica, en otras palabras, un estricto pedido de $<$.

Pero la primera parte de la fórmula en cuestión también dice lo siguiente : no hay ningún elemento maximal, en otras palabras, para cada elemento, no es estrictamente una más grande.

Si usted tiene tal interpretación, escoger un elemento $x_0$. Entonces no es máxima, por lo que no debe ser $x_1>x_0$. De manera similar, deben ser $x_2>x_1$. Proceder, con la inducción a crear $x_n$ todos los $n\in \mathbb{N}$. Si $n<m$,$x_< x_{n+1}<...< x_m$, y por lo tanto, fuera de la transitividad, $x_n < x_m$, y así si $n\neq m$, $x_n\neq x_m$. Ahora se puede tener un número finito de interpretación y una secuencia en ella ?

Answer 2

Me gusta pensar acerca de esto visualmente/gráficamente. Así que piensa acerca de cualquier $P(x,y)$ relación como la que hay una flecha de $x$$y$.

Debido a la relación ser asymmetical y transitiva, usted nunca puede tener un ciclo de flechas, y por lo tanto somos capaces de organizar todos los objetos en el dominio de tal forma que cada flecha para ir de izquierda a derecha.

Pero si el dominio es finito, entonces debe haber uno o más a la derecha-la mayoría de los objetos, lo que significa que no tienen un saliente de flecha ... pero que contradice la primera conjunción, que requiere que cada objeto tenga un saliente de la flecha. Así, es imposible satisfacer esta con un número finito de dominio.

Answer 3

Si $\Bbb M$ es cualquier interpretación deje $P^M=\{(x,y)\in M: \Bbb M\text { satisfies } P(x,y)\}$ $P^M$ es una relación binaria en a $M.\;$(I. e. $P^M$ es un subconjunto/subclase de $M\times M.$).

Deje $\Bbb M$ ser un número finito de interpretación con $n$ de los miembros ($n\in \Bbb N$). Supongamos $P^M$ satifies la primera condición (I. e. el dominio de $P^M$$M$) y que $P^M$ es transitiva. A continuación, $P^M$ no puede ser anti-simétrica debido a $\exists x\;(P^M(x,x)).$

Prueba: Tome $x_1\in M$ $1\leq j\leq n$ deje $x_{j+1}\in \{y\in M: P^M(x_j,y)\}.$ existe $i,j$ $1\leq i<j\leq n+1$ $x_i=x_j$ por el Pigeon-Hole Principio. Ahora transitividad de la $P^M$ implica que, por inducción en $k$, $P^M(x_i,x_{i+k})$ siempre $1\leq k\leq n+1-i.$, Pero luego tenemos a $P^M(x_i,x_j)$ $x_i=x_j,$ contradiciendo anti-simetría.

Nota: Si lo prefiere, deje $M=\{m_i:1\leq i\leq n\},$ y deje $x_1=m_1$ y deje $x_{j+1}=m_u(j)$ donde $u(j)=\min \{v: P^M(x_j,m_v\}$, si quieres un algoritmo recursivo para la definición de cada uno de los x_j.