Statements and connectives

The words that build mathematical claims, "not", "and", "or", "if ... then", mean something slightly different in conversation every time they are used, and a proof cannot rest on a word whose meaning moves.

The previous lesson unpacked "the sum of two odd integers is even" into a claim with an "if ... then" inside it, and its proofs worked only because it was clear what that claim asserted. This lesson makes that clarity routine. It says which sentences can be true or false, fixes the meaning of each connective with a truth table, and spends most of its time on the conditional, the connective every theorem is written in. It assumes school algebra and the definitions of even and odd: an integer is even when it equals $2k$ for some integer $k$, and odd when it equals $2k+1$.

Statements

A statement is a sentence that is either true or false. "$91$ is prime" is a statement, and a false one, since $91=7\times 13$. "$2^{10}>1000$" is a true one, since $2^{10}=1024$. What matters is that the sentence has a truth value, not that anyone knows it. "Every even integer greater than $2$ is the sum of two primes" is Goldbach's conjecture, proposed in a letter to Euler in 1742 and checked by computer for every even number up to $4\times {10}^{18}$. Nobody knows whether it is true, but it is certainly one or the other, so it is a statement.

Plenty of mathematical sentences are not statements. "Is $91$ prime?" is a question and "Let $n=91$" is an instruction. The subtler case is a sentence with a free variable, such as "$x>3$", which is true when $x=5$, false when $x=1$, and has no truth value until $x$ is pinned down. Such a sentence is an open sentence. Turning open sentences into statements is the job of the next lesson; this one works with statements, or with open sentences read for one value of the variable at a time.

Statements are written with capital letters, $P$, $Q$, $R$, so that the structure of a claim can be seen apart from its content. The rules below depend only on whether each part is true or false, never on what it says.

Not, and, or

Each connective is defined by saying, for every combination of truth values of its parts, whether the compound is true. With two parts there are four combinations, and a truth table lists them, one per row.

Negation, written $\neg P$ and read "not $P$", is true exactly when $P$ is false. Conjunction, $P\wedge Q$, read "$P$ and $Q$", is true exactly when both parts are true. Disjunction, $P\vee Q$, read "$P$ or $Q$", is true when at least one part is true, including when both are.

The last column is the one that departs from conversation. "Soup or salad" on a menu usually means one but not both. In mathematics "or" is always inclusive, and the sentences mathematicians write show why. The rule "if $ab=0$ then $a=0$ or $b=0$" must not exclude $a=b=0$, and "$n$ is divisible by $2$ or by $3$" is true of $6$. When the exclusive sense is wanted it is spelt out: "$P$ or $Q$ but not both", which is $(P\vee Q)\wedge \neg (P\wedge Q)$.

The negation of a statement is whatever is true in exactly the cases where the statement is false, and ordinary language often reaches for an opposite instead. The negation of "$x>3$" is "$x\le 3$", not "$x<3$": at $x=3$ both "$x>3$" and "$x<3$" are false, so the second cannot be the negation of the first. And "$x\le 3$" is itself a disjunction, "$x<3$ or $x=3$".

Negating a compound statement

Two compound statements are equivalent when they have the same truth value in every row of their truth table. Since the table lists every case, checking the rows is a complete proof. Note that $\neg (P\wedge Q)$, which denies the whole conjunction, is a different thing from $\neg P\wedge Q$, where $\neg$ applies only to $P$.

The most useful equivalences say how to negate an "and" or an "or". To deny that two things both hold is to say that at least one fails, and to deny that at least one holds is to say that both fail. These are De Morgan's laws, after Augustus De Morgan, who stated them in 1847, and they are what a proof needs whenever it must say what the failure of a condition looks like.

Example. Show that $\neg (P\wedge Q)$ and $\neg P\vee \neg Q$ are equivalent, and use this to negate "$x>0$ and $x<5$".

Compute both columns in each of the four rows.

The fourth and seventh columns agree in every row, so the two statements are equivalent. Now let $P$ be "$x>0$" and $Q$ be "$x<5$". The negation of $P\wedge Q$ is $\neg P\vee \neg Q$, and the negations of the parts are "$x\le 0$" and "$x\ge 5$". So the negation of "$x>0$ and $x<5$" is "$x\le 0$ or $x\ge 5$".

Now you. Show that $\neg (P\vee Q)$ and $\neg P\wedge \neg Q$ are equivalent, and use this to negate "$x<0$ or $x>1$".

The common error is to negate the parts and leave the connective alone. "Not ($x>0$ and $x<5$)" is not "$x\le 0$ and $x\ge 5$", which no number satisfies. Negating a compound always turns "and" into "or" or the reverse.

The conditional

The fourth connective is the conditional, $P\Rightarrow Q$, read "if $P$ then $Q$" or "$P$ implies $Q$". $P$ is the hypothesis and $Q$ the conclusion. The fifth is the biconditional, $P⟺Q$, read "$P$ if and only if $Q$", which is true when $P$ and $Q$ have the same truth value.

The first two rows of the conditional need no defence. "If $n$ is divisible by $4$, then $n$ is even" is kept by a number divisible by $4$ that is even, and would be broken by one divisible by $4$ that is odd: a true hypothesis with a false conclusion is exactly what it means for an implication to fail.

The last two rows are the ones that surprise. Whenever the hypothesis is false, the conditional is true, whatever the conclusion, so "if $2+2=5$, then $7$ is even" is a true statement. A conditional true because its hypothesis is false is called vacuously true. It looks like a convention, and slightly at odds with sense, but no other choice would let mathematics state its theorems.

Why a false hypothesis gives a true conditional

