Problem 1 The divisibility predicate, the perfect square predicate, and the prime predicate, can

be defined as follows:

m|n

perfectSq(n)

prime(n)

def

def

def

true

false

true

false

true

false

if m is a divisor of n,

if m is not a divisor of n.

if there is m € N such that n = m²,

otherwise.

if n is a prime number > 2,

otherwise.

There are two parts:

(a) Show that perfect Sq: N→ {true, false) is first-order definable in the structure (N, I, +,0).

Hint: z = y²iff x + y = lcm(y, y + 1).

(b) Show that prime : N→ {true, false) is first-order definable in the structure (N, ], +,0).