Propositions

In Mathematics, we deal with statements like these:

In life, we deal with statements like these:

In Math, as in life, some statements are easy to determine if they’re true or false. However, when we encounter more complicated expressions, we typically need a way to carefully evaluate that statement’s truth.

We can start to evaluate these expressions by examining simple expressions, then simple combinations of expressions, and working our way up, so to speak, to increasingly more complicated expressions until we finally have the truth of the desired expression.

In this section, we talk about how to evaluate these simple expressions, and how to combine those simple expressions.

Defining Propositions

We start by defining what a proposition is:

Propositions are the building blocks of any logical system. These are what we evaluate and combine to form larger statements.

As a convention, we often use lowercase letters to refer to specific propositions we are working with.

All of the sentences in the previous example have definite truth values.

Compound Propositions

You’ll notice that some of the propositions in the previous examples look like they consist of simpler propositions.

Some propositions can be broken up into simpler propositions. Other propositions are already expressing a simple claim that isn’t a combination of other simple claims.

Note that the above definition of a compound proposition does not require its constituent propositions to themselves be primitive — any combination of primitive and compound propositions can be combined to form one larger compound proposition.

There are a large number of ways we can combine propositions, primitive or compound, together to form more complicated propositions.

Logical Connectives

We start by introducing a very simple way to make a more complicated proposition from a single proposition.

We do not consider the negation $\lnot p$ of a proposition $p$ to be primitive.

The rest of the logical connectives we introduce combine two given propositions into one proposition.

Note that in this definition, or is true when both propositions in the disjunction are also true. Usually in spoken and written English, or is used in an exclusive sense, meaning only one of the propositions is true. In Mathematics, or is almost always taken to be inclusive, and will be the case throughout the rest of these notes. Unless otherwise stated, you should assume the word or is being used inclusively.

The following logical connective more closely aligns with what most people normally say when they use the word or.

The next definitions have to do with cause-and-effect type relationships between two propositions.

Translating Compound Propositions into English Sentences

Knowing how the truth value of a compound proposition relates to the truth values of its constituent propositions will provide guidance on how to translate a symbolic logical expression into familiar English sentences.

For starters, note that since $\neg p$ has the opposite truth value of $p$, we can describe the truth value of $\neg p$ as not whatever $p$ happens to be since $\neg p$ can only be true or false. As such, we usually translate $\neg p$ as “Not $p$”.

Next, by our definition of conjunction, we know that a compound proposition such as $p \land q$ is true only when $p$ and $q$ are both true. Hence, we translate the symbolic expression $p \land q$ as “$p$ and $q$”.

Since the mathematical definition of disjunction is inclusive, we can (or probably should) translate the symbolic expression $p \lor q$ as “$p$ or $q$, or both” in order to emphasize the inclusive nature of disjunction. Again, based on the definition though, it should be understood that the sentence “$p$ or $q$” is the inclusive version of the word or.

On the other hand, for the exclusive-or, we do need to indicate in the English sentence that not both must be true. This means when we translate an expression such as $p \veebar q$, we do need to translate this roughly as “$p$, or $q$, but not both”, or perhaps something similar indicating only one of the propositions is true.

The implication is perhaps the most complex expression to translate into English. We won’t be able to start appreciating why this is until Chapter 2, but note that there are a wide variety of ways we can translate an implication into English. Some of these translations may seem confusing now, but should become clear the more we work with implications (again, a detailed discussion of implications will be postponed to Chapter 2). For now, here is a large list of possible translations for the logical expression $p \to q$:

• “If $p$, then $q$”
• “$p$ implies $q$”
• “$p$ is sufficient for $q$”
• “$p$ is a sufficient condition for $q$”
• “$q$ is necessary for $p$”
• “$q$ is a necessary condition for $p$”
• “$p$ only if $q$”
• “$q$ if $p$”
• “$q$ whenever $p$”

Likewise, the biconditional can also be a bit cumbersome, but we will examine the biconditional in large detail in the upcoming sections. For now, here is a list of ways the biconditional $p \leftrightarrow q$ can be translated into English:

• “$p$ if and only if $q$”
• “$p$ is necessary and sufficient for $q$”

Of course, there may be more elegant ways to translate propositions into English sentences. Having some command over the language gives you more ability to translate these into English sentences, but the above methods more than suffice in most instances.

Sentences That Are Not Propositions

Of course, not all sentences represent propositions. A sentence is only a proposition if it is true or false (but not both). Any sentence that can’t be described as true or false is not a proposition.

Modeling Logic with Truth Tables

We are often working with three or more propositions at a time, usually combined into large numbers of expressions made using the logical connectives discussed previously.

It can be cumbersome to work with them individually. Here, we will learn a technique for handling multiple expressions efficiently.

A Convenient Shorthand

To make our upcoming work easier, we adopt a common shorthand for truth values:

Using numbers will make the following concept a bit more space efficient, and give a more mathematical flavor going forward.

Atomic Propositions: Building Blocks of Truth Tables

A truth table is simply a table organizing multiple logical expressions based on the truth values of their constituent, or atomic propositions.

By atomic, we mean propositions used to construct compound propositions by combining them with logical connectives.

In the expressions

$p$ and $q$ are considered atomic.

Note that atomic propositions themselves do not need to be primitive.

In general, a proposition that is named or labeled (usually with a lowercase letter) is considered atomic because it can be used to build up other propositions when combined with other labeled propositions using the logical conenctives.

Constructing Truth Tables

As stated before, a truth table is simply a table showing the truth value of a logical expression based on the truth values of its atomic propositions.

Here is an overview:

1. We start with the given expression, and identify all atomic propositions used to form it.
2. We create a table with enough columns for all of the atomic propositions as well as the desired logical expression. We list all atomic propositions in the left-most columns, in alphabetical order. The last, right-most column is reserved for the desired proposition.
3. Under the columns for the atomic propositions, we list all possible combinations of truth values between the atomic propositions. A good way to ensure that all combinations are listed is to follow a “rotary,” “dial,” or “odometer” method, where the right-most atomic proposition’s values change the most frequently between rows, and the first, left-most atomic proposition’s values cycle the least frequently between rows. Instead of dialing through digits 0 through 9 like an odometer, you flip back to 0 after reaching 1.
4. For each row, evaluate the desired logical expression by substituting that row’s truth values in for its atomic propositions.

This yields a complete truth table for your desired expression. Let’s see an example where we fill out a truth table for the logical expression $p \land q$:

This example shows the basic procedure. From now on, we can just fill in the values as needed, without any need to repeat any of the exposition here.

Truth Tables for the Logical Connectives

We have seen how to construct a truth table from scratch. Now, it’s really just a matter of appealing to the definitions of the logical connectives in order to construct truth tables for them. Knowing the truth tables for the logical connectives is going to make working with even more complicated expressions much easier, since any complicated expression is essentially just a bunch of atomic propositions combined with the logical connectives described here.

Here, we are going to use $p$ and $q$ as the atomic propositions for the expressions.

Negation $\neg$

This is a really simple truth table, since negation can operate on one proposition at a time. Remember that the negation of a proposition has the opposite truth value of the proposition itself.

Conjunction $\land$

We already saw this in the example above, but we’ll show the table here for the sake of completeness.

Disjunction $\lor$

Based on the definition of disjunction, we know that if at least one of the atomic propositions is true, then the disjunction itself is also true.

Exclusive-or $\veebar$

The definition essentially tells us that the exclusive-or of two atomic propositions is true whenever the atomic propositions have different truth values; or put another way, not equal to each other.

Implication $\to$

The definition of implication tells us that the only time an implication is false is if $p$ is true, and $q$ is false. Otherwise, the implication is true.

Biconditional $\leftrightarrow$

The definition for a biconditional essentially tells us that if the two atomic propositions have the same truth value, meaning they are equal to each other, then the biconditional itself is true. It is false otherwise. We can almost think of the biconditional as being the exact opposite of an exclusive-or between two propositions.

Combining All Logical Connectives Into One Table

Something we can do is simply append the columns for each of the logical connectives into one big overall table. You have to be careful when doing this to make sure the rows line up with the appropriate rows for the atomic propositions. If the order of the atomic propositions differs, or if the numbering method used yields a different ordering for the combinations of truth values for the atomic propositions, the results may not be correct.

Here, we used the same ordering for the atomic propositions themselves, and the combinations of truth values for those atomic propositions. We will have to extend the negation table by an additional two rows, but again, we fill in any values needed by appealing to the definition of negation, and paying attention to the values of the atomic propositions in the row we are evaluating.

Intermediary Columns

Notice that we just produced a truth table that has more than one expression column, one expression column for each of the logical connectives we use to form compound propositions.

If we are trying to determine the truth value of a complicated expression, we can do the same thing. We can identify all of the parts of the more complicated expression, and gradually build up the truth value of the final, desired expression. Doing this helps us keep track of values, preventing us from having to work out complicated expressions all at once.

We use so-called intermediary columns to hold the parts of the complicated expression that are easy to calculate. Usually, we break a complicated expression up based on where the logical connectives are. Here is an example.

Logical Order of Operations

