Assignment 5: solutions, marking scheme, etc. Problem 1: The wff is not a universally valid formula. Interpret φ as the empty directed graph on the vertices 5 and 19 -- nobody points to anybody -- no directed edges. What is true is that in any directed graph which is symmetric and transitive (the conditions in the antecedent of the given conditional), any vertex which is not "isolated", i.e., which points to somebody or to which somebody points, points to itself. So: Just take a directed graph in which all nodes are isolated. Problem 3: (a) D = {17, 43}, directed graph { (17, 43), (43, 17) } with vertex set D. 17 points to 43 and vice versa. (b) Same D, directed graph { (17, 17), (17, 43) }. (c) A domain D of size 1 or 2 does not work -- convince yourself of this. But if D = { 17, 19, 43} then directed graph { (17, 43), (43, 19), (19, 17) } works. Total marks for the second part of this assignment: 48, I think. I told the grader not to grade the last problem. It is similar to one or two earlier problems on the assignment. Problem 4: At the start of predicate logic, we said that our favourite letters for object variables were u through z. So u and v are different object variables. If one interprets φ as a directed graph (a binary relation on the universe, or domain, D, then the wff says "If everybody in D points to everybody in D, then everybody points to itself." That is certainly a true statement. So by Completeness the given wff is a theorem. Here's one proof of it (I was too lazy to do HTML for φ, so it is \phi below): (1) (\forall u)(\forall v) \phi(u,v) < hyp > (2) (\forall v) \phi(u,v) < (1), Spec spec > (3) \phi(u,v) < (2), Spec spec > (4) (\forall u) \phi(u,v) < (3), 6.1.1 (i.e., gen), since u dnof in the wff in line 1 > (5) \phi(v,v) < (4), Spec (i.e., 6.1.5), with the term t being v > (6) (\forall v) \phi(v,v) < (5), 6.1.1, since v dnof in the guy in line (1) > One can also prove line (6) by starting with a Dummy Renaming (6.4.4) for v (say, replace v by w) right at the start, then do spec, replacing u by v, then a second spec, replacing w by v. Grader: Please do up a marking scheme for 9 marks for a proof using 6.4.4 as above. The 6.4.4 step is the big one, and lots of marks should attach to giving correct "dno" stipulations -- or, in the case of 6.4.4, making it clear that the student knows that it (the student) must satisfy "dno" conditions with its choice of new dummy. For the first proof I gave above, give 1 mark for each of the first three lines, 3 marks for line 4 (with 2 of the 3 marks for citing the dnof condition and saying exactly WHICH wff it is important that u not occur freely in), 1 mark for line 5, and 2 marks for line 6, with one of those marks being for stating the right dnof condition (again the wff in line 1 is the crucial one). Problem 5 (7 marks total): First some semantic discussion, on the next dozen lines or so. Actual proof below that. Unfortunately, the bullet proof goes so fast that one has no time to stop and think semantically, to wonder why the wff involved here is universally valid, is an absolute truth. I thought about it for several minutes, saying things to myself like C does not care who "y" is. So, if, for all elements then, if there is a particular a of the domain, a in the domain such that D(a) D(a) implies C, holds, then C holds. And, conversely, if the existence of a then, since C doesn't care particular a in the domain which a made D(a) hold*, it is such that D(a) holds the case that for all b in the implies that C holds, domain, if D(b) holds then C holds. *Footnote: y dnof in C. I don't claim that the above discussion should totally convince anyone that the given wff is an absolute truth, but it goes some of the way to making it seem plausible that it is. I don't have time to think it out better myself and explain better here. Proof: One can start with the left side and work toward the right, or vice versa, or write down the whole wff and a string of syntactic equivalences, until a theorem emerges. (\exists y)D --> C <==> < 2.4.11, defn. of \exists (but not necessary to mention "definition of \exists" in an annotation > ¬¬ (\forall y) ¬ D \/ C <==> < 2.4.4 > (\forall y) ¬ D \/ C <==> < 6.4.2 -- y dnof in C > (\forall y) (¬ D \/ C) <==> < 2.4.11, WL > (\forall y) (D --> C). // 1 mark for each mention of 2.4.11 (so, total of 2 marks there) 1 mark for 6.4.2 2 marks for mentioning that y dnof in C, when using 6.4.2 1 mark for mentioning WL in the last step above. 1 mark for 2.4.4 Problem 6 (8 marks): The reason in line (1) is "ass" or "hyp", for "assumption" or "hypothesis". 1 mark The reason in line (2) is Ax6. 1 mark The wff A in the above instance of Ax6 is v = x, 1 mark where x is an object variable different from v. 1 mark (What's important here is that boldx be chosen to be DIFFERERENT FROM boldv. If the student says that boldx is "fresh", that is not good enough, and gets no mark. If it (the student, she or he) says that "boldx is fresh with respect to A", that also is not enough, unless it has stipulated somewhere in the assignment paper, maybe at the beginning of the paper, that "being fresh w.r.t. a wff B" means "not occurring in B". If that is stated somewhere, then the student gets this mark.) The reason in line (3) is now M.P., with a reference to lines (1) and (2). 2 marks, 1 for M.P., 1 for mentioning lines (1) and (2). Now lines (4), (5) should be (4) boldv = boldv < Ax5 > 1 mark for this (5) v = u < (3), (4), Eqn > 1 mark Problem 7 (10 marks): Pretend that u, v, w, and z below are bold. It is too time- and space-consuming to type the HTML for bold. (1) u=v /\ v=w < ass > 1 mark (2) u=v < (1), splitting, or 2.5.1 or 2.5.2 > (3) v=w < same > 1 mark each for these two lines. 1.5/2 if "(1)" is not mentioned. (4) u=v --> (u=w == v=w) < Pick a variable boldz which is different from w. Then let A be boldz = w, and substitute on boldz. This then is an instance of Ax6. > 3 marks for this annotation, broken down as in the similar step in problem 3 (5) u=w == v=w < (2), (4), M.P. > 1 mark for line numbers, 1 mark for M.P. (6) u=w < (5), (3), Eqn > 1 mark So, by the D.T., |-- (u=v /\ v=w) --> u=w. 1 mark Actually, the way to use 2.5.2 would be to put lines 2 and 3 above as lines 1 and 2, do the rest of the proof as above, then conclude at the end from 2.5.2 that u=w is also provable from the conjunction of the equations above in lines 2, 3. But I have been sloppy with the numbering of 2.5.1, 2.5.2, so accept either number, please, grader. Or just "splitting". Max. mark: 10 Problem 8: Probably easiest is to use a fact which I proved before here in another file. Fact (all for one, and one for all): Suppose that x dnof in C. Then |-- (\forall x)C == C. Now for the required bullet proof: Suppose that x dnof in A. Then (\exists x)(B --> A) is ¬(\forall x) ¬(B --> A) <==> < 2.4.11, 2.4.17', 2.4.4, WL > ¬(\forall x)(B /\ ¬ A) <==> < 6.1.7 > ¬( (\forall x)B /\ (\forall x)¬A ) <==> < 2.4.18' > ¬(\forall x)B \/ ¬(\forall x)¬A <==> < the "Fact" above, since x dnof in ¬A; then 2.4.4 > ¬(\forall x)B \/ A <==> < 2.4.11 > (\forall x)B --> A. // Problem 9: I posted two solutions for this recently, in Bulletin 3.