Math for CS: Intro to Proofs

A proposition is a statement that is either true or false.

We are given some examples in plain English of what is a proposition and what isn’t.

Then, we go on to mathematical examples, including Fermat’s last theorem and Goldbach’s conjecture.

A predicate can be understood as a proposition whose truth depends on the value of one or more variables. So "n is a perfect square" describes a predicate, since you can’t say if it’s true or false until you know what the value of the variable n happens to be. Once you know, for example, that n equals 4, the predicate becomes the true proposition: 4 is a perfect square.

Axioms - propositions that are simply accepted as true.

Starting from these axioms, Euclid established the truth of many additional propositions by providing "proofs."

A proof is a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question.

There are several common terms for a proposition that has been proved. The different terms hint at the role of the proposition within a larger body of work.

• Important true propositions are called theorems
• A lemma is a preliminary proposition useful for proving later propositions
• A corollary is a proposition that follows in just a few logical steps from a theorem

These definitions are not precise. In fact, sometimes a good lemma turns out to be far more important than the theorem it was originally used to prove.

Euclid’s axiom-and-proof approach, now called the axiomatic method, remains the foundation for mathematics today. In fact, just a handful of axioms, called the Zermelo-Fraenkel with Choice axioms (ZFC), together with a few logical deduction rules, appear to be sufficient to derive essentially all of mathematics. We’ll examinethese in Chapter 7.

Some of these axioms are too primitive for proofs. Instead of starting with such primitive axioms, we’re going to take a huge set of axioms as our foundation: we’ll accept all familiar facts from high school math. This will give us a quick launch, but you may find this imprecise specification of the axioms troubling at times. For example, in the midst of a proof, you may start to wonder, "Must I prove this little fact or can I take it as an axiom?" There really is no absolute answer, since what’s reasonable to assume and what requires proof depends on the circumstances and the audience. A good general guideline is simply to be up front about what you’re assuming.

Logical deductions or inference rules, are used to prove new propositions using previously proved ones.

Patterns of Proof

In principle, a proof can be any sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question. This freedom in constructing a proof can seem overwhelming at first. How do you even start a proof? Here’s the good news: many proofs follow one of a handful of standard templates. Each proof has it own details, of course, but these templates at least provide you with an outline to fill in. We’ll go through several of these standard patterns, pointing out the basic idea and common pitfalls and giving some examples. Many of these templates fit together; one may give you a top-level outline while others help you at the next level of detail. And we’ll show you other, more sophisticated proof techniques later on. The recipes are very specific at times, telling you exactly which words to write down on your piece of paper. You’re certainly free to say things your own way instead; we’re just giving you something you could say so that you’re never at a complete loss.

I won’t be writing the recipes here, they can be looked up in the course lesson.

Here is a link to the lesson, for reference.

If that doesn’t work, go unit 1.1 through the course here