
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
spaceconsuming 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.