Just like in the arithmetic of real numbers, there is an order we should follow when evaluating logical expressions.

For instance, in the arithmetic of real numbers, we abide by the following rules:

1. Parentheses $()$
2. Exponents
3. Multiplication and division (left to right)
4. Addition and subtraction (left to right)

Using this scheme for evaluating arithmetic expressions, we do the following:

Here we introduce a scheme to help us determine which operations should be done in order to achieve the correct final result.

Why Order Matters

Consider the following example.

Establishing an Order of Operations

The following is a commonly used scheme for an order of operations:

1. Parentheses $()$
2. Negation $\neg$
3. Conjunction $\land$
4. Disjunction $\lor$
5. Exclusive-or $\veebar$
6. Implication $\to$
7. Biconditional $\leftrightarrow$

Using this order, we remove any ambiguity from logical expressions.

Using the Order of Operations

With the order of operations, we remove any ambiguity, and do not have to rely on parentheses unless we want to give precedence to operations lower in the order.

A Note on Conventions

In this book, we adopt the above order of operations, but will only make shallow use of it. Basically, what this effectively means is that we will make very liberal use of parentheses, even when they aren’t strictly necessary.

While the relative order between $\neg$, $\land$, $\lor$, $\to$, and $\leftrightarrow$ is somewhat standardized (heavy emphasis on the word “somewhat”), it is hardly universal. This is especially true when $\veebar$ is thrown into the mix.

Many texts use $()$ liberally as well. In some ways, the order of operations presented here was entirely engineered to meet this book’s needs, and this order’s scope is only contained within this book.

This is why, going forward, we will hardly rely on this order of operations, and instead opt to use the standard trick of using $()$ to indicate which operations take precedence over others.

A Note on Organizing Arithmetic

A blank piece of paper allows one to express an idea anywhere on the page, in any arrangement. But following a chain of arithmetic is much easier when it’s laid out in a consistent, organized manner.

In this book, any arithmetic (based on real numbers, logic, or some other system) will generally be shown in a tabular format. There will be two benefits to this:

1. Relatively easy to follow from one step to the next.
2. Justification for each step can be explicitly shown.

Let’s see an example.

There is a slightly different format we’ll use for expressions that don’t already appear in a large, single block.

Satisfiability

We’ve seen plenty of primitive propositions whose truth values are fixed:

We’ve also seen compound propositions whose truth values depend on the truth values of its atomic propositions.

Typically, the compound propositions we work with are made up of generic propositions that could be true, or could be false. This means we need to examine all combinations of truth values for the atomic propositions to determine the overall truth value of the compound proposition.

Of course, we usually will only be interested in compound propositions that are true. This is how we frame the upcoming discussion: when are compound propositions true?

Propositions that are Sometimes True

We’ve seen some examples of compound propositions that — for some combinations of truth values — are true.

Let’s dispense with the suspense; we already know what word we’ll use to describe compound propositions that can be true.

Propositions that are Always True

We have yet to see a proposition that is always true, no matter what combination of truth values are assigned to its atomic propositions.

Sometimes when we come across a tautology in an expression, we can replace it with the symbol $\top$ (sometimes also written $T_0$), but since the truth value is always $1$, we can always replace the expression with its truth value $1$.

It should be noted that it may preferable to either use $\top$ or $T_0$ when working with propositions, because those symbols have additional context to them than the literal value $1$. Those symbols signify that we are working with a proposition always happens to be true.

Propositions that are Never True

We’ve seen a proposition that is always true, but are there propositions that are never true?

You can’t assert both $p$ and $\neg p$, because they contradict each other — which leads us to our next definition.

Just like with tautologies, we sometimes use the symbol $\bot$ (sometimes also written $F_0$) to represent a contradiction. But since a contradiction is always false, we can also just use $0$ — though we may prefer $\bot$ or $F_0$ if we wish to convey that we’re talking about a proposition, rather than a literal value.

Laws of Logic

At this point, we’re familiar with the fundamental unit of logic — the proposition. We’ve seen how to combine them into compound propositions, and how to use truth tables to identify propositions that are always true — tautologies.

With these tools, we are ready to start discussing the heart of logical deduction and our unique ability to reason — the Laws of Logic!

A Simple Example

Before we dive into the deep end, let’s wade in a shallow example where we examine a few propositions that involve the biconditional connective.

In the previous example we saw how — when the biconditional between two propositions is a tautology — we can essentially just swap out one expression that has the same behavior under its atomic propositions for another, without changing the overall truth value.

Let’s see another example.

Let’s see one more example of some “equivalent” expressions.

We just saw three examples of biconditionals that were tautologies. A reasonable next question would be “so what?”

The past couple of examples have demonstrated how complicated expressions can be replaced (and better understood) with simpler expressions.

Logical Equivalence

The reason why we can replace a complicated proposition with a simpler proposition is because that simpler proposition exhibits the exact same behavior as the more complicated proposition when the atomic propositions assume — or take — the same combination of truth values. By “the same behavior,” we mean they have the same truth values, meaning the biconditional is a tautology.

At least one of $S_1$ and $S_2$ needs to be compound for this to be interesting. We actually already saw an example where only one side was: $\neg \neg p$ is logically equivalent to just $p$, even though $p$ itself is primitive. Comparing two primitive propositions to each other isn’t nearly as useful — a primitive proposition’s truth value doesn’t depend on the truth value of any other proposition, so there’s no combination of truth values to check across.

Logical equivalence is the basis for the Laws of Logic.

Laws of Logic

The Laws of Logic are nothing more than a list of logical equivalencies.

Here, we present a rather long list of known logical laws.

Just like we did in the examples, all of the above can be verified by examining a truth table containing a biconditional and determining whether or not the biconditional is a tautology.

Some More Laws of Logic

There are a couple more logical equivalencies that prove to be useful.

Simplifying Logical Expressions

In the previous section we saw an example where we used tautologically true biconditionals to “simplify” complicated propositional expressions into simpler propositional expressions. Whatever we could say about the simpler expressions could also be said about their more complicated, logically equivalent counterparts (except perhaps our preference for working with the simpler expressions, of course).

In this section we do more work with logical equivalencies, similar to what we saw in the examples seen previously. Our work here will bear a striking resemblance to our experience in dealing with the arithmetic and algebra of real numbers. In fact, the upcoming work we are about to engage with has been dubbed the “algebra of propositions.”

Revisiting a Previous Example

In the previous example, we saw how to take a complicated proposition and produce a simpler proposition that always had the same truth value.

Now that we have a big list of logical equivalencies under our belt, we can see how to use those equivalencies to more quickly find equivalent propositions, rather than trudge through truth tables all the time.

A New Example

Let’s turn our sights to a new example we haven’t seen before, and compare using truth tables to using logical equivalencies.

A Note on Organizing Logical Equivalencies

In the previous example, we listed the logical equivalencies on separate lines, citing the logical law being appealed to. This is certainly a fine way to organize one’s work, and has its advantages.

In this book, we opt to use a tabular format to organize our work, unless the occasion calls for some other format. We adopt a three-column format:

We can demonstrate this format using the same proposition from the previous example.

One Big Example

We’ve seen a couple of examples where we use a couple of logical laws. Some examples require more laws to simplify.

Application: Switching Networks

While the content we’ve seen so far seems ethereal, with little application outside of simplifying logical propositions, logic dictates almost every avenue of study. In our everyday lives, we like to think our actions are reasonable and make sense. Certainly, we can use logic to analyze a situation so we can maximize our profit from it, whether our profit is in the form of friendship, promotions at work, happiness, health, or money.

One such application of logic has had a profound impact on human history. In 1938, a paper “A Symbolic Analysis of Relay and Switching Circuits” was published. In that paper, author Claude Shannon showed that Boolean Logic (what we’ve been studying so far in this book) can be used to simplify the design of relay circuits that were used in the construction of electromechanical devices back in the day. (Likewise, these relay circuits could be used to solve Boolean algebra problems, essentially meaning that relay circuits are equivalent to Boolean/propositional expressions.)

This insight paved the way for future computer advancements, culminating in the development of modern computer chip designs, including modern CPU, GPU, and now TPU chip designs.

In this section, we take a look at a very basic framework for taking “complicated” circuits and producing equivalent, simpler circuits.

Electrical Circuits

An electrical circuit at its core is simply a network of switches that are designed to allow or block electricity from flowing from one terminal to another.

Here is the simplest switching network:

Here, $T_1$ is the starting terminal, and $T_2$ is the ending terminal. Electrical current is applied at $T_1$.

Here, there is one switch, labeled $p$. In the diagram above, $p$ is “open,” meaning it isn’t allowing electricity to flow through.

Here is the same circuit, with switch $p$ “closed,” thus allowing electricity to flow:

The connection between these circuits and logic is this: open switches correspond to false propositions, and closed switches correspond to true propositions.

So, the first circuit we saw corresponds to when $p$ represents a false proposition ($p = 0$). The second circuit corresponds to when $p$ represents a true proposition ($p = 1$).

Two Fundamental Circuits

Here we start by showing two circuits that are used to construct more elaborate circuits.

Here is the first:

