Problem
(Source: "Mathematics for Computer Science", Lehman, Leighton, Meyers, 2018.)
In this problem we’ll examine predicate logic formulas where the domain of discourse is $\mathbb{N}$. In addition to the logical symbols, the formulas may contain ternary predicate symbols $A$ and $M$, where:
$A(k,m,n)$ means $k = m + n$
$M(k,m,n)$ means $k = mn$
For example, a formula $Zero(n)$ meaning that $n$ is zero could be defined as
$Zero(n)=A(n,n,n)$
Having defined $Zero$, it is now OK to use it in subsequent formulas. So a formula for $Greater(m,n)$ meaning $m > n$ could be defined as
$Greater(m,n) = \exists k \left( \neg \left( Zero(k) \right) \wedge A(m,n,k) \right)$
This makes it OK to use $Greater$ in subsequent formulas.
$M(k,m,n)$ means $k = mn$
Write predicate formulas using only the allowed predicates $A$, $M$ that define the following predicates:
(a) $Equal(m,n)$ meaning that $m = n$.
(b) $One(n)$ meaning that $n = 1$.
(c) $n = i(m \cdot j + k^2)$.
(d) $Prime(p)$ meaning $p$ is a prime number.
(e) $Two(n)$ meaning that $n = 2$.
(f) $Even(n)$ meaning $n$ is even.
(g) (Goldbach Conjecture) Every integer $n \geq 4$ can be expressed as the sum of two primes.
(h) (Fermat's Last Theorem) Now suppose we also have
$X(k,m,n)$ means $k = m^n$
Express the assertion that there are no positive integer solutions to the equation:
$x^n + y^n = z^n$
when $n > 2$.
(i) (Twin Prime Conjecture) There are infinitely many primes that differ by two.
Solution attempt
Attempts for each item:
(Note: As I define predicates in each item, I may reuse them in subsequent items.)
a) Since $m=n$ if and only if $m \leq n$ and $n \leq m$:
$Equal(m,n) = \left( \neg Greater(m,n) \right) \wedge \left( \neg Greater(n,m) \right)$
b) Any natural number $n$ multiplied by 1 is equal to $n$, so:
$One(n) = \forall k \left(M(k,n,k)\right)$
c) What I've attempted here is to break down the expression as follows: $n = i \cdot x_1$ for some $x_1$, $x_1 = (x_2 + x_3)$ for some $x_2$ and some $x_3$, $x_2 = (m \cdot j)$ for some $m$ and some $j$, and $x_3 = k^2$. So the attempt becomes:
$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) There are two ways that seem to work:
$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) There are two ways that I thought of that seem to work for this one, based on the fact that 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) $
The idea is that, if there exist $a$ and b such that $a$ is the number 2, and $n = ab$, then $n$ is even.
g) $\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) First, define a predicate that tests whether two numbers $m$ and $n$ are twin primes by checking that they are primes and they differ by 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 )$
Then, the conjecture could be expressed as below:
$\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 ) )$
As an attempt to express that there are infinitely many twin primes, I'm stating two things: (1) there exist two numbers that are twin primes, (2) if there are two numbers $m,n$ that are twin primes, then there are two numbers $p,q$ that are greater than $m,n$ and are also twin primes.
Could someone please verify if these attempts make sense? Thank you in advance.
Best Answer
Everything looks good!
Just a few nit-picks:
You never defined $Four(n)$ ... though that's easy:
$Four(n)=\exists a (Two(a) \land A(n,a,a))$
And yes, you always have a second option here:
$Four(n)=\forall a (Two(a) \to A(n,a,a))$
Also, your:
should be:
$TwinPrime(m,n) = Prime(m) \wedge Prime(n) \wedge \exists t \left( Two(t) \wedge \left( A(\color{red}m,n,t) \lor A(n,\color{red}m,t) \right) \right )$