A Closer Look at the Implication

Out of the two conditional-style connectives we’ve seen — the implication $p \to q$ and the biconditional $p \leftrightarrow q$ — we’ve given the biconditional a fairly thorough treatment already. Now we turn back to the implication, to see what else it has to offer.

Recall from its definition that the implication $p \to q$ is false exactly when $p$ is true and $q$ is false. In other words, $\text{true} \to \text{false}$ is a false proposition. This deserves special emphasis:

The reason $\text{true} \to \text{false}$ is a false proposition is that we don’t want true statements leading to false ones in a logical system.

Components of an Implication

Before going any further, it’s worth giving names to the two propositions that make up an implication.

The hypothesis is the proposition we’re assuming to be true; the conclusion is what we’re claiming follows once that assumption holds. This is exactly the vocabulary we need to describe the table above in plain English: an implication is false only when its hypothesis is true but its conclusion is false. Whenever the hypothesis is false, we get to declare the implication true no matter what the conclusion happens to be — there’s nothing false about the implication if the assumption driving it never held in the first place.

We’ll lean on this vocabulary constantly going forward, so it’s worth getting comfortable with it now, before we start examining implications more closely.

Trvially True Implications

Curiously, we consider both $\text{false} \to \text{false}$ and $\text{false} \to \text{true}$ to be true propositions. This is because if we start with a false hypothesis, the truth of the conclusion is irrelevant.

Variations on the Implication

There are some simple ways we can change around an implication. Exactly how we make these changes affects how the new implication we form is related to our original starting implication. In this section, we look at three such variations — the converse, the inverse, and the contrapositive — and see how each one relates back to the implication we started with.

The Converse, Inverse, and Contrapositive

The first two modifications are relatively straightforward.

Basically, the converse is obtained by swapping the two statements on either side of the arrow $\to$. The inverse is obtained by negating both statements on either side of the arrow $\to$.

Of course, we can apply both transformations at the same time. There’s a special name for that transformation as well.

As always, an example in plain English will illuminate some key aspects of these kinds of propositions.

Yet again, this is worth highlighting.

Since we’ve figured out that an implication is logically equivalent to its contrapositive, we could have deduced that the converse and inverse are logically equivalent just by noticing that the inverse is the contrapositive of the converse (and vice versa).

Logical Implications

So far, we’ve studied what an implication means on its own, and how it relates to variations like its converse, inverse, and contrapositive. Now we turn to a special kind of implication — one that’s true no matter what truth values its hypothesis and conclusion happen to take on. These implications are especially useful, since knowing one holds lets us deduce its conclusion with total certainty the moment its hypothesis is satisfied.

We already know, from the Law of Material Implication, that $p \to q$ is logically equivalent to $\neg p \lor q$. Before moving on, it’s worth building some intuition for why that’s true, and seeing what it buys us.

Building Intuition for the Material Implication

Keeping this equivalence in mind makes negating an implication far less error-prone. As a reminder, from the Simplifying Logical Expressions section, we already worked out that

which lines up with what we’d expect: an implication is false exactly when $p$ is true and $q$ is false.

It’s worth emphasizing why parentheses matter here. An expression such as $\neg p \to q$ is shorthand for $(\neg p) \to q$ — the negation $\neg$ is the most tightly-binding operation in an expression, so it only applies to $p$, not to the whole implication. This is a very different statement from $\neg (p \to q)$, as the truth table below makes clear.

Any doubts about how an expression should be parsed can always be put to rest by adding parentheses of your own.

Tautologically True Implications

There’s a special name for these kinds of implications.

Based on the previous example, where we saw that $(a \land (a \to b)) \to b$ was a tautology, we can use this new notation and write

Quantified Logical Implications

Now that we’ve taken a closer look at the implication itself, let’s revisit quantified statements to see how the same ideas — logical implication, and the converse, inverse, and contrapositive — carry over to them.

A Simple Logical Implication

Suppose we have some open statement $p(x)$ with some non-empty universe $\mathcal{U}$ (non-empty just means $\mathcal{U}$ contains at least one element, which we can refer to as $\alpha$).

What can we conclude if we know that the statement $\forall x\ [p(x)]$ is true — that is, we know $\forall x\ [p(x)] = 1$?

One thing we can conclude is that if $\alpha \in \mathcal{U}$ (meaning $\alpha$ is some element found within the universe $\mathcal{U}$), then $p(\alpha) = 1$. Since some value of $x$ exists that makes $p(x) = 1$, we can conclude that $\exists x\ [p(x)] = 1$.

Does this work the other way? That is, does knowing that $\exists x\ [p(x)]$ is true mean that $\forall x\ [p(x)]$ is true? Certainly not — knowing that some value exists that makes $p(x) = 1$ is not the same thing as knowing that every value of $x$ within $\mathcal{U}$ makes $p(x) = 1$.

This leads us to our first logical implication:

As a reminder, $\forall x\ [p(x)]$ is a single statement with a definite truth value — it’s not an open statement or a propositional function. The statement being expressed is that “every value of $x$ within $\mathcal{U}$ makes $p(x)$ true.” Likewise, $\exists x\ [p(x)]$ is also a single statement, which can be translated as “there exists at least one value of $x$ that makes $p(x)$ true.”

Another way to state this is to say that $\forall x\ [p(x)] \to \exists x\ [p(x)]$ is a tautology, where $\forall x\ [p(x)]$ is the hypothesis of the implication, and $\exists x\ [p(x)]$ is the conclusion.

A Simple Definition

Just like with ordinary statements, we can ask whether one open statement logically implies another.

Conjunction, Disjunction, and Quantifiers

Recall from the previous chapter that the existential quantifier distributes over disjunction, and the universal quantifier distributes over conjunction:

We also saw that the other pairing — the existential quantifier with conjunction, and the universal quantifier with disjunction — doesn’t distribute the same way. Now that we have the language of logical implication, we can pin down exactly what does survive in those two cases.

Suppose $\exists x\ [p(x) \land q(x)]$ is true. Then some value $a$ within $\mathcal{U}$ makes $p(a) \land q(a)$ true, which means $p(a)$ is true and $q(a)$ is true individually. Since $a$ makes $p(x)$ true, $\exists x\ [p(x)]$ is true; since $a$ also makes $q(x)$ true, $\exists x\ [q(x)]$ is true. So both $\exists x\ [p(x)]$ and $\exists x\ [q(x)]$ are true, meaning $\exists x\ [p(x)] \land \exists x\ [q(x)]$ is true as well. This holds no matter what $p(x)$ and $q(x)$ are, so

By a similar argument, suppose $\forall x\ [p(x)] \lor \forall x\ [q(x)]$ is true. Then at least one of $\forall x\ [p(x)]$ or $\forall x\ [q(x)]$ is true. If $\forall x\ [p(x)]$ is true, then every value of $x$ within $\mathcal{U}$ makes $p(x)$ true, which certainly means every value of $x$ makes $p(x) \lor q(x)$ true as well — so $\forall x\ [p(x) \lor q(x)]$ is true. The same reasoning applies if instead $\forall x\ [q(x)]$ is the true one. Either way,

The Converse, Inverse, and Contrapositive of Quantifiers

Just like how the statement $p \to q$ has a converse, inverse, and contrapositive, so does the universally quantified statement $\forall x\ [p(x) \to q(x)]$.

Just as an ordinary implication is logically equivalent to its contrapositive, a quantified implication is logically equivalent to its contrapositive. Furthermore, the converse and inverse of a quantified implication are logically equivalent to each other.

Arguments

The heart of mathematics is not mere computation, but the act of taking a combination of known facts and combining them in some way to arrive at new conclusions. Think back to when you learned the Pythagorean Theorem or the Quadratic Formula. It’s certainly true that these tools help you compute things — the hypotenuse of a right triangle, or the roots of a quadratic function — but that’s a computational activity.

