Andrew Cooper

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

[pullquote color=”reynoldsred” align=”alignright”]The logical form of a statement indicates the structure of its proof.[/pullquote]

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.

[pullquote color=”reynoldsred” align=”alignleft”]You don’t need to know exactly how the whole thing is going to go before you get started.[/pullquote]

 

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:

1. 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.
2. 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$

[pullquote color=”reynoldsred” align=”alignleft”] The structure of a conditional proof is drawn from the consequent.[/pullquote]

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.

There is another quantifier, besides existential and universal: the unique existential quantifier.

Definition. The sentence $\exists!x:S(x)$ is true if there is exactly one $x$ in the universe so that $S(x)$ is true. We read There is a unique $x$ such that $S(x)$.“

Notice that mathematically, unique means something rather different from what it means in ordinary English. Mathematically, unique always appears attached to some property. If we said Maxine’s a unique person, mathematically we’d mean There is only one person in all the universe, and that one person is Maxine.

Proposition. $\exists!x:S(x)$ is equivalent to each of the following:

1. $\left[\exists x:S(x)\right]\wedge \left[\forall y,z,\left(S(y)\wedge S(z)\right)\Rightarrow y=z\right]$
2. $\exists x:\left[S(x)\wedge \forall y,\left(S(y)\Rightarrow y=x\right)\right]$

Proof.

First we’ll show that each of (1) and (2) is enough to guarantee $\exists!x:S(x)$. (1) guarantees that there is at least one $x$ with $S(x)$. If we had two distinct members of the universe, say, $y$ and $z$, satisfying $S(y)$ and $S(z)$, then we’d have $y=z$, so $y$ and $z$ wouldn’t actually be distinct after all. Thus there is at most one $x$ with $S(x)$.

Now assume (2) is true. We know that there is at least one $x$ with $S(x)$. Suppose we had another, say $x’$. Then applying $\forall y, S(y)\Rightarrow y=x$ with $y=x’$, we see that $x=x’$. So $x’$ was $x$ to begin with. So there is at most one $x$ with $S(x)$.

Now we’ll show that $\exists!x:S(x)$ guarantees (1) and (2).

First, examine (1). Since we are proving a statement of the form $A\wedge B$, we must establish both conjuncts $A$ and $B$. The first conjunct $\exists x:S(x)$ is clearly true; there is a unique $x$ with $S(x)$, therefore there is some $x$ with $S(x)$. Now let’s prove the second conjunct, $\forall y,z,\left(S(y)\wedge S(z)\right)\Rightarrow y=z$. If this were false, we’d have $\exists y:\exists z:\left(S(y)\wedge S(z)\wedge y\neq z\right)$. Thus we have two distinct values of $x$ for which $S(x)$ is true. But this contradicts $\exists!x:S(x)$.

Now consider (2). We need to find the special $x$; let’s use the $x$ given by $\exists!x:S(x)$. Such an $x$ has $S(x)$. Now given $y$ with $S(y)$, we see that since there is exactly one value $z$ with $S(z)$, and $S(y)$ and $S(x)$, it must have been that $y=x$.

Thus we’ve shown that $\exists!x:S(x)$ guarantees (1) and (2) and each of (1) and (2) guarantees $\exists!x:S(x)$. This completes the proof.$\Box$

We can describe (1) above as saying: there is at least one $x$ with $S(x)$, and there is at most one $x$ with $S(x$).

We can describe (2) as saying: there is a special $x$ with has both $S(x)$, and the property that whenever $S(y)$ is true, $y$ must be the same as $x$.

Here we could say some words about how to prove a statement of the form $\exists!x:S(x)$, but we’ll postpone that a bit.

Exercising our powers of what-if-not thinking, let’s ask how $\exists!x:S(x)$ could be false. Consider the following statements:

1. There is a unique President of the United States.
2. There is a unique US Senator from Florida.
3. There is a unique US Senator from Washington, DC.

(1) is true. (2) and (3) are false, but false for different reasons. Let’s see why:

Exercise. Compute the denial of $\exists!x:S(x)$, using the fact that $\exists!x:S(x)$ can be expressed

\begin{equation*}
\left[\exists x:S(x)\right]\wedge \left[\forall y,z,\left(S(y)\wedge S(z)\right)\Rightarrow y=z\right]
\end{equation*}

Explain the relevance of this to the problem of uniqueness of Senators from Florida and from Washington, DC.

Some sentences feel an awful lot like statements but aren’t. For example,

is even

This is not a statement because it doesn’t have a truth value; unless we know what is, we can’t really do much.

Definition. A sentence with one or more variables, so that supplying values for the variables yields a statement, is called an open sentence.

You can think of an open sentence as a function whose values are statements. In fact we will use function notation to name open sentences.

n is even

Just as with ordinary functions, this notation works by substitution. With defined as above,

3 is even

which happens to be a false statement. , on the other hand, is a true statement.

Along with an open sentence, we have to provide some kind of indication of what sort of thing the variable might be. For our example , it makes most sense to let be a natural number or possibly an integer. We call possible values for the variable of an open sentence the universe of that sentence.

