Logic: Proofs with Quantifiers – Foundations of Mathematics

Now we're at the stage where you're probably antsy to start actually writing proofs. Excellent! Let's get started.

The main message (and it's the reason we spend so much time discussing logic) is this: The logical form of a statement indicates the structure of its proof. That is to say: each bit of logic that makes up a statement (quantifiers and connectives) has a corresponding move in writing the proof.

That's not to say that the logical structure is the only thing you need to understand to write a proof. Statements have both form (the logic) and content. The content will come into play eventually, and you'll often need a bit of creativity -- an "aha!" moment. The secret is that the logical form of the statement, and the structure of the proof it indicates, gives you a scaffold to support that creative moment and put it to good use when inspiration strikes.

There's another secret, which is that writing a proof (like a lot of writing) happens in a dramatically different order from the order in which reading a proof does. There are a lot of drafts and revisions. There's a lot of goal-setting and question-asking. The important thing to remember here is that You don't need to know exactly how the whole thing is going to go before you get started.

Let's do some examples with a familiar idea, divisibility. We'll start with the definition:

Definition. We say that the integer $p$ divides the integer $q$ if there is some integer $k$ with $q=pk$ . We refer to $k$ as a quotient of $p$ by $q$ . In symbols, $p$ divides $q$ means $\exists k: q=pk$ . We call the number $k$ the quotient of $q$ by $p$ .

Notation. We write $p|q$ for $p$ divides $q$ .

Notice that in this definition, we've specified the universe for both $p$ and $q$ . The definition itself is an open sentence with two variables; a third variable is required to state the definition. Finally, observe that the quotient is not assumed to be unique.

Proposition. 3 divides 12.

Let's think about how we'd prove this. What do we need to do? We need to show that it's possible to express 12 as a product of 3 and something. The easiest way to do this is to find that something. This one's easy.

Proof. Let $k=4$ . Then $12=3\cdot 4=3\cdot k$ . This shows that 3 divides 12. $\Box$

The claim we wanted to prove was existential: $\exists k: 12=3\cdot k$ . This example shows that there is essentially just one way to prove an existential claim, and that way has two steps:

Propose a candidate. In this case, our candidate was $k=4$ .
How you come up with the candidate is where the fun/excitement/headaches of an existential proof are.
Verify that the candidate works. In this case, the verification step was simple arithmetic.
Usually, this step will be more straightforward than the proposal step, but that's usually because in the proposal step you'll have picked the candidate to make the verification step easy.

Let's do a more interesting example.

Proposition. For any integers $a$ , $b$ , and $c$ , if $a$ divides $b$ and $a$ divides $c$ , then $a$ divides $b+c$ .

Let's translate this into symbols. It's best to go in steps. First, we have the key word any, which means this starts with a universal quantifier. In fact there are three of them: one for each of the variables $a$ , $b$ , and $c$ . Then we've got an and and an if... then. So a good start is:

$\forall a,\forall b,\forall c, \left[(a|b)\wedge(a|c)\right]\Rightarrow a|(b+c)$

We can then substitute in what $a|b$ means, namely $\exists k: b=ak$ , and what $a|c$ means, namely $\exists \ell: c=a\ell$ . I've used different letters for the quotients, because they might be different. (If the quotients in $a|b$ and $a|c$ end up being the same, then we can just declare $k=\ell$ at the end, so we don't lose anything by using more variables. Always err on the side of using more variables.) We should also substitute $a|(b+c)$ : $\exists m: b+c=am$ . Then our statement reads:

$\forall a,\forall b,\forall c, \left[\left(\exists k: b=ak\right)\wedge\left(\exists \ell: c=a\ell\right)\right]\Rightarrow \left(\exists m: b+c=am\right)$

Now let's think about how to start our proof. We want to prove something about all possible triples of integers $a,b,c$ . How would you prove that all cows are brown? You'd need to test every cow with a brownometer. It would be much more convenient if you had an assistant to bring each cow to a testing barn, so you didn't have to carry that heavy brownometer around with you. So you'd tell your assistant: bring me the first cow. Then, having checked that cow was brown, you'd say: bring me the second cow. You'd check that cow. Then you'd ask your assistant to bring in the third cow, etc. We'll do the same thing.

When you need to prove a universal claim, you start out with the word let, which is the rhetorical equivalent of telling your assistant to bring the next cow into the brownometry barn:

Proof. Let $a$ , $b$ , and $c$ be integers.

So far, so good. Now we've handled the 3 universal quantifiers; the next logic we encounter is the $\Rightarrow$ . How do we handle that? By assuming the antecedent, and trying to prove the consequent is true.