In order for electricity to flow from terminal $T_1$ to terminal $T_2$, both switches $p$ and $q$ must be closed ($p = 1$ and $q = 1$).

This is exactly the same as saying $p \land q$: when either $p$ or $q$ is open (equal to $0$), then there isn’t a connected path from $T_1$ to $T_2$. When both are closed (equal to $1$), then there is a path from $T_1$ to $T_2$.

This circuit is called the “Series Circuit” and corresponds to the conjunction operator.

Here is the second fundamental type of circuit: the “Parallel Circuit”

Here, we see that as long as at least one of $p$ or $q$ is closed (at least one of $p$ or $q$ is equal to $1$), then electricity can flow from $T_1$ to $T_2$.

Of course, saying $p$ or $q$ must be closed is equivalent to the disjunction of $p$ and $q$: when $p \lor q = 0$, electricity can’t flow from $T_1$ to $T_2$. When $p \lor q = 1$, electricity can flow.

From just these two circuits, we can build up many useful circuits.

A Simple Example

The ability to simplify circuits relies on our ability to model a given circuit as a proposition containing a combination of atomic propositions, negations, conjunctions, and disjunctions.

We do that by identifying the series and parallel circuits being used in the given circuit.

A Complex Example

We can take a more complicated circuit and do the same thing:

Obfuscating Circuits

Something we could do, if we were worried someone may take our circuit designs, is to obfuscate them by taking a simple circuit and using the laws of logic “in reverse,” so to speak, to produce an equivalent, more complicated circuit.

In the previous example, we saw how the laws of logic can be used to turn simple propositions into more complex ones. For example, a combination of the identity laws and inverse laws allow us to introduce superfluous atomic propositions.

We also saw that propositions can be used to model non-electric networks as well, such as a valved plumbing network. Any kind of gated network can be modeled as a proposition.

Open Propositions

All of the propositions we’ve dealt with so far have had definite truth values. For example,

is a proposition that is known to be false. A statement such as

is a compound proposition that is true.

However, a statement such as

is not a proposition, because we don’t know whether it’s true or false. We would need to know the value of $n$ in order to reach such a conclusion. For example, the statement is false when $n = 5$, but true when $n = 16$. Here, we’ll deal with sentences involving variables like this one.

Open Statements

Both of these examples are open statements — sentences with variables whose truth value can’t be pinned down until we substitute something in for those variables.

Just like with ordinary propositions, we write $p(x) = 0$ if the value of $x$ makes $p(x)$ a false proposition, and $p(x) = 1$ if the value of $x$ makes $p(x)$ a true proposition.

A propositional function can depend on more than one variable, as the next example demonstrates.

Constraining Inputs

Let’s reconsider the president example.

The previous examples show that restricting the allowable inputs of a propositional function can greatly affect the truth values it yields. This collection of allowable values has a special name, and knowing what it consists of is vitally important.

As demonstrated earlier, a propositional function can have many variables — we’d need to specify the universe of discourse that all of those variables have to adhere to.

It’s also possible to specify a separate universe for every variable in a propositional function.

Of course, it’s also possible for some of a propositional function’s variables to share a universe of discourse, while others have some other universe.

Quantifiers

Consider the following propositional functions, both defined on the universe $\mathcal{U}$ of all integers:

We can find values of $n$ that make $s(n)$ true, such as $n = -4$. We can also find values of $n$ that make $s(n)$ false, such as $n = 13$. The same is true of $t(m, n)$: the values $m = 3$ and $n = -7$ make $t(m, n)$ true, while $m = 4$ and $n = -1$ make $t(m, n)$ false.

Now consider the following statements:

$\alpha$ and $\beta$ aren’t open statements, even though variables show up in them. The difference is that each statement is making a specific claim, and the truth value of that claim doesn’t depend on the values taken by the variables.

Statement $\alpha$ is claiming that some specific integer exists that makes $s(n)$ true. As we saw above, one such value is $n = -4$, so $\alpha$ is a true proposition. It doesn’t matter that $n = 13$ makes $s(n)$ false — $\alpha$ is only claiming that some satisfying value exists, and we already found one.

Likewise, $\beta$ is making a specific claim: that every single value of $m$ and every single value of $n$ makes $t(m, n)$ true. We saw that $t(m, n)$ is false when $m = 4$ and $n = -1$. Because it isn’t true that every $m$ and every $n$ make $t(m, n)$ true, $\beta$ is a false statement — regardless of the fact that some values of $m$ and $n$ do make $t(m, n)$ true.

We explore these kinds of statements here, and in the next couple of sections.

The Existential Quantifier

The phrases “for some $n$” (used in statement $\alpha$) and “for all $m$ and all $n$” (used in statement $\beta$) are said to quantify the propositional functions $s(n)$ and $t(m, n)$.

The following phrases are all equivalent, and specify the existential quantifier:

• “for some $x$”
• “for at least one value of $x$”
• “a value of $x$ exists such that”
• “an $x$ exists such that”

For any propositional function $p(n)$, we can consider the statement

which is equivalent to the statement “For some $n$, $p(n)$,” which in turn is equivalent to saying “For some $n$, $p(n)$ is true.” Note that in the first two phrasings, we omit the “is true” part — it’s assumed that we’re considering the existence of values of $n$ that make $p(n)$ true. We could also consider the existence of values of $n$ that make $p(n)$ false, by considering the statement

Similarly, we can use logical connectives along with the existential quantifier. So for propositional functions $x(n)$ and $y(n)$, we can consider the statements

where we enclose the propositional functions in brackets to specify that the existential quantifier applies to the whole logical connective. This is different from the statements

where the existential quantifier only applies to the propositional function $x(n)$. In general, it’s a good idea to enclose whatever statement you want a quantifier applied to in brackets.

At this point, it’s worth pointing out that $p(x)$ is an open statement, whose truth value can only be determined after substituting in a value for $x$ from some universe of discourse, whereas $\exists n\ p(n)$ is not an open statement — it has a definite truth value (either some value of $x$ from the universe exists such that $p(x) = 1$, or no such value exists).

It’s also worth pointing out that when we say something like $\exists n\ p(n) = 1$, we mean that the statement $\exists n\ p(n)$ is equal to $1$ — we are not simply saying that $p(n) = 1$ (again, because $p(n)$ is an open statement, we’d have to substitute a value in for $n$ before we know whether $p(n) = 0$ or $p(n) = 1$).

Remember that, by definition, a statement such as $\exists n\ p(n)$ is true if we can find at least one value of $n$ that makes $p(n) = 1$. There could be infinitely many such values, $1000$ values, $10$ values, or even exactly $1$ value — the existence of at least one such value is enough to make $\exists n\ p(n)$ a true statement.

The Universal Quantifier

The following phrases are all equivalent, and specify the universal quantifier:

• “for all $x$”
• “for any $x$”
• “for each $x$”
• “for every $x$”

The statement $\forall x\ p(x)$ asserts that all values of $x$ make $p(x)$ true. The statement $\forall x\ \neg p(x)$ asserts that all values of $x$ make $p(x)$ false. Again, it’s advisable to use brackets to specify how the quantifier is being used, as in $\forall x\ [p(x)]$ and $\forall x\ [\neg p(x)]$.

Explicit and Implicit Quantification

Some open propositions may not be as explicitly stated as we’d like. Determining whether a statement uses an existential or universal quantifier may require a close look at its wording, or some outside knowledge.

A Quick Word on Notation

In every example so far, we’ve specified a universe of discourse, and it’s been implicitly understood that all substitutions for variables come from that universe. We can make this more explicit.

For example, up to now, we’d say something like “For some universe $\mathcal{U}$, consider the statements $\forall x\ [p(x)]$ and $\exists x\ [p(x)]$,” where we substitute values from the universe $\mathcal{U}$ in for the variable $x$. We can instead write “Consider the statements $\forall x \in \mathcal{U}\ [p(x)]$ and $\exists x \in \mathcal{U}\ [p(x)]$,” using the symbol $\in$ (a stylized Greek letter epsilon) to indicate that $x$ represents some value from the collection $\mathcal{U}$. A construct such as “$x \in \mathcal{U}$” is read as “$x$ is an element residing in universe $\mathcal{U}$.”

By extension, when we say something like “$\forall x \in \Psi\ [p(x)]$,” we’re saying that for all values $x$ found within a universe, which we’re denoting $\Psi$ (a capital Greek letter psi), $p(x)$ is a true statement.

Alternatively, when we write something like “$\exists x \in \Psi\ [p(x)]$,” this is equivalent to saying there exists some value, which we’ll refer to as $x$, residing in a universe denoted by the Greek letter $\Psi$, such that $p(x)$ is a true statement.

Quantified Laws of Logic

What can we deduce from knowing that a universally quantified open statement is true? What can we deduce from knowing that an existentially quantified statement is true? How are universally quantified statements and existentially quantified statements related to each other? In this section, we dig deeper into quantifiers, and explore propositional logic involving them.

A Simple Definition

Just like with ordinary statements, we can ask whether two open statements are logically equivalent.

Conjunctions and Disjunctions with Quantifiers