One thing that cannot be emphasized enough is that variables can represent any type of thing, not just numbers or other mathematical objects. So we could think about the open sentence

r is t years old

and say that the universe for is everyone in this class and the universe for is any whole number between 15 and 60.

Definition. Given an open sentence with one variable , the statement is true when, no matter what value of we use, is true; otherwise is false.
Given an open sentence with one variable , the statement is true when there is some value of for which is true; otherwise is false.

Terminology. We call the universal quantifier, and we read for all , . We call the existential quantifier, and we read there exists such that .

Observe that if there are only two possible values in the universe for (let’s call them and ), then is true when both and are true. But this is the same as being true. Similarly, is true when one of or is true. But this is the same as . So we see that the quantifiers are in some sense a generalization of and . So the following makes sense:

De Morgan’s Laws, quantifier version: For any open sentence with variable ,

1. 
2. 

For example, a denial of the statement

There is a china teapot floating halfway between the earth and the sun.

is

Every china teapot is not floating halfway between the earth and the sun.

the universal quantifier, conditionals, and the universe

Quantifiers are most interesting when they interact with other logical connectives. For example, consider the following (true) statement:

Every multiple of 4 is even.

We could choose to take our universe to be all multiples of 4, and consider the open sentence

n is even

and translate the statement as . But that isn’t very interesting. A much more natural universe for the sentence is even is the integers. But then we have to do something clever, because if our universe for is the integers, then is false. The solution is to create another open sentence

k is a multiple of 4

How do we use and to translate our true statement? We can think of an open sentence as a test–if we plug in a value for its variable(s), we see whether that variable passes the test. Here we have two tests: , a test for evenness, and , a test for multiple-of-4-ness. The statement we are trying to translate says that passing the test is enough to guarantee passing the test. That sounds like a conditional. Indeed the correct translation for Every multiple of 4 is even is:

Try translating this statement back into English using some of the various translations for to see that it really does mean the same thing as Every multiple of 4 is even.

Exercise. Translate and into English. Explain why these are false statements. Assume the universe for both and  is the integers.

In fact, we can always expand the universe by putting in another conditional. If we let be the sentence is an integer and expand our universe to include all mathematical objects encountered in this course, we could translate Every multiple of 4 is even as .

A Note about Notation. It’s important to keep in mind that, just as for the functions you’ve encountered in calculus and before, the particular symbol we use for a variable is not relevant to the meaning of that variable. The statements

and

both say the same thing. namely, Every integer which is a multiple of 4 is even. The fact that we called the variable when we defined and when we defined does not require us to always use those variables. Notice that in the English translation, no variables appear at all! We could equally well have written

except that that’s a bit difficult to pronounce.

The existential quantifier and the universe

We just saw that generally speaking, a universal quantifier should be followed by a conditional. What should an existential quantifier be followed by? Consider the following true statement

There is a multiple of 7 which is even.

How can we represent this symbolically? We could take the universe to be all multiples of 7 and write . But as before, that’s not very interesting. So let’s keep our universe as it should be: the integers. As before, we’ll need a test for multiple-of-7-ness: denote by the sentence is a multiple of 7.

Now think about what the statement There is a multiple of 7 which is even means. What is the relationship between multiple-of-7-ness and evenness? Just that some number happens to be both. Therefore we can translate:

Notice that because is commutative, our symbolic statement is equivalent to . But this is just fine, because our statement and the statement

There is an even number which is a multiple of 7

pretty clearly mean the same thing.

Let’s lock in the connection between and with another example. This time we’ll use De Morgan’s laws and consider the statement

Every multiple of 7 is even.

which happens to be false. Therefore its negation is true. We compute that negation:

which we could phrase in English as There is an integer which is a multiple of 7 and not even. Thus we see that the existential quantifier pairs naturally with the connective .

Exercise. Let stand for is even, stand for is a multiple of 7, and stand for is an integer. Let the universe for all three sentences be the set of all mathematical objects encountered in this course. Write a symbolic translation of There is a multiple of 7 which is even using these open sentences.

Exercise. Translate into English. Explain why this is a true statement. Give a useful denial. Assume the universe for both and is the integers.

quantifier order

Many interesting open sentences have more than one variable, such as:

= is years old

Since there are two variables, we are entitled to ask the question which one? twice. And we may have a different answer each time. There are eight possibilities, of which four are

1. For any person , for any age , that person is that age.
2. For any age , for any person , that person is that age.
3. There is a person who is some age .
4. There is an age so that some person is that age.

A moment’s thought should make clear that statements 1 and 2 mean the same thing (in our universe, both are false), and statements 3 and 4 mean the same thing (in our universe, both are true if woefully uninformative). This says that we can move existential quantifiers past one another, and move universal quantifiers past one another.

The other four possibilities are

5. For any person , there is an age so that that person is that age.
6. There is an age so that every person is that age.
7. For any age , there is a person who is that age.
8. There is a person who is every age.

Quantifier order matters.
Mixed quantifiers do not commute.

Notice that statement 5 is true (in our universe): everyone has an age. But statement 6 says that everyone is the same age, which is false in our universe. So statement 5 and statement 6 mean different things. Similarly, statement 7 is likely true in our universe, whereas statement 8 is false. The lesson is that quantifiers of different flavors do not commute!