Take a theorem nobody doubts: for every integer $n$, if $n$ is divisible by $4$, then $n$ is even. It claims something about every integer, so it is true only if each instance, one conditional per integer, is true. At $n=8$ the instance has a true hypothesis and a true conclusion. At $n=6$ the hypothesis is false and the conclusion true. At $n=7$ both are false. If either of the last two instances counted as false, this theorem would be false, and so would nearly every theorem of the form "if ... then", since nearly any hypothesis fails for some values. Those rows have to be true for mathematics to be sayable at all.

Nothing else could go in them either. Making both rows false turns $P\Rightarrow Q$ into $P\wedge Q$, so the theorem would assert that $n$ is divisible by $4$. Making only the false-true row false turns it into $P⟺Q$, so the theorem would claim every even number is divisible by $4$, which $6$ refutes. Making only the false-false row false gives a column identical to $Q$, and the hypothesis would do nothing.

The conditional asserts no connection between its parts: "if $2+2=5$, then $7$ is even" is true though its halves are unrelated. In mathematics that costs nothing, because the connection is what the proof supplies. The table also tells a proof where to look. A conditional can fail only in the row where $P$ is true, so to prove $P\Rightarrow Q$ it is enough to assume $P$ and show that $Q$ follows, which is what the previous lesson did when it began "let $a$ and $b$ be odd".

That same row gives the negation. Since $P\Rightarrow Q$ is false only when $P$ is true and $Q$ false, its negation is $P\wedge \neg Q$. The negation of an implication is not another implication: it says the hypothesis holds and the conclusion fails, which is what a counterexample exhibits.

Example. Negate "if $n$ is prime, then $n$ is odd", decide whether the conditional is true for $n=2$, $n=9$ and $n=7$, and say what this shows.

The negation is "$n$ is prime and $n$ is even", since $\neg (P\Rightarrow Q)$ is $P\wedge \neg Q$. For $n=2$ the hypothesis is true and the conclusion false, so the conditional is false, and its negation is true: $2$ is prime and even. For $n=9$ the hypothesis is false, since $9=3\times 3$, so the conditional is vacuously true. For $n=7$ both parts are true and so is the conditional. The claim "every prime is odd" is therefore false, and $n=2$ is the counterexample: an integer at which the negation holds.

Now you. Negate "if $x>2$, then $x^2>4$", and decide whether the conditional is true for $x=3$, $x=-3$ and $x=1$.

Converse, inverse and contrapositive

Swapping and negating the parts of $P\Rightarrow Q$ gives three new conditionals: the converse $Q\Rightarrow P$, the inverse $\neg P\Rightarrow \neg Q$, and the contrapositive $\neg Q\Rightarrow \neg P$. Their tables settle which say the same thing as the original.

The contrapositive agrees with the original in every row, so the two are equivalent. The converse and inverse agree with each other and differ from the original in the middle two rows. So a proof of $\neg Q\Rightarrow \neg P$ is a proof of $P\Rightarrow Q$, which a later lesson turns into a method, while a proof of $P\Rightarrow Q$ says nothing about $Q\Rightarrow P$. Treating it as if it did is the commonest logical error in student proofs.

Example. Write the converse, inverse and contrapositive of "if $n$ is divisible by $6$, then $n$ is divisible by $3$", and decide which are true for every integer $n$.

The statement is true: if $n=6k$ for an integer $k$, then $n=3(2k)$, and $2k$ is an integer. The converse is "if $n$ is divisible by $3$, then $n$ is divisible by $6$", which is false, since $n=3$ is divisible by $3$ and not by $6$. The inverse is "if $n$ is not divisible by $6$, then $n$ is not divisible by $3$", and $n=3$ refutes it too, as it must, being equivalent to the converse. The contrapositive is "if $n$ is not divisible by $3$, then $n$ is not divisible by $6$", which is true because it is equivalent to the original.

Now you. For real numbers $x$, write the converse, inverse and contrapositive of "if $x>3$, then $x^2>9$", and decide which are true.

Necessary, sufficient and only if

When $P\Rightarrow Q$ holds, $P$ is a sufficient condition for $Q$: having $P$ guarantees $Q$. And $Q$ is a necessary condition for $P$: without $Q$ there is no $P$, which is the contrapositive read aloud. Divisibility by $6$ is sufficient for divisibility by $3$, and divisibility by $3$ is necessary for divisibility by $6$. These are one fact seen from its two ends.

"$P$ only if $Q$" also means $P\Rightarrow Q$. "Only" marks the necessary condition, which is the conclusion: "$n$ is divisible by $4$ only if $n$ is even" says divisibility by $4$ cannot happen without evenness. By contrast "$P$ if $Q$" means $Q\Rightarrow P$. The two are opposite, so together they make "if and only if": $P⟺Q$ is the same as $(P\Rightarrow Q)\wedge (Q\Rightarrow P)$, a condition both necessary and sufficient. That is why proving an "if and only if" takes two proofs, one per direction.

One convention catches every newcomer. Definitions are written with "if", as in "an integer $n$ is even if $n=2k$ for some integer $k$", but a definition is always read as "if and only if". The previous lesson used its definitions in both directions, producing a $k$ from an even number and concluding evenness from a $k$, and was right to.

What connectives cannot say

The five connectives are now fixed, and the negation of each compound can be written down mechanically. Yet the argument for the conditional's table used something no connective contains. "For every integer $n$, if $n$ is divisible by $4$, then $n$ is even" is not a conditional between two statements, since "$n$ is divisible by $4$" is an open sentence; the phrase "for every integer $n$" is what made the whole a true statement. Refuting "every prime is odd" needed the opposite phrase: there is a prime that is even. Nearly every theorem is about all numbers or some number, and neither "all" nor "some" can be built from the five connectives. The next lesson adds them, with rules for negating them that turn "not every" into "some fails".