Without the Pythagorean Theorem or the Quadratic Formula, how would we go about computing those quantities in the first place? There may be other methods available, but those two tools in particular are extremely helpful — and the reason they exist is that someone took what was already known about right triangles and quadratic expressions, and arrived at the now-famous results. The difference between doing mathematics and computing is a little like this: mathematics is knowing that for all right triangles, where the legs have lengths $a$ and $b$, and the hypotenuse has length $c$, we have

computation is figuring out that a right triangle with leg lengths $5$ and $12$ has a hypotenuse of length $13$ using the Pythagorean Theorem.

In order to know anything in mathematics, we start with what’s currently known, and extrapolate from that prior knowledge. We call this providing an argument, or a proof. In this section, we examine the basic structure of such an argument.

Premises and Conclusions

Let’s elaborate on the idea of using existing knowledge. We essentially take a collection of known facts together, and their combination provides some new fact:

Notice that we combine several facts using the word “and.” All the facts are supposed to come together in order to create the new fact — if any fact could be left out, then it wasn’t needed. This is the same situation we had with the conjunction $\land$: every proposition attached to a conjunction has to be true in order for the conjunction itself to be true.

Let’s rewrite the representation above using mathematical notation, where $p_1$ represents known fact #1 (a fact is just another term for a proposition), $p_2$ represents known fact #2, and so on through $p_n$ for known fact #$n$, with the letter $c$ denoting the new fact:

Notice that this definition doesn’t require the premises to be primitive propositions — each premise can be primitive, or it can be some long, complicated compound proposition. What matters is that we combine all of the premises into a conjunction.

Valid Arguments

The previous example demonstrates something important about arguments: an argument asserts that, when all premises are true, the conclusion is also true. If there’s a scenario where all premises are true but the conclusion isn’t, then that argument doesn’t accurately reflect when the conclusion is true.

In order for an argument to accurately reflect when its conclusion is true, the conclusion must be true whenever the premises are true — otherwise, the argument is simply wrong.

On the other hand, we don’t care what happens when any of the premises are false. An argument only tells us that if all premises are true, then so is the conclusion — it’s irrelevant when any premise is false.

Mathematics is all about developing valid arguments, because these arguments form the base of the knowledge we have. Arguments give us a way to come up with new and efficient ways to perform computations, make classifications, or establish any other kind of equivalency.

Rules of Inference

We’ve already seen that, with ever-larger numbers of component propositions, a truth table requires more and more rows to complete — and that logical equivalencies let us simplify compound propositions without needing a truth table at all.

We can bypass truth tables when determining whether an argument is valid too. Instead of logical equivalencies, though, we use logical implications. In this section, we collect a list of commonly occurring logical implications, and see how to use them strategically. We’ll still verify each one with a truth table — the point here is just to build up a list of implications we can use later.

Two Straightforward Implications

We introduce the first logical implication with an example.

We can verify this more formally with a truth table (representing $p$ as premise $p_1$, the proposition $p \to q$ as premise $p_2$, and the conclusion $q$ using the letter $c$): the column for $[p \land (p \to q)] \to q$ is entirely $1$s, so

In other words, whenever we know $p$ is true, and $p \to q$ is true, then $q$ is true as well. As such, the argument $[p \land (p \to q)] \to q$ is valid. It’s common to write this kind of argument out in tabular form: we list all the premises in a single column, add a horizontal line, and write the conclusion below it, with a $\therefore$ symbol (read “therefore,” or “thus”) to its left:

Also note that because $\land$ is commutative, we could just as well present this argument with its premises in the other order:

This kind of argument is commonly referred to as Modus Ponens.

There’s another kind of valid argument closely related to Modus Ponens. Again, we demonstrate it with an example first.

A truth table confirms that $[(p \to q) \land \neg q] \to \neg p$ is indeed a tautology, so

The argument

is valid, as is the same argument with its premises swapped. This argument is commonly referred to as Modus Tollens. Both Modus Ponens and Modus Tollens have $p \to q$ as a premise — in some sense, Modus Tollens is the “contrapositive” of Modus Ponens.

Chains of Logical Implications

The argument

is valid — we already confirmed this in the previous section, where we showed $[(x \to y) \land (y \to z)] \to (x \to z)$ is a tautology. This argument is commonly referred to as the Law of the Syllogism.

Because $\land$ is commutative, the premises of any argument can be swapped and the argument remains valid — a fact we won’t keep explicitly mentioning, though it will be used implicitly throughout our work.

Naturally, we can chain more and more propositions together at the end of each premise’s implication. Here’s an example involving five propositions:

An Easy Logical Implication

Not all of the arguments at our disposal are profound — some may seem quite obvious. For instance, suppose we know proposition $p$ is true, and proposition $q$ is true. Since they’re both true, we also know their conjunction $p \land q$ is true. The argument

is valid, and is called the Rule of Conjunction. Why care about an argument this simple? Because as we develop more sophisticated arguments, propositions $p$ and $q$ may come up — either as premises, or as results derived from other premises. When this happens, $p$ and $q$ can be combined into a conjunction, and that conjunction can be used to further develop the argument, as we’ll see used strategically in the next section.

A Logical Implication to Eliminate Choices

As this example demonstrates, if we know at least one of two propositions $p$ and $q$ is true, but that one of them (say $q$) is false, then the other must be true — otherwise the disjunction would have been false. The argument

is valid, and is called the Rule of Disjunctive Syllogism. A truth table readily confirms this.

A Logical Implication Based on Contradictions

Suppose we’re given some proposition $p$, and want to determine whether $p = 0$ or $p = 1$. One thing we could try is to assume $p = 0$ (meaning $\neg p = 1$). If assuming $p = 0$ yields a contradiction $F_0$, then surely $p \neq 0$, since true statements should never yield contradictions — hence we must have $p = 1$. The argument

is valid, and is called the Rule of Contradiction. Since there’s only one premise, $\neg p \to F_0$ (a proposition that’s just $\neg p \to 0$, replacing the general contradiction $F_0$ with its truth value), there’s no conjunction operator present. A truth table confirms the argument $(\neg p \to F_0) \to p$ is valid.

A Big List of the Rules of Inference

We’ve presented five different kinds of arguments so far. These arguments are commonly referred to as rules of inference, because they let us infer, or deduce, a conclusion given a list of premises. There are many more such rules; we present a sample of them below.

Rules of Inference $\neq$ Logical Equivalencies

Before seeing how these rules of inference can be used, it’s worth taking a step back to see what we’ve accomplished — but perhaps more importantly, what we have not accomplished.

Notice that each rule of inference above is a logical implication — demonstrated by the fact that we used the single arrow $\Longrightarrow$, rather than the double arrow $\Longleftrightarrow$. While some of the arguments above may happen to contain logical equivalencies (such as the Rule of Conjunction), most of these are not logical equivalencies.

For instance, examining the Law of the Syllogism, we have

However, note that when $p = r = 0$ and $q = 1$, we have $(p \to q) = 1$, $(q \to r) = 0$, and $(p \to r) = 1$, but $(p \to q) \land (q \to r) = 1 \land 0 = 0$. Hence,

As such, we have not shown that the expression $(p \to q) \land (q \to r)$ can be replaced with the simpler expression $p \to r$. This is a subtle difference, but an important one.

We’ll see in the next section that both logical equivalencies and logical implications can be used to develop arguments — but logical implications won’t be helpful when trying to simplify complicated logical expressions.

Using the Rules of Inference

In the previous section, we collected a large sample of commonly occurring logical implications. We briefly touched on why we’d want such a list — to determine whether a given argument is valid. In addition to determining validity, we can also use the rules of inference to make valid deductions from a given list of premises.

In this section, we work through several examples of both use cases.

Determining an Argument’s Validity

Suppose we’re presented with some argument: a list of premises, and a desired conclusion. We can determine if the argument is valid by appealing to the rules of inference.

