Reference no: EM131805411

Mathematical Logic

This coursework is worth 5 percent of the module. There will be no assessed coursework for the Mastery material. The deadline for handing in the work is 1600 on Tuesday 5 December 2017.

Question [1] Let L = be a language with equality and: a 2-ary function symbol m and a constant symbol e .

(i) Write down the axioms for groups as a single closed formula γ in this language.

(ii) For the following groups A₁, . . . , A₅ (which you should regard as normal models of your formula γ from (i)), find closed L= -formulas φ1, . . . , φ5 such that for all i, j ∈ {1, . . . , 5} :

A_i |= φ_j ⇔ i = j.
A₁ = (Q(√-1) {0} ;)
A₂ = (Z; +)
A₃ = (Q; +)
A₄ is the group of 2 x 2 invertible matrices over Q (under multiplication)

A₅ is the group of 2 x 2 invertible matrices of determinant 1 over Q . (Note that some of these are written additively.)

Justify your answers.

Question [2] Suppose L is a first-order language and φ(x₁) is an L -formula. Suppose: (a) x₂ is a variable free for x₁ in φ ; and (b) x₂ is not free in φ .

(i) Prove carefully that |-_KL ((∀x₁)φ(x₁) → (∀x₂)φ(x₂)) , where φ(x₂) is the result of substi- tuting x2 for all free occurrences of x₁ in φ(x₁) .

(ii) Give examples to show that, if either of the conditions (a), (b) is removed, then the result stated in (i) need not be true.

Question [3] Let L= be a language (with equality) for rings with an ordering, having binary function symbols + , • , constant symbols 0, 1 and a 2 -ary relation symbol ≤ . Consider the real numbers as an L= -structure

R = (R; +, •, 0, 1, ≤)

in the usual way. Let Σ consist of the set of closed L= -formulas φ with R |= φ .

Suppose that K is an L= -structure (with domain K ) which is a normal model of Σ .

(i) Show that is a field and for all a K with a > 0 and positive integers n we have that
na > 0 (where na is a + a + . . . + a , n times).
(ii) Show that if a > 0 there is b ∈ K with b² = a .
(iii) Prove that there exists such a structure and an element c K such that for all positive natural numbers n , we have 0 < nc < 1 .

[Hint: Extend the language by an extra constant symbol and use a compactness argument.]

Question [4] (i) Suppose A is a set of subsets of some countable set X with the property that if A, B ∈ A , then either A = B or A ∩ B = ∅ . Prove that A is countable.

(ii) Give an example of such an A where A and the sets in A are infinite.

(iii) Does the result in (i) remain true if we assume only that A ∩ B is finite for distinct A, B ∈ A ?