Assume that $a$ divides $b$ and $a$ divides $c$ . We'll show that $a$ divides $b+c$ .

Now what does it mean to prove $a$ divides $b+c$ ? $a|(b+c)$ is the same as $\exists m: b+c=am$ . It's an existential claim! So we have to propose some $m$ and verify that it satisfies $b+c=am$ . That is, we need to solve the equation $b+c=am$ . Now we could just write $m=\frac{b+c}{a}$ , but that's no good because we need $m$ to be an integer, and there's no guarantee that any random fraction is going to be an integer.

Instead, we'll use our assumptions.

Because $a$ divides $b$ , there is a $k$ with $b=ak$ . Because $a$ divides $c$ , there is $\ell$ with $b=a\ell$ . Set $m=k+\ell$ .

That's the proposal step. Now to verify. We need to verify two things: first, that $m$ is an integer,

Because $k$ and $\ell$ are both integers, and the sum of any two integers, $m$ is an integer.

and second that $m$ satisfies the equation $b+c=am$ .

We also have

$b+c=ak+a\ell=a(k+\ell)=am$

which shows that $a|(b+c)$ . $\Box$

Notice that my orange annotations were a lot longer than the actual text of the proof. To drive this point home, let me reproduce the proof below, without the annotations so you can see how short it is:

Proof. Let $a$ , $b$ , and $c$ be integers. Assume that $a$ divides $b$ and $a$ divides $c$ . We'll show that $a$ divides $b+c$ . Because $a$ divides $b$ , there is a $k$ with $b=ak$ . Because $a$ divides $c$ , there is $\ell$ with $b=a\ell$ . Set $m=k+\ell$ .

Because $k$ and $\ell$ are both integers, and the sum of any two integers, $m$ is an integer. We also have

$b+c=ak+a\ell=a(k+\ell)=am$

which shows that $a|(b+c)$ . $\Box$

I want to point something out in this proof, which is that the orange text focuses primarily on the consequent $a|(b+c)$ . This is an important but counterintuitive lesson: the structure of a conditional proof is drawn

from the consequent. That is, when we prove $P\Rightarrow Q$ , we need to look at the logical structure of $Q$ to guide our thinking. Think of $P$ as your set of tools, and $Q$ as the goal you want to achieve. Anyone who's played baseball or softball has been told: keep your eye on the ball. $P$ is the bat; $Q$ is the ball.

Here's another example.

Proposition. Quotients are unique. That is, for any integers $a$ and $b$ with $b\neq 0$ , if $a|b$ , there is exactly one $k$ so that $b=ak$ .

Proof. Let $a$ and $b$ be integers so that $b\neq 0$ . Assume $a|b$ .

We've just taken care of the universal quantifier and stated the antecedent. Because we're going to focus on the consequent, we haven't gone to the trouble to unpack the antecedent yet. Let's state our goal.

We need to show that there is a unique $k$ with $b=ak$ . That is, we need to show there such a $k$ , and there is only one such $k$ .

Because we're proving an and, we prove each conjunct separately.

Such a $k$ exists because $a|b$ .

Nicely done. How about the second conjunct?

We now need to show: $\forall k,k', \left(b=ak\wedge b=ak'\right)\Rightarrow k=k'$ .

This is a universally quantified conditional, so we let, assume the antecedent, and try to prove the consequent. Let's strategize a moment. How do we prove two numbers (here, $k$ and $k'$ ) are equal? One strategy is to prove that their difference $k-k'$ is zero. Another strategy would be to prove that $\frac{k}{k'}=1$ . Another strategy would be to prove that $k\leq k'$ and $k\geq k'$ .

Let $k$ and $k'$ be integers. Assume $b=ak$ and $b=ak'$ . Then

$0=b-b=ak-ak'=a(k-k')$

By the zero-product principle, either $a=0$ or $k-k'=0$ .

When you know an or, you can break the proof down into cases. The important thing is that the cases cover all possibilities. Here we have:

case $a=0$ . Then $b=ak=0\cdot k=0$ . But we assumed $b\neq 0$ . So this case doesn't actually happen, so we must really be in the other case.

case $k-k'=0$ . Then $k=k'$ . This is what we wanted to show.

When you do a proof by cases, you need to end each case by either showing that that case doesn't occur, or that it ends with what you're trying to prove.

Because we've established the claim in each case, we are done. $\Box$ .

You might have been tempted to do the following:

$\begin{align*} b&=b\\ ak&=ak'\\ k&=k' \end{align*}$

That is, to divide through by $a$ . But we don't know we can do that yet. Divisibility and proofs involving divisibility are about multiplication, not about division. In fact, division is about divisibility, rather than the other way around.