The previous example shows that the existential quantifier does not distribute over the conjunction operator $\land$. In other words, for general open statements $p(x)$ and $q(x)$,

It’s still true that whenever $\exists x\ [p(x) \land q(x)]$ holds, $\exists x\ [p(x)] \land \exists x\ [q(x)]$ holds as well — it’s just the reverse direction that can fail, as the previous example showed.

In general, we do have that

since if a value of $x$ within the universe exists that satisfies the disjunction, one of the statements in the disjunction must be true. So, the existential quantifier distributes over disjunction.

According to the previous example, for any two open statements $p(x)$ and $q(x)$,

though whenever $\forall x\ [p(x)] \lor \forall x\ [q(x)]$ holds, $\forall x\ [p(x) \lor q(x)]$ is guaranteed to hold as well.

On the other hand, it appears we have

So, the universal quantifier distributes over conjunction, but not over disjunction. We summarize the two equivalences below.

Negating Quantified Statements

For some open statement $p(x)$ and universe $\mathcal{U}$, what do $\neg \exists x\ [p(x)]$ and $\neg \forall x\ [p(x)]$ mean, exactly?

Focus first on $\neg \exists x\ [p(x)]$. Remember that $\exists x\ [p(x)]$ asserts that at least one value of $x$ makes $p(x)$ true. If we negate that statement, we’re saying that zero values of $x$ make $p(x)$ true (it’s nonsensical to talk about a negative or fractional number of satisfying values, so we can ignore those). Thus, $\neg \exists x\ [p(x)]$ asserts that no value of $x$ makes $p(x)$ true — in other words, every value of $x$ makes $p(x)$ false. This is equivalent to $\forall x\ [\neg p(x)]$, so

Now consider $\neg \forall x\ [p(x)]$. Remember that $\forall x\ [p(x)]$ asserts that every value of $x$ makes $p(x)$ true. So, naturally, the negation of $\forall x\ [p(x)]$ means that not every value of $x$ makes $p(x)$ true — hence, there must exist at least one value of $x$ that makes $p(x)$ false. This is equivalent to $\exists x\ [\neg p(x)]$, so

Let’s summarize this finding.

Multiple Quantifiers

In an earlier section, we examined propositional functions with two and three variables. For each variable in an open statement, we needed to substitute some value from the respective universe in order to determine the statement’s truth value.

Here, we look at quantifying statements with two or more variables.

Bound and Free Variables

Up to now, we’ve only dealt with quantified statements with a single variable — in every one of those examples, that variable was bound by whatever quantifier was used, and every quantified statement had a definite truth value.

In our definition above, any variable not bound by a quantifier is called a free variable. As such, statements like $\forall x\ [p(x, y)]$ and $\exists x\ [p(x, y)]$ don’t have a definite truth value. In both cases, we still need to either bind the variable $y$ with a quantifier, or substitute a value in for it from $\mathcal{U}$, before the truth value can be determined. This is important enough to highlight.

Repeated Quantifiers

In order for a quantified statement to have a definite truth value, there can be no free variables. We can bind every variable with the same kind of quantifier, which is useful, since there are many mathematical statements we can make that rely on more than one variable.

Notice that when the same quantifier is used, the order in which we express the quantification didn’t matter — this gives us our first logical equivalency for repeated quantifiers.

There’s a shorthand notation commonly used with repeated quantifiers. For some universe $\mathcal{U}$ and the open statement $p(x, y)$, we can use the following conventions:

Naturally, this extends to three variables — for the open statement $q(a, b, c)$, we can write

Of course, this can be extended to as many variables as needed.

Mixed Quantifiers

Some statements involve both the existential quantifier and the universal quantifier.

Based on the two previous examples, we know that we can’t just swap mixed quantifiers arbitrarily. Perhaps under very specific circumstances it could be done, but in general, it isn’t something we can do. This is worth highlighting.

As such, we need to exercise caution regarding the order of quantifiers.

Negating Multiple Quantifiers

One more thing to talk about is how to negate propositions involving multiple quantifiers.

For a given universe $\mathcal{U}$ and an open statement $p(x)$ defined on that universe, we saw earlier that

When negating a multiply quantified statement, we just need to keep punting the negation inside the quantified statement, one layer at a time, until all that’s left is to negate the contained proposition:

So, after punting the negation further inside each nested layer, we’ve determined that whatever open statement $p(x, y)$ represents,

This same strategy works for the other forms of multiply quantified statements, so we summarize the important combinations below.

A Final Word on Propositions in General

Throughout this chapter, we’ve spent a great deal of time working with logical expressions in the abstract. We’ve modeled them with truth tables to see when they’re satisfiable, and we’ve used logical equivalencies to simplify complicated propositions, as well as to expand simple propositions into complex ones. We’ve also examined how to work with variables, and what effect quantifying those variables has on a proposition’s truth value.

Remember that all of the letters we’ve used in our logical expressions — $x$, $y$, $z$, as well as $a$, $b$, $c$, and even $p$, $q$, $r$, $s$, and $t$ — all represent statements. Those statements could be primitive, as in

or they could be compound, as in

The purpose of all of this was to get a grip on mathematical logic. Translating English sentences representing mathematical statements into symbolic form gives us the ability to manipulate those statements using the logic studied in this chapter.

Translating a mathematical statement into symbolic form also forces us to be precise in our use of language when describing the exact problem we want to solve. Any misunderstanding invalidates any reasoning we may be able to employ, because at that point, the intended problem is no longer being discussed — a different problem, even if only slightly different, is being reasoned about instead.

With these logical tools at our disposal, we’re better able to accurately use language to precisely describe a problem of interest, and to then use the laws of logic to analyze it. Mathematical logic is the foundation of all mathematics yet to be learned, and will be employed heavily throughout the remainder of this book, and in future books.

Application: Modeling Logic Puzzles

Logic puzzles are almost everywhere, from supermarket puzzle books to viral posts on social media. Some are well known, like the Zebra Puzzle and Sudoku. Others are lesser known, including the Knights and Knaves puzzle.

Regardless of which puzzle is being tackled, the logical tools we’ve explored throughout this chapter can be used to work out a solution. In this section, we’ll explore a few different kinds of logic puzzles, and use mathematical logic to solve them.

Who Did It?

These kinds of puzzles involve a series of statements produced by an equal number of suspects. What’s known is that some number of the suspects are telling the truth, and the goal is to determine which suspect is the culprit.

The Knights and Knaves Puzzle

Knights and Knaves puzzles were originally posed by Raymond Smullyan. The premise is that on a certain island, there are two kinds of inhabitants: knights, who always tell the truth, and knaves, who always lie. Every inhabitant on the island is either a knight or a knave, but never both.

The Muddy Children Puzzle

This is another logic puzzle posed by Raymond Smullyan. Here, a father asks his two children whether they know if they have a muddy forehead.

The Common Theme

Notice that in the first two puzzles, our main strategy was to perform casework: for each case, we checked whether it was consistent with prior knowledge, and immediately discarded any case that led to a contradiction. The case that was consistent with everything we knew provided the answer to the puzzle.

The last puzzle was solved by working through stages, with an additional piece of information added at each stage. Accumulating new information at each stage was enough to solve the problem.

The common theme in each solution was breaking the puzzle up into several parts — whether stages or cases — and examining each part with an appropriate analysis. Breaking a logic puzzle up into stages or cases, then examining each one in turn, is the key to solving almost any logic puzzle.

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

Sets

Trying to precisely define a set can be rather tricky. While there are formal definitions and axioms, here we will rely on our intuition. Even without a formal specification, we can still derive many useful results that hold up under scrutiny.

In this section, we’ll learn what a set is (intuitively), and how to describe what kinds of things are in a set.

Intuitively Defining a Set

Sets, or collections, of objects abound in daily life. We could speak of the set of fruits available for purchase at a local grocery store, the set of birds native to North America, the set of components used to build a specific computer, the set of roads from New York to Los Angeles, and so on. We can make note of a couple of things here:

• The order in which we list the items in the collection doesn’t appear to be relevant. If we simply want to know what kinds of birds are native to North America, we can list the Wild Turkey before the Sandhill Crane, or the Sandhill Crane before the Wild Turkey.
• If we accidentally list an item more than once, that also doesn’t affect the set we’re dealing with. For example, if we list I-80 W twice by accident, it doesn’t change the fact that I-80 W is still a road between New York and Los Angeles. Sometimes we may care about this when planning a trip, but not if we just want to know what roads exist between New York and Los Angeles.
• However, if we miss an object — if it’s listed zero times — that does affect our set, because then our set is not complete. For example, if a local grocery store sells mangos but forgets to advertise them, they may lose out on customers who want to purchase mangos.

As such, the order in which we list elements from a set is irrelevant. The number of times we list an element from a set is also irrelevant. All we care about is whether or not an object is in a set or not.

Sets of objects also appear frequently in mathematics. We could speak of the set of numbers used to count objects, the set of points that make up a line in space, the collection of parabolas with real roots, the set of solutions to a system of equations, and so forth. Again, we don’t really care about the order in which these objects can be listed out, and we also don’t care if some objects from the set are listed more than once. However, in order to be a complete description, every possible object must be listed at least once.

