Let C be a set, and A and B be disjoint sets. Find a bijection h: C A × C B ? C A?B, and show that it is well-defined, injective, and surjective. (b) Denote by |X| the cardinality of a set X. (i) Let A, B, C, and D be sets such that |A| = |B| and |C| = |D|. Prove that |A C | = |B D| . (ii) Find a pair of sets A and B so that |A| < |b|,="" but="" |an="" |="|BN" |.="" find="" an="" example="" where="" b="" is="" countably="" infinite.="" (no="" proof="" is="" necessary.)="" (iii)="" find="" two="" different="" explicit="" bijections="" f,="" g="" :="" 5n="" 2="" n="" .="" by="" explicit,="" i="" mean="" recipes="" for="" converting="" elements="" of="" 5n="" into="" elements="" of="" 2n="" .="" explain="" your="" answer="" graphically="" in="" terms="" of="" the="" trees="" for="" 2n="" and="">
Mathematical logic - 2021 Sample Exam 1. (a) Let C be a set, and A and B be disjoint sets. Find a bijection h : CA × CB → CA∪B, and show that it is well-defined, injective, and surjective. (b) Denote by |X| the cardinality of a set X. (i) Let A, B, C, and D be sets such that |A| = |B| and |C| = |D|. Prove that |AC | = |BD| . (ii) Find a pair of sets A and B so that |A| < |b|,="" but="" |an|="|BN|." find="" an="" example="" where="" b="" is="" countably="" infinite.="" (no="" proof="" is="" necessary.)="" (iii)="" find="" two="" different="" explicit="" bijections="" f,="" g="" :="" 5n="" →="" 2n.="" by="" ex-="" plicit,="" i="" mean="" recipes="" for="" converting="" elements="" of="" 5n="" into="" el-="" ements="" of="" 2n.="" explain="" your="" answer="" graphically="" in="" terms="" of="" the="" trees="" for="" 2n="" and="" 5n.="" 1="" sa="" m="" ple="" 2.="" let="" ϕ="" be="" the="" following="" sentence="" in="" a="" first-order="" language="" with="" one="" one-="" place="" function="" symbol="" f="" :="" ϕ="((∀x∃y(x" =="" fy))="" ∧="" (∀x∀y(fx="fy" →="" x="y)))" (i)="" give="" a="" short="" explanation="" of="" what="" it="" means="" for="" a="" structure="" to="" satisfy="" the="" sentence="" ϕ="" above.="" (ii)="" show="" that="" there="" are="" uncountably="" many="" different="" isomorphism="" types="" of="" countable="" structures="" which="" satisfy="" ϕ.="" (iii)="" for="" each="" n=""> 0, let ψn be the sentence ∀x(¬(x = f · · · f︸ ︷︷ ︸ n times x)) Show that there are only countably many different isomorphism types of countable structures which satisfy both ϕ and ψn for all n > 0. 2 Sa m ple 3. (a) Consider the set of propositions PROP using only the logical con- nectives → and ¬. Define what it means for a map v : PROP → {0, 1} to be a valuation. Define what it means for a proposition ϕ to be satisfiable. (b) Show that if {α, γ1} � χ and {β, γ2} � χ then {(α∨β), γ1, γ2} � χ. (c) Suppose that Γ is a set of propositions. Show that if Γ � ϕ then there is a finite subset Γ′ ⊆ Γ such that Γ′ � ϕ. (d) Let X be a countably infinite set. (i) Find a set of propositional variables VAR and a bijection f : 2VAR → {(A,B,R) | A,B ⊆ X,R ⊆ X2} . (ii) Find a set of propositions Γ so that V (Γ) = {v | v(ϕ) = 1 for all ϕ ∈ Γ} corresponds to P = {(A,B,R) | A,B ⊆ X,R ⊆ ((A∩B)×(A∪B))∪((A∪B)×(A∩B))} under the bijection f . You must prove that f(V (Γ)) = P . 4. (a) Define what it means for a set of propositions to be consistent. Show that the set {a, (¬b), (a→ b)} is inconsistent. (b) Find a set Γ = {ϕ1, ϕ2, ϕ3, ϕ4} consisting of four propositions so that Γ is inconsistent and any proper subset of Γ is consistent. Give a natural deduction proof that Γ is inconsistent, illustrate this proof with a Venn diagram involving the sets V (ϕi), and also prove that {ϕ1, ϕ2, ϕ3} is consistent. (c) Give natural deduction proofs of the following: (i) {α→ (¬β → γ), α→ (¬β → ¬γ)} ` α→ β (ii) {(α→ ¬β)→ (γ → α),¬β, γ → (α→ δ)} ` γ → δ 3 Sa m ple 5. (a) Let L be a first-order language with one two-place predicate sym- bol P . Write an L sentence ϕ so that 〈{a, b}; {(a, a), (b, b)}〉 � ϕ and 〈{a, b}; {(a, a), (b, a)}〉 6� ϕ . (b) Let ϕ be the sentence ∃x(f(f(x))) 6= f(x)). For each of the follow- ing sentences, explain if it is satisfiable or not. If it is satisfiable, find a structure which satisfies it, and if not, explain why it is unsatisfiable. (i) ϕ ∧ (∃y∀xf(x) = y) (ii) ϕ ∧ (∀x∃yf(x) = y) (iii) ϕ ∧ (∃y∀xf(y) = x) (iv) ϕ ∧ (∀x∃yf(y) = x) (c) Consider the structure X = 〈N; fX , 0N〉 where fX is the function defined by fX (n) = n+ 1. (i) Show that Γ = Th(X ) ∪ {(x 6= f · · · f︸ ︷︷ ︸ n times 0} is satisfiable. (ii) Give an example of a structure Y and a substitution s so that Y � Γ [s]. 4 Sa m ple