Don't forget about Jebs boy
George "P" Bush
1
What does a proof look like?
A proof is a series of statements, each of which follows logically from what has gone before. It starts with things we are assuming to be true. It ends with the thing we are trying to prove.
So, like a good story, a proof has a beginning, a middle and an end.
• Beginning: things we are assuming to be true, including the definitions of the things we’re talking about
• Middle: statements, each following logically from the stuff before it
• End: the thing we’re trying to prove
The point is that we’re given the beginning and the end, and somehow we have to fill in the middle. But we can’t just fill it in randomly – we have to fill it in in a way that “gets us to the end”.
It’s like putting in stepping stones to cross a river. If we put them too far apart, we’re in danger of falling in when we try to cross. It might be okay, but it might not. . . and it’s probably better to be safe than sorry.
2 Why is writing a proof hard?
One of the difficult things about writing a proof is that the order in which we write it is often not the order in which we thought it up. In fact, we often think up the proof backwards.
Imagine you want to catch a movie at the Music Box. How are you going to get there? You see that the Brown Line will take you there from the Loop. You know that you can get the #6 Bus to the Loop, and you know that you can walk to the #6 Bus stop from Campus. But when you actually make the journey, you start by walking to the #6, and you end by getting the Brown Line. And if someone asks you for directions, it will not be very helpful if you explain it to them backwards. . .
Or to put it another way, to build a bridge across a river, we might well start at both ends and work our way towards the middle. We might even put some preliminary supports at various points in the middle and fill in all the gaps afterwards. But when we actually go across the bridge, we start at one end and finish at the other.
One of the easiest mistakes to make in a proof is to write it down in the order you thought of it. This may contain all the right steps, but if they’re in the wrong order it’s no use. It’s like taking a piece of music and playing all the notes in a different order. Or writing a word with all the letters in the wrong order.
This means that for all but the simplest proofs, you’ll probably need to plan it out in advance of actually writing it down. Like building a long bridge or a large building – it needs some planning, even though building a small bridge or a tiny hut might not.
3
3 What sort of things do we try and prove?
Here is a classification of the sorts of things we prove (this list is not exhaustive, and it’s also not clear cut – there is some overlap, depending on how you look at it):
4
-
-
-
-
-
-
7.
-
-
-
-
-
x = y i.e. “something equals something else”
x =⇒ y
x ⇐⇒ y
x is purple (or has some other interesting and relevant property)
∀x p(x) is true i.e. “all animals of a certain kind x behave in a certain way p(x)”
∃x s.t. p(x) is true i.e. “there is an animal that behaves in a certain way p(x)”
Suppose that a, b, c and d are true. Then e is true. [Note that this is just a version of 2 in disguise.]