It seems a bit cumbersome to write out our logic in paragraphs like this. Just like we did when showing two compound propositions were logically equivalent, we can write out a sequence of steps in tabular form.

There are many rules of inference, so we may be able to validate a given argument in multiple different ways.

Going forward, when we write out these tabular arguments, we’ll omit the word “Steps,” and just write out which numbered step is being used in a rule of inference — this will save us a bit of writing. It’s also worth pointing out that since some propositions are given as premises, they require no justification beyond noting they’re premises of the argument.

Some arguments require multiple rules of inference to determine validity.

In the previous example, step (5) made use of a logical equivalency between contrapositives. As we work through an argument, we can introduce logically equivalent propositions whenever we want — so we should make use of this as much as possible.

Making Valid Inferences

When determining whether an argument is valid, we’re given a list of premises and a conclusion, and we write out our justifications in tabular form, with the conclusion as the table’s last entry. Theoretically, we could do the same thing even without being given a conclusion — we just wouldn’t have a “goal” to reach. We could apply whatever rule of inference seems appropriate to the given premises, and to any previous conclusions reached from them.

Note that once you use a rule of inference on a given list of premises, you’re making a valid argument — every intermediate step in the previous section’s longer example produced a valid argument, since each was constructed by means of a rule of inference.

One more strategy we could use is a truth table, to see what combinations of truth values for the propositions yield true premises.

It’s good practice to try and come up with a sequence of inference rules to reach these kinds of conclusions without going through a truth table.

Logically Equivalent Arguments

Fundamentally, an argument is nothing more than a logical implication — a hypothesis (a conjunction of multiple premises) and a conclusion.

We’ve already seen that it’s possible to construct logically equivalent propositions using the laws of logic. Since an argument is fundamentally a proposition based on an implication, it should be possible to construct a different argument that’s logically equivalent to a given one. In some cases, this new, equivalent argument may be easier to verify than the original — which is exactly why it’s worth investing time in constructing logically equivalent arguments in the first place.

Proof by Contradiction

The general structure of an argument is

meaning we’re only considering cases where each premise $p_1$ through $p_n$ is true.

If we take the propositional form of this argument with just one premise, we get $p_1 \to c$. We’d need $c = 1$ for this implication to be true — but this is logically equivalent to $\neg p_1 \lor c$. We can extend this a bit further:

So, if $p_1 \to c$ is a valid argument, then $\neg (p_1 \land \neg c)$ is a true proposition. This means it would be impossible to have both $p_1 = 1$ and $c = 0$ — that is, both $p_1 = 1$ and $\neg c = 1$ — since that would be a contradiction. In other words, we get the argument $(p_1 \land \neg c) \to F_0$.

This is where this proof strategy gets its name: for a valid argument, assuming the negation of the desired conclusion produces a contradiction. Since the negation of the conclusion must therefore be false, the conclusion itself must be true.

A truth table confirms that $(p_1 \to c)$ and $[(p_1 \land \neg c) \to F_0]$ are logically equivalent — meaning the arguments themselves are equivalent, since arguments are just implications. So, establishing that one of these is valid means the other is valid too.

Chains of Implications

Suppose we knew the argument

was valid. Since $p = 1$, we know $q \to r = 1$. But now suppose we also knew $q = 1$: since $q \to r = 1$ and $q = 1$, we’d have $r = 1$ as well. Notice that since $p = 1$ and $q = 1$, we have $p \land q = 1$. Writing this out as a proposition, we get $p \to (q \to r)$ — and since having both $p$ and $q$ necessarily gives us $r$, this becomes the argument $(p \land q) \to r$.

This suggests that the argument $p \to (q \to r)$ is logically equivalent to the argument $(p \land q) \to r$. A truth table confirms this suspicion: the biconditional $[p \to (q \to r)] \leftrightarrow [(p \land q) \to r]$ is a tautology, meaning we have a logical equivalency between the two arguments. Just as before, establishing the validity of one automatically establishes the validity of the other.

Invalid Arguments

All of us have, at one point, been presented with an argument that doesn’t seem quite right. Just because someone can string together a group of premises and assert some conclusion doesn’t mean that conclusion actually follows from the premises.

Remember that an argument is valid if the argument’s implication is a logical implication — meaning that no matter what truth values the argument’s propositions have, the overall implication always evaluates to $1$. This means that if we can come up with even one truth value assignment reducing to the form $1 \to 0$, the argument isn’t valid. In other words, for any argument $(p_1 \land p_2 \land \dots \land p_n) \to c$ with $c = 0$ (and all premises true), the argument is invalid.

Here, we’ll examine some of the most common fallacies made when constructing an argument, and how to detect when a given argument is invalid.

Argument by the Converse

Consider the argument

with premises $p_1 : p \to q$, $p_2 : q$, and conclusion $c

p$. Remember that for an argument, we assume $(p_1 \land p_2) = 1$, meaning we need both $p_1 = 1$ and $p_2 = 1$.

Since $p_2$ is just $q$, we assume $q = 1$. Now we need $p_1 = 1$, meaning $p \to q = 1$. Since $q = 1$, this holds whether $p = 0$ or $p = 1$. But if $p = 0$, our conclusion $c = p$ has truth value $0$. Since we can simultaneously make $(p_1 \land p_2) = 1$ and $c = 0$, this argument is invalid.

This is sometimes referred to as an argument by the converse.

Before showing another invalid argument, it’s worth comparing this invalid argument to the closely related, but actually valid, Modus Ponens argument:

In Modus Ponens, $p$ is a premise, while $q$ is the conclusion. In the argument by the converse, $q$ is a premise, while $p$ is the conclusion. Even though these arguments look similar, it’s important not to get them mixed up.

Argument by the Inverse

Consider the argument

with premises $p_1 : p \to q$, $p_2 : \neg p$, and conclusion $c : \neg q$. Rather than working out truth values by hand, we can use a truth table: there’s a row where both premises are true — $p = 0$, $q = 1$ — but the conclusion $c$ is false. Hence, the implication $[(p \to q) \land \neg p] \to \neg q$ isn’t a tautology, meaning it isn’t a logical implication:

So, this is sometimes referred to as an argument by the inverse. Again, it’s worth comparing this invalid argument to a valid one it resembles:

Pay attention to the second premise in each: Modus Tollens uses $\neg q$, while the argument by the inverse uses $\neg p$.

While Modus Ponens and Modus Tollens can safely be used to determine an argument’s validity, an argument by the converse or the inverse produces a fallacy in reasoning. Even if a given argument happens to be valid, any justification for it that relies on one of these two invalid forms will be incorrect.

A Strategy for Invalidating an Argument

In the previous example, none of the rules of inference we knew about looked like they’d help us reach the desired conclusion, so we suspected the argument wasn’t valid. Constructing a truth table let us see truth value assignments that lead to a false implication.

We invalidate an argument by providing a counter example to it. Note that providing an assignment that makes the argument’s implication true does not prove the argument valid — to show an argument is valid, we have to make sure that every truth value assignment making all premises true also makes the conclusion true. This isn’t the case for invalidating an argument — one counter example is all that’s needed.

However, depending on the number of underlying propositions involved, we may want to avoid constructing a full truth table. We can still work out truth value assignments directly, just by ensuring all premises evaluate to $1$ when the conclusion evaluates to $0$.

Notice what we did in the previous example: we started off by choosing values for the propositions that would make the conclusion false, then used those values to try to choose values for the other propositions that make the premises all true.

Sometimes, we may have choices for the truth values we assign to propositions — if that’s the case, there’s nothing wrong with experimenting to see whether all premises can be made true while the conclusion stays false.

If we’re unable to make all premises true while holding the conclusion false, the argument may actually be valid — after all, if no counter example exists, the argument has to be valid. At that point, it may be worth trying to use the rules of inference to validate the argument. Similarly, if assuming values that make the conclusion false yields a contradiction, the argument might be provable by way of a proof by contradiction.

