Problema

(Fuente: "Matemáticas para la informática", Lehman, Leighton, Meyers, 2018).

En este problema examinaremos fórmulas de lógica de predicados donde el dominio del discurso es$\mathbb{N}$. Además de los símbolos lógicos, las fórmulas pueden contener símbolos de predicados ternarios$A$y$M$, dónde:

$A(k,m,n)$medio$k = m + n$

$M(k,m,n)$medio$k = mn$

Por ejemplo, una fórmula$Zero(n)$significa que$n$es cero podría definirse como

$Zero(n)=A(n,n,n)$

Habiendo definido$Zero$, ahora está bien usarlo en fórmulas posteriores. Entonces, una fórmula para$Greater(m,n)$significado$m > n$podría definirse como

$Greater(m,n) = \exists k \left( \neg \left( Zero(k) \right) \wedge A(m,n,k) \right)$

Esto hace que esté bien usar$Greater$en fórmulas posteriores.

$M(k,m,n)$medio$k = mn$

Escribir fórmulas de predicados usando solo los predicados permitidos$A$,$M$que definen los siguientes predicados:

(a)$Equal(m,n)$significa que$m = n$.

(b)$One(n)$significa que$n = 1$.

(C)$n = i(m \cdot j + k^2)$.

(d)$Prime(p)$significado$p$es un número primo.

(mi)$Two(n)$significa que$n = 2$.

(F)$Even(n)$significado$n$incluso.

(g) (Conjetura de Goldbach) Todo entero$n \geq 4$puede expresarse como la suma de dos números primos.

(h) (Último teorema de Fermat) Supongamos ahora que también tenemos

$X(k,m,n)$medio$k = m^n$

Exprese la afirmación de que no hay soluciones enteras positivas para la ecuación:

$x^n + y^n = z^n$

cuando$n > 2$.

(i) (Conjetura de los primos gemelos) Hay infinitos números primos que difieren en dos.

Intento de solución

Intentos para cada elemento:

( Nota : como defino predicados en cada elemento, puedo reutilizarlos en elementos posteriores).

a) Desde$m=n$si y solo si$m \leq n$y$n \leq m$:

$Equal(m,n) = \left( \neg Greater(m,n) \right) \wedge \left( \neg Greater(n,m) \right)$

b) Cualquier número natural$n$multiplicado por 1 es igual a$n$, entonces:

$One(n) = \forall k \left(M(k,n,k)\right)$

c) Lo que he intentado aquí es desglosar la expresión de la siguiente manera:$n = i \cdot x_1$para algunos$x_1$,$x_1 = (x_2 + x_3)$para algunos$x_2$y algo$x_3$,$x_2 = (m \cdot j)$para algunos$m$y algo$j$, y$x_3 = k^2$. Entonces el intento se convierte en:

$C(n) = \exists i \exists x_1 \exists x_2 \exists x_3 \exists j \exists k \left(M(n,i,x_1) \wedge A(x_1,x_2,x_3) \wedge M(x_2,m,j) \wedge M(x_3,k,k)\right)$

d) Hay dos formas que parecen funcionar:

$Prime(p) = \forall a \forall i (One(a) \rightarrow \left( \neg Equal(i,a) \wedge \neg Equal(i,p) \rightarrow \neg \exists k \left( M(p,i,k) \right) \right)$

$Prime(p) = \forall i \exists a (One(a) \wedge \left( \neg Equal(i,a) \wedge \neg Equal(i,p) \rightarrow \neg \exists k \left( M(p,i,k) \right) \right)$

e) Hay dos formas en las que pensé que parecen funcionar para esta, basadas en el hecho de que 2 = 1 + 1:

$Two(n) = \exists k \left( One(k) \wedge A(n,k,k) \right)$

$Two(n) = \forall k \left( One(k) \rightarrow A(n,k,k) \right)$

F)$Even(n) = \exists a \exists b \left( Two(a) \wedge M(n,a,b) \right)$

La idea es que, si existen$a$yb tal que$a$es el número 2, y$n = ab$, entonces$n$incluso.

gramo)$\forall n \forall a \left( Four(a) \wedge \left(Greater(n,a) \lor Equal(n,a)\right) \wedge Even(n) \rightarrow \exists p_1p_2\left( Prime(p_1) \wedge Prime(p_2) \wedge A(n,p_1,p_2) \right ) \right)$

h)$\forall n \forall a \left( Two(a) \wedge Greater(n,a) \rightarrow \left( \neg \exists x,y,z,x_n,y_n,z_n \left ( X(x_n,x,n) \wedge X(y_n, y, n) \wedge X(z_n, z, n) \wedge A(z_n,x_n,y_n) \right ) \right ) \right)$

i) Primero, defina un predicado que pruebe si dos números$m$y$n$son primos gemelos comprobando que son primos y se diferencian en 2:

$TwinPrime(m,n) = Prime(m) \wedge Prime(n) \wedge \exists t \left( Two(t) \wedge \left( A(q,n,t) \lor A(n,q,t) \right) \right )$

Entonces, la conjetura podría expresarse de la siguiente manera:

$\left( \exists n,m \left( TwinPrime(n,m) \right) \right) \wedge (\forall n,m \left( TwinPrime(n,m) \rightarrow \exists q,p \left ( Greater(q,n) \wedge Greater(p,m) \wedge TwinPrime(q,p) \right ) \right ) )$

Como un intento de expresar que hay infinitos primos gemelos, estoy afirmando dos cosas: (1) existen dos números que son primos gemelos, (2) si hay dos números$m,n$que son primos gemelos, entonces hay dos números$p,q$que son mayores que$m,n$y también son primos gemelos.

¿Podría alguien verificar si estos intentos tienen sentido? Gracias de antemano.