Mathematics-Computer Science 4215H Mathematical Logic Trent University, Winter 2021
Assignment #8 Due on Friday, 19 March.
Do all of the following problems, all of which are straight out of the textbook0 (which explains the numbering), reproduced here for your convenience.
6.6. [Problem 6.6] Q = (Q,<) is a structure for LO. For each of the following formulas ? of LO, determine whether or not Q |= ?. (1) ?v0 ?v2 v0 < v2 [1] (3) ?v4 ?v5 ?v6(v4 < v5 ? (v5 < v6 ? v4 < v6)) [1] 6.7. [Lemma 6.7] Suppose M is a structure for L, t is a term of L, and r and s are assignments for M such that r(x) = s(x) for every variable x which occurs in t. Then r(t) = s(t). [2] 6.8. [Proposition 6.8] Suppose M is a structure for L, ? is a formula of L, and r and s are assignments for M such that r(x) = s(x) for every variable x which occurs free in ?. Then M |= ?[r] if and only if M |= ?[s]. [4] 6.9. [Corollary 6.9] Suppose M is a structure for L and ? is a sentence of L. Then M |= ? if and only if there is some assignment s : V ? |M| for M such that M |= ?[s]. [2] 6.10. [Proposition 6.10] Suppose ? and ? are formulas of some first-order language. Then { (? ? ?), ?} |= ?. [3] 6.11. [Proposition 6.11] Suppose ? is a set of formulas and ? and ? are formulas of some first-order language. Then ? ? {?} |= ? if and only if ? |= (? ? ?). [2] [Total = 15]
Recent Comments