As discussed in the previous section, the validity of an argument implies the validity of any equivalent argument. By that same token, an argument being invalid also means any logically equivalent argument is invalid — so invalidating an equivalent argument is another way to invalidate a given argument.

Universal Specification

Throughout our discussion of arguments so far, we haven’t made use of any quantified statements — though we devoted several sections to quantifiers in the previous chapter, so we certainly got some mileage out of them there. Here, we start to discuss how quantified statements can be used in arguments.

The reason we want to do this is that many of the results we’re going to come across are stated in the language of quantifiers. For example, consider the Pythagorean Theorem:

Notice that implicit in this statement is the universal quantifier “if any.” We could write the Pythagorean Theorem using our current mathematical symbology as follows:

The Pythagorean Theorem works for every single conceivable right triangle in the plane — not just some specific kind, but every single one. That’s the power of the theorem: it lets us compute a side length of any right triangle when the other two are known. Since scientists, engineers, architects, and mathematicians all need to calculate lengths of triangles constantly, this theorem has come in handy very often. It would be near-useless if it only applied to one triangle, like a $3$-$4$-$5$ triangle — it wouldn’t be nearly as widely known or applicable as it is today.

This is why we care about quantifiers: they let us extend results beyond a single example to potentially infinitely many of them. So much of what’s calculable in engineering, science, and mathematics is possible only because the underlying theorems are so extensive — and that’s precisely because they’re quantified.

Here, we discuss Universal Specification, one way to use quantifiers in arguments that lets us go from broadly true statements to specifically true statements.

Motivating Examples

The Rule of Universal Specification

Thinking back to the previous examples, the general strategy was to figure out what classifications were in use, then figure out which classification an object belonged to. Once we knew an object’s category, we knew it had a certain property, since that property was shared by every object in the category.

This is the formal statement of what we were trying to say in the previous three examples. When we spoke of “categories” or “kinds,” we were dealing with inclusion within the universe $\mathcal{U}$ — an element $c$ belonging to the category is the same thing as saying $c \in \mathcal{U}$; not belonging is $c \notin \mathcal{U}$ (read “not a member of,” or “not an element of” — analogous to the inequality $\neq$ symbol).

The next part of this rule is to notice there’s an implicit implication: $c \in \mathcal{U} \to p(c) = 1$. So, if $c$ is an element of the universe, then $p(c)$ is true. But if $c$ is not an element of the universe, we don’t know whether $p(c) = 0$ or $p(c) = 1$, because either way, the implication is trivially true. The argument

is valid. Just like with the other rules of inference, this is a valid rule usable in the analysis of a mathematical argument. The intuition is that if every member of a group satisfies some property, then picking any element from that group means the chosen element satisfies that property too.

Universal Specification and Modus Ponens

With the quantified statement $\forall x \in \mathcal{U}\ [p(x)] = 1$, $p(x)$ may represent a primitive statement, or a compound one. Very often, $p(x)$ represents an implication — for example, if $p(x)$ represents $a(x) \to b(x)$, we could rewrite the quantified expression as $\forall x \in \mathcal{U}\ [a(x) \to b(x)] = 1$.

The argument

is valid — a combination of Modus Ponens and the Rule of Universal Specification, for any open statements $a(x)$ and $b(x)$ defined on some universe $\mathcal{U}$.

Universal Specification and Modus Tollens

If we can combine the Rule of Universal Specification with Modus Ponens, surely we can combine it with Modus Tollens too.

Notice that we listed $d \in D$ as a premise, even though it wasn’t explicitly one of the argument’s premises — inclusion in the universe is often an implicit assumption, since analyzing an object not in the universe wouldn’t tell us anything useful.

It’s also worth pointing out that even though one of the premises is a quantified statement, we’re able to extract a non-open statement from it using the Rule of Universal Specification: $s(d) \to t(d)$ is not an open statement, because both $s(d)$ and $t(d)$ have definite truth values, since $d$ is a specified member of $D$, not a placeholder like $x$.

The argument

is valid — combining the Rule of Universal Specification with Modus Tollens. In both cases, once we have a non-open statement, we can use any of the other rules of inference we’ve learned — we’re not limited to Modus Ponens and Modus Tollens.

Arguing by the Converse and Inverse

The argument

is invalid, since it combines argument by the converse with the Rule of Universal Specification. Likewise, the argument

is invalid, combining argument by the inverse with the same rule.

One should be careful when analyzing arguments — just as arguing by the converse or inverse is a fallacy without quantified statements, it’s equally fallacious with them.

Universal Generalization

In the previous section, we talked about a rule of inference that lets us go from broadly true statements to specifically true statements — if something is true for every member of a universe, we can pick out any element from that universe and be assured it still has whatever property we’re interested in.

Up to now, none of the arguments we’ve examined have had a universally quantified statement as a conclusion — meaning none of our conclusions could have been generalized. Most results in mathematics are stated in general terms, not specific ones. The Pythagorean Theorem applies to every right triangle, not just isosceles ones, or ones with integer side lengths. The Quadratic Formula doesn’t apply only to $x^2 + 2x + 1 = 0$, or only to $x^2 - 6x + 9 = 0$ — it works even when the leading coefficient isn’t $1$, or when all the coefficients are irrational, or when the corresponding parabola doesn’t even intersect the $x$-axis.

Here, we’ll see what it takes to have a universally quantified statement as the conclusion of an argument. With this, we’ll finally be able to start noticing patterns and formulating results — in other words, to start engaging in mathematics!

A Motivating Example

Let’s dissect this example. What we’re essentially trying to do is determine a weakness for each monster — exploiting it lets us fell that monster and save the kingdom. Mathematically, we’re trying to show

where the universe of discourse is all monsters invading the kingdom, $x$ represents a monster in that universe, and $d(x)$ is the open statement “monster $x$ was successfully defeated.”

We used $M$ to denote the universe — we know there are four types of monsters, but not the total number. We picked an arbitrary monster (the phrase “any monster” is our clue that the choice is arbitrary) and identified a trait it had: it was made of matter. Since we picked an arbitrary monster, we couldn’t rely on it having a hungry stomach (an eyeball monster or robot might not have one), nor could we rely on it having exposed eyes sensitive to light (a lion-shaped monster or robot might not). It was important to pick a trait all the monsters share, since we’re trying to defeat all of them, not just some kind.

This is the power of universal generalization: if we pick an arbitrary element from the universe, and only use traits common to every single element, then whatever we do with that arbitrarily chosen element applies to all elements. Since we only relied on properties shared by everyone, the same procedure can be replicated for every element of the universe.

Exhaustive Checking

Notice that nowhere in the monster example did we discuss going around and checking each and every specific monster for a weakness. One reason is that the exact number of monsters was never disclosed — there could have been $10$, in which case checking each one wouldn’t be burdensome. There could have been $100$, which would be tedious but manageable. If there were $10{,}000{,}000$, checking each one individually would take an extremely long time. If there were infinitely many, checking each one would be flatly impossible.

This is why we tried to find a weakness shared by all the monsters — no matter how many there are, they should all have something in common that can be exploited. To hammer the point, imagine working with all of the whole numbers instead of monsters — there are infinitely many, so we can’t simply check each one against some condition. We need to rely on properties shared by all whole numbers, not just some of them.

The Rule of Universal Generalization

The ultimate goal of this section is to establish the truth of statements of the form $\forall x\ [p(x)]$ — that is, to show $p(c)$ is true for every $c$ within the prescribed universe of discourse $\mathcal{U}$. But as described above, we may not always be able to simply examine each element $c$ within $\mathcal{U}$: if it contains many elements, checking each one can be incredibly burdensome, and if it contains infinitely many, it’s literally impossible. This is why we need some property that every element of $\mathcal{U}$ has.

In the monster example, we picked an arbitrary element and only relied on properties every single member of the universe had as well — so what we did with that arbitrarily picked element applies to all elements. Whatever we discover to be true about it must also be true of every element in the universe.