By well-defined, what we mean is that, if presented with a description of some set $A$, we’re able to determine whether some given object — which we’ll refer to as $x$ — is an element of $A$, without any ambiguity.

Typically, we use capital letters such as $A$, $B$, $C$, $\dots$, $X$, $Y$, and $Z$ to represent sets. That isn’t always the case, but it’s fairly common. In contrast, we typically use lowercase letters such as $a$, $b$, $c$, $\dots$, $x$, $y$, and $z$ to denote elements.

Something else worth noting is that we enclose the elements of a set within curly braces $\{\ \}$, as demonstrated in the next example.

Building a Set

There are two primary ways to describe what kinds of elements are within a set.

One way is to simply list them all. Of course, this method is only practical if the desired set contains a small number of elements, though it’s perhaps the most specific, and leaves absolutely nothing to the imagination.

However, nothing stops us from defining sets that have infinitely many elements. When dealing with such a set, the Roster Method is somewhat inadequate on its own. We could list enough elements to make the pattern obvious, and finish with an ellipsis.

It’s because of this kind of ambiguity that another method of defining sets is more commonly used, called the Set-Builder Method. This method requires specifying a rule, or a list of conditions, that determine whether an element is a part of the set. Typically, this method looks something like this:

There are a few different parts to this notation, worth going over one at a time:

• $A$ — the letter, or general symbol, we use to refer to the set.
• $\{\ \}$ — the curly braces that enclose the definition of the set. Every set is enclosed by curly braces.
• $x$ — the letter, or again some general symbol, we use to refer to some element within the set.
• $\mid$ — this bar separates the listing of the element from the condition. When reading out the definition of a set, the vertical bar can be translated as “such that.”
• $\text{condition}$ — specifies what must be true about $x$ for it to be an element of $A$. In other words, the condition is what we use to test whether some object is contained within $A$.

As such, when we see something like $A = \{x \mid \text{condition}\}$, we can read this as “$A$ refers to the set of all elements $x$ such that the condition is satisfied.” There’s some flexibility in how this method can be used, as demonstrated below.

The Set-Builder Method is extremely useful for describing sets with infinitely many elements — but that doesn’t mean it isn’t useful for describing sets with finitely many elements too. This is especially true when there’s a large number of elements in the set.

Size of a Set

In the previous section, we saw sets that can have vastly different numbers of elements. Some sets have a finite number of elements, meaning that if we started to list out all of that set’s elements, we’d eventually be able to stop, having written down every element. In contrast, some sets have infinitely many elements, meaning that if we start listing elements and stop at any point in time, there would still be elements missing.

For finite sets, knowing the number of elements they contain can be useful.

Even though we don’t yet speak of the cardinality of an infinite set, it’s technically correct to say that the cardinality of an infinite set like $\mathbb{Z}$ is countably infinite. This idea will be explored later, when we talk about the different special sets of numbers.

Care must be taken when we’re dealing with sets that contain a wide variety of items. If a set has an element that is itself a set with multiple items, the elements of that inner set do not count towards the outer set’s cardinality.

Subsets

A set can contain a wide variety of objects. They can contain objects that most people interact with on a daily basis — automotive parts that can be used to service a 1967 Camaro, tools used to carve statues out of wood, or art supplies needed to paint a picture. Likewise, they can contain a wide variety of mathematical objects, like numbers, shapes, or axioms.

Sometimes, we only care about some of the objects in a set. For example, we may only be interested in automotive parts needed to service a car’s headlights, or we may only be interested in art supplies needed for a fresco painting. Regardless, we’re able to build a lot of structure by constructing new sets from old ones — simply by restricting what elements are included in the new set. Here, we explore this kind of relationship between sets.

Starting with a Base Set

If we’re interested in selecting only some of the elements from a set, we’ll need to know what the original, or underlying, set contains. This is exactly the same idea behind the Universe of Discourse discussed when we studied open propositions in Chapter 1. There, a Universe of Discourse (or simply Universe) was the set of all values we allow to be substituted in for the variables of a propositional function.

It’s the exact same situation here. We even commonly use the same script letter $\mathcal{U}$ to denote the base set, though we can still use any symbol we want.

Subsets

The definition of a subset is closely related to what we’ve discussed so far in this section. We start with a universe of discourse, and then construct a set using only elements from that universe. We could go even further, constructing a third set by only taking elements from that second set.

Notice that the above definition uses a universally quantified logical implication. This offers us a chance to review logical implications, and what they mean in the context of sets and subsets. Since there’s a logical implication involved, the proposition

is always true; thus, when we have $A \subseteq B$, there are only three scenarios to worry about:

Notice that there’s no row where $x \in A = 1$ and $x \in B = 0$ — since we’re asserting $A \subseteq B$, that scenario simply can’t happen.

Every Set Is a Subset of Itself

It’s also natural to wonder whether a set counts as a subset of itself. Recall that $A \subseteq B$ requires every element of $A$ to also be an element of $B$ — in other words, that $(x \in A) \to (x \in B)$ holds for every $x$. When $B$ is $A$ itself, that condition becomes $(x \in A) \to (x \in A)$, which is always true, since any proposition implies itself. So every element of $A$ automatically satisfies the requirement for membership in $A$, which gives us the following theorem.

Proper Subsets

Of course, when we assert $A \subseteq B$, all we’re saying is that whenever $x \in A$, we also have $x \in B$. However, this definition doesn’t say whether every single element of $B$ must be contained within $A$ too. We have a special term to describe when $A$ is a subset of $B$, but $B$ has elements not contained within $A$.

Notice that by the previous example, for two sets $A$ and $B$, it’s possible for both $A \subseteq B$ and $A \subset B$ to be true. However, that’s not always the case, as demonstrated by the next example.

Based on the previous two examples, it seems that if we know $A \subset B$, we also know $A \subseteq B$. Let’s formally show this is the case.

Notice that if we know $A \subseteq B$, we don’t automatically know $A \subset B$. For example, we have $A \subseteq A$, but $A \not\subset A$.

The Empty Set

Just because we can put just about anything in a set doesn’t mean we need to have something in a set. There’s a special and unique kind of set that has no elements in it at all!

The empty set is a very special set, and occurs throughout all of set theory, but it does have some interesting quirks that are a bit strange at first, though they become more natural as we work more and more with this kind of set.

First, note that because it’s a set containing nothing, we can write

There’s absolutely nothing written in between the curly braces, so we have, for example, that $\emptyset \neq \{0\}$ — above, we wrote a single number between the braces, and since $\{0\}$ is a set containing one item, it’s not equal to the empty set.

The second thing to note is that a set can have the empty set as one of its elements:

Because $S$ is a set containing one element (that element itself being a set), we have $|S| = 1$. Thus, since $S$ contains at least one element, it’s not the same thing as the empty set, even though it’s the set containing the empty set: $S \neq \emptyset$. Comparing $S$ to $\emptyset$, since $\emptyset$ contains no elements, we have $|\emptyset| = 0$. If we substitute $\{\emptyset\}$ in for $S$, we see that $\{\emptyset\} \neq \emptyset$.

The Empty Set Is Always a Subset

Recall the definition of subset, which states that $A \subseteq B$ when every element in $A$ is also an element of $B$. In other words, $(n \in A) \to (n \in B)$ is always true. We use that definition, as well as the definition of the empty set, in our next theorem:

Notice that in this theorem, we didn’t place any special requirements on set $A$ — it just had to be an arbitrary set constructed from some universe $\mathcal{U}$. Thus, by the Rule of Universal Generalization, since $A$ was arbitrary, and we have $\emptyset \subseteq A$, the empty set must be a subset of every possible conceivable set — including the universe $\mathcal{U}$ itself!

Proof Technique: Element Arguments

In the previous two sections, we provided proofs for two theorems (Theorem 3.4.1 and Theorem 3.3.1). Both proofs required that we select an arbitrary element from some set $A$, and show that because that arbitrarily chosen element satisfies some property, all elements of set $A$ satisfy that property. This is simply a rehash of the concept of Universal Specification and Universal Generalization as discussed in Chapter 2.

In this section, we adapt the methods of Universal Specification and Universal Generalization to a new, powerful proof technique we can use for sets.

The Underlying Argument

Here, we show off the basic structure of the argument that underlies an element argument.

Let’s suppose $p(x)$ and $q(x)$ are open statements defined on some set $A$ (here the set $A$ is acting like our universe set $\mathcal{U}$).

Even though every element argument follows this basic structure, pay close attention to step (4). Notice that the reason given was either an axiom, definition, premise, or theorem. This is the part of the argument that changes with each and every property we’re trying to show is true for every element of some given set $A$. Depending on what we’re trying to show, we’ll need to bring in multiple axioms, definitions, premises, or theorems in order to reach the desired conclusion.

Typically, step (4) will be expanded into multiple steps, depending on how many axioms, definitions, and theorems are needed to get from proposition $p(c)$ to $q(c)$.

Some Straightforward Theorems

Here is one basic theorem whose proof relies on a fairly typical element argument.

