## Saturday, 31 March 2012

### Proving Things

Philosophy students working in areas that require technicalities often tell me that while they understand the various definitions and the general gist of some overall result or bunch of results (e.g., Lindenbaum Lemma, Overspill, etc.), they're no good at proving stuff. What I think plays a role is that it's not straightforward to prove things, and one can easily screw up a proof. Which is a bit embarrassing.
At a certain level, no one is any good at proving stuff unless they practice over and over and over again! Even the brilliant mathematics student reaches a point (often in mid-UG studies) where the weird innate talent that helped them sail through school runs dry, and they have to learn to think carefully and practice proof techniques they pick up from textbooks and teachers.
The post below about diagonalization has, tucked just beneath the surface, examples of things that aren't too hard to prove, and are useful for getting some practice at proofs by induction. For example,
Because of the presence of $\underline{0}$ and $S$ in $\mathcal{L}$, there is a canonical way of denoting numbers, using canonical numerals. Roughly, the number $n$ is denoted by the term $S\dots S\underline{0}$, with $S$ repeated $n$ times. More exactly, one defines a function
$\underline{ }:\mathbb{N} \rightarrow Tm(\mathcal{L})$,
by primitive recursion as follows:
$\underline{0}:= \underline{0}$
$\underline{n+1}:=S\underline{n}$
So, for example, the number 7 is denoted by $\underline{7}$, which is the term $SSSSSSS\underline{0}$. By induction, it is easy to prove that $(\underline{n})^{\mathbb{N}}=n$.
So, how do we prove this by induction?
Induction is used to prove claims of the form,
for all $n$, $n$ has property P,
by two preliminary steps:
(i) Base step: show that $0$ has P.
(ii) Induction step: show that if $k$ has P, then $k+1$ has P too (where $k$ is arbitrary).
It's always useful to identify the property in question. In this case,
$n$ has the property P iff $(\underline{n})^{\mathbb{N}}=n$
So, the two steps required are:
(i) Base step: show that $(\underline{0})^{\mathbb{N}}=0$.
(ii) Induction step: show that if $(\underline{k})^{\mathbb{N}}=k$, then $(\underline{k+1})^{\mathbb{N}}=k+1$.
The Base step is completely obvious, because $(\underline{0})^{\mathbb{N}}$ is defined to be the number $0$.
The induction step is fairly straightforward. We want to show that,
if $(\underline{k})^{\mathbb{N}}=k$, then $(\underline{k+1})^{\mathbb{N}}=k+1$.
So, first assume the Induction Hypothesis:
$(\underline{k})^{\mathbb{N}}=k$
The sub-aim is to prove,
$(\underline{k+1})^{\mathbb{N}}=k+1$
from the Induction Hypothesis. And this proof should involve the definition of the function $\underline{ }$ that takes numbers to their numerals, and perhaps further "background facts". So, one can do it like this,
$(\underline{k+1})^{\mathbb{N}} = (S\underline{k})^{\mathbb{N}}$
$= S^{\mathbb{N}}((\underline{k})^{\mathbb{N}})$
$= S^{\mathbb{N}}(k)$
$= k+1$, as required.
In the first line, we replace "$\underline{k+1}$" by its definition, namely "$S\underline{k}$". In the second line, we use the usual clause for evaluating the denotation of a compound term $ft$ relative to an interpretation $\mathcal{A}$, namely,
$(ft)^{\mathcal{A}} = f^{\mathcal{A}}((t)^{\mathcal{A}})$.
In the third line, we use the Induction Hypothesis; and in the final line, we use the fact that $S^{\mathbb{N}}$ is the successor function.

1. What I think plays a role is that it's not straightforward to prove things, and one can easily screw up a proof.

I remember in the early part of my career as a logician not having trouble with proving things but being rather mystified at determining what to prove. All of the logic classes I'd taken as an undergrad and early grad student had homeworks along the lines of "prove X" or "give a countermodel to Y", not "determine whether this sentence is true and give a proof of it or give a counterexample if it is false", or, more importantly "take these definitions/lemmas/corollaries and come up with some novel result using these concepts and prove it." While I've learned how to do the latter -- to both identify whether a particular statement is likely to be true or false, and to generate such statements in the first place -- I'm still not entirely sure how, or how this type of skill can be taught to the young researcher. It's very big difference trying to prove something that you know is provable (because it was assigned to you as homework) and trying to prove something that you're not even sure is true.

