Rolfe Schmidt

Series Outline

1. Proof — Series introduction
2. Proof I: Language and Logic — this post, introduce sentential grammar
3. Proof II: Bringing Meaning to Language –truth tables and syntax trees
   

In my introduction to this mini-series I talked about when and why someone whould learn about proof. Now it is time to start talking about what a proof is.

So let’s try to define “proof”. Here’s a pretty good first stab: A proof is an incontrovertible argument. Let’s accept this. We immediately run into a couple of issues.

1. Now we need to define “incontrovertible” and “argument”
2. “Argument” seems to have something to do with language. To check whether something “is an argument” we’ll just need to check the grammar, or syntax
3. “Incontrovertible” has something to do with the meaning of language, or semantics.

So we’ve just scratched the surface here and it’s pretty clear that talking about proof means talking about language, not Math! Many people get confused when trying to prove things in school because they think proof is all about the “idea”. Don’t get me wrong — ideas are what make Math worth studying. But an idea is not a proof. A proof must use language to communicate the idea to another person, and put the idea in a form that we can validate.

Once you get comfortable with this separation of “idea” and “proof”, you may start to notice that some of your thinking is “visual”, and other thinking is “linguistic”. Could there be a better way to prove things using this visual thinking? Perhaps, but if you want to tell me about it you’ll have to tell me with language. So if your visual proof system is really better than our standard linguistic one, that extra power will be something we can’t talk about!

So studying proof is really studying (a certain type of) language. Now when kids learn to talk, do they start by improvising in iambic pentameter? Or do they stumble around with basic vocabulary and grammar? When you study another language, isn’t the first step learning vocabulary, idioms, and grammar? You need those before you can speak with meaning or elegance. (I’m not saying you should teach people by saying inane things — you should expose learners to meaning and elegance from the start. But I digress.)

Learning about proof is very similar to learning human languages. You need to learn the grammar and the semantics before you can translate your ideas. But here we have an important difference — in logic we must be strict about our grammar or we won’t be able to validate our proofs later. A proof with a grammar error is not a proof. So if you want to know what a proof is, you need to know the grammar.

I’m sorry for sounding like an old schoolmarm here. Later we’ll see that reality is much more fun. But this formal style of proof is critical, because it is always an option, our arguments can always be made formal and validated.

So let’s face the grammar.

I will introduce the grammar in two layers. Proof is all about figuring out when a sentence is true or false, so we will only worry about propositions: sentences that are either true or false. Grammar is all about building sentences. The first layer of our grammar — the grammar of sentential logic — tells us how we can build new propositions from old ones.

I’ll need to get a little mathy here and start using symbols to represent propositions. I’ll use boldface capital letters as “sentence symbols”. When you see a sentence symbol, you can replace it with a grammatically correct sentence to get a new grammatically correct sentence. The rest of this post will be about making these ideas concrete.

First let me say a little more about the sentence symbols. In my examples here, I’ll just use the symbols A, B, C, and D. Whenever you see these symbols, I encourage you to substitute an English sentence in its place. I’ll do this for you every once in a while, and here are the translations I’ll use

Now none of these English sentences is very precise. Our second layer of grammar (coming later), will help us write better propositions. But at a common sense level these are sentences that seem like they must be true or false. They are propositions. One of the neat things we’ll see is that we can say a lot about propositions just by looking at the structure of the sentence.

Sow how can we take our propositions symbols A, B, C, and D and build new ones? Here are four useful ways:

Thse are called sentential connectives. Yes there are other logical connectives, and you can see notation for them in a table here. But the neat thing is that these are the only ones we need. Sometimes we’ll throw in to mean “if and only if”, but we don’t really need it — we could just use two “if” statements instead. All propositions involving any (finite) number of variables can be built with these four connectives. We could get even more parsimonious and get down to just one connective: “not and”. It is neat to know that we only need one logical operation say everything, but that makes for pretty tough reading.

Each one of these connectives gives us a sentence-building operation — a way to make a new sentence from one or two old ones. To do this we had to introduce some new symbols to our language: . The parentheses are critical. Every sentence must have parentheses around it or we will never understand how to break a big sentence down into its pieces. Here is an example: what does the sentence mean? Using my example translations, it reads something like “Janos is tall and Janos plays basketball or Janos is not tall”. This is an ambiguous sentence, think about it a bit. But we could write to mean, basically if Janos is tall, he must play basketball. This is not ambiguous.

Now we’re in a position to state all of the rules of our grammar. To keep close to standard terminology, we’ll say that an expression is any finite sequence of our symbols. A “grammatically correct” expression is called a well formed formula of wff (pronounced “woof”). An expression is a wff if and only if

1. it is a sentence symbol A, B, C, D, …
2. Or it is built from one or more wffs using one of our four sentence-building operations listed above.

That’s it. This is the whole of the grammar. But we can use it to build pretty complicated propositions. Here’s an example that’s really not too bad:

Here are some simpler examples of sentences I can build up from these symbols. Try to translate them into English. Use my translations or make up your own!

When you translate these to English, you’ll notice that sentences can be true regardless of the meaning of the symbols. is an example. These are called tautologies. Some are false no matter what: . Finally, some statements are “interesting”: , or with my translations “if global warming is not the only environmental problem we are facing, it is not true that you can consume all you want as long as you buy carbon offsets”.

This “sentence-building” view of our grammar has a nice side-effect. It allows us to write a computer program that will write out every possible wff. This sort of observation will be crucial down the road when we talk about Gödel’s incompleteness theorem and the relationship between truth and provability.

After introducing my definition of proof, this post has really dwelt on grammar or syntax. Basically, we’ve been starting to talk about how an argument must be written. In the next post in this series (not sure when it will arrive), I plan to talk about the semantics — what makes a sentence incontrovertible. Then we’ll follow this up with that promised “second-layer” of grammar, first-order logic.

If you want to dive deeper into the subject (I’m making no attempt at a rigorous presentation here), there are plenty of books on the subject. I happen to have Enderton’s A Mathematical Introduction to Logic, and I like it but I haven’t read it through. I learned most of this in a course with a great teacher and from bits and pieces I’ve put together since.

[This is still a draft. I will edit it. If you don't like something, tell me and I may change it. If you do like something, watch out it may disappear.]