Pregunta sobre la búsqueda de fórmulas en el cálculo de predicados

Question

Que un idioma $L=\{+,<\}$ . Sea $M$ sea la estructura $(\mathbb{Z},+,<)$ . Encontrar una fórmula $\phi[x]$ con $x$ es la única variable libre (por lo que puede utilizar otros símbolos como $\forall y$ etc.) tal que para cualquier $a \in \mathbb{Z}$ , $\phi[a]$ se cumple en $M$ sólo si $a-1$ es divisible por $3$ .

Inténtelo : Lo que creo es que $a-1$ es divisible por $3$ sólo si $a \equiv 1$ . Así que quiero poner algo como divide y luego obtener el resto $0<y<2$ pero esto no funciona ya que no se nos da la división. Eso es todo lo que se me ocurre. Agradecería cualquier pista. Gracias.

Answer 1

Para este tipo de cosas hay que deletrear lo que significa multiplicar por una constante como $3$ significa en términos de suma:

$$\phi(a) \equiv \exists i(i + i + i + 1 = a)$$

A menudo verá algo así abreviado como:

$$\phi(a) \equiv \exists i(3i + 1 = a)$$

donde se entiende que la multiplicación por una constante no es más que una abreviatura de la suma repetida: $3i = i + i + i$ .

Según tu comentario, estás trabajando sobre la firma que sólo tiene símbolos de función para $+$ y $<$ y ningún otro símbolo no lógico (cuento = como símbolo lógico). En este caso, es necesario introducir una definición local del número 1 en $\phi$ que puedes hacer de la siguiente manera:

$$ \phi(a) \equiv \exists z \cdot\exists e \cdot \exists i\cdot (z + z = z \land z < e \land (\forall j\cdot\lnot(z < j \land j < e)) \land 3i + e = a) $$

Aquí la fórmula $z + z = z$ actúa como definición de $z$ como $0$ . Entonces $z < e$ y $\forall j\cdot\lnot(z < j \land j < e)$ actuar como definición de $e$ como el menor número entero positivo, es decir, $1$ .

(Observe que en este ejemplo ni siquiera es necesario tomar = como símbolo lógico).

Answer 2

En primer lugar, tenga en cuenta que puede fijar $0$ como el único $y \in \mathbb{Z}$ tal que $x+y=x$ para todos $x \in \mathbb{Z}$ : $$\mathtt{zero}(y) \equiv \forall x(x+y=x)$$ A continuación, cada vez que desee escribir $\psi(0)$ escriba en su lugar $\forall y(\mathtt{zero}(y) \to \psi(y))$ etc.

También podemos precisar $1$ como el único $y \in \mathbb{Z}$ tal que $0<y$ y, para todos $x \in \mathbb{Z}$ si $0 < x$ entonces $y \le x$ . Así que $$\mathtt{one}(y) \equiv \forall z((\mathtt{zero}(z) \to z<y) \wedge \forall x (\forall z(\mathtt{zero}(z) \to z<x) \to w < x \vee w=x))$$ Por último, se puede concretar la operación "menos uno" de la siguiente manera: dado $n \in \mathbb{Z}$ toma el único $y$ tal que $y+1=n$ . Es decir $$\mathtt{minusone}(n;y) \equiv \forall z(\mathtt{one}(z) \to y+z=n)$$

Así que aquí tienes una frase en toda su crudeza describiendo lo que quieres: $$\forall y (\mathtt{minusone}(x;y) \to \exists z(y = (z+z)+z))$$