Undefinability de nivelación de primer orden de la lógica

Question

Mi pregunta es para mostrar que no hay pena de $\psi$ en un lenguaje de primer orden de la lógica, sin ningún no-lógico símbolos tales que para cada finitos de la estructura $\mathcal{A}$: $$\mathcal{A} \vDash \psi \; \text{if and only if} \; | \mathcal{A} | \; \text{is even}.$$ Hay una frase de $\psi$ si añadimos un unario símbolo de función $f$ a nuestro idioma?

Mi intento de solución:

Para la primera parte, supongamos por contradicción que hay un $\psi$. Deje $\Gamma = \{ \lnot \gamma _n : n \ge 0\}$ donde $\lnot \gamma _n$ expresa que hay 2n+1 objetos.

Ahora vamos a $\mathcal{A}$ ser una estructura tal que $\mathcal{A} \vDash \Gamma$.

Si $\mathcal{A}$ es finito, entonces $| \mathcal{A} |$ es uniforme y por lo $\mathcal{A} \vDash \psi$.

Sabemos $\{ \psi \}$ es consistente, ya que cada finito, incluso la estructura es un modelo de $\{ \psi \}$. Así que por Lowenheim-Skolem teorema, $\{ \psi \}$ tiene un modelo contable, $\mathcal{B}$ decir. Por lo $\mathcal{B} \vDash \psi$.

Así que si $\mathcal{A}$ es infinito, $\mathcal{A} \vDash \psi$ $\mathcal{A}$ $\mathcal{B}$ son equivalentes(?).

Por lo tanto, $\Gamma \vDash \psi$. Por la compacidad no es $\Gamma _0 \subset \Gamma$ finito tal que $\Gamma _0 \vDash \psi$. Esto es una contradicción ya que podemos encontrar fácilmente un modelo de $\mathcal{C}$ $\Gamma _0$ que $\mathcal{C} \vDash \Gamma _0$ pero $\mathcal{C}$ no modelo de $\psi$ : cualquier modelo de cardinalidad $2k+1$ donde $k$ elegido es mayor que el índice de cualquier $\gamma _n$ se producen en $\Gamma _0$ va a hacer. Por lo tanto, no hay tal $\psi$.

Es el método correcto? Yo no estoy seguro sobre el caso al $\mathcal{A}$ es infinita y la aplicación de la Lowenheim-Skolem teorema. También tengo ni idea de la segunda parte de la pregunta. Cualquier ayuda se agradece. Gracias

Answer 1

Creo que su argumento está bien, pero un poco más involucrado que tiene que ser.

Supongamos por contradicción que $\psi$ es una frase de la lógica de primer orden con no nonlogical símbolos, y que el finito de modelos de $\psi$ son precisamente los conjuntos finitos, incluso de la cardinalidad. Desde $\psi$ ha arbitrariamente grande finito de modelos, por compacidad $\psi$ tiene una infinita modelo de $\mathcal A.$ Desde $\neg\psi$ ha arbitrariamente grande finito de modelos, $\neg\psi$ tiene una infinita modelo de $\mathcal B.$ Pero esto contradice el hecho de que $\mathcal A$ $\mathcal B$ son elementarily equivalente. También, por el teorema de Löwenheim, se podría suponer que $\mathcal A$ $\mathcal B$ son countably infinito, por lo que son isomorfos.

La adición de un único símbolo de función $f$ no va a cambiar nada. Si tuviéramos una frase $\psi$ en este idioma expandido con la propiedad de que $(A,f)\vDash\psi\iff|A|\text{ is even},$, a continuación, en particular, esta equivalencia se mantenga para los modelos en los que $f$ es la función identidad. Claramente, entonces, podríamos escribir una frase en la pura teoría de la identidad que hace el mismo trabajo $\psi.$

Como André Nicolás de la respuesta de la muestra, el segundo ordende la frase $$\exists f\forall x[f(x)\ne x\wedge f(f(x))=x]$$ caracteriza a los conjuntos de incluso la cardinalidad.

Answer 2

Nos muestran que si nuestro lenguaje $L$ (entre tal vez otros símbolos) un único símbolo de función $f$, entonces no es una sentencia de $\varphi$ con las siguientes propiedades. (i) Para cada entero positivo incluso $n$ hay un $L$estructura $A$ cuyo conjunto subyacente tiene cardinalidad $n$ y en que $\varphi$ es verdadera y (ii) no Existe un entero positivo impar $n$ tal que $\varphi$ que es verdad en una estructura de cardinalidad $n$.

Por ejemplo, podemos dejar $\varphi$ ser la frase $$\forall x(\lnot(f(x)=x)\land (f(f(x))=x)).$$

Añadido: Ahora que se ha añadido que el lenguaje para la primera pregunta no tiene no-lógica de los símbolos, podemos hacer un par de comentarios. Lowenheim-Skolem no es necesario. Compacidad muestra que cualquier frase, $\varphi$ que es verdad en lo finito de conjuntos de la forma arbitraria de alta cardinalidad es cierto en todos los conjuntos.

Answer 3

La uniformidad es fundamentalmente una propiedad de finito de estructuras; hay maneras de extender a conjuntos infinitos, pero hay diferentes incompatible maneras de hacerlo. Por ejemplo, usted podría decir que el apoyo debe ser dividido en dos conjuntos que están en bijection, o se podría decir que es incluso si no puede ser dividido en dos sets en bijection y un singleton; estas dos definiciones caracterizar finito incluso estructuras, pero la primera en encontrar conjuntos infinitos a ser, incluso, pero no el segundo.

Si se limita a finito de estructuras, no se puede apelar a la compacidad o LS. Usted debe utilizar Ehrenfeucht–Fraïssé juegos. La idea es muy similar a lo que ya han hecho. Si 'hasta' puede ser expresada mediante una fórmula, esta fórmula debe tener algún cuantificador profundidad de $q$. Lo que significa que el Alerón debe de ganar alguno de los $k$-ronda de juego, para $k\geq q$, en dos estructuras donde uno es par y el otro no. Así que para demostrar que no es definible, debe exhibir una familia de pares de estructuras de $(M,M')_k$ que son equivalentes para $k$-juegos de ronda, sin embargo, $M$ es incluso y $M'$ no lo es.