Reference no: EM132409822

Mathematical Logic Questions -

1. First Order Formulas and Interpretations

We fix a signature

S = (f₁(·), f₂(· , ·), f₃(· , ·), R₁(· , ·), R₂(· , ·))

and consider the interpretation

I = (Z, x |→ x + 1, (x, y) |→ x · y, (x, y) |→ x + y, ≤, =).

(a) Translate the following formulas to English/Math:

φ₁ = (∀y(∀x(∃z(R₂(x, f₃(y, z))))))

φ₂ = (∃y(∀x(∀z(R₂(x, f₃(y, z))))))

φ₃ = (∃y(∀x(∃z(R₂(x, f₂(y, z))))))

φ₄ = (∀x(R₁(f₁(x), f₂(x, y))))

φ₅ = ((R₁(f₁(y), x)) → (R₁(f₂(y, y), f₂(x, x))))

(b) For each of the above formulas, state whether or not they are satisfied in interpretation I. For formulas that are not sentences (that is, have free variables) provide a valuation v such that I, v together satisfy the formula or argue that no such valuation exists.

(c) For each of the following sets of numbers, provide a formula that defines this set in interpretation I:

- The set that contains only the number 0.

- The set of integers that are the sum of two squares (an example is 25, since 25 = 3² + 4²).

2. Definability (and the Compactness Theorem)

We consider the signature

S = (f(·), P(·), EQ(· , ·))

where f is a function symbol, P is a one-place predicate and EQ a two place predicate. We will consider only interpretations where the predicate EQ is interpreted as equality.

Write a formula that defines the set of all interpretations of this signature, where the property P holds for all elements in the range of f. Give an example of such an interpretation.

Describe a set of formulas that defines the set of all interpretations of this signature where infinitely many elements have the property P. Give an example of such an interpretation.

Show that the set of all interpretations, where the property P holds only for finitely many elements of universe is not definable. Give an example of such an interpretation.

3. Halting Problem

Show that there is no algorithm H that takes the code of some program P and determines whether P halts and outputs "I will pass MATH1090!". That is, H should say

- loop, if P loops forever or doesn't output "I will pass MATH1090!"

- halt, if P halts and outputs "I will pass MATH1090!"

Reduce the original halting problem to this and explain your reduction!