The following examples use the concepts of even and odd integers. Most readers are familiar enough with what these are already, so we’ll refrain from giving a formal definition just yet (one will follow in the next section) — the lack of one here shouldn’t be a hindrance.

So far, our use of the Rule of Universal Generalization has been intuitive — we haven’t explicitly shown how to use it within an argument.

Using the Rule of Universal Generalization in Arguments

Once again, let’s take a step back. In the monster example, we thought of a trait shared by all monsters (a universal quantifier), and concluded that all monsters would be defeated (another universal quantifier). In the even-integer example, we made use of multiple properties shared by all integers, building a chain that led to a final conclusion — much like the Law of the Syllogism. In both cases, we had premises that were universally quantified.

Let’s start simple, with two premises:

Is this argument valid?

This argument — which we might call the Universally Generalized Law of the Syllogism — is valid. Pay particular attention to step (2): here, we clearly specify that $c$ is an arbitrary element of $\mathcal{U}$, meaning whatever is true of $c$ is true for every element of $\mathcal{U}$. This is what allows us to use the Rule of Universal Generalization at the end.

If we had instead assumed $n$ was specifically an odd integer in the earlier examples, we could not have used the Rule of Universal Generalization, since what’s true of all odd integers isn’t necessarily true of all even integers — an assumption like that isn’t arbitrary. The rule only applies when an element is arbitrarily chosen.

Just like the Law of the Syllogism, many implications can be chained together.

Many of the rules of inference can be adapted into universally generalized versions with some care — these will prove vital not just in the rest of this chapter, but throughout all of mathematics. One strategy for universally generalizing a rule of inference is to use the Rule of Universal Specification to get an arbitrary element from the universe, then apply the Rule of Universal Generalization on that arbitrary element.

Assumed Premises

Let’s re-examine the argument for the Universally Generalized Law of the Syllogism:

The conclusion involves an implication of the form $p(x) \to r(x)$. What happens if we pick an element $c$ from $\mathcal{U}$ where $p(c)$ is false? Then $p(c) \to r(c)$ becomes trivially true — but this defeats the entire purpose of the argument. We only want to deduce true statements from true statements. If any premise were false, the whole argument would reduce to a trivially true implication, and the point of proposing it becomes moot.

This is why, if the conclusion of a proposed argument contains an implication, the hypothesis of that conclusion can be assumed true, and used as a premise of the argument. These are often referred to as assumed premises. When the conclusion is a universally quantified implication, we can assume the truth of the hypothesis on an arbitrarily picked element, as in the example below.

It’s worth mentioning that step (13) used the logical implication $(x \land y) \Longrightarrow (x \to y)$. This can be verified with a truth table, but notice that it’s a valid argument by itself, so we can use it as a reason in other arguments — remember, all the rules of inference are just specific valid arguments.

With this final rule, we’re now ready to start delving into the heart of mathematics!

Axioms, Definitions, Theorems, and Proofs

Over the past two chapters, we’ve been building up a system of mathematical logic — what propositions are, how to determine their truth, when two propositions are equivalent, and how to use propositions in arguments to make valid deductions.

However, this isn’t how most of mathematics is communicated. Most of us understand math in terms of numbers and geometric shapes: arithmetic, algebra, trigonometry, lines and angles, polygons and circles, graphs and equations. What we’ve done so far looks very different. What gives?

The reason we spent so much time getting a grip on mathematical logic is that mathematics is fundamentally about using known facts (propositions) to deduce new facts (valid arguments). We’ve talked about the Pythagorean Theorem in numerous introductions, and asked how we know it’s true — it wasn’t inscribed on a stone tablet and sent down for all to see. Someone had to figure it out.

Moving forward, we’re going to be deducing new facts from old facts, all having some mathematical interest. Everything we do will rest on the logic we’ve learned so far, though the structured use of that logic will usually stay implicit rather than being explicitly pointed out — the tools are there to fall back on whenever we’re unsure about the soundness of a piece of reasoning. From this point forward, our examples will be mathematical in nature, rather than concerned with people and the situations they find themselves in.

Axioms, definitions, theorems, and proofs are the main tools of mathematics — they’re what we use, and what we produce. Let’s begin!

Defining Definitions

In everyday language, it’s common to speak with conditionals — but everyday language isn’t precise. People tend to use implications when speaking, even when what they mean is really a biconditional.

When writing mathematics, it’s imperative to be as precise as possible. If what you want to state involves a biconditional, you should use the double-ended arrow $\leftrightarrow$ — it’s almost never appropriate to use the implication arrow $\to$ when a biconditional is meant.

The exception is definitions. The purpose of a definition is to assign a meaning, idea, or concept to a single word — so it’s usually fine to state definitions in terms of implications. Suppose we want to define some new word, and assign it some definition. The most accurate way to convey that meaning is

Remember that for any two propositions $p$ and $q$, we have $p \leftrightarrow q \Longleftrightarrow (p \to q) \land (q \to p)$. So, instead of saying $\textit{word} \leftrightarrow \textit{definition}$, we’re fine saying $\textit{word} \to \textit{definition}$ or $\textit{definition} \to \textit{word}$ — even though an implication is used, what’s really meant is the biconditional.

Here, we present some mathematical words and definitions you’re likely already familiar with, presented just for completeness.

Notice that in this definition, we wrote the propositions out in English rather than assigning them a single letter. Also note that we wrote “and only if” in parentheses — that’s to stress that a definition is really a biconditional. Going forward, it’s usually fine to say just the “if” part, since the biconditional is what’s meant either way.

It may seem excessive to go over the details of how even and odd integers are defined — the point isn’t to teach what they are, but to show how much nuance even a simple definition can carry. Notice that our definition of even really has three requirements: $n$ must be an integer, $n = 2k$ for some number $k$, and $k$ must be an integer. If any one of these fails, we can’t describe $n$ as even. Three analogous requirements apply to odd. All definitions in mathematics work this way — they assert conditions that must be satisfied before the associated word can be applied.

In order for the word “parity” to be applied, we need two integers to begin with — if either isn’t an integer, the word doesn’t apply. Using a more notational style: with $p(a, b)$ representing “$a$ and $b$ have the same parity,” $e(a)$ representing “$a$ is even,” and $o(a)$ representing “$a$ is odd,”

In the previous two sections, we examined arguments with universally quantified premises, but were more concerned with the form their conclusions took — we never discussed how to get universally quantified premises in the first place. Appealing to a definition is one way to do so, as we’ll see in the next section.

Asserting Axioms

Whereas definitions are things that can simply be decreed, axioms represent something fundamentally different — statements of mathematical interest that are intuitively correct, but require no proof of correctness.

Theorizing Theorems

Whereas axioms are asserted and define an entirely new branch of mathematics, theorems are always deducible from axioms and definitions.

Axioms can only ever appear as premises in arguments; theorems can be premises or conclusions. Typically, we start with a collection of axioms and definitions, deduce some initial round of theorems, then deduce a second round using the previous theorems along with the axioms and definitions — and we can repeat this process to yield ever more theorems. During all of this theorem-proving, we may even come up with new definitions along the way.

Some theorems can be proven from other, previously deduced theorems, in addition to the given axioms and definitions. In other cases, some theorems are simply special cases of other theorems — and we have special names for those too.

Often, the word “theorem” is reserved for major results. We could be pedantic about classifying various theorems as lemmas or corollaries, but we’ll mostly just stick to the word theorem — the important thing about all of them is that they’re deducible from axioms, definitions, and other theorems.

Providing Proofs

The final mathematical building block we’ll discuss is the proof.

We’ve discussed arguments at length up to this point, especially how to determine whether a given argument is valid — and we’ve touched lightly on using the rules of inference to chain logical implications together into new logical implications. All a proof really is is a valid argument.

