MATH0037
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
MATH0037
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 {ϕ, ψ, (-θ)} F χ then F (ϕ - (ψ - (θ 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
θ脯 = Vx( g . . . g x = x) ?
`_
脯 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; Rx ) satisfies ϕ if and only if Rx 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 (Z; {(n, n + 1)}) . Write a sentence that is satisfied by both.
(iii) Write a sentence in the language of rings that is satisfied by Z and not by M2 (Z), 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 , . . . , c脯 , 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)
2023-03-06