Let’s rewrite this proof using the structure presented above.

This particular proof was a one-to-one translation of the basic structure of an element argument. Let’s look at a theorem that takes a little more work to prove.

This proof required that we give a name to an element we knew existed — namely, an element that was contained within $C$, but was not contained within $B$, and as such not contained in $A$ either. There’s a special name we give to this situation, which we describe below.

Existential Specification and Existential Generalization

When we discussed quantifiers, we talked about two different kinds: those of the universal variety, and those of the existential variety. The Universal Quantifier has its own specification and generalization schemes, and the Existential Quantifier naturally has its own counterparts.

The concept of Existential Specification comes into play when we know some element exists, and in order to manipulate that element, we simply give it a name. In other words, if we know that

then we can simply use a symbol to refer to that particular element where $p(x)$ is a true statement. The exact symbol chosen doesn’t matter: it could be the letter $c$, a Greek letter like $\beta$, or some geometrical symbol like $\square$ — just as long as we’re consistent with what symbol is used. For example, knowing that $\exists x \in \mathcal{U}\ [p(x)]$ is true, we could use the letter $c$ to denote the particular element within $\mathcal{U}$ such that

The concept of Existential Generalization is essentially the reverse of Existential Specification. If we know that the particular element $c \in \mathcal{U}$ makes the open statement $p(x)$ true, meaning $p(c) = 1$, then we know that some element exists that makes $p(x)$ a true statement (because we identified such an element), meaning we know that

We implicitly used Existential Specification and Existential Generalization in the proof for Theorem 3.5.2. Since we’re discussing a general proof strategy, let’s write out a formal argument in tabular format, as we’ve previously done for Theorem 3.5.2:

As can be seen, even though we can formally lay out every step of our proof in a tabular format, the paragraph format presented above is perhaps more readable and less cumbersome to write.

Two Additional Theorems

We’ve already examined the theorems

and

We could naturally examine situations involving both regular subsets and proper subsets.

Element arguments represent a powerful proof technique because they give us a way to account for what elements are in what sets, which will be an important skill in the upcoming sections when we start to talk about how we can combine and operate on sets.

Remember that when we talk about a set, what we care about is whether some given object is a member of that set or not, so by picking an arbitrary element, we can use the subset relationships discussed so far to determine if that element is a member of any other set.

A Set of Operations on Sets

We’ve discussed how to construct new sets by simply taking some of the elements from one set and putting them into a new set. While subsets are vitally important not only in Set Theory but throughout all of mathematics, subsets are formed by only considering one set at a time.

We can construct a wide variety of sets by considering two or more sets at a time. In this section, we learn what kinds of sets we can construct by considering more than one set at a time.

Complement

Before we talk about more than one set at a time, let’s talk about one more operation that only relies on one set. Technically, it does require two sets, because this particular operation requires knowing what universe is being considered — every element in the universe that isn’t in $A$ ends up in $A$’s complement.

The idea of set complement is really simple: we take all elements within $\mathcal{U}$ that are not in $A$, and put all of those elements in a new set we usually call either $A^C$ or $\overline{A}$, though occasionally other names are used.

Of course, the essential property we care about when it comes to sets is whether a specific element is a member of that set or not. How do we tell that an element $x$ is in $A^C$ or not? Based on the definition of complement, we see that the following logical equivalency is used to test if $x$ is in $A$’s complement:

Union

Now that we’ve talked about what’s outside a set, we can start to consider what happens when we combine two sets into one.

The first thing we can do is take all elements from two different sets, and simply mash them all up into one set.

As long as an element is in $A$ or $B$, or even both $A$ and $B$, it will be included in the union of $A$ and $B$.

One situation not yet considered is when one set is entirely contained within another. Because a union consists of elements contained in either set, this means that the union will actually just be whichever set contains the other one — since every element of the smaller set is already an element of the larger one, unioning them adds nothing new.

Intersection

Another kind of set we can compose from two other sets is to take elements that are in both sets. Here, we’re not taking elements that are present in either set; instead, we demand that the elements are present in both sets.

Just like with the union of two sets, we’d like to determine if an element $x$ is contained within the intersection of two sets. There’s a logical equivalency we can use to determine if element $x$ is contained within $A \cap B$:

Before continuing on, it’s worth pointing out the similarity between the union and intersection symbols and the logical or and and operators, respectively:

When two sets in question don’t overlap at all, there’s nothing in the intersection. Of course, this means that the set $A \cap B$ has nothing in it, or in other words,

This means that the intersection of two sets with nothing in common is simply the empty set.

When one of $A$ or $B$ is a subset of the other, the intersection will end up just being whichever set was the subset.

Difference

It’s possible that we may want to exclude certain elements from the universe within any sets we construct. Of course, any given set can contain any element from the universe, whether or not we want it included. One thing we can do to remedy such a situation is to collect all of the elements we want excluded in a special set, which we’ll refer to as $B$ for now (an “exclusion set”). Then, for some given set we’ll call $A$, we can make a new set by removing all elements from $A$ that are also in $B$. This gives us a new set containing all elements from $A$ that we don’t want excluded.

$A - B$ consists of whatever’s left of $A$ once every element $A$ shares with $B$ — that is, every element of $A \cap B$ — has been removed.

Once again, there’s a logical equivalency we can use to determine if a given object is contained in the set $A - B$:

Care should be taken when one of the sets is a subset of the other (in other words, when one of the sets is entirely contained within the other). If $B$ is a subset of $A$, then $A - B$ consists of exactly those elements of $A$ that aren’t also in $B$. But if $A$ is entirely contained within $B$, we’d have to remove every element of $A$, leaving us with the empty set $\emptyset$.

Based on the previous example, it seems that if $A \subseteq B$, then $A - B = \emptyset$. Is that true for every single set? In a later section, we’ll start to use element-argument-style proofs to determine if that’s indeed the case, but for now, our intuition on the matter seems clear.

Symmetric Difference

With set difference, we only consider elements that are in $A$ but not in $B$. With a symmetric difference, we instead want elements that are either in $A$ and not in $B$, or in $B$ and not in $A$.

The symmetric difference consists of everything covered by the union of $A$ and $B$, except whatever’s also covered by their intersection — in other words,

Of course, we can examine given objects to determine membership in such a set:

When one set is a subset of the other, the symmetric difference essentially carves the smaller set out of the larger one — it’s called a symmetric difference because it’s essentially a difference between the larger set and the subset.

We saw in the previous example that $S \triangle E$ and $E \triangle S$ ended up being the exact same set. Is that always the case? In a later section, we’ll use an element argument to demonstrate that this observation does indeed hold in general.

Multiple Unions and Intersections

We can combine as many sets into a new set as we want. However, before we start combining multiple sets into one, we should recognize that dealing with multiple sets can be cumbersome. First of all, imagine having to deal with multiple sets with a wide variety of names that were hard to track. We can mitigate this issue by coming up with a naming scheme that makes each set we’re dealing with easy to track.

Before looking at an example, let’s stress the fact that an index set is basically used to enumerate and track sets, and so doesn’t necessarily need to be taken from some universal set (though it could be taken from its own particular universal set).

It’s worth noting that this kind of index set is impractical, and so won’t be used going forward unless there’s some niche application where it would be useful.

With an index set to help us, working with multiple sets is easy.

As always, if we want to check to see if a given object is in this set, all we have to do is check to see if that object is in at least one of the sets making up the multiple union:

Of course, if the index set uses whole numbers starting from $1$ and ending at $n$, we can instead write this logical equivalency as

Naturally, there’s an intersection counterpart to the multiple union.

Checking if a given object is in the multiple intersection of a collection of sets works nearly the same as checking if it’s in the multiple union, but we need to make sure the object is in all sets, which we can check with multiple and operations:

Of course, if the index set uses whole numbers starting from $1$ and ending at $n$, we can instead write this logical equivalency as

Graphical Depictions of Sets

In the previous section, we defined the complement, union, intersection, difference, symmetric difference, multiple union, and multiple intersection of sets purely symbolically. While the symbolic definitions are precise, it’s often easier to build an intuition for what these operations actually do by picturing them.

The standard way to picture a set is as a circle, with each circle drawn inside a rectangle standing for the universe $\mathcal{U}$. Whenever an operation includes some region formed by these circles, we shade that region green.

Complement

Since the complement of $A$ consists of everything in the universe that isn’t in $A$, the circle for $A$ itself is left unshaded, while everything else within the surrounding rectangle is shaded to represent $A^C$.

Union

As long as an element is in $A$ or $B$, or even both, it’s included in the union — so both circles are shaded in their entirety, overlap included.

Intersection

Here, only the sliver shared by both circles is shaded, since that’s the only region representing elements common to both $A$ and $B$.

Difference

Only the part of $A$’s circle left over once the overlapping sliver shared with $B$ has been carved away is shaded.

Symmetric Difference

The symmetric difference shades everything covered by either circle except the overlapping sliver shared by both — everything a union would shade, minus whatever an intersection would shade.

Multiple Union

This same idea of shading extends naturally to more than two sets at once — every region covered by at least one of $A_1$, $A_2$, or $A_3$ is shaded to represent their multiple union.

