Bulletin 3: Some sketches of solutions
(Three of you got in-person explanations of the solution
below from me on Monday or Tuesday; you can look quickly at
what is below or not, as you like.)
Problem 9 on Assignment 5:
Look through the list of axioms and theorems, etc. for
predicate logic (I don't anticipate any changes in this
sheet, by the way; what you had at Test 2 is what you will
have at the exam).
Only TWO of them have anything to do with the symbol =
in predicate logic. So you know you'll have to use one
and maybe both of them to do problem 9.
Actually I think one needs both of them. My suggestion is
to use Ax 6 with a suitable wff A. The key to a proof is
finding the right wff A. I suggest an atomic wff A
(no boolean connectives, i.e., complexity 0), in fact, an
Note that if the wff given
in problem 9 is a theorem, then by Spec spec the conditional in
its body is also a theorem. And if that wff is a theorem then it can
be proven from the empty set of assumptions, so that by 6.1.1 its
universal qtfcn., the wff given in problem 9, is also a theorem.
So it is enough to prove the conditional which is the body of the
given wff. I suggest a pf. using the D.T.
Then your Hilbert proof would begin
(1) x = f(x) < ass >
Take x as t and f(x) as s in Ax 6 now. The job now is
to think of an appropriate wff A to use in our instance of Ax 6.
Then after writing that instance in line (2), we have
(3) A[w:= x] == A[w:= f(x)] < (1), (2), M.P. >
Now the goal should be to choose A so that the left side of (3)
is a well-known theorem and the right side is what we want -- the
consequent of the conditional discussed in the paragraph above,
f(x) = f(f(x)). If you want to think about this for a while, do so.
I will suggest two different wffs A that work, about 60 lines down
from the rest of this file. You can also just scroll there
immediately to check that my A works.
After finding such an A, mention that one side is a theorem --
write it in line (4), stating somehow that it is a theorem, in
the annotation to that line, and either giving a reference for
it (we proved this in class, or "something just like this" was
on assignment 3 -- but in general beware of doing things like
this on the exam -- sometimes I want you to prove again things
we already proved...) or proving it in a separate Lemma outside the
Hilbert proof. Then conclude by Equanimity that our desired
consequent is also a theorem, in line (5) or so. Then cite
D.T., then put the (forall x) on, using 6.1.1.
Exercise 1 on p. 187:
One way, which uses 6.5.6:
Begin with two assumptions, in the usual way when one wants to
prove a "repeated conditional" U --> (V --> W) by the D.T.
Put U in line (1) and V in line (2).
In line (3) eliminate the (forall x) in one of the assumptions
by Spec spec.
In line (4) you could write A, with a suitable
annotation pointing to line (2), involving 6.5.6.
Annotate as I did in class and as GT does in similar
steps in proofs which use 6.5.6. And draw the right
conclusion at the end of such a Hilb. pr., as GT does
in similar pfs. in his book. (We did one in class, and I
suggested several days ago reading two others in GT.) I
leave the rest of what you must do in such a proof to you.
Another way: Rewrite the consequent of the given
conditional as what it really is without the \exists
quantifiers (write out what the given consequent really
abbreviates). GT must have had this proof in mind, given
the Hint he gives at the end of exercise 1.
Do a Lemma or so, proving that
|-- U --> V == notV --> notU;
you should know this as "contrapositive" from a course
taken before 1090. A proof via 2.4.11 and 2.4.4 is very
short and easy.
That gives you a wff synt. equiv. to the
(ex. x)A --> (ex. x)B
we began with, which looks just like the right side of Ax 3,
which is closely related to your assumption in line (1). Figure
out the rest yourself.
This way avoids 6.5.6.
Let A be (f(x) = f(z)). Let z be the variable substituted for,
in Ax 6. With our t and s in the discussion above, we get
as the consequent of Ax 6 in this case
(f(x) = f(x)) == (f(x) = f(f(x))). :^D
Note that if the atomic wff A above is thought of as a
wall of a house with a window in it, into which can be put
any term, just by substitution for z, then the left and right
sides of the above biconditiional are that wall with the
window filled with our terms t and s, respectively, from
line (1) of our proof.
We proved that |-- (term = same term) in class, or at
least proved that |-- (g(y) = g(y)) or some such thing,
and remarked that the same proof works for any term. So the
left side of the biconditional :^D is a known theorem.
Second way: Let A be (z = f(z)), again with z being
the variable substituted for. Then A[z:=t] is
(x = f(x)), the guy in line (1) of our Hilb. pf. And
A[z:=s] is (f(x) = f(f(x))). :*D
Again by M.P. we get the above biconditional from Ax 6 and
This time the left side of our biconditional right side
of Ax 6
is our assumption
in line (1), so by equanimity we get our desired equation
f(x) = f(f(x)) from the biconditional before :*D and line (1).
I actually prefer this proof (this choice of A) to the first
proof, since it does not require referring to something
proven in class or on Test 2. It's kinda neat because the
instance of Ax 6 turns out to be of the form
U --> (U == V), so that assuming U gives V, by M.P.
followed by Equanimity.
This, by the way, is a fairly typical proof of a theorem
involving equality. For others, peek at Chapter 7 in our