Exam comments (1)
Well, so far the news is not so great.
I might as well have not asked my questions 5.(d) about BL1 and
5.(e) about BL2. Only one or at most two people out of 46 did a good
job with either of those problems. I think no one did a good job
BL1 was the same as our system BL except that it had some unknown wff
A as a twelfth axiom. Otherwise the same axioms and two primary
inference rules as our system BL. I asked about soundness and
completeness of BL1. I gave 0 marks for just circling the label of
the right answer. People had to give GOOD explanations for the
right answer to get marks. I asked for a one-sentence explanation.
I'll give more than one sentence as explanation here, first, to make
sure that people understand. BL1 is still complete, but not
necessarily sound. Reason: Let B be a tautology. Then there is a
proof of B within BL, since BL is complete. But
a strict annotated Hilbert proof
within BL is precisely
a strict annotated Hilbert proof
within BL1 that never mentions A
as an axiom, in an annotation.
(I assume that A is not one of the 11 axioms already present in BL.
It would be pretty weird to list an axiom TWICE. But if we did,
then BL1 and BL would be THE SAME system, in which case BL1 is
sound and complete because BL is.)
So there is a proof of B within BL1.
BL1 would be sound if A were a BL-theorem (i.e., a tautology).
Clearly BL1 is not sound if A is not a tautology, since then
A is provable from the empty set in BL1 but is not a tautology.
OK. One-sentence explanation of why BL1 is complete but not
We may assume that A is not already an axiom of BL; then a
proof in BL is just a proof within BL1 which never mentions
A as an axiom, so anything provable in BL is provable in BL1,
so all tautologies are provable in BL1; if A is not a tautology
then BL1 is not sound.
BL2 was our system with one of our eleven axioms removed. BL2 is
sound. (I asked whether it is sound.) Reason: Suppose B is a
BL2-theorem; then there is a proof of B from the ten axioms of
BL2 using the two primary inference rules. But that proof is then
automatically also a proof of B in BL. So by soundness of BL,
B is a tautology; so, BL2 is sound.
Next piece of bad news. Problem 6:
I asked for a bullet proof that
|-- (ex. x)(A \/ B) == (ex. x)A \/ (ex. x) B.
I thought we had done enough such proofs of duals of theorems
about (\forall ) that people would be happy and just zip right
through this. The easy proof rewrites the first existential in
terms of universals, then 2.4.17' on the body and WL, then 6.1.7 to
split the universal into a conjunction of universals, then 2.4.18'
and definition of (exists ) again.
But no. While some people are giving this intended, very easy
proof, many are using 6.1.6, 6.5.3, etc. Even 6.5.6....
Those metatheorems do not say that one wff is syntactically
equivalent to another. They are provability statements.
You cannot just toss away quantifications or introduce them in a
string of biconditionals and give provability statements as your
reason. Look at this:
C \/ D
<==> < 6.5.3 >
(ex. x)C \/ (ex. x)D.
That is nonsense. 6.5.3 says that each of the existentials above
is PROVABLE FROM the corresponding wff in the first line. It doesn't
say that they are syntactically equivalent to them. That, in fact,
It is true that |-- C --> (ex. x)C -- one way to see this is
to use 6.5.3 and D.T. But --> is very different from ==. ...
People who jumped right in and used 6.1.6 (same comments about
6.1.6, by the way) and 6.5.3 ... and even 6.5.6... got very few
marks on Problem 6. Look at those metatheorems. They don't
have a single biconditional symbol triple-bar appearing
anywhere in them. So how do you justify a <==> with them??
What is true using 6.1.6 and 6.5.3 and D.T. twice is this:
(ex. x)(A \/ B)
not(forall x) not(A \/ B)
<== < contrapositive of "6.1.6 plus D.T." >
not not(A \/ B)
<==> < 2.4.4 >
A \/ B
==> < 6.5.3 plus D.T. plus a somewhat long argument
about disjunctions in conditionals >
(ex. x)A \/ (ex. x)B.
So the middle of this chain "syntactically implies"
both the beginning wff and end wff. But that is a
loooong way from saying that the first and last wff
in the above stack are syntactically equivalent....
That's like saying that "a less than or equal to b"
and "b greater than or equal to c" imply that a = c.
You folks surprised me with this.
If there is a free occurrence of x in a wff C, then
C is syntactically equivalent, in general, to NEITHER
of (forall x) C, (exists x) C. And 6.1.6, 6.5.3 do
not say anything about syntactic equivalence.
Third piece of bad news: The last problem, finding an
interpretation under which a 2-place predicate satisfying
a given wff interprets as true.
As usual, interpret the predicate as a binary relation,
in the sense of 1019 or 1190, on the domain D. The wff
interpreted as saying that
(1) everybody in D points to somebody in D,
(2) if a points to b and b points to c then a points to c,
(3) nobody points to himself.
One person got 6 marks out of 6 on this.
One got 2 out of 6.
The other 44 people got 0.
Here goes: D is nonempty because all universes of
discourse are, so has one element a1 in it. a1 has to point
to someone, and the someone cannot be a1. Let a1 point to
a2 must point to someone, and the someone is not a2. And
the someone also is not a1, because if a2 pointed to a1
then by (2) a1 would point to itself.
So a2 must point to a third guy, a3. So, by (2), a1 also
points to a3.
a3 must point to someone other than a3. But it cannot point
to a1 or a2 because then, by (2), a1 or a2 would point to
So a3 points to a fourth guy a4. By (2), a1 and a2 also
point to a4.
Here goes a sketch of an induction:
Let n be a positive integer, and suppose that we have
already found elements a1, ..., an in D, n of them,
such that each ai points to each aj with i < j.
an must point to someone in D. The someone
cannot be an itself, and cannot be any of
the guys we already listed because then by (2)
the guy listed would also point to itself. So an
must point to an (n+1)st guy a_(n+1) in D. And
then all of the guys we just listed also point to the
new one, by (2).
OK. So a domain D in which the predicate interprets as
true must be infinite. And there is an obvious candidate
for D, given the above discussion:
Let D be ZZ , the set of positive integers, and let
a point to b iff a < b. Then 1 points to everyone
else, 2 points to everyone except 1 and 2, etc. This
interpretation "works", because every positive integer
is less than itself plus 1, no pos. integer is less than
itself, and "less than" is transitive. In some sense,
this is the "smallest" interpretation in which the given
wff interprets as true, as one sees easily by the above
Not difficult. Just think. And persist. 44 zeroes.
Fourth piece of bad news:
Very few of you got 4 out of 4 on the simple
"substitutions" problem. The first substitution was
undefined, the second and third produced no change in
the wffs in which the substitutions were made, and
the fourth double substitution yielded (w = w).
Very easy. You folks don't know the substitution rules.
Many scores of 0, 1 or 2 out of 4. Maybe six or so
people out of 44 got perfect 4 scores.