Multiple Intersection

Here, only the single region shared by all three circles at once — where $A_1$, $A_2$, and $A_3$ all overlap — is shaded, representing their multiple intersection.

The Laws of Set Theory

Understanding the laws of set theory is essential because they solve the problem of determining when two or more sets are equal, through fundamental equations including associativity, commutativity, and distribution. These laws provide a structured framework for defining and manipulating sets, ensuring consistency and precision in operations such as subset, difference, and symmetric difference.

In other words, by developing laws of set theory, we can essentially manipulate equations involving sets as if they were algebraic equations. In addition, the laws of set theory will allow us to convert complicated expressions involving sets into simpler ones, much like how we took complicated logical expressions and simplified them into smaller, logically equivalent expressions.

By studying these laws, one can formulate and prove mathematical concepts and theorems accurately. Furthermore, the foundations of many branches of mathematics are developed using the language of sets and set theory. In addition to the further development of mathematics, these laws also prove crucial to subjects like computer science and data science.

Equal Sets

We’ve briefly described some aspects of set equality when we first introduced what sets were. We talked about how repetition and order are irrelevant with respect to what elements are contained within a set. As such, even if some elements are repeated in various descriptions, they still represent the same set.

However, as we’ve also seen, there are a wide variety of methods to describe a set and what elements are contained within it. Just because we come up with different descriptions, that doesn’t necessarily mean we’re describing different sets — sometimes we may be describing exactly the same set.

However, defining set equality by having the same elements isn’t exactly rigorous. Two sets can share some number of elements while also having different elements. As such, we don’t define set equality by simply having the same elements — instead, we look to the end of the previous example for inspiration.

This definition is precise because we can determine whether a set is a subset of another set under scrutiny. As such, because the definition of set equality requires we show two things to be true, proofs showing two sets to be equal are usually broken up into two parts.

It’s this definition of set equality that makes the next two theorems somewhat straightforward to prove.

Thus, by this theorem, whenever we know that $A \subseteq B$, we can replace $A \cap B$ with just $A$ anywhere we see $A \subseteq B$ in an equation. It’s worth stressing that we can only make such a replacement when we know $A \subseteq B$ — otherwise, doing so may not be correct.

There are a few more such equalities we can make use of, which we now show in the next theorem.

Because of this theorem, whenever we know one of

is true, we automatically know that the other three are true as well.

Disjoint Sets

The total opposite of two sets $A$ and $B$ being equal is when $A$ and $B$ have absolutely no elements in common. Of course, if two sets share no element in common, then their intersection is a set with no elements in it — the empty set.

Many of the concepts discussed so far may seem disparate. However, they’re more connected than may initially appear.

This theorem connects the concepts of equal sets, disjoint sets, unions, and symmetric differences.

Membership Tables

Remember that $x \in A$ is a statement about $x$ being a member of set $A$. Because it’s a statement, it has a truth value of either $0$ or $1$.

One powerful tool we had at our disposal for analyzing logical expressions was a truth table. We can adapt truth tables to analyze set relationships as well. In this case, membership tables offer a tabular way of representing element arguments.

Instead of using some generic symbol for a generic object whose membership in some set we want to analyze, we could simply list whatever sets we’re analyzing. As such, we could rewrite the above table like so:

All of the set operations have their corresponding tables, which we can include inside one large table:

Based on the values above, we see that there are obvious analogues with logical operators:

Notice that the set difference resembles the logical complement of an implication.

In addition to the set operations, we can determine subset relationships. Let’s take a look at one more table to see an example:

Notice that the columns $(x \in A \cap B) \to (x \in A)$ and $(x \in A) \to (x \in A \cup B)$ have all $1$s. As such, we can write

which is exactly the definition of subset. As such, we can determine that a set $A$ is a subset of some other set $B$ by comparing their respective columns. If $A$ has $1$s in every row where $B$ also has a $1$, then we know that $A \subseteq B$.

Let’s prove a simple observation we may have had in our study of set relationships and operations.

Membership tables can be a convenient way to represent an element argument in tabular form. However, membership tables won’t totally replace element arguments, as sometimes the element argument is simpler to make for more esoteric situations where tables can be cumbersome to use.

Some Laws of Set Theory

We’ve already examined a number of simple laws (referred to as theorems) above, and have demonstrated their truth by way of element arguments and membership tables. What’s demonstrated above only scratches the surface of the multitude of equal-set relationships we can exploit. Below, we present a large table offering even more such laws.

As you look over this table, it would be wise to compare it with the table presented in Chapter 1, Section 5. You should see many analogues.

For any sets $A$, $B$, and $C$ taken from some universal set $\mathcal{U}$, we have the following equivalencies:

Certainly, many more such laws and equivalencies exist, but the table above represents some of the more ubiquitous laws that are often used.

These laws present us an opportunity to directly compare three different proof techniques. First, we use a membership table.

Now, compare such a simple strategy with a standard element argument used in the next proof.

The last of these laws we’ll prove in this section will be the Distributive Laws. Instead of making two separate element arguments to establish that $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$ and $(A \cup B) \cap (A \cup C) \subseteq A \cup (B \cap C)$, we’ll use logical equivalencies to show that $A \cup (B \cap C)$ and $(A \cup B) \cap (A \cup C)$ are subsets of each other simultaneously.

Of course, the rest of the Laws of Set Theory can be proven in many different ways. Because it’s a good exercise to provide a proof for all the above laws, proofs for the remaining laws are asked for in this chapter’s practice questions.

Using the Laws of Set Theory

Just as we can use the Laws of Logic to simplify complicated logical expressions, we can also use the Laws of Set Theory to simplify complicated expressions involving sets.

We made use of an additional law of Set Theory above, where we can express the set difference operation using only intersection and complement:

We’ll now justify that equality:

For any two sets $A$ and $B$ taken from some universal set $\mathcal{U}$, we have that

As a matter of fact, we can also express the symmetric difference operation using only union, intersection, and complement, which we justify below:

For any two sets $A$ and $B$ taken from some universal set $\mathcal{U}$, we have that

This just goes to show how important the union, intersection, and complement operations are when it comes to sets, because no matter how we want to combine any combination of sets, we can always do so using just those three operations.

Generalized DeMorgan’s Laws

We’ve seen DeMorgan’s Laws applied to two sets at a time. Let’s see what happens when we have three sets at a time:

It stands to reason that repeated applications of DeMorgan’s Laws would work for intersection as well.

Furthermore, no matter how many sets we have, it seems as if we can just repeatedly apply DeMorgan’s Laws and the Associative Law. Based on this observation, we make the following observations, where $I$ is an index set over which the multiple union or intersection is taken:

Of course, mere intuition doesn’t prove anything to be true. Instead, we must rely on rigorous tools, such as element arguments and logical equivalencies, to establish truth without any doubt.

The generalized versions of DeMorgan’s Laws will prove extremely useful in our further study of math.

Proof Technique: Exhaustion

All of the proof techniques discussed thus far work on sets that have infinitely many elements. For example, we’ve talked about theorems that apply to all even numbers, not merely some of them. For example, for all even numbers, adding one yields an odd number. As another example, no matter which two even numbers are added together, the sum is always another even number.

We’ve even talked about theorems that apply to all sets in general, not merely some of them. These include the set operations and the set equalities.

It’s not hard to see why methods that apply to sets of infinitely many objects are powerful. On the other hand, there may be times when there are only a finite number of objects we’re interested in examining. Here, we discuss a method for proving theorems dealing with only a finite number of elements.

A Contrived Example

Admittedly, dealing with only a finite number of elements seems hardly useful, as we mostly want results that apply generally, and not specifically. Here, we provide a contrived example simply to demonstrate the technique.

We could perhaps call the result derived in the previous example a theorem, since we did provide a proof for the fact, but we prefer to reserve the term theorem for “major” results. That result was merely an exercise.

The Method of Exhaustion

Based on the previous example, we can see why the method presented in this section is called the Method of Exhaustion: it’s because we exhaustively check every single element in the desired set for a desired property. Note that while the term exhaustion is used to describe the thoroughness of checking every element, it doesn’t necessarily refer to the feeling one may get whilst performing the checking — though it should be said that for rather large sets, this method can be tiresome.

Let’s lay out the argument in logical fashion, same as we’ve done before. The reason this method works is because we verify that every element in the desired set has some desired property.

Suppose set $A$ is a finite subset consisting of the $n$ elements

taken from some universal set $\mathcal{U}$. Furthermore, suppose $p$ is an open statement defined on $\mathcal{U}$. The Method of Exhaustion is simply an argument of the form

That’s all there really is to it.

Computer-Assisted Proofs and the Four Color Theorem

Just because a set is finite doesn’t mean it’s feasible to hand-check every single element within it. Sometimes tasks can be automated by writing computer programs to check thousands or even millions of elements in a timely fashion.

While the example presented above was rather contrived, one major result proved using the Method of Exhaustion was the Four Color Theorem. This theorem states that any planar (basically meaning flat) map only needs at most four different colors so that no adjacent regions on the map share the same color. For centuries, cartographers have been making maps of various places around the world, and one way to draw maps is to color regions so they’re easily distinguishable. It’s typically expected that adjacent regions on a map are colored differently, helping them stand out visually.

