1 of 2

10.1 What’s a Proof?

We start with a problem you solved many chapters ago.

Sudoku with question mark in box that has 4, 5, 7, 8 and 9. 1 and 6 are in that column, and it can't be 3.

Now imagine they don’t believe you. How can you explain to them that that number must go there?

You might say something like this.

Every 3-by-3 box must have a 2, so the 3-by-3 box on the middle-right, where the question mark is, needs a 2 in it. We can see that the row above the question mark already has a 2 over on the left. And there are 2s in the columns to the left and right. That means a 2 cannot go in any of the other squares in the box, and thus 2 must go where the question mark is.

Proof: a step-by-step explanation.

That explanation is what we mean by a proof. A proof is a kind of step-by-step explanation that something does or does not follow from certain information.

In this class we focus on arguments, so we can put the idea this way: a proof is a demonstration or explanation that shows that the conclusion does (or doesn’t) follow from the premises.

In the example above, the premises are the rules of Sudoku and the information in the puzzle, and the conclusion is that a 2 goes where the “?” is. What the proof does is demonstrate why it is valid to conclude that a 2 goes there.

Proof: a demonstration that an argument is valid or invalid.

So a proof is a demonstration that an argument is valid or invalid. 

Your explanation given above demonstrates in a step-by-step way that a 2 must go where the “?” is. The information in the puzzle logically entails that a 2 goes there, and your proof shows why that is so.

It is essential to not confuse a proof and an argument: they are not the same thing.

A proof ≠ an argument!

An argument is just a set of premises and a conclusion. An argument is either valid or not, regardless of whether anyone knows that it is or proves that it is.

A proof, by contrast, is a step-by-step explanation that an argument is valid or not.

Proofs can be good or bad, successful or unsuccessful. For example, evaluate this proof:

Every 3-by-3 box needs numbers 1-9. The 3-by-3 box with the question mark has four empty squares, which must be 1, 2, 3 and 6. The square with the question mark can’t be a 1, since there’s already a 1 in that column. So it must be a 2.

In order for a proof to be good, the steps in it must have two features: each step must be

  1. obvious, and
  2. valid.

A good proof: every step is (1) obvious and (2) valid.

The problem with this proof is that the last step isn’t valid. Even if the question mark can’t be a 1, it doesn’t follow that it must be a 2, because we haven’t ruled out the possibilities that it’s a 3 or a 6.

The first proof, though, given at the beginning of this section, was good: it showed with obvious and valid steps that the “?” must be a 2.

Whether a proof is good can vary with one’s audience.

There’s an important complication about proofs, however, that you have to be aware of. What is obvious to one person isn’t necessarily obvious to another. That means that whether a proof counts as good can vary depending on one’s context or audience.

If one’s audience is not familiar with certain logical inferences, you might have to break the steps of the proof down to baby steps with very simple inferences.

An argument is valid or not no matter who the audience is.

But if one’s audience is logically sophisticated, you might be able to move very fast through complicated forms of reasoning.

That illustrates another difference between arguments and proofs. An argument is valid or not no matter who the audience is. Validity is not relative to the audience, or anything else: it is an objective fact about the logic of the argument. But whether a proof is good is relative to the intended audience.

There are two kinds of proof: formal and informal.

Audience-relativity creates a complication we must deal with. In order to deal with it, we will learn how to create two kinds of proof: formal and informal.

Formal proofs are proofs written in BOOL that use a set of rules which explicitly tell you what steps are allowed. They are the final part of BOOL that you learn in the next chapter.

Formal proofs: written in BOOL using a set of defined rules.

Formal proofs solve the problem of audience-relativity, because the rules of BOOL determine exactly which steps are allowed. We can use BOOL to show that the formal proof rules are valid, and so we can know that, as long as we stick to those steps, every proof we give in BOOL will be valid too.

We don’t want to just be constrained to proving things in BOOL, though. BOOL is a tool to help us understand our everyday reasoning. It’s not a replacement for our reasoning.

So we also need to understand how to create proofs in English or some other natural language. That is what informal proofs are for.

Informal proofs are proofs written in English that use steps your audience can understand.

Informal proofs: written in English using steps your audiences can understand.

Informal proofs can be tricky to create, because you don’t have a set of explicit rules to follow. But they are also versatile, because they aren’t constrained by the rules of BOOL.

Informal proofs still have the problem of audience-relativity, but we will give you guidelines for dealing with it. The guidelines will show you how to create informal proofs and what you can presuppose about your audience. As you become more sophisticated in your proof techniques, we will explain how you can presume your audience is more sophisticated too.

In this chapter you’ll learn about informal proofs, and in the next chapter you’ll learn about formal proofs. For now, let’s see if you’ve got the distinction between the two kinds.