[callout headingicon=”noicon” textalign=”textright” url=”https://www.youtube.com/watch?v=OncDlwNH9F0″ target=”true” type=”basic”]

If man is five, then the devil is six.

And if the devil is six, then god is seven.

This monkey’s gone to heaven.

Black Francis, Monkey Gone to Heaven

[/callout]

Logic as a game of pushing symbols is fun, but our purpose with it is to construct arguments. In fact, classically an advanced education was divided into two curricula: the lower division, the trivium or three-fold path, consisted of

1. grammar
2. logic
3. rhetoric

These three are in fact intimately related. We’ve already seem some interaction between grammar and logic; let’s see some ways that logic interacts with rhetoric, that is, the construction of compelling arguments.

proving $P\Rightarrow Q$

Many of the statements we want to prove in mathematics are conditionals. How could we go about doing this? Actually it’s easy. Recall the truth table for $\Rightarrow$:

$P$	$Q$	$P\Rightarrow Q$
T	T	T	1
	F	F	2
F	T	T	3
	F	T	4

We want to establish that $P\Rightarrow Q$ is true. That is, we want to make sure that we end up with a T in the third column of the truth table above. Phrased this way, it looks like our job is pretty easy (because there are so many Ts in that column!). If $P$ is false, we’re good to go. So we may as well assume $P$ is true. Then we only have to worry about $Q$ being false. Since $Q$ is a statement, it’s either true or false. So ruling out $Q$ being false means showing $Q$ is true.

Thus: we need to assume $P$ is true and prove $Q$ is true. The shorthand for this is: assume $P$; prove $Q$. In fact many primers on proof will belabor this point, putting the above maxim in a box in some bold color and telling you that now you know how to prove conditionals! But of course it’s how one gets from the assumption of $P$ to the conclusion of $Q$ that is where the fun lies, and we haven’t said really anything about that (yet). This is called a direct proof of $P\Rightarrow Q$.

other uses of the truth table for $P\Rightarrow Q$

modus ponens

Now let’s imagine that we know $P\Rightarrow Q$ is true; in other words, that we’re in line 1, line 3, or line 4; but we don’t know which one. If we had some additional information, like we happened to know that $P$ was true, then we’d know for sure we’re in line 1. But then we’d also know that $Q$ is true.

So we have the following rule: if we know $P$ and we know $P\Rightarrow Q$, then we know $Q$ also.

If you think about it for a moment, this is more or less the definition of the word if. But Classical and medieval logicians gave it a name, modus ponens.

modus tollens

What if we happened to know that $Q$ was false? Then we’ve got to be in line 4, so we know that $P$ is also false. So we have the following rule:

If we know $Q$ is false and we know $P\Rightarrow Q$, then we know $P$ is false also.

This is known to the medieval logicians as modus tollens.

If modus tollens seems a bit odd to you, just consider the following statement:

When you see ice in my scotch, that’ll be the day I die!

How does this work? Logically, the speaker is asserting $\text{ice is in my scotch } \Rightarrow\text{ it is the day I die}$. But since they’re around to have the conversation with us, we know the consequent is false. So the intended meaning must be that the antecedent was false, i.e. there’s no ice in their scotch. In fact we use this sort of discourse all the time in ordinary conversation.

reductio ad absurdum

A similar mode of reasoning also relies on the fact that only a false statement can imply a false statement. The idea is to establish a claim (we’ll call it $P$) by showing that $P$ couldn’t possibly be not true. So we assume $\sim P$, and make valid logical steps until we get to some egregious statement $Q$ which we all agree is false. Since our reasoning was sound, this must have meant that $\sim P$ was false, i.e. that $P$ was true. for example:

Consider what would happen if lowering the income tax rate always lowered income tax revenues. If we set the income tax rate at 100\%, we’d bring in more income tax revenue than any other rate. But at a 100\% income tax rate, nobody will have any reason to work, hence there will be no income tax revenue at all. Thus we should expect to get no income tax revenue at any other rate. On the other hand, the current income tax rate does generate income tax revenue. So we see that sometimes, lowering the income tax rate may increase income tax revenues.

Exercise. In the above argument, identify: $P$, the goal we set to prove; $\sim P$, the thing we assumed; $Q$, the truly egregious statement we all agree is false.

[panel heading=”what’s with these names?” headingtype=”p” type=”panel-info” state=”closed”]”modus ponens” is often translated as “the method of affirming”, but that’s a bad translation. In Latin, “pono” means “to put” or “to place”. So you might call this “the placement method”. Why? If you’ve ever watched a legal drama, the lawyers say things like “I put it to you, the jury, that…”. That’s sot of what’s going on here.

“modus tollens” is often translated as “the method of denying”, but again that’s bad Latin. “tollo” means “to snatch”. My preferred translation of this would be something like “the thief’s method”.

Actually both modus ponens and moduls tollens are less mysterious than they are made to seem by their fancy names. Perhaps the best name for both would be “modus manifestissumus” — “the really obvious method”.

“reductio ad absurdum” actually gets translated correctly, as “reduction to the absurd”. The idea is to take the denial of what you want to prove, and turn it into something. . . absurd.[/panel]

some other useful logical facts

Below is a list of logical facts. You should establish each one by using one or more of the following ways: making a truth table for the formulae involved; comparing truth tables; making algebraic manipulations of the formulae. You should also convince yourself that the statements make sense without resorting to these formal, abstract methods.

1. If $P\wedge Q$ is true, then $P$ is true.
2. If $P$ is true, then $P\vee Q$ is true.
3. If $P\Rightarrow Q$ and $Q\Rightarrow R$ are both true, then $P\Rightarrow R$ is true.
4. $P\Rightarrow (Q\vee R)$ is equivalent to $\left(P\wedge (\sim Q)\right)\Rightarrow R$ and $\left(P\wedge (\sim R)\right)\Rightarrow Q$.
5. $P\Rightarrow (Q\wedge R)$ is equivalent to $\left(P\Rightarrow Q\right)\wedge \left(P\Rightarrow R\right)$.
6. If $P\Rightarrow R$ is true and $Q\Rightarrow R$ is true, then $\left(P\vee Q\right)\Rightarrow R$ is true.
7. If $\left(P\vee Q\right)\Rightarrow R$ is true, then $P\Rightarrow R$ is true and $Q\Rightarrow R$ is true.

We can restate each of the above facts as the claim that a certain logical formula is a tautology:

1. $\left(P\wedge Q\right)\Rightarrow P$ is a tautology.
2. $P\Rightarrow\left(P\vee Q\right)$ is a tautology.
3. $\left[\left(P\Rightarrow Q\right)\wedge\left(Q\Rightarrow R\right)\right]\Rightarrow \left(P\Rightarrow R\right)$ is a tautology.
4. $\left[P\Rightarrow (Q\vee R)\right]\Leftrightarrow\left[\left(P\wedge (\sim Q)\right)\Rightarrow R\right]$ is a tautology.
5. $\left[P\Rightarrow (Q\wedge R) \right]\Leftrightarrow\left[\left(P\Rightarrow Q\right)\wedge \left(P\Rightarrow R\right)\right]$ is a tautology.
6. $\left[\left(P\Rightarrow R\right)\wedge\left(Q\Rightarrow R\right)\right]\Rightarrow\left[\left(P\vee Q\right)\Rightarrow R\right]$ is a tautology.
7. $\left[\left(P\vee Q\right)\Rightarrow R\right]\Rightarrow\left[\left(P\Rightarrow R\right)\wedge\left(Q\Rightarrow R\right)\right]$ is a tautology.

 

 

So far our statements haven’t been very interesting. In fact most mathematical statements of interest are things like

If a function is differentiable, then it is continuous.

These statements are known as conditional, because they depend on some criteria, or conditions, being satisfied.

Consider the following statement (first, convince yourself that it is a statement!):

If it rains, the laundry will be ruined.

What is this statement about? It’s not really about whether or not it rained; it’s not really about whether or not the laundry was ruined. Rather it’s about the relationship between rain and laundry.  That’s what makes conditionals so interesting.

Definition. Given two propositions $P$ and $Q$, the proposition $P\Rightarrow Q$ (read if $P$ then $Q$) is given by the truth table:

$P$	$Q$	$P\Rightarrow Q$
T	T	T	1
	F	F	2
F	T	T	3
	F	T	4

 

Exercise. Is $\Rightarrow$ commutative or associative?

A word of caution: this truth table causes consternation among most people when they first encounter it. In particular,  lines 3 and 4 sometimes rub people the wrong way. Statements like

If $1=2$, then $3=4$.

don’t exactly feel true. But we’ll go over each line of the truth table to justify why these are the right choices. To make things easier, we’ll label the two inputs to the conditional so we can refer to them. There are several labeling schemes:

$P\Rightarrow Q$
antecedent		consequent
hypothesis		thesis
assumption		conclusion

 

Now let’s go through each line of the truth table for $\Rightarrow$. There are two analogies that will help us understand this: the analogy of science, and the analogy of a contract.

The Science Analogy

Let’s consider the conditional

If it rains, the laundry will be ruined.

as a scientific claim. As good laundrologists, we want to put this to the test. So we conduct an experiment. Line 1 of the truth table is the situation when our experimental variable (the rain) is present, and so is our measured variable (the ruin of the laundry). These particular experimental data support the claim. We’ll record that as a T (though good experimental scientists know that a scientific claim is only ever provisionally established).

Line 2 is what would happen if the experimental variable were there, but the expected outcome (laundry being ruined) didn’t happen. Then we would know for sure that the proposed theory is definitely false. We record a F.

What about lines 3 and 4? That’s what scientists call the control condition; the experimental variable isn’t present. So what do we record in our lab notebook? No matter what happens with the laundry, the control data don’t tell us one way or the other about the claim. In particular, they leave open the possibility that the claim is true. So we record a provisional T in our lab book, just the same as the provisional T on line 1.

The Contract Analogy

Now let’s consider a conditional like

If you do all the work in this course, you’ll get an A.

Treat this as a contract or an agreement between us. Line 1 of the truth table is: you did the work, and you got the A. No problem: the agreement was carried out just fine. Line 2 of the truth table is: you did the work, but you didn’t get the A. That’s a clear violation of the agreement; in other words the agreement didn’t hold. Hence the truth value of F.

What about lines 3 and 4? That’s when you didn’t do all of the work. I could still give you an A (if I’m feeling kind) or not give you an A, but either way — you couldn’t really say that I’d violated the agreement. The agreement is still in force the whole time. That’s why we assign the truth value T to these lines.

 

In both analogies, a really solid way to think about this is what-if-not thinking: what would it mean for the conditional to be false? How could you know for sure that If it rains, the laundry will be ruined is false? Only if it it rains but the laundry isn’t ruined. How could you know for sure that it’s false that If you do all the work in this course, you’ll get an A is false? Only if you do all the work in this course, but nevertheless you don’t get the A. Let’s record that as a proposition:

Proposition. $\sim (P\Rightarrow Q)$ is equivalent to $P\wedge (\sim Q)$

We also have the equivalence:

Proposition. $P\Rightarrow Q$ is equivalent to $(\sim P)\vee Q$

Exercise. Prove this proposition in two ways: first, from the proposition above it using one of De Morgan’s Laws; and second, by comparing truth tables.

Notice that I used the words but and nevertheless to translate the logical symbol $\wedge$. Normally $\wedge$ is translated and, but the word but can be very useful when you want to deny a conditional. When it comes to truth values, the following words all mean the same thing:

and, but, yet, nevertheless

When it comes to $\Rightarrow$, there are even more possibilities for reasonable English translations; so many in fact that it’s impossible to list them all. Here are a few that you will likely encounter. The following all mean the same thing, namely $\text{the King of France is bald } \Rightarrow \text{ roses are red}$:

If the King of France is bald, then roses are red.
Roses are red if the King of France is bald.
The baldness of the King of France guarantees that roses are red.
The baldness of the King of France suffices for roses to be red.
For roses to be red, it is sufficient that the King of France be bald.
It is necessary for the King of France to be bald, that roses be red.
Roses’ redness is necessary to the King of France’s baldness.
Should the King of France be bald, roses will be red.
Supposing the King of France is bald, roses are red.
The King of France is bald only if roses are red.

I’ve departed from my normal typographical convention and put the keywords in italics, the antecedent in blue bold, and the consequent in green underline.

Some things to notice about these translations, in no particular order:

• Sometimes the antecedent occurs first in the sentence, sometimes the consequent does.
• Sometimes the antecedent occurs first in time, sometimes the consequent does.
• The grammatical form of the antecedent and the consequent have to be adapted to read nicely.
• The conditional keyword is sometimes split into more than one word.
• If is different from only if.

Exercise. Create English translations of the conditional above, using the conditional keywords when and whenever.

How to keep it all straight? Use what-if-not-thinking. That is, ask yourself how you’d know the sentence was false. For example: what would it mean for Roses’ redness is necessary to the King of France’s baldness to be false? If the redness isn’t truly necessary, that means there’s a circumstance in which the King is bald but the roses aren’t red.

biconditionals

There is also a kind of conditional called the biconditional, which we denote $P\Leftrightarrow Q$:

$P$	$Q$	$P\Leftrightarrow Q$
T	T	T	1
	F	F	2
F	T	F	3
	F	T	4

 

Proposition. $P\Leftrightarrow Q$ is equivalent to $(P\Rightarrow Q)\wedge (Q\Rightarrow P)$

We therefore write and read $P\Leftrightarrow Q$ as $P$ if and only if $Q$, or sometimes as $P$ iff $Q$ or $P$ exactly when $Q$.

Exercise. Is $\Leftrightarrow$ commutative or associative?

Let’s get another little word.

Definition. Given two propositions and , the proposition (read or ) has truth value as given below:

T	T	T	1
T	F	T	2
F	T	T	3
F	F	F	4

 

Exercise. Prove the following propositions. First make sure you know what they mean.

Proposition. is commutative.

Proposition. is associative.

Lines 2-4 probably aren’t surprising, but line 1 bothers pretty much everybody, so we should explore it a bit. Consider a statement like Barack Obama was born in Hawaii or Angela Merkel has a Ph.D. in chemistry. The two statements that make up this statement are both true (Obama was indeed born in Hawaii, and Merkel was a chemist before entering politics), so this is the type of statement that’s relevant to line 1. But we normally wouldn’t use the word or here; we’d use the word and instead. So seeing it written with the word or kind of makes us uncomfortable. Unfortunately (actually, very fortunately) there isn’t the option to assign a truth value of U — we have to give either a T or an F. And (there’s a long story, which you’ll work out for homework) it turns out to be much better to give a T than to give an F.

When we want to be extra clear, we refer to this flavor of or — the one with a T in the first row — we call it inclusive or. Generally speaking mathematicians use inclusive or, so get used to it!

Let’s take a look at how interacts with . Try your hand at proving the following, using truth tables:

Theorem. and distribute over one another; that is:

1. is equivalent to (this is distributing over .)
2. is equivalent to (this is distributing over .)

We also have the following very useful and very interesting result, which lets us translate between ands and ors:

De Morgan’s Law:

1. is equivalent to
2. is equivalent to

We are now ready to give our first logical computation, and formulate a useful denial of . We’ll use the symbol to mean is equivalent to.

by De Morgan’s Law 2
by De Morgan’s Law 1

Notice that just as in arithmetic, we work from the outside in, and write each step out. Also just as with arithmetic (and this can’t be emphasized enough) brackets are both useful and necessary!

The formula we ended with looks very little like the formula we started with–for example, it’s much longer. Why might a formula like

be more useful than

Let’s assign the variables as follows:

P= Roses are red.
Q= Violets are blue.
R= The king of France is bald.

 

Then says

Either roses are red and violets are blue, or the king of France is bald.

Its denial says

It is not the case that either roses are red and violets are blue, or the king of France is bald.

But what does that mean? Our logical computation says that it means just the same thing as

The king of France is not bald, and either roses aren’t red or violets aren’t blue.

Try convincing yourself, and explaining to someone else, why these two denials mean the same thing.

As with arithmetic, this is not the only way to come up with a denial of . Above we applied de Morgan’s Law first; but since we know that and distribute over one another, we could equally well have derived

by de Morgan’s Law 1
by de Morgan’s Law 2

which reads Either the king of France is not bald and roses are not red, or the king of France is not bald and violets are not blue.

As with arithmetic, the commutative, associative, and distributive rules for and will become so second nature to you that will begin applying them without thinking about it. But here we’ve spelled everything out.

Statements by themselves aren’t that interesting; let’s see how to combine them.

“not”

A writing teacher once told me the best way to clean up your writing is to eliminate as many adverbs and adjectives as possible. But one very important adverb–which changes the meaning of anything it touches–is the word not. Let’s formalize this.

Definition. Given a statement , the statement (read It is not the case that  or the abbreviated version not is true exactly when is false.

Note that if is a statement, it’s either true or false; in either case, we know what truth value has. So is by definition a statement. Also note the word exactly, which modifies when.

Proposition 1. is true exactly when is true.

Proof. There are only two kinds of statements , namely true and false.

If is false, then is true (this is the definition of ). But the only (that’s the exactly in the definition of ) way for to be true would be if were false; since is true, we know is false. So in this situation, and are both false.

If is true, then is false (remember, is only true when is false). So is true. So here again, and agree with one another.

In both cases, we’ve seen that and agree. Thus when is true, is true; and this is the only way for to be true. .

Notice that is a different formula from . For example, if is I wear a plaid shirt every day, then

is It is not the case that I wear a plaid shirt every day and
is It is not the case that it is not the case that I wear a plaid shirt every day.

But of course and are the same insofar as truth goes. One might say they mean the same thing.

To make better formal sense of the distinction between being the same statement and merely being statements that mean the same thing, we need the following definition:

Definition. A propositional formula or propositional form is a string of logical connectives and variables, so that when each of the variables is substituted with a statement, the result is a statement.

For example, is a propositional formula because if we supply a statement in place of , we obtain a statement.

Definition. Two propositional forms are equivalent if, whenever we substitute the same statements in for their variables, we obtain statements with the same truth values.

Armed with this definition, we can rewrite Proposition 1 in a different way:

Restatement of Proposition 1. and are equivalent.

denials, useful and otherwise

Definition. A formula equivalent to is called a denial of . If we plug a statement in to the variable , we obtain a denial of that statement.

E.g. and are denials of . is a denial of .

E.g. A denial of Andrew Cooper is from Texas is It is not the case that Andrew Cooper is from  Texas.
Another denial is Andrew Cooper is not from Texas.
Another denial is Andrew Cooper is either from someplace other than Texas, or he is not from anyplace in particular, a drifter if you will, rootless, without a home.

These examples show that there are many different denials of any given formula or statement.

One question I want you to ask, and to keep asking is: is a given formulation of a statement useful to me? Utility is in the eye of the beholder, so I won’t give you a formal definition of what I mean when I say useful denial. But I’ll say this: merely attaching It is not the case that… to the beginning of a statement probably will not yield any insight.

You might be asking yourself: why should I expect that formulating a denial would yield any insight, anyway? Here’s why, and it’s a very important less in thinking that I hope you take away from this course into the rest of your life beyond mathematics. Statements are, by definition, either true or false (and not both). So, when we are faced with a statement we don’t understand (or wish to understand better, or wish to prove), we usually ask questions like

• What does this statement mean?
• If this statement were true, what else would be true?
• When have I encountered similar (or just similar-looking) statements in the past?

These are great questions, but they don’t always get us where we need to go. Sometimes they can even lead us astray. Since we know that the statement in question is either true or false, we could as well ask about it:

• What would it mean for this statement to be false?

That is, we could formulate a denial of the statement. If we articulate all the ways the statement could be false, then we have also articulated what it means for the statement to be true: that’s just everything not on our list.

I call this method what-if-not thinking, and we’re going to use it a lot. But it depends, critically, on being able to formulate denials precisely and accurately. (Don’t worry, we’ll develop lots of practice.)

 

truth tables

Definitions like that of are kind of hard to read, so let’s record them symbolically. We can think of as being like a function: you tell it the truth value of , and it tells you the truth value of . So, just like you first did in some long-ago algebra class, we can record the values in a table. We call such a table a truth table. The truth table for looks like this:

T	F
F	T

We can make a truth table for any formula; here’s the truth table for :

T	T
F	F

Observe that we always list the input values (the first column) in the same order.

It’s pretty clear that Two formulae are equivalent if the output columns of their truth tables are the same.

 

“and”

not was nice, but it only acts on one statement or formula. (We call such operations unary, from the Latin unus “one”.) Let’s get some binary operations: operations which combine two statements or formulae. We’ll start with the word and.

Before reading any further, make sure you’ve done the pre-meeting exercise: read the dictionary.com entry on the word and and see if it would help you understand what the word meant, if you didn’t already know. Try this definition also.

Instead of giving a wordy definition, I’ll just give the truth table for “and”. The symbol we use is . Since there are two inputs, each of which has two possible truth values, there are four possible inputs:

T	T	T	1
T	F	F	2
F	T	F	3
F	F	F	4

Because we’re going to use this table rather than just look at it, I’ve given numbers to the rows.

Let’s play around a bit with this. What’s ? We’ll make a truth table. In order to compare it with the truth table for , we need to list the inputs in the same order.

T	T	T	1
T	F	F	3
F	T	F	2
F	F	F	4

 

Look carefully at the row labels. In order to populate row 2 of the   table, we have to look at row 3 of the table — this row is the “FALSE and TRUE” row.

We can conclude from this truth table that

Proposition. and are equivalent formulae.

Or, somewhat more pithily, we say

Restatement of Proposition. is commutative.

While this proposition may not surprise you, it does indicate a slight difference from the  ordinary-English word and.

Let’s try something else out, too: what about ? This time we’re have three inputs, each of which has two possible truth values, for a total of possible input truth values:

T	T	T	T	T	1
		F		F	2
	F	T	F	F	3
		F		F	4
F	T	T	F	F	3
		F		F	4
	F	T	F	F	3
		F		F	4

Here I’ve done two tricks: first, instead of writing so many Ts and Fs, I combined some rows in the and columns to make the table easier to read. Second, I wrote down the intermediate step of computing as a separate column. The last column records which row of the truth table for I used to go combine the values in the third and fourth columns to get the truth value in the last column.

Exercise. Make a truth table for .

Proposition. is equivalent to .

The pithy way to say this is

Restatement of Proposition. is associative.

Finally, let’s do two truth table computations with and :

Exercise. Make truth tables for and . Before beginning this, think hard about how many rows and how many columns your truth table will require. Then see if you notice anything interesting.

Tautologies and Contradictions

The result of the previous exercise will leave us with the need for the following definition:

Definition. A formula which always has a truth value of T, no matter what inputs it takes, is called a tautology. A formula which always has a truth value of F, no matter what inputs it takes, is called a contradiction.

If we’re thinking of propositional formulae as functions, then tautologies and contradictions are the constants. (There are only two constant functions, because statements can only be true or false (and not both).)

The philosopher’s version of this definition goes something like A tautology is a sentence that is true in virtue of its form. and A contradiction is a sentence that is false in virtue of its form., the point being that neither a tautology nor a contradiction can contain much in the way of meaningful content, because its form gets in the way. But that’s all a bit above our heads.

Shades of Meaning

Here’s a shocking claim:

and and but mean the same thing.

What do I mean by this? Consider the two statements:

1. I have a dog and he weighs twelve pounds.
2. I have a dog but he weighs twelve pounds.

In terms of the facts on the ground, what do we know in situation 1? That I have a dog. That the dog weighs twelve pounds. What do we know if situation 2? Exactly the same information!

So what’s different? Presumably, if I’m saying statement 2, it’s because I’m vaguely embarrassed to have such a small dog (sorry, Mugzy). That is, the difference between and and but lies in how the speaker feels about the circumstances. And because that’s not something that can be true or false, our logical framework just doesn’t care about it.

You might think this is a bug, but I see it as a feature. (Perhaps better to say: you might see this as a bug, and I see it as a feature.) It will allow us to subtly influence our reader’s perception — and our own perception — in ways that may make our written proofs clearer and easier to understand.

A neat thinking trick you can deploy to help make sure you aren’t being unduly influenced (say, when you’re watching talking heads): every time someone says but, just repeat what they said with an and instead. And make sure you don’t use but when you mean and.

Quando orientur controversiae, non magis disputatione opus erit inter duos philosophos, quam inter duos Computistas. Sufficiet enim calamos in manus sumere sedereque ad abacos, et sibi mutuo dicere:

Calculemus!

When controversies arise, there will be no more need for debates between two philosophers than there is between two computers. It will be enough for them to take their pencils into their hands, sit at their abaci, and say to each other:

Let’s compute!

Gottfried Leibniz

 

Logic is the business of writing down our reasoning in such a way that anyone who comes along can think what we thought, in a way that unambiguously compels assent. It is a useful tool across mathematics (why we learn it as part of this course) and a field of mathematical study in its own right, with applications to computer science and engineering, linguistics, and philosophy.

In some sense, logic is just a way of encoding ordinary argumentation. Though some facts about logic seem counterintuitive, we will see that, once we decide that we care about whether sentences are true or false, and that a few basic operations behave the same way they do in ordinary rhetoric, there is really no other option. We must accept the counterintuitive results along with the intuitive ones, and reject some of our intuitions. This theme of being able to formalize some, but not all, of our intuitions is a common one across mathematics.

What we’ll learn in this class is only a piece of “propositional logic” and “predicate logic”, which in turn is only a piece of the branch of mathematics that is logic.

Besides the statement-based theory we’ll learn, logicians also study other, nonstandard systems of reasoning, which are just as beautiful and interesting as what we’ll deal with. But in some way those other systems all differ from the basic way that people construct and interpret arguments.

Don’t worry, the logicians will forgive us if we use the word “logic” just for a slice of their very deep and beautiful field.

Perhaps the important thing about the logic we’ll learn (so-called predicate logic) is its computational flavor. That is, if we write out an argument in terms of logical symbols, and if we are good enough at logical computations, we can decide whether the argument is right or wrong. We can be sure (as sure as we are that the only solution of is ) that the argument is correct.

Overview of Logic

• Statements (this page). The basic unit of logic is the statement or proposition.
• Not & And. Statements can be made more interesting by combining them. We can write propositional formulae to discover useful facts about how statements relate to each other in general.
  
• Or. Another little word.
• Conditionals. If-then statements are the bread and butter of mathematical proofs.
• Order of Logical Operations. Just like arithmetic operations, the order of logical operations matters.
• Logic in Proofs. Simple chains of statements can be used to make deductions and structure proofs.
• Quantifiers. All about “for all” and “there is”.
• Uniqueness. We all like to feel special. But “unique” is something else!
• A Case Study: Divisibility. An illustration of how logic comes into a familiar idea.
• Watch Out! Some common pitfalls to avoid.

Statements

Logic deals with statements.

Definition. A statement is a sentence which is either true or false, and not both.

This isn’t a philosophy course, so we won’t concern ourselves with what it means for something to be true. I’ll refer to that idea as capital-T Truth. We’re interested in the more mundane concept of little-t truth, which we don’t need to know much about, other than it comes in two flavors (true and false), and we’re going to be dealing with sentences which have to be one and can’t be both.

Being a statement imposes two kinds of constraints:

• a form or grammatical constraint: the statement must be a sentence. In fact it should be a declarative sentence with a subject and a verb.
• a meaning or semantic constraint: the statement must be either true or false, and not both.

Practice Question. Which of the following are statements? For each non-statement, explain why it’s a nonstatement. For each statement, explain how you know it’s a statement.

1. The only solution of is
2. 
3. The improper Riemann integral of a function might exist without the function being integrable.
4. 
5. What can we say about the sequence ?
6. 
7. Foreign cars are better than domestic cars.
8. Euclid was left-handed.
9. The function is harmonic for .
10. This sentence is false.

a: This is a statement (it’s true)
b: This is not a statement (it’s not a sentence)
c: This is a statement.
d: This is a statement (it’s true)
e: This is not a statement (it’s a sentence, but not a declarative sentence)
f: This is not a statement.
g: This is not a statement.
h: This is a statement.
i: This is not a statement.

We’re ready for our first proof!

Theorem. The sentence This sentence is false is not a statement.

Proof. Let’s denote the sentence This sentence is false by the letter S.

If S were a statement, then S would be either true or false.

If S were true, then by the meaning of S we could conclude that S would have to be false. So S would be both true and false. (This, however, is not allowed for statements.) So S can’t be true.

If S were false, then by the meaning of we could conclude that would have to be true. So S would be both false and true. (This, however, is not allowed for statements.) So S can’t be false.

We’ve just established that S cannot be a true statement, and that S cannot be a false statement. But those are the only two types of statements. So S must not be a statement at all.

Let’s dwell on the proof we just saw.

• First, notice that the claim being proved is set apart from the text clearly, so that everyone knows what we are doing: we are proving that This sentence is false is not a statement.
• Next, we have indicated where the proof itself starts (with the boldface word Proof). This may seem a bit over-the-top, but it’s clear anyway.
• We’ve also given a clear indication of when the proof ends: we say so explicitly (“So S must not be a statement at all.”) and give a special symbol: .
• One good trick to make this proof more readable was the first line of the proof: we replaced This sentence is false with the letter S. We didn’t have to do this, but it saved us some headaches from reading things like
  “If This sentence is false were false, then by the meaning of This sentence is false, we could conclude that This sentence is false would have to be true.”
• The clarity of all of the above was helped by formatting: the use of symbols, italics, boldface, and indentation.

Finally, I want to point out that this, our first proof, was also our first reductio ad absurdum or proof by contradiction. We’ll talk more about that later, but notice that we started by supposing the opposite of what we wanted to establish: we wanted to show S was not a statement, but we assumed S was a statement to begin with. Then we painted ourselves into a logical corner. That’s the essence of a reductio ad absurdum.

 

What the sentence This sentence is false shows is that being a statement has to do with both grammar (form) and semantics (meaning): the very similar sentence This sentence appears in black type is definitely a statement, even though its form is the same.