We typically describe a proof as being given in reference to a theorem — if someone proposes a statement of mathematical interest, and a proof can be given for it, that statement is henceforth called a theorem, because it can be deduced. Remember that an argument is simply an implication, with a conjunction of multiple propositions as the hypothesis, and a single proposition as the conclusion — any of these propositions, in the hypothesis or the conclusion, can be primitive or compound.

In the next section, we start learning specific methods of proof, and ways to devise them. This is the primary activity of mathematics.

Proof Technique: Direct Proofs

At this point, we’ve talked a lot about mathematical logic, arguments, and some common terminology. In this section, we introduce a method for providing a proof for a proposition — the most straightforward technique we have at our disposal.

The Underlying Argument

Consider a statement such as $p \to q$ — but remember that a theorem is almost always implicitly universally quantified, so what we really want to show is $\forall x\ [p(x) \to q(x)]$ for every element $x$ within some universe $\mathcal{U}$. How would we show this is always true?

Recall the strategy behind the Rule of Universal Generalization: pick an arbitrary element $x_0 \in \mathcal{U}$, establish some property for that one element, then generalize the result to the entire universe. Suppose we assume $p(x_0)$ holds for our arbitrarily chosen $x_0$, and suppose we also have some already-established fact — a definition, a piece of algebra, or a previously proven theorem — telling us $p(x_0) \to q(x_0)$ is true for this particular $x_0$. The argument

is the basis for any direct proof. Is this argument valid?

Notice that step (3) is labeled an established fact rather than an assumed one — it can’t simply be handed to us as a premise, since that would already be the theorem we’re trying to prove. Instead, it has to come from somewhere else entirely: a definition, an algebraic identity, or an already-proven theorem that happens to connect $p(x_0)$ to $q(x_0)$ for this particular $x_0$. And step (5)’s conclusion isn’t generalizing the bare fact $q(x_0)$ from step (4) alone — it’s generalizing the implication $p(x_0) \to q(x_0)$, which is really what’s been established once we notice that $q(x_0)$ only followed because we assumed $p(x_0)$ in the first place. That’s why the citation for step (5) includes step (2) as well as step (4).

Since $x_0$ was an arbitrary element of $\mathcal{U}$ — not some specific one — the Rule of Universal Generalization lets us conclude the implication holds for every element of $\mathcal{U}$, not just the one we happened to pick.

This strategy is called a direct proof because we start by assuming the hypothesis $p(x_0)$, and derive the conclusion $q(x_0)$ from it directly, via a single use of Modus Ponens. In practice, establishing $p(x_0) \to q(x_0)$ itself might take several steps — appealing to definitions, algebra, or previously proven theorems along the way — but each of those steps is really just another instance of this same pattern: take a fact you already have, apply a known implication, get the next fact, and repeat until you reach the conclusion.

An In-Depth Example

Let’s break down a simple example of a proof for a mathematical proposition. Since we’re providing a proof, we can call the proposition a theorem.

And there we have it — a fully worked-out proof for a simple result. Most of the time, proof-writing uses a mixture of English, arithmetic, and algebraic manipulation written out in a paragraph format. We showed this one using formal logic to demonstrate that, if we’re ever unsure whether a proof is correct, we can fall back on the tools of mathematical logic. From here on, we’ll write proofs using this more conventional, paragraph-style approach instead.

A Conventionally Written Proof

Let’s rewrite the previous, very lengthy proof in a more conventional style.

This proof is much more compact, and much easier to follow. Again, if we’re ever unsure whether a proof is correct, we can write out the open statements, refer to the rules of inference, and lay out an argument in tabular form. Theorems and their proofs will be presented in specially marked magenta boxes going forward — if you’d like to try providing a proof before seeing one (always an excellent exercise), the proof stays collapsed until you’re ready to see it.

More Theorems and Proofs Regarding Even and Odd Numbers

Our next few theorems expand on the idea of even and odd numbers.

Let’s quickly discuss the first two theorems above. They may seem obvious to anyone with a high-school education, but they give us a chance to practice writing proofs using easy results — meaning we can easily check the logic used is valid. The main tool in both proofs was the definitions of even and odd integer, with a little algebra to make sure the relevant equations stayed balanced after adding $1$ to $n$.

The third theorem had an interesting proof: we used two previous theorems, which is completely valid, since they’re already proven to be true. The fourth theorem’s proof is perhaps the simplest so far — we could have invoked the second theorem first on $n$, then the third on $n + 1$, but the similarity to the third theorem’s proof was close enough that we could almost copy it directly. Sometimes this is warranted; other times there’s enough of a difference to necessitate an original proof.

Let’s expand our understanding of even and odd numbers even further.

It’s usually a good idea to play around with a theorem to see how it works in practice.

The next proof involves a product instead of a sum.

Notice that in the last step, we simply replaced the quantity $2ab + a + b$ with the single letter $c$ — since $2$, $a$, and $b$ are integers, $2ab + a + b$ must be an integer too, so we can just refer to it as $c$ to make the subsequent step easier. Just like we can always make substitutions in algebra, we can make substitutions for algebraic expressions in proofs too — we should just make clear what substitution is being used.

Theorems and Proofs Involving Square Numbers

Let’s explore some more theorems involving square numbers, along with even and odd numbers.

The algebra in a proof like this can be handled however you feel comfortable — simple steps can be omitted or combined, but anything tricky should be clearly laid out.

This proof is another demonstration of how previous theorems can be used in the proofs of other theorems.

The next theorem’s proof has some tricky algebra, so it’ll be laid out more carefully. This theorem is actually just the converse of the previous one — and remember, just because a theorem is true doesn’t mean its converse is automatically true.

This proof required a common algebraic trick — factoring a difference of squares — but just because it’s common doesn’t mean it’s an obvious step. It also required knowing a bit more about even and odd integers than what’s shown here (though these facts aren’t too hard to prove either). Why that trick specifically, and not one of the myriad other tricks available?

If we’re lucky, or clever enough to squint at the problem just right, we might have a flash of insight on how to proceed. But we also could have tried taking the square root of both sides of the first equation: $n = \sqrt{2k+1}$. What do we do with that? Nothing seems like a good next step — we’re stuck. We do have $n$ isolated on the left-hand side, which is generally a good strategy in proofs, but here it leaves us with no way to proceed. Perhaps if we were really good at handling roots in equations we could push through, but nothing comes to mind immediately.

Sometimes we’ll have no choice but to deal with sticky algebraic expressions — but other times, clever logic can free us from having to rely on algebra that might be too clever for us to grasp in a timely manner. One such logical strategy is the subject of the next section.

Proof Technique: Indirect Proofs

As seen in the last section, a direct proof is a proof method where we assume the truth of the hypothesis, and show the truth of the conclusion. But the last example in that section shows that a direct proof can sometimes be quite tricky to devise.

If we’re ever stuck trying to show a proposition is a theorem by taking a direct approach, we can use mathematical logic to prove an equivalent implication instead. Since we’re not proving the original implication to be a logical implication, but rather showing a logically equivalent one is, this is called an indirect approach.

The Underlying Argument

Suppose we’re trying to show $p \to q$ is a logical implication for every element of some universe $\mathcal{U}$ — that is, $\forall x\ [p(x) \Longrightarrow q(x)]$, meaning the argument

is valid, where $x_0$ is an arbitrarily chosen element of $\mathcal{U}$. Remember that an implication is logically equivalent to its contrapositive: $(p \to q) \Longleftrightarrow (\neg q \to \neg p)$. As such, this argument is logically equivalent to

so if we ever want to prove a statement of the form $\forall x\ [p(x) \to q(x)]$, we can instead prove $\forall x\ [\neg q(x) \to \neg p(x)]$. This method is also commonly called Proof by Contraposition.

We won’t re-derive why these two arguments are equivalent here, since that’s just the logical equivalence of an implication and its contrapositive from the previous chapter — instead, we want to get comfortable taking the contrapositive of a given implication, and showing that the contrapositive is always true.

