Answer all questions .

1.

(i)  Let f : X - Y be a function, and let F : 2Y  - 2X  be defined by F (g) = g 。f . Show that:

(a)  if f is surjective then F is injective.

(b)  if f is injective then F is surjective.

(ii)  Denote by |X| the cardinality of a set X .

(a)  Find a pair of sets A and B so that |A × B| = |AB | and |AB | < |BA |. Justify the second inequality.

(b)  Find an explicit bijection f : 7.  - 3. .

(20 marks)

2.

(i)  Show that if {ϕ, ψ, (-θ)} N χ then N (ϕ - (ψ - (θ V χ))).

(ii)  Find a set Γ consisting of four propositions so that Γ is unsatisfiable and any

proper subset of Γ is satisfiable.

(iii)  Let X be a countably infinite set.

(a) Write down a suitable set of propositional variables, a set Γ of propo- sitions in those variables, and a bijection f from the set of valuations satisfying Γ to the set of graphs with vertex set X .

(b)  Define what it means for a graph with vertex set X to be connected. Is there a set of propositions containing Γ that is satisfied by a valuation v if and only f (v) is connected? Justify your answer.

(20 marks)

3.

(i)  Let ϕ be the following sentence in a first-order language with one one-place function symbol g and two one-place relation symbols U and T:

Vx((Ux V Tx) A (-(Ux A Tx)))

(a)  Give an example of a structure satisfying ϕ .

(b)  Let ψ be the the following sentence

VxVy(gx = y - ((Tx - Uy) A (Ux - Ty))) .

For which n are there two non-isomorphic structures that satisfy ϕ , ψ , and the sentence

θn  = Vx( g . . . g x = x) ?

`╱

n  times

Justify your answer.

(ii) Write down a first-order formula ϕ in a language with one two-place relation symbol R such that x = (X; R疋 ) satisfies ϕ if and only if R疋  is not the graph of a function f : X - X .

(15 marks)

4.

(i)  Show that -(-a V b) 上 (a A -b).

(ii) Is {a V b, a - c, b - c, -c} consistent?

(iii)  Show that if Γ u ϕ 上 1 then Γ 上 (ϕ - ψ).

(iv)  Show that (-ϕ V ψ) 上 (ϕ - ψ).

(20 marks)

5.

(i)  Let c be a first order language. Define what it means for two c–structures to be elementarily equivalent.

(ii) Write a sentence in the language of directed graphs that is satisfied by the graph ({1, 2, 3}; {(1, 2), (2, 3)}) and not by (勿; {(n, n + 1)}) . Write a sentence that is satisfied by both.

(iii) Write a sentence in the language of rings that is satisfied by 勿 and not by M2 (勿), the ring of two-by-two matrices with integral entries.   Justify your answer.

(iv)  Let c be the language of groups with additional constant symbols c1 , . . . , cn , and let G be a countably infinite c–structure with the property that G is generated by {ci(G)}. Show that G is elementarily equivalent to a group H that contains G as a proper subgroup.

(25 marks)