Do any three of the following problems ( prove any three)
1. Prove that the following axiomatic system is recursive:
a. x + (y + z) = (x + y) + z
b. x + 0 = x and 0 + x = x
c. For all x, exists y such that x + y = 0 and y + x = 0
d. For all x and y, x + y = y + x
e. For all x, x neq 0 implies nx neq 0
f. For all x, exists y such that ny = x
(Recall that nx has nothing to do with multiplication, it's a short cut for writing the addition of x with itself n-times.)
(Recall that an axiomatic system is recursive if given any concatenation of symbols, it can be checked in a finite number of steps if that concatenation corresponds to an axiom or not. Think of an algorithm to do so; how can a computer do it?)
2. Prove that the statement "x is the Godel number of a true statement" is not expressible in the language of the system that is consistent.
(Guideline for the proof: if it was expressible, it's negation will be expressible "x is not the Godel number of a true statement", then... use the auto-reference method.)
3. Prove the following statement: If every integer n > 4 is the sum of two odd primes, then every odd integer m > 8 is the sum of three odd primes.
4. Prove that for any natural number n, 8 | 5^n + 2(3^(n-1)) + 1