It was shown at some point in the late 1800s that no more than five colors were needed for any map so that no adjacent regions shared a color, but it was suspected that no more than four colors were needed as well. Though many mathematicians attempted to prove that no more than four colors were needed, many efforts proved fruitless.

Progress marched forward in the 1960s with the advent of computing technology. Two mathematicians, Kenneth Appel and Wolfgang Haken, further developed results derived from Heinrich Heesch to complete a proof. Essentially, one major step in the proof was showing that all maps could be “reduced” to a small number of essential configurations (basically, all maps are distortions of some simpler underlying map that represent the same types of regions). Appel and Haken found that there were only $1834$ such configurations.

Once Appel and Haken found these configurations, it was simply a matter of checking each and every one of them — using the Method of Exhaustion.

This proof was the first major proof to be verified by computer. As such, it was a controversial result: not all mathematicians readily accepted the proof, because it was hard and time-consuming for a human to check.

Nevertheless, the proof has mostly withstood scrutiny, with a minor error being corrected by Appel and Haken sometime in the late 1980s.

The point is that while the Method of Exhaustion may seem overly simple and contrived, being restricted to only finite sets instead of infinite sets, it’s still a valid proof technique that can come in handy.

Set Partitions

When working with a set of related objects, we may want to split that set up into smaller, more manageable sets.

For example, we may want to split up the integers based on parity: even integers, and odd integers. When dealing with the real numbers, we may want to split them up into three separate sets: the positive real numbers, the negative real numbers, and the number $0$. One more example may be the positive rational numbers, where we split them up based on how big they are — we may have all of the positive rational numbers less than $1$ in one set, and all of the positive rational numbers greater than or equal to $1$ in the other set.

No matter how we split up a set, we’ll want to make sure that all elements of the original set are accounted for in one of the smaller subsets we form.

Partitioning a Set

In the introduction to this section, we mentioned three examples of how we may split a large set into smaller subsets, making sure every element within the original set is in one of the subsets. A partition of a set creates these subsets while making sure that every element is accounted for; however, the word partition also invokes the idea of separation — no two subsets should share any elements. The following definition of partition offers something more precise.

Note that none of the sets in the partition can be empty. The whole point of forming a partition is to take elements from the original set and put them into a subset.

Examples of Partitions

Proof Technique: Casework

Previously, we talked about a proof technique where we examine every single element of a finite set. In a sense, we examined multiple cases, and verified some result for each of those cases. An exhaustive proof is a special kind of proof by casework.

Sometimes, we may have trouble demonstrating that some result holds for a set of elements. However, if we partition the set into groups that have their own special traits, and those traits make it easy to show the desired result holds, a proof by casework can be used to establish the desired result for the entire set.

The Underlying Argument

Suppose we were trying to prove a statement of the form

Suppose that we somehow knew that

If we knew how to show that

we would then have that

Thus, because $p = p_1 \lor p_2 \lor p_3 \lor \dots \lor p_n$, we would also have that $p \to c$ by extension.

This proof technique is simply an extension of the Rule of Proof by Cases:

as presented in Chapter 2, Section 6. Even though we could have discussed this proof technique in Chapter 2, we decided to hold off until partitions were discussed, because a lot of casework is done by considering elements from disjoint sets. However, when doing casework, it’s not important that elements from the universe of discourse are in only one subset of a partition.

Whether we form a partition of the universe, or we split the universe up into overlapping subsets, isn’t important. What’s important is that, once we have our desired subsets, every element is represented by at least one of those subsets.

Picking Arbitrary Elements from a Partition

When we partition a set, we split it into disjoint subsets where every element is accounted for in one of the subsets. We don’t have to form these subsets arbitrarily. Instead, we could take all elements from the original set that have some common property, and stick those elements into a subset. We can repeat this process until all elements are accounted for.

Then, from each of these subsets, we choose an arbitrary element. Then, whatever is true of that element will be true for all elements within that subset. In essence, we’re using the principles of Universal Specification and Universal Generalization, along with a partition, to prove a theorem.

Our first theorem will be a result about absolute values of real numbers. As a reminder, here’s the definition of absolute value of a real number.

An Example with Lots of Cases

Here, we’re going to discuss perfect squares and what kinds of numbers can be the units digits of perfect squares. Before we discuss the next theorem, let’s make some observations about the non-negative integers.

From the observations presented in the previous example, we see that any non-negative integer can be written as $10a + b$. This observation will help us in the upcoming theorem.

A Common Mistake

The most common error that can occur when doing a proof by cases is not accounting for every element in the universe being considered. It is essential that all the cases you consider account for every possible element.

It may seem like the previous example demonstrates that $n^2 \geq n$ for all integers. After all, we showed it was true for positive integers and negative integers. However, there’s one integer that’s neither positive nor negative, namely $0$. In this situation, since it’s only one integer left unaccounted for, we could simply compute $0^2$ and compare it to $0$ to determine that the above statement is indeed true for all integers. We formalize this proof now.

Russell's Paradox and a Formal Resolution

Sets are a powerful abstraction that allows us to collect a wide variety of objects into one structure. Typically, all objects within a set share some common characteristic other than mere inclusion in the set. They may be points on the plane, equilateral triangles, even numbers, or even fruits.

As powerful as sets are, we haven’t given a formal definition of what a set is. We’ve been relying on an intuitive definition, and though it works well enough for our purposes, sooner or later the cracks start to show. Sometime around 1901, a mathematician named Bertrand Russell formulated his now-infamous paradox that seemed to dismantle the entire theory of sets. The scary thing about the paradox is that a lot of mathematical research and important results rested on the foundations of Set Theory. If Set Theory is wrong, are all results depending on sets wrong as well?

In this section, we’ll eke out what this paradox is, and hint at a solution that solves the problem.

Sets That Are Members of Other Sets

Over the course of this chapter, we’ve defined sets that mostly have numbers, though we’ve constructed other more intricate sets. Sometimes we’ve constructed sets that contain other sets.

We’ve got a handle on this situation, but let’s ask a more interesting question:

Can a Set Contain Itself?

What would it look like for a set to contain itself? Let’s see if we can make such a set.

Determining if a set is contained in another set when both sets contain infinitely many elements takes some care, so we’ll sidestep that issue by considering the following set:

What kind of set is $\boxtimes$? It’s a set whose elements are sets. But these are special sets. In the previous example, we were concerned with what a set that contains itself would look like. Here, we don’t scrutinize whether a given set contains itself. Instead we’re just assuming that we’ve somehow curated every set, and are only including sets that don’t contain themselves.

Now consider the following question: is $\boxtimes$ contained within $\boxtimes$? Remember that for propositions such as $\boxtimes \in \boxtimes$, there are only two possibilities: either $\boxtimes \in \boxtimes = 0$ or $\boxtimes \in \boxtimes = 1$. Let’s consider both possibilities.

Case 1: $\boxtimes \in \boxtimes = 0$.

Here, we’re considering the possibility where $\boxtimes$ doesn’t contain itself. Well, since $\boxtimes \notin \boxtimes$, we know that

However, notice what the logical implications are if $\boxtimes \notin \boxtimes$: either $\boxtimes$ is not a set (it is, so this would be a contradiction) or $\boxtimes \in \boxtimes$ (which contradicts the supposition that $\boxtimes \notin \boxtimes$). Either way, the proposition $\boxtimes \notin \boxtimes$ yields contradictions. As such, we may suspect that $\boxtimes \in \boxtimes = 1$. Let’s check.

Case 2: $\boxtimes \in \boxtimes = 1$.

Suppose we somehow knew that $\boxtimes \in \boxtimes$.

So, by assuming $\boxtimes \in \boxtimes$, the logical implication is that $\boxtimes \notin \boxtimes$? This is a clear contradiction.

At this point, both cases yield contradictions. This could be a problem, but solutions do exist.

Resolving the Paradox

How come we haven’t had this problem dealing with any of the previously defined sets in this chapter? It has to do with the fact that we were constructing sets with particular objects. Even numbers are easy to grasp, quadrilaterals are easy to grasp, but abstract set requirements aren’t so easy to grasp. We even had trouble trying to come up with a set that contained itself in the second example above.

While not a resolution to the paradox, defining sets using easy-to-grasp elements does at least avoid the issue.

Perhaps the most commonly used formal system of Set Theory is ZFC Set Theory. ZFC is short for Zermelo–Fraenkel–Choice, where Zermelo and Fraenkel are the two mathematicians who formulated this type of Set Theory, and the word choice refers to the Axiom of Choice, which is something that will be examined later in this book.

ZFC Set Theory came around in the early 20th century, and is free of paradoxes like Russell’s Paradox. ZFC Set Theory is an intricate system, and requires some more advanced mathematics to understand. While it isn’t discussed in this book, further reading on ZFC Set Theory and on the history of Russell’s Paradox is easy to find, for anyone curious enough to look into how it inspired the search for more axiomatic systems of Set Theory.