Revisiting a Previous Proof

Recall Theorem 2.13.11, whose proof required some tricky algebra. Let’s revisit it with a different proof. Restating the theorem: “If $n^2$ is odd, then $n$ is odd.” The hypothesis is “$n^2$ is odd”; the conclusion is “$n$ is odd.” Since we want to give an indirect proof using the contrapositive, the statement we want to prove is “If $n$ is not odd, then $n^2$ is not odd.”

We may already know that if an integer isn’t odd, it’s even (we’ll prove this fact later, though the reader is probably already familiar with it) — so let’s rewrite the statement as “If $n$ is even, then $n^2$ is even.”

Now we proceed as if giving a direct proof: start by assuming $n$ is even. Since $n$ is even, there’s some integer $k$ such that $n = 2k$. Squaring $n$:

Since $k$ is an integer, $2k^2$ is an integer too, which we can call $c$. So there exists an integer $c$ such that $n^2 = 2c$, meaning $n^2$ is even, as desired.

So, by assuming $n$ is even, we can deduce $n^2$ is even, meaning $n \text{ is even} \Longrightarrow n^2 \text{ is even}$. Finally, since the contrapositive is logically equivalent to the original implication, we now also have $n^2 \text{ is odd} \Longrightarrow n \text{ is odd}$, as desired.

Let’s recap what we did, before formally writing a proof — this proof technique breaks down into three steps.

Step 1: Write the contrapositive

For an indirect proof of $p \to q$, start by writing the contrapositive $\neg q \to \neg p$.

Step 2: Proceed with a direct proof on the contrapositive

Assume $\neg q$ is true. Using the rules of inference, the laws of logic, any available axioms or definitions, and any previously proven theorems, deduce the truth of $\neg p$ if possible.

Step 3: Invoke the logical equivalence of the contrapositive

Once $\neg p$ is deduced from assuming $\neg q$, we have $\neg q \Longrightarrow \neg p$. Since an implication is always logically equivalent to its contrapositive, we also have $p \Longrightarrow q$ — it’s almost like getting two theorems for the price of one!

Now let’s present a formal proof of Theorem 2.13.11, using this indirect technique.

More Examples

Notice that in this proof, we didn’t explicitly state what the contrapositive was — we just started by assuming the conclusion was false, meaning $n$ must have been odd, then showed $n^2$ is odd as a result. Not all proofs will explicitly state the contrapositive, though it’s good practice, and something we’ll do frequently. It’s also worth noting we introduced the new variable $c$ to refer to the more complicated expression $2k^2 + 2k$ — a very common practice to improve clarity.

Our next theorem eschews even and odd integers, and instead deals with all real numbers and inequalities.

There are a couple of things worth pointing out about this proof. First, $\neg(x > 10)$ evaluated to $0 \leq x \leq 10$, rather than just $x \leq 10$ (and likewise for $y$ and $xy$) — this is because our universe is all non-negative real numbers, so we’re not considering negative numbers at all, and $0$ is a natural lower bound. Second, we used DeMorgan’s Law to distribute the negation into the parenthesized expression — a law used so frequently that its use often goes unmentioned. It’s usually a good idea to mention which logical laws you’re using, but plenty of writing doesn’t explicitly do so — it’s something we’ll simply have to get used to.

The contrapositive isn’t the only indirect method we have for proving theorems. The next section details another very common one.

Proof Technique: Contradiction

As discussed in the previous section, when trying to prove a statement like $p \to q$, we can take an indirect approach by proving some other statement, logically equivalent to $p \to q$, is true. There, the indirect method we used was the contrapositive. In this section, we use the Rule of Contradiction to arrive at another indirect proof method.

The Underlying Argument

Consider some arbitrary statement $p$. Since the implication $(\neg p \to F_0) \to p$ is always true (as we saw in the section on Rules of Inference), we can write $(\neg p \to F_0) \Longrightarrow p$ — meaning it’s a valid rule of inference, representing the valid argument

Now suppose we’re trying to prove $\forall x\ [p(x) \to q(x)]$ for every element of some universe $\mathcal{U}$. Pick an arbitrarily chosen element $x_0 \in \mathcal{U}$. What happens if we assume $p(x_0) = 1$ and $q(x_0) = 0$ (meaning $\neg q(x_0) = 1$)? The implication $p(x_0) \to q(x_0)$ would be false. Let’s look at what happens in an argument where we assume both $p(x_0)$ and $\neg q(x_0)$ as premises: a truth table confirms that

which means the argument

is logically equivalent to the argument

Thus, in order to show $\forall x\ [p(x) \to q(x)]$, we could instead show $[p(x_0) \land \neg q(x_0)] \Longrightarrow F_0$ for our arbitrarily chosen $x_0$. This is the idea behind proof by contradiction: assume the negation of the desired conclusion as an additional premise, then show that doing so yields a contradiction.

Revisiting a Previous Theorem

Let’s once again revisit Theorem 2.13.11: “If $n^2$ is odd, then $n$ is odd.” To prove this by contradiction, we first identify our premises. $n^2$ being odd is one; but in a proof by contradiction, we also have the negation of the conclusion as a premise. Since the conclusion is “$n$ is odd,” its negation is “$n$ is not odd” — that is, “$n$ is even.” So our premises are:

Using the definitions of even and odd as usual: there’s an integer $a$ such that $n = 2a$. Squaring $n$:

Since $n^2$ is double whatever integer $b$ happens to be, $n^2$ is even. But this directly contradicts our premise that $n^2$ is odd! Thus, assuming $n$ is even yields a contradiction whenever we assume $n^2$ is odd — so $n$ can’t be even, and must be odd, as desired.

Over the past three sections, we’ve proven “if $n^2$ is odd, then $n$ is odd” in three different ways — directly, indirectly via the contrapositive, and indirectly via a contradiction. This is the versatility of mathematical logic: if we’re ever stuck trying to prove a theorem one way, we can try another tactic.

Some theorems are established in so many ways it’s hard to keep track of how many proofs exist — there are entire books dedicated to proofs of the Pythagorean Theorem alone. But not every theorem is so easily established in a variety of ways. Perhaps most infamous is Fermat’s Last Theorem: for over 350 years, mathematicians tried to either establish or disprove the statement that when $n > 2$, there are no integers $a$, $b$, $c$ (with $abc \neq 0$) satisfying $a^n + b^n = c^n$. A proof was eventually given by Andrew Wiles in the mid-1990s, requiring such abstract and sophisticated methods that there are entire graduate courses dedicated to studying it.

As you study more mathematics, you’ll collect ever more tools for proving theorems, or providing counter-examples. For now, let’s show some more results using the method of contradiction.

Numbers Can’t Be Both Even and Odd

Notice that in some of our previous proofs, we used the fact that if $n$ isn’t even, it must be odd. For example, the contrapositive proof that $n^2$ odd implies $n$ odd required us to assume that $n$ not being odd meant $n$ was even. We haven’t actually proven this — are there numbers that are both even and odd? Most readers already know none exist, and now we can prove it.

A few things worth pointing out about this proof. First, notice we used the letter $a$ when assuming $n$ was even, and $b$ when assuming $n$ was odd — not the same letter for both, since $n$ can’t simultaneously equal $2a$ and $2a + 1$ for the same value of $a$ (that would mean two consecutive integers are equal, which is absurd).

Second, when we reached the contradiction, we asserted it was the assumption of $n$ being odd that was the problem, not the assumption of $n$ being even. Remember, the hypothesis of the theorem is that $n$ is even — we’re only considering even integers, and testing what happens if $n$ was also assumed odd. Once we reach a contradiction, either the “even” assumption or the “odd” assumption must be faulty — but since $n$ being even is the hypothesis we’re given, it must be the “odd” assumption that’s at fault.

