Write the predicate formulas for the given predicates

[favq]

Homework Statement

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.

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.

Relevant Equations

$A(k,m,n)$ means $k = m + n$
$M(k,m,n)$ means $k = mn$

Attempts for each item:

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 exists a and b such that a is the number 2, and n = a*b, then n is even.

g) My attempt:

$\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, 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?

 

[LightHero]

Yes, your attempts make sense. They look good and capture the conditions that you are trying to express in each item.