Expresando una oración lógica de primer orden que requiere contar

Question

Dado el conjunto$ R(x,t)= \{ (a, 1), (b, 1), (c, 1), (a, 2), (b, 2) \}$. ¿Cómo puedo expresar con una oración lógica de primer orden "si para$t$ la cantidad de tuplas$(x, t)$ es igual a$d$, entonces para$t+1$ la cantidad de tuplas$(x,t+1)$ es igual a$d$,$d+1$ o$d-1$?

Por ejemplo, en$t=1$,$d=3$ así que en$t=2$$d$ debería ser$2, 3$ o$1$.

Answer 1

Digamos que estamos tratando de expresar "existen exactamente dos$x$ tal que$\phi(x)$".

1. Necesitamos decir que hay dos cosas,$x_1$ y$x_2$, que satisfacen$\phi$.
2. $x_1$ y$x_2$ deben ser distintos.
3. $x_1$ y$x_2$ deberían ser los únicos elementos que satisfacen$\phi$. Es decir, para cualquier otra cosa$y$ que satisfaga$\phi$,$y$ debe ser igual a$x_1$ o$x_2$.

$\exists x_1\,\exists x_2\, \phi(x_1)\land\phi(x_2)\land(x_1\neq x_2)\land(\forall y\,\phi(y)\rightarrow (y = x_1 \lor y = x_2))$

Ahora, ¿puede generalizar "existe exactamente$n$"?

Answer 2

Como André Nicolas dijo, si usted no tiene ningún límite en $d$, entonces usted no puede expresar "$A$ tiene más de un elemento de $B$" en la lógica de primer orden. André sugiere agregar formal de la teoría de números para la lógica de primer orden, y este hecho va a trabajar. Otra posibilidad es ir un poco más allá de la lógica de primer orden, lo que permite a uno existencial de segundo orden cuantificador. A continuación, puede formalizar "hay un $a\in A$ y hay una función de $f$ que es un bijection entre el$A-\{a\}$$B$." Alternativamente (como $d$ es finito) se puede obtener con un único universal de segundo orden cuantificador, diciendo: "Por cada uno-a-uno la función $f$ cuyo dominio es un subconjunto $B'$ $B$ y cuya imagen es un subconjunto $A'$$A$, el rango no es de todos los de $A$ y, además, si el dominio es todos los de $B$ , en el rango son todos los de $A$, excepto para exactamente un elemento." Es desagradablemente largo, pero probablemente aún más fácil que la incorporación de una gran cantidad de teoría de números.

Answer 3

Si tenemos una explícita límite superior para $d$, como es el caso en este ejemplo, no hay ningún problema. Así, por ejemplo, en el lenguaje de la primaria de la teoría de grafos, se puede decir que existe un camino de longitud $\le 17$ unirse a cualquiera de los dos puntos.

Supongamos ahora que no hay tal enlazado. Entonces, en general, no se puede hacer sin necesidad de ampliar el lenguaje y la teoría para incluir un fragmento importante de la educación formal de la teoría de números, ya que las sentencias no pueden ser de longitud variable.

Hay soluciones parciales. Por ejemplo, en el lenguaje de la primaria de la teoría de campo, se puede, mediante la adición de una infinita cantidad de oraciones, de producir una teoría en la que todos los modelos son algebraicamente cerrado. Pero uno no puede hacer con una sola frase (o, equivalentemente, un conjunto finito de oraciones).