Finally, notice the contradiction we arrived at had nothing to do with $n$ being even or odd at all — it was about the number $1$. When using the contradiction method, the contradiction we arrive at may be about the hypothesis of the proposition being examined, or it might be some piece of previous knowledge that happens to show up. In some sense, every piece of knowledge we have can be used as a premise, it’s just that we don’t necessarily need — or want — to explicitly lay out every premise, or the statements of our theorems would become unwieldy.

Another Example

Mistakes in Proofs

So far, we’ve seen three different proof techniques: one direct, and two indirect. Applying any of them requires close adherence to the rules of inference discussed throughout this chapter.

However, if we make an argument that uses an invalid inference rule, we have an invalid argument, and hence an invalid proof. In this section, we discuss a few of the most common types of errors that can be made.

Violating Hypotheses of a Theorem or Axiom

Remember that a theorem guarantees some result holds when a certain collection of premises are satisfied. If even one premise fails to hold in a given scenario, the theorem no longer applies — its conclusion may still happen to be true, but not because of the theorem itself. Consider the following “proof” that $1 = 2$:

Let $a$ and $b$ be real numbers such that $a = b$.

Clearly something went wrong somewhere, since obviously $1 \neq 2$.

The first thing to do is check the arithmetic on each line — in this case, the arithmetic checks out, so that’s not the issue. Take a close look at the second-to-last step, where we went from $b(a-b) = 2b(a-b)$ to $b = 2b$ by canceling the common $(a-b)$ term — which we did by dividing both sides by $(a-b)$.

The problem is that we initially said $a = b$, meaning $a - b = 0$. So when we divided both sides by $(a - b)$, we were really dividing by $0$ — an invalid arithmetical manipulation, even though the arithmetic was performed “correctly” once that division was allowed.

It’s common when solving equations to cancel out like terms, and there’s a theorem to help with this:

This theorem has two premises: $p_1 : a \neq 0$ and $p_2 : ab = ac$. If both are true, the theorem guarantees the conclusion $c : b = c$. Now, what happens when we try to apply this theorem to the flawed proof above? There, $p_1 : a - b \neq 0$ and $p_2 : b(a - b) = 2b(a - b)$. Premise $p_1$ is false — so this theorem does not guarantee $b = 2b$.

To be clear, it may still be the case that $b = 2b$ in some instances — like when $b = 0$, since $0 = 2(0)$. But the truth of $b = 2b$ isn’t guaranteed by the Cancellation Law; we’d have to appeal to an entirely different theorem to establish it.

Arguing by the Converse or Inverse

As described earlier in this chapter, an implication isn’t in general logically equivalent to its converse or inverse (though in some cases it may be). Thus, we can’t in general deduce the truth of a proposition by examining the truth of its converse or inverse.

Circular Reasoning

One particular error that occasionally occurs is implicitly assuming the truth of the conclusion, instead of deducing its truth from the premises. It sounds silly to prematurely assume the truth of a conclusion, but many proofs require multiple paragraphs of carefully written logic — and it can be easy to mistake the conclusion for a premise, and start working out faulty results. It’s a subtle mistake, but a mistake nonetheless.

As this example demonstrates, one way this error occurs is that the assumption is stated quickly, and then a bunch of results are derived afterward. When reading an attempted proof, we may gloss over the assumptions being made and focus on the results derived from them — which is exactly where we might miss the fact that we’re assuming the truth of the conclusion. Always be on the lookout for unwarranted assumptions in proposed proofs of a statement.

Abusing Universal Generalization

Universal Generalization proves a universally quantified statement is true by taking a specific, but arbitrarily chosen, element from the universe of discourse, and manipulating it to show some result. Since that element was arbitrarily chosen, any derived results hold for whatever element we pick, and hence hold for all elements in the universe.

Typically, we use a variable to represent the arbitrarily chosen element — since its value is unknown, the only thing we know about it is what’s known about every element in the universe.

Problems arise when the element we pick is not arbitrarily chosen.

Proof Technique: Equivalence

All of the proof techniques we’ve discussed so far only seem to go one way. When we provide a proof for $a \Longrightarrow b$, what we’re really saying is that if $a$ is true, then $b$ is true too — but since an implication isn’t generally logically equivalent to its converse, we can’t go the other way: knowing $b$ is true doesn’t necessarily tell us $a$ is also true.

However, just because that’s true in general doesn’t mean there are never instances where an implication is logically equivalent to its converse. Consider the statement $n \text{ is even} \Longrightarrow n + 1 \text{ is odd}$. Clearly, its converse is also a logical implication: $n + 1 \text{ is odd} \Longrightarrow n \text{ is even}$. So, whenever “$n$ is even” is true, “$n + 1$ is odd” is also true — and vice versa. These propositions are either simultaneously true, or simultaneously false. Hence, we can write $n \text{ is even} \Longleftrightarrow n + 1 \text{ is odd}$.

In this section, we demonstrate a technique for proving statements of the form $a \Longleftrightarrow b$.

The General Strategy

The technique for showing a logical equivalence is based on the fact that $(p \leftrightarrow q) \Longleftrightarrow (p \to q) \land (q \to p)$. If we ever want to prove $a \Longleftrightarrow b$, we need to provide a proof for $a \Longrightarrow b$, and a proof for $b \Longrightarrow a$. As a reminder: to prove $a \Longrightarrow b$, we assume $a$ is true and deduce the truth of $b$; to prove $b \Longrightarrow a$, we assume $b$ is true and deduce the truth of $a$. Of course, any proof technique already discussed can be used for either direction.

Since a theorem is almost always implicitly universally quantified, what we’re really trying to show is $\forall x\ [p(x) \leftrightarrow q(x)]$ for every element $x$ within some universe $\mathcal{U}$. The argument

is the basis for any proof of logical equivalence: once both directions have each been established on their own — using whatever proof technique fits each one — the Law of Mutual Implication combines them into the desired biconditional.

Another Result About Even and Odd Numbers

In this proof, we clearly delineated which part we were working on with labeled headers — this keeps things organized, and we finished by making clear we’ve shown the logical implication works both ways, meaning we have a logical equivalency.

Notice also that this theorem uses the “if and only if” construct — as a reminder, that’s how biconditionals are specified. It’s also worth pointing out that we used a direct approach for “$n$ is even $\Longrightarrow$ $n^2$ is even,” but an indirect approach for the reverse direction. We’re allowed to mix and match proof techniques for either part — all we need is some proof, regardless of the technique.

Multiple Equivalencies

Of course, multiple propositions may be logically equivalent to each other. Suppose we knew $a \Longleftrightarrow b$ and $a \Longleftrightarrow c$. Can we conclude $b \Longleftrightarrow c$? Since $a \Longleftrightarrow b$ and $a \Longleftrightarrow c$, we have $b \Longrightarrow a$ and $a \Longrightarrow c$. Thus, by the Law of the Syllogism, $b \Longrightarrow c$. Similarly, we also have $c \Longrightarrow a$ and $a \Longrightarrow b$, meaning $c \Longrightarrow b$. Finally, because we have both $b \Longrightarrow c$ and $c \Longrightarrow b$, we must also have $b \Longleftrightarrow c$. This means overall,

The technique for showing multiple equivalencies is based on the fact that

The most straightforward way to show $a \Longleftrightarrow b \Longleftrightarrow c$ is to first show $a \Longrightarrow b$, then $b \Longrightarrow c$, and finally $c \Longrightarrow a$.

Extending this to three open propositions $p(x)$, $q(x)$, and $r(x)$, the argument

is the basis for showing all three are logically equivalent — proving each implication around the cycle separately is enough to guarantee $p(x)$, $q(x)$, and $r(x)$ all share the same truth value, for every $x$.

Because of all the work we did previously, we were able to make quick work of this proof — instead of working out every result from first principles, we simply appealed to previously established theorems to do all the heavy lifting.

Note that we can extend logical equivalency to as many propositions as we can logically show. For example, if we wanted to show that some collection of $n$ propositions were all logically equivalent, we’d make use of the fact that