1. Sara,
"take these definitions/lemmas/corollaries and come up with some novel result using these concepts and prove it." While I've learned how to do the latter -- to both identify whether a particular statement is likely to be true or false, and to generate such statements in the first place -- I'm still not entirely sure how, or how this type of skill can be taught to the young researcher.

Good question, and I'm interested in this sort of thing.
It's the question of originality rather than simply acquiring the skills required for proofs. My initial guess is that fostering originality in a young researcher depends on,
(i) how "immersed" one is in the research activity of the discipline;
(ii) how closely one interacts with other colleagues working in the field;
(iii) having a good mentor or a supervisor.

When I'm thinking all the time about a topic, and spending time with such colleagues daily, then I find all kinds of questions pop into my mind. Plus I'm able to suggest problems and lines of inquiry to my current students and colleagues. These are important in all areas of inquiry, of course; but I think more so in our field. So, I think the social interaction aspect of this is quite important for formal parts of philosophy, probably more so than other areas of philosophy.

Jeff

2. Jeffrey, I agree with you completely, but I'd add something.
Contrary to what happens in mathematics, there is no clear idea of what should a philosophical logician be able to prove. We only have a clear idea of what does she or he have to know (i.e. the results of Godel, Tarski, Skolem, etc.), and the ability to construct proofs is sometimes considered secondary.
Following Sara's comment, I find that some intermediate logic textbooks (and consequently some intermediate logic courses) addressed to philosophers are clear and beautiful explanations of those important results in mathematical logic, but lack interesting or challenging exercises. Most of the exercises are mechanical and intended to help the students in understanding the main proofs (e.g. 'design a Turing machine that doubles the number', 'prove in system X that $\forall x(Fx \wedge Gx)$ implies $\forallx (Fx \wedge \forall x Gx))$'). This can cause the sad impression that a philosopher is supposed to 'see' and understand logical systems and proofs, but not to produce them. This is unsurprising: the most interesting results in mathematical logic are really difficult to prove and involve novel or even strange strategies.
In my case, I learned how to prove things (or at least, I started to enjoy a lot that task) after reading and solving some elementary mathematical textbooks where proofs were creative and philosophical but clearer than in logic (e.g. set theory). As I see it, logic is an advanced subdiscipline of mathematics, maybe not the best place to start proving interesting things.

3. "As I see it, logic is an advanced subdiscipline of mathematics, maybe not the best place to start proving interesting things."

Yes, definitely - and that's why philosophy students often get more than they bargained for when they take an intermediate course, after intro logic. Usually, intro logic is around the level of advanced high-school mathematics (A-level, we'd say in the UK). But intermediate logic has to be taught as a genuine mathematics course. E.g., things like "prove that a consistent set can be extended to a maximal consistent set", or "prove that negation is not definable using just conjunction and disjunction" are non-trivial problems, quite different from "give a derivation of B from A" or "use a truth table to determine if A is a tautology". The methods are quite hard and unless one is already fairly proficient in mathematics, the step-up is a shock - for philosophy students. I've seen it on lots of occasions.

When I teach intermediate logic, I spend two weeks doing a quick introduction to naive set theory, some number theory (informal PA and induction) and a bit of discrete mathematics (e.g., sequences, orderings). Usually, the mathematics students who haven't even done intro logic perform better than the philosophy students who have done intro logic. But I'd add that the best students, however, are those doing combined degrees in mathematics and philosophy - they can join the dots, so to speak, between the two disciplines.

Jeff

4. A book that I found very useful, and that I have often recommended to students is Daniel Velleman's How to prove it (Cambridge UP, 1994). It is full of feasible, but still interesting problems, and it really teaches how to find a proof strategy.

1. Thanks, Aldo - I've often heard praise for this book, but never looked at it myself. I'll get hold of it.

5. That math students perfom better than philosophy students at proving things should not surprise us, even if phil-students have taken an introduction to logic course before. The reason I belive is the one you gave, namely, that an introduction to logic course equals a high-school mathematics level, meaning that what you are suppouse to do is TO SOLVE, rather than TO PROVE. (Well, sometimes to prove sth using the principle of induction, but simple.)

The step from solving to proving should be progressive, otherwise it will be a shock. Your options: naive ST, number theory and discrete math seem to be the most appropiate. Those are the choices that, for instance, friends of the computer science and engineer departments told me take when going for the next step. I can think no other way of accomplishing mathematical maturity.

Velleman's book is wonderful. I got it and it is helping me a lot in this transition to the world of proofs.