Elementary discrete mathematics

Table of contents

• Front page
• Summer I 2020 syllabus
• Problems
• 0. What is discrete mathematics?
• PART 1: SETS AND LOGIC
• Part 1 videos
• 1. Sets
• 2. Propositional logic
• 3. Predicate logic
• PART 2: PROOF AND RECURSION
• Part 2 videos
• 4. Proofs
• 5. Recursion and integer representation
• 6. Sequences and sums
• 7. Asymptotics
• 8. Proof by induction
• INTERLUDE
• PART 3: COMBINATORICS
• 9. Introduction to combinatorics
• 10. Ordered samples
• 11. Unordered samples
• 12. Multinomial coefficients
• 13. Probability
• PART 4: RELATIONS
• 14. Boolean matrices
• 15. Relations
• 16. Closure and composition
• 17. Equivalence relations
• 18. Partial orders
• EPILOGUE

0. What is discrete mathematics?

0.1 It’s math you do quietly, right?

The phrase “discrete mathematics” is often used nebulously to refer to a certain branch of mathematics that, from the college point of view, is “not calculus” or perhaps is applicable to computer science. In this section, we will try to understand what it means for a topic to fall under the umbrella of discrete mathematics.

0.2 But really, what is it?

Here’s a question: What is the next number after $1$? Your answer depends on “where you live,” so to speak. If you live in the rational numbers (numbers that can be expressed as fractions, like $3/7$) or the real numbers (including numbers that can’t be written as fractions, like $\pi$), you can’t answer the question. If you give be a real or a rational number that’s a little more than $1$, say $1.1$, I can find something even smaller; say, $1.01$.

If you live in the set of natural numbers, which is the set of numbers that are useful for counting things in the world, the question does have an answer: $2$. The natural numbers do not suffer from the crowding issue that the rationals and the real do; all of their elements are sufficiently “far apart” in this way. There is $1$, and then $2$, and nothing in between. In this sense they are discrete. In this book, we will (usually) live in the natural numbers.

0.3 Some examples

Here are some questions we might try to answer using discrete mathematics. In fact, you will be able to answer all these questions by the end of the book.

Suppose we have a program that will activate condition 4 if conditions 1 and 2 are met but not condition 3. How do we know when condition 4 is active?

We can use logic to represent this program with the statement $(p \wedge q \wedge \neg r) \to s$, and then use truth tables to determine exactly when condition 4 will trigger.

Which of these two programs is more efficient?

A sequence is a function of natural numbers. An example is the number $(a_n)$ of steps it takes to run a computer program with $n$ inputs. If $(a_n)$ grows must faster than $(b_n)$ does, that can tell us that one program scales worse for large quantities of data.

Some members of a community are sick. How do we know who is at risk of being infected?

Relations encode relationships between sets of objects. We may compose relations to iterate those relationships over and over again. If person $x$ is sick and has come into contact with person $y$, and $y$ has come into contact with person $z$, and $z$ has since seen $w$, then $w$ is at risk.

0.4 How to use this book

Chapters 1-8 must be done in order. Each chapter has a section of exercises located on the problems page. These exercises should be attempted after each chapter. If you are in MATH 174 at Coastal Carolina University, these exercises are your homework.

Then, chapters 9-13 (on combinatorics) and chapters 14-18 (on relations) may be attempted in that order, or in the order 14-18; 9-13. Be aware that some of the exercises in 14-18 assume that the reader has learned the combinatorial material. So, if you follow the alternate order, leave these exercises for later.

This book is paired with a four playlists on my YouTube channel. Playlist 1 (sets and logic) maps to chapters 1-3, playlist 2 (proof and recursion) maps to chapters 4-8, playlist 3 (combinatorics) maps to chapters 9-13, and playlist 4 (relations) maps to chapters 14-18.

These videos are very short demonstrations and examples of the material pursued in depth by the book. I am not sure which ordering is better: book then videos, or videos then book. Choose your own adventure.

I try to use the invitational “we” throughout the book and maintain some level of formality, but sometimes my annoying authorial voice pokes through. I apologize if that bothers you.

Each chapter ends with several “takeaways” that summarize the chapter. Starting with the fourth chapter, if necessary, each chapter begins with hint to go back and look at some things you may not have thought about in a while.

0.5 The point of this book

– is to teach you discrete mathematics, of course.

But much more broadly, this book is intended to teach you to think mathematically. You may be a student who has never seen any math beyond calculus or algebra, or perhaps you dread doing math. The point of this book is to get you to learn to think deeply, communicate carefully, and not shy away from difficult material.

As you proceed, have something to write with on hand. Work each example along with the book. Then, at the end of each chapter, work the exercises. Some are more difficult than others, but are well worth doing to improve your understanding. Work along with someone at roughly your skill level, share solutions and ask each other questions.

Everyone can be a “math person!” So, let’s get started.

1. Sets

Videos:

• Introduction to sets
• Containment
• Algebra of sets

1.1 Membership

For nearly all interested parties, sets form the foundation of all mathematics. Every mathematical objects you have ever encountered can be described as a set, from numbers themselves to functions and matrices.

We will say that a set is an unordered collection of objects, called its elements. When $x$ is an element of the set $X$, we write $x \in X$.

Examples. Our starting point will be the set of all natural numbers,

$\mathbf{N} = \{0,1,2,3,\ldots \}.$

Certain sets are special enough to get their own names, with bold or “blackboard bold” face. Sometimes (especially in ink) you will see $\mathbb{N}$ instead. Note that the elements of the set are enclosed in curly braces. Proper notation is not optional; using the wrong notation is like saying “milk went store” to mean “I went to the store to get milk.” Finally, not everyone agrees that $0$ is a natural number, but computer scientists do.

If we take $\mathbf{N}$ and include its negatives, we get the integers

$\mathbf{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots \}.$

Notice that in the case of an infinite set, or even a large finite set, we can use ellipses when a pattern is established. One infinite set that defies a pattern is the set of prime numbers. You may recall that a prime number is a positive integer $p$ with exactly two factors: itself and $1$. We may list a few: $2, 3, 5, 7, 11, 13, 17, 19, 23,$ but there is no pattern that allows us to employ ellipses.

Fortunately there is another way to write down a set. All previous examples have used roster notation, where the elements are simply listed. It may be more convenient to use set-builder notation, where the set is instead described with a rule that exactly characterizes this element. In that case, the set of primes can be written as

$\{ \, p \, | \; p \text{ is a prime number} \}.$

To provide one last example, consider the set of all U.S. states. In roster notation this set is a nightmare: {AL, AK, AZ, AR, CA, CO, CT, DE, FL, GA, HI, ID, IL, IN, IA, KS, KY, LA, ME, MD, MA, MI, MN, MS, MO, MT, NE, NV, NH, NJ, NM, NY, NC, ND, OH, OK, OR, PA, RI, SC, SD, TN, TX, UT, VT, VA, WA, WV, WI, WY}. But in set-builder notation we simply write

$\{ \, S \, | \, S \text{ is a U.S. state} \}.$

Definition 1.1.1. Two sets $X$ and $Y$ are equal if they contain exactly the same elements, in which case we write $X=Y$.

Remember that sets are unordered, so even $\{a,b\}=\{b,a\}$.

Definition 1.1.2. Let $X$ be a finite set. Its cardinality, denoted $|X|$, is the number of elements in $X$.

Example. If $X=\{a,b,c\}$, then $|X|=3$.

We can talk about the cardinality of infinite sets, but that is far beyond the scope of this course.

1.2 Containment

One of the most important ideas when dealing with sets is that of a subset.

Definition 1.2.1. Let $X$ and $Y$ be sets. We say $X$ is a subset of $Y$ if every element of $X$ is also an element of $Y$.

Examples. Put $X = \{a,b,c\}$, $Y = \{a,c\}$, and $Z=\{b\}$. Then $Y \subseteq X$, $Z \subseteq X$, but $Y \not\subseteq Z$ and $Z \not\subseteq Y$.

In mathematics, true statements are either definitions (those taken for granted) or theorems (those proven from the definitions). We will learn to prove more difficult theorems later, but for now we can prove a simple one.

Theorem 1.2.2. Every set is a subset of itself.

A proof is simply an argument that convinces its reader of the truth of a mathematical fact. Valid proofs must only use definitions and the hypotheses of the theorem; it is not correct to assume more than you are given. So the ingredients in the proof of this theorem are simply going to be a set and the definition of the word “subset.”

Proof. Let $X$ be a set. Suppose $x$ is an arbitrary element of $X$. Then, $x$ is also an element of $X$. Because $X$ was shown to have any arbitrary element of $X$, then $X \subseteq X$. $\square$

Notice that the actual make-up of the set $X$ is irrelevant. If $X$ has an element, then $X$ also has that element, and that is all it takes to conclude $X \subseteq X$. It would be incorrect to try to prove $X \subseteq X$ from an example: just because $\{0\}$ is a subset of itself doesn’t necessarily mean that $\{0,1\}$ is!

We will discuss logic and proof-writing at length as we continue. For now, let’s continue learning about sets and proving the “simple” theorems as we go.

Definition 1.2.3. The set with no elements is called the empty set, denoted $\{ \}$ or $\varnothing$.

With a little logical sleight-of-hand, we can prove another (much more surprising) theorem.

Theorem 1.2.4. The empty set is a subset of every set.

Proof. Let $X$ be a set. We may conclude $\varnothing \subseteq X$ if every element of $\varnothing$ is an element of $X$. Observe that this statement is equivalent to saying that no elements of $\varnothing$ are not elements of $X$. Because there are no elements of $\varnothing$ at all, this statement is true; and we are done. $\square$

Perhaps you already agree with the central claim of the proof, that there are no difference between the statements "everything in $\varnothing$ is in $X$" and "nothing in $\varnothing$ is not in $X$". If you do not, take it on faith for now. When we study predicate logic later you will have the tools to convince yourself of the claim.

Such a statement that relies on the emptiness of $\varnothing$ is said to be vacuously true.

When $X \subseteq Y$, we say $Y$ contains $X$ or that $Y$ is a superset of $X$. With the idea of containment in hand we can construct a new type of set.

Definition 1.2.5. Let $X$ be a set. Its power set is the set $\mathcal{P}(X)$ whose elements are the subsets of $X$. That is,
$\mathcal{P}(X) = \{ \, E \, | \, E \subseteq X \, \}.$

Wait - our elements are sets? Yes, and this is perfectly fine! Elements can be all sorts of things, other sets included. When we have a “set of sets” we typically refer to it as a family or a collection to avoid using the same word and over and over.

Example. Let $X = \{a,b,c\}$. Then

$\mathcal{P}(X) = \{ \varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, X\}.$

Notice that the number of sets in $\mathcal{P}(X)$ can be derived from the number of elements in $X$.

Theorem 1.2.6. If $X$ is finite, then $|\mathcal{P}(X)|=2^{|X|}$.

We will come back to prove this theorem much later, once we have learned how to count!

1.3 The algebra of sets

You are used to word “algebra” as it refers to a class where you must solve some equations for $x$. If you think about those classes, they are really about understanding operations and functions of real numbers. Think about it: a successful algebra student will know how to manipulate sums, products, polynomials, roots, and exponential functions – ways of combining and mapping real numbers.

So, “algebra” in general refers to the ways objects may be combined and mapped. In this section, we will see many ways that sets can be combined to produce new sets.

Definition 1.3.1. Let $X$ and $Y$ be sets. Their union is the set $X \cup Y$ of all elements that are in at least one of $X$ or $Y$; in set builder notation this is
$X \cup Y = \{\, x \, | \, x \in X \text{ or } x \in Y \}.$

Definition 1.3.2. Let $X$ and $Y$ be sets. Their intersection is the set $X \cup Y$ of all elements that are in both $X$ and $Y$; in set builder notation this is
$X \cap Y = \{\, x \, | \, x \in X \text{ and } x \in Y \}.$

A useful way to visualize combinations of sets is with a Venn diagram. The Venn diagrams for union and intersection are shown below.

Example. Let $X = \{1,2,3,4\}$ and $Y=\{2,4,7,9\}$. Their union is
$X \cup Y = \{1,2,3,4,7,9\}$ and their intersection is $X \cap Y = \{2,4\}.$ Notice that we do not repeat elements in a set. An element is either in the set or it isn’t. (A generalization, the multiset, will be developed in Chapter 11.) Therefore, $|X \cup Y|$ (recall, the number of elements in the union) won’t just be $|X|+|Y|$.

Theorem 1.3.3. If $X$ and $Y$ are finite sets, then $|X \cup Y| = |X|+|Y|-|X\cap Y|.$

Proof. If an element is only in $X$, it will be counted by $|X|$. If an element is only in $Y$, it will be counted by $|Y|$. Therefore any elements in $X \cap Y$ will be counted twice. There are exactly $|X \cap Y|$ of these elements, so subtracting that amount gives $|X \cup Y|$. $\square$

Definition 1.3.4. Let $X$ and $Y$ be sets. The difference $X-Y$ is the set of all elements in $X$ but not $Y$; i.e. $X-Y=\{ \, x \, | \, x \in X \text{ and } x \not\in Y\}.$

Example. Like before, let $X = \{1,2,3,4\}$ and $Y=\{2,4,7,9\}$. Then $X-Y=\{1,3\}$. Notice that $Y-X=\{7,9\}$; just like with numbers, taking a diference is not commutative. (That is, the order matters.)

Often when working with sets there is a universal or ambient set, sometimes denoted $\Omega$, that all of our sets are assumed to be subsets of. This set is typically inferred from context.

• In calculus, this set might be $\mathbf{R}$.
• If my set is “students taking MATH 174,” my universal set might be the set of all students at Coastal Carolina.
• In probability theory, the sets are events (e.g. “the roll is odd”) and $\Omega$ is the sample space (e.g. all possible rolls of the die).

Definition 1.3.5. Let $X$ be a set contained in some universal set $\Omega$. The complement of $X$ (relative to $\Omega$), denoted $\overline{X}$, is all the elements not in $X$. In other words, $\overline{X}=\Omega-X$.

Example. Suppose $X=\{a,b,c\}$ is contained in the universal set $\Omega=\{a,b,c,d,e\}$. Then $\overline{X}=\{d,e\}$.

Definition 1.3.6. Let $X$ and $Y$ be sets. Their Cartesian product (in this book, just “product”) is the set $X\times Y = \{(x,y)\,|\, x \in X \text{ and } y \in Y\}.$ The elements of the product are called ordered pairs.

As the name implies, the ordering of the entries in an ordered pair matters. Therefore, we will adopt the convention that unordered structures are enclosed in $\{$ curly braces $\}$ and ordered structures are enclosed in $($ parentheses $)$. The immediate consequence to this observation is that $X \times Y$ is different from $Y \times X$.

Examples. You are likely familiar with $\mathbf{R}^2=\mathbf{R}\times\mathbf{R}$, the Cartesian plane from algebra and calculus. The elements of this (infinite) set are ordered pairs $(x,y)$ where both $x$ and $y$ are real numbers.

To make a discrete example, put $X=\{a,b,c\}$ and $Y=\{1,2\}$. Then
$X \times Y = \{(a, 1), (a,2), (b,1), (b,2), (c,1), (c,2)\}.$ As an exercise, calculate $Y \times X$ yourself. The pair $(1,a)$ is an element.

Theorem 1.3.7. If $X$ and $Y$ are finite sets, then $|X \times Y| = |X||Y|$.

Proof. The elements of $X\times Y$ may be tabulated into a rectangle, where each row corresponds to an element of $X$ and each column corresponds to an element of $Y$. There are $|X|$ rows and $|Y|$ columns and therefore $|X||Y|$ elements in the table. $\square$

1.4 Operations involving more than two sets

Note: While this section is cool, we will not make use of its content very often in this course. You may choose to skip this section for now and return to it after Chapter 8, when you are more comfortable with the material.

There is one last thing to say about sets (for now, anyway). There is no reason to limit ourselves to two sets in union, intersection, and product. If we have a family of $n$ sets $X_1, X_2, \ldots, X_n$, we may take $n$-ary unions, intersections, and products.

The $n$-ary union $\bigcup_{i=1}^n X_i = X_1 \cup X_2 \cup \cdots \cup X_n$ is the set of elements that are in at least one of the sets $X_i$.

The $n$-ary intersection $\bigcap_{i=1}^n X_i = X_1 \cap X_2 \cap \cdots \cap X_n$ is the set of elements that are in all of the sets $X_i$.

The $n$-ary product $\prod_{i=1}^n X_i = X_1 \times X_2 \times \cdots \times X_n$ is the set of ordered $n$-tuples $(x_1, x_2, \ldots, x_n)$, where the element $x_i$ is a member of the set $X_i$.

Suppose instead the family $X_1, X_2, \ldots$ is infinite. We will, exactly once in this book, need to take an infinite union. The infinite union $\bigcup_{i=1}^\infty X_i = X_1 \cup X_2 \cup \cdots$ is the set of all elements that are in at least one of the $X_i$. (Notice that the definition hasn’t changed – just the number of sets!) Likewise the infinite intersection $\bigcap_{i=1}^n X_i = X_1 \cap X_2 \cap \cdots$ is the set of elements in all the $X_i$.

Takeaways

• A set is a collection of objects. Given a mathematical object, there is almost definitely a way to define that object as a set.
• A given set has many subsets, the collection of which forms its power set.
• The cardinality of a finite set is the number of its elements.
• There are many ways to combine and manipulate sets: union, intersection, difference, and product.

Chapter 1 problems

2. Propositional logic

Videos:

• Negation, conjunction, and disjunction
• Conditional statements
• Compound statements
• Rules of inference
• Logical equivalence

In mathematics, we spend a lot of time worried about whether a sentence is true or false. This is fine in the case of a simple sentence such as “The number $2$ is prime.” (That sentence is true.) But there are much more complicated sentences lurking around, and whole constellations of sentences whose truth depends on one another. (An unsolved problem in mathematics is deciding whether the Riemann hypothesis, a statement about the prime numbers, is true. Most people believe it is, and many results in the literature are true given the hypothesis. The Riemann hypothesis is going to make or break a lot of research.)

So, we are interested in tools that will allow us to judge whether complicated statements are true. Such models of truth are called logic.

2.1 Statements and connectives

Definition 2.1.1. A statement is a sentence that is either true or false.

Examples. “The number $2$ is prime” and “It is perfectly legal to jaywalk” are statements. Non-statements include questions (“Is it raining?”), commands (“Do your homework”), and opinions (“Mint chocolate chip ice cream is the superior flavor”). It is important to note, not necessarily for mathematical purposes, that opinions are statements of pure taste. Claims whose truth values exist but are unknown are beliefs.

Atomic propositional statements of the type discussed in this chapter are flatly always true or false. You may think of them in the same way you think of constant functions in algebra. They are denoted with lowercase letters $p$, $q$, $r$, etc. If the only statements were atomic, logic would be boring. Fortunately, we can combine statements with connectives. In the next chapter, we will look at predicate statements whose truth values depend on an input. Likewise, these may be thought of as the non-constant functions.

Compound statements arise from combining atomic statements with connectives. They are denoted using Greek letters like $\varphi$ (“phi”), $\psi$ (“psi”), and $\gamma$ (“gamma”). The truth of a compound statement depends on the connectives involved and the truth values of the constituent statements. A tool for determining the truth of a compound statement is called a truth table.

In a truth table for the compound statement $\varphi$, the left side of the table is the atomic statements involved in $\varphi$ and the right side of the table is $\varphi$ itself. Each row gives a possible combination of truth values for the atomic statements, and the corresponding truth value for $\varphi$. At this point, it is easier to start introducing connectives and seeing some truth tables.

Definition 2.1.2. Let $p$ be a statement. Its negation is the statement $\neg p$, the statement that is true exactly when $p$ is false and vice-versa.

The statement $\neg p$ is typically read "not $p$" or “it is not the case that $p$ is true.” If we have an English rendering of $p$, we try to write $\neg p$ in a natural-sounding way that also conveys its logical structure.

Example. Suppose $p$ represents the statement “It is raining.” Then, $\neg p$ stands for “It is not raining.”

Below is the truth table for $\neg p$.

$p$	$\neg p$
$T$	$F$
$F$	$T$

As you can see, on the left are columns corresponding to the atomic statements involved in $\neg p$ (just $p$), and each row is a possible combination of truth values for these statements. Here is a quick, useful theorem without proof:

Theorem 2.1.3. If the compound statement $\varphi$ involves $n$ different atomic statements, then its truth table has $2^n$ rows.

Look familiar? We will prove this theorem when we prove the related theorem about power sets later on.

Negation is called a unary connective because it only involves one statement. Our remaining connectives are all binary connectives, as they combine two statements.

Definition 2.1.4. Let $p$ and $q$ be statements. Their conjunction is the statement $p \wedge q$, which is true only when $p$ and $q$ are both true.

The symbol in the conjunction is called a “wedge,” and $p \wedge q$ is read "$p$ and $q$." This definition is meant to be analogous to our English understanding of the word “and.” The statements $p$ and $q$ are called conjuncts.

Example. Letting $p$ be “It is raining” and $q$ be “I brought an umbrella,” the statement $p \wedge q$ is “It is raining and I brought an umbrella.” The statement is true only if it is currently raining and the speaker brought an umbrella. If it is not raining, or if the speaker did not bring their umbrella, the conjunction is false.

Here is the truth table for $p \wedge q$:

$p$	$q$	$p \wedge q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

Notice that this table is organized intentionally, not haphazardly. The rows are divided into halves, where $p$ is true in one half and then false in the other half. The rows where $p$ is true are further subdivided into half where $q$ is true and half where $q$ is false. If there were a third letter, we would subdivide the rows again, and so on. This method of organizing the truth table allows us to ensure we did not forget a row. Our leftmost atomic letter column will always be half true followed by half false, and the rightmost atomic letter column will always alternate between true and false.

Definition 2.1.5. Let $p$ and $q$ be statements. Their disjunction is the statement $p \vee q$, which is true if at least one of $p$ or $q$ is true.

The symbol in the conjunction is called a “vee” and $p \vee q$ is read "$p$ or $q$." This definition is meant to be analogous to our English understanding of the word “or.” The statements $p$ and $q$ are called disjuncts. (Did you notice that I was able to copy and paste from an above paragraph? Conjunction and disjunction share a very similar structure.)

Example. Letting $p$ be “It is raining” and $q$ be “I brought an umbrella,” the statement $p \vee q$ is “It is raining or I brought an umbrella.” This time, the speaker only needs to meet one of their conditions. They are telling the truth as long as it is raining or they brought an umbrella, or even if both statements are true.

The truth table for $p \vee q$ follows.

$p$	$q$	$p \vee q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

Of great importance to computer science and electrical engineering, but not so much in mathematics (so it will not appear again in this book), is the exclusive disjunction (or “exclusive-or”). It is a modified disjunction where exactly one of the disjuncts must be true.

Definition 2.1.6. If $p$ and $q$ are statements, their exclusive disjunction is the statement $p \oplus q$, which is true if and only if exactly one of $p$ and $q$ is true.

The statement $p \oplus q$ is read "$p$ exclusive-or $q$."

Example. The statement “You can have the soup or the salad” is likely meant as an exclusive disjunction.

In mathematics, disjunctions are generally considered inclusive unless stated otherwise. (An example for us all to follow!)

Our next connective is probably the most important, as it conveys the idea of one statement implying another. As we discussed earlier in the chapter, mathematics is nothing but such statements. It is also the only connective that is not relatively easy to understand given its English interpretation. So we will begin with the truth table, and think carefully about each row.

Definition 2.1.7. If $p$ and $q$ are statements, the conditional statement $p \to q$ is true if $p$ can never be true while $q$ is false.

There are many ways to read $p \to q$, including “if $p$, then $q$,” "$p$ implies $q$“, and "$p$ is sufficient for $q$.” The statement before the arrow is the antecedent and the following statement is the consequent. Here is the conditional’s truth table.

$p$	$q$	$p \to q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

That $p \to q$ is true in the bottom two rows may surprise you. So, let’s consider each row separately.

Example. Let $p$ be “You clean your room” and $q$ be “I will pay you $10,” so that $p\to q$ is “If you clean your room, then I will pay you $10.”

In the case that both $p$ and $q$ are true, the speaker has told the truth. You cleaned, and you were paid. All is well.

In the case that $p$ is true but $q$ is false, the speaker has lied. You cleaned the room, but you did not earn your money.

What if $p$ is false? Well, then the speaker did not lie. The speaker said that if you clean your room you will be paid. If the room isn’t cleaned, then $p \to q$ cannot be falsified, no matter where $q$ is true or false.

If that explanation is not sufficient for you, reread the definition of the conditional: $p \to q$ being true means that $p$ cannot be true without $q$. If you are unsatisfied by the English connection, then consider $p \to q$ to be a purely formal object whose definition is the above truth table.

Definition 2.1.8. If $p$ and $q$ are statements, the biconditional statement $p \leftrightarrow q$ is true if $p$ and $q$ are both true, or both false.

The statement $p \leftrightarrow q$ may be read as "$p$ if and only if $q$, "$p$ is necessary and sufficient for $q$," or "$p$ is equivalent to $q$." Here is the truth table.

$p$	$q$	$p \leftrightarrow q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$T$

Example. Let $p$ be “You clean your room” and $q$ be “I will pay you $10,” so that $p\leftrightarrow q$ is “I will give you $10 if and only if you clean your room.” (The statements were reordered for readability. We will see later in the chapter that this is the same statement, but this wouldn’t work for $p \to q$.) This time, the clean room and the $10 paycheck are in total correspondence; one doesn’t happen without the other.

2.2 Connecting connectives

We are not required to use one connective at a time, of course. Most statements involve two or more connectives being combined at once. If $\varphi$ and $\psi$ are statements, then so are: $\neg \varphi$, $\varphi \wedge \psi$, $\varphi \vee \psi$, $\varphi \to \psi$, and $\varphi \leftrightarrow \psi$. This fact allows us to combine as many connectives and statements as we like.

How should we read the statement $p \wedge q \to r$? Should it be read "$p$; also, if $q$ then $r$"? Or, “If $p$ and $q$, then $r$?” Just like with arithmetic, there are conventions defining which connective to apply first: negation, then conjunction/disjunction, then implication, then bi-implication. So, "If $p$ and $q$, then $r$" is correct. However, to eliminate confusion in this book we will always use parentheses to make our statements clear. Therefore, we would write this statement as $(p \wedge q) \to r$.

Remember that a statement involving $n$ letters will have $2^n$ rows in its truth table. The column for the left-most statement letter should be true for half the rows then false for half the rows, and you should continue dividing the rows in half so that the right-most statement letter’s column is alternating between true and false.

Finally, it is a good idea to break a statement into small “chunks” and make a column for each “chunk” separately. Observe the following example.

Example. Write down the truth table for the statement $(p \wedge q) \to (r \to \neg s)$. When is this statement false?

Since the statement has $4$ letters, there will be $2^4=16$ rows to the truth table. Let’s go through the first row very slowly, where all four atomic statements are true. Then $p \wedge q$ is true and $\neg s$ is false. Since $r$ is true and $\neg s$ is false, that means $r \to \neg s$ is false. Finally, because its antecedent is true and its consequent is false, the compound statement $(p \wedge q) \to (r \to \neg s)$ would be false.

Here is the full truth table. Be sure you understand how each row is calculated.

$p$	$q$	$r$	$s$	$p \wedge q$	$\neg s$	$r \to \neg s$	$(p \wedge q) \to (r \to \neg s)$
$T$	$T$	$T$	$T$	$T$	$F$	$F$	$F$
$T$	$T$	$T$	$F$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$T$	$F$	$T$	$T$
$T$	$T$	$F$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$T$	$T$	$F$	$F$	$F$	$T$
$T$	$F$	$T$	$F$	$F$	$T$	$T$	$T$
$T$	$F$	$F$	$T$	$F$	$F$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$	$T$	$T$
$F$	$T$	$T$	$T$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$F$	$F$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$F$	$F$	$T$	$T$
$F$	$T$	$F$	$F$	$F$	$T$	$T$	$T$
$F$	$F$	$T$	$T$	$F$	$F$	$F$	$T$
$F$	$F$	$T$	$F$	$F$	$T$	$T$	$T$
$F$	$F$	$F$	$T$	$F$	$F$	$T$	$T$
$F$	$F$	$F$	$F$	$F$	$T$	$T$	$T$

There are tricks to calculate truth tables more efficiently. However, it wouldn’t do you any good to read them; they must come with practice.

2.3 Inference and equivalence

Mathematics is all about relationships. If the statement $\varphi \to \psi$ is always true, then it tells us that whenever $\varphi$ is true then $\psi$ must be as well. If the statement $\varphi \leftrightarrow \psi$ is always true, then it tells us that from the point of view of logic $\varphi$ and $\psi$ are actually the same statement. That is, it is never possible for them to have different truth values.

Definition 2.3.1. A tautology is a statement that is always true, denoted $T$.

Definition 2.3.2. A contradiction is a statement that is always false, denoted $F$.

Definition 2.3.3. A rule of inference is a tautological conditional statement. If $\varphi \to \psi$ is a rule of inference, then we say $\varphi$ implies $\psi$ and write $\varphi \Rightarrow \psi$.

Remember that a conditional statement does not say that its antecedent and consequent are both true. It says that if its antecedent is true, its consequent must also be true.

There are many rules of inference, but we will explore two.

Definition 2.3.4. Modus ponens is the statement that says we may infer $q$ from $p \to q$ and $p$. Symbolically: $[(p \to q) \wedge p] \to q.$
Example. Consider the conditional statement “If you clean your room, then I will give you $10.” If the speaker is trustworthy, and we clean our room, then we may conclude we will be receiving $10.

Another example: “If a function is differentiable, then it is continuous.” (You may know the meanings of these words, but it is not important.) If this statement is true, and the function $f$ is differentiable, then without any further work we know that $f$ is continuous.

Theorem 2.3.5. Modus ponens is a rule of inference.

Notice that in the definition no claim is made that modus ponens is always true. That is up to us.

Since we know how to use truth tables, we may construct one to show that $[(p \to q) \wedge p] \to q$ is always true. Before reading the table below, try to make your own!

$p$	$q$	$(p \to q)$	$(p \to q) \wedge p$	$[(p \to q) \wedge p] \to q$
$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$F$	$T$
$F$	$F$	$T$	$F$	$T$

Proof. The above table shows that $[(p \to q) \wedge p] \to q$ is true no matter the truth of $p$ and $q$. $\square$

Definition 2.3.6. In the context of conditional statements, transitivity is the rule that if $p$ implies $q$ and $q$ implies $r$, then $p$ implies $r$. Or, $[(p \to q) \wedge (q \to r)] \to (p \to r).$

The wording of the definition above should you make you suspicious that this is not the only time we will see transitivity. In fact, you may have seen it before…

Example. If you give a mouse a cookie, then he will ask for a glass of milk. If he asks for a glass of milk, then he will also ask for a straw. Therefore, if you give a mouse of cookie then he will ask for a straw.

Theorem 2.3.7. Transitivity is a rule of inference.

We could simply write down another truth table and call it a day. In fact, go ahead and make sure you can prove transitivity with a truth table. Once you’re done, we’ll try something slicker to prove transitivity.

Proof. Suppose that $p \to q$ and $q \to r$ are true statements, and that moreover $p$ is true. By modus ponens, $q$ must also be true. Then, $r$ is true, by a second application of modus ponens. Therefore, if $p$ is true, $r$ must be also; this is the definition of $p \to r$. $\square$

Pretty cool, right? We can cite proven theorems to prove a new one.

Does it work the other way? In other words: if I know that $[(p \to q) \wedge (q \to r)] \Rightarrow (p \to r)$, does that mean $(p \to r) \Rightarrow [(p \to q) \wedge (q \to r)]$? Regrettably, no: consider the case there $p$ and $r$ are true but $q$ is false.

Some rules of inference do work both ways. These are called equivalences.

Definition 2.3.8. If $\varphi \leftrightarrow \psi$ is a tautology, then it is an equivalence and $\varphi$ and $\psi$ are equivalent statements. We write $\varphi \equiv \psi$.

Equivalent statements are not the same statements, but they are close enough from the point of view of logic. Equivalent statements are interchangeable, and may be freely substituted with one another.

We will quickly run through many equivalences before slowing down to prove a few.

Algebraic properties of conjunction, disjunction, and negation

Our first batch of statements should look familiar to you; these are the ways that statements “act like” numbers. As you read each one, try to justify to yourself why it might be true. If you aren’t sure of one, make a truth table.

Equivalence	Name
$p \equiv \neg (\neg p)$	Double negation
$p \wedge q \equiv q \wedge p$	Commutative of conjunction
$p \vee q \equiv q \vee p$	Commutative of disjunction
$(p \wedge q) \wedge r \equiv p \wedge (q \wedge r) \equiv p \wedge q \wedge r$	Associativity of conjunction
$(p \vee q) \vee r \equiv p \vee (q \vee r) \equiv p \vee q \vee r$	Associativity of disjunction
$p \wedge T \equiv p$	Conjunctive identity
$p \vee F \equiv p$	Disjunctive identity
$p \wedge F \equiv F$	Conjunctive absorption
$p \vee T \equiv T$	Disjunctive absorption
$p \wedge \neg p \equiv F$	Conjunctive cancellation
$p \vee \neg p \equiv T$	Disjunctive cancellation

Distributive properties

In our numbers, multiplication distributes over addition. This is one fact that is likely implemented twice in your head, once for a number: $a(b+c) = ab + ac,$ and once for “the negative” (truly the number $-1$): $-(b+c) = -b - c.$ However, these rules are one and the same; the distributive law. Likewise, we will have distributive laws for negation, conjunction, and disjunction.

Equivalence	Name
$\neg (p \wedge q) \equiv \neg p \vee \neg q$	DeMorgan’s law
$\neg (p \vee q) \equiv \neg p \wedge \neg q$	DeMorgan’s law
$p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$	Conjunction over disjunction
$p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$	Disjunction over conjunction

DeMorgan’s law is one of the most important facts in basic logic. In fact, we will see it three times before we are through. In English, DeMorgan’s law says that the negation of a conjunction is a disjunction and vice-versa.

To show that $\neg (p \wedge q)$ and $\neg p \vee \neg q$ are equivalent, we can show that the biconditional statement $\neg (p \wedge q) \leftrightarrow \neg p \vee \neg q$ is a tautology. Thinking about the definition of the biconditional gives us another way: we can show that the truth tables of $\neg (p \wedge q)$ and $\neg p \vee \neg q$ are the same; in other words, that both statements are always true and false for the same values of $p$ and $q$.

Proof (of DeMorgan’s law for conjunction). Let $p$ and $q$ be statements. The statements $\neg (p \wedge q)$ and $\neg p \vee \neg q$ are equivalent, as shown by the below truth table.

$p$	$q$	$\neg (p \wedge q)$	$\neg p \vee \neg q$
$T$	$T$	$F$	$F$
$T$	$F$	$T$	$T$
$F$	$T$	$T$	$T$
$F$	$F$	$T$	$T$

Therefore, $\neg (p \wedge q) \equiv \neg p \vee \neg q$. $\square$

You’ll notice a few columns are skipped in the above truth table. After a few tables, it is more convenient to skip “easy” columns. For example, we know that $p \wedge q$ is true only when $p$ and $q$ are both true, and false everywhere else. Therefore, we can “flip” that column to quickly get the column for $\neg (p \wedge q)$.

As an exercise, prove DeMorgan’s other law.

Properties of the conditional

Finally, we come to the properties of conditional (and biconditional) statements. These do not have “obvious” numerical counterparts, but are useful all the same.

Equivalence	Name
$p \to q \equiv \neg p \vee q$	Material implication
$\neg (p \to q) \equiv p \wedge \neg q$	False conditional
$p \to q \equiv \neg q \to \neg p$	Contraposition
$p \leftrightarrow q \equiv (p \to q) \wedge (q \to p)$	Mutual implication

Material implication is the surprising result that the conditional is just a jumped-up disjunction! In fact, DeMorgan’s law, material implication, and mutual implication together prove that all of the connectives we’ve studied can be implemented with just two: negation and one other. However, this would make things difficult to read, so we allow the redundancy of five connectives.

Let’s prove material implication with a truth table, and then we will prove contraposition with another method.

Proof (of material implication). Let $p$ and $q$ be statements and observe that the truth tables for $p \to q$ and $\neg p \vee q$ are the same:

$p$	$q$	$p \to q$	$\neg p \vee q$
$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$
$F$	$T$	$T$	$T$
$F$	$F$	$T$	$T$

Therefore, $p \to q \equiv \neg p \vee q$. $\square$

There is another way to think about material implication. The statement $p \to q$ means that $p$ never happens without $q$. Another way to say this is that $q$ happens, or else $p$ did not; so, $\neg p \vee q$.

Before we prove contraposition by the other method, we must justify said method with a theorem.

Theorem 2.3.9. Statements $\varphi$ and $\psi$ are equivalent if and only if $\varphi \Rightarrow \psi$ and $\psi \Rightarrow \varphi$ are both rules of inference.

The phrase “if and only if” in a mathematical statement means that the statement “works both ways.” In this case, $\varphi \equiv \psi$ means $\varphi \Rightarrow \psi$ and $\psi \Rightarrow \varphi$ are both rules of inference; and conversely, $\varphi \Rightarrow \psi$ and $\psi \Rightarrow \varphi$ both being rules of inference means $\varphi \equiv \psi$. It means that “$\varphi \equiv \psi$” and “”$\varphi \Rightarrow \psi$ and $\psi \Rightarrow \varphi$ are both rules of inference" are equivalent statements. Fortunately, we already have a rule that justifies this equivalence.

Proof (of Theorem 2.3.9). Mutual implication says that $p \leftrightarrow q \equiv (p \to q) \wedge (q \to p)$. $\square$

It’s that easy. Whenever we have a conditional statement and its converse (the order reversed), we have the biconditional; likewise, we may trade in a biconditional for two converse conditional statements.

Now we will prove contraposition by showing that $p\to q$ implies $\neg q \to \neg p$, and vice-versa. Before you read the below proof, write down these rules: material implication, double negation, and commutativity of disjunction.

Proof (of contraposition). Suppose $p$ and $q$ are statements and that $p \to q$ is true. By material implication, $\neg p \vee q$ is true. Commutativity says this is the same as $q \vee \neg p$. So, we may apply material implication backwards, negating $q$ this time, to get $\neg q \to \neg p$; therefore, $p \to q$ implies $\neg q \to \neg p$.

Conversely, suppose $\neg q \to \neg p$ is true. Then material implication (and double negation) gives $q \vee \neg p$. We may commute the disjunction and apply material implication again, negating $\neg p$, to get $p \to q$.

By mutual implication, $p \to q \equiv \neg q \to \neg p$. $\square$

Takeaways

• Statements may be modified and combined in (mainly) five ways: negation, conjunction, disjunction, implication (the conditional), and bi-implication (the biconditional).
• A truth table allows us to see when a compound statement will be true or false.
• If one statement always implies another, that implication is a rule of inference.
• If two statements are always true or always false together, they are equivalent.
• Rules of inference and equivalences may be justified with truth tables or algebraically.

Chapter 2 problems

3. Predicate logic

Videos:

• Predicates
• Introduction to quantifiers
• Quantifiers, continued
• Inference and equivalence with quantifiers

3.1 Predicates

Basic propositional logic as you learned it in the preceding chapter is powerful enough to give us the tools we will need to prove many theorems. However, it is deficient in one key area. Consider the following example.

Example. If Hypatia is a woman and all women are mortal, then Hypatia is mortal.

We can all agree that this statement is a tautology; that is, if it is true that Hypatia is a woman (she was; she was a Greek mathematician contemporary with Diophantus) and if it is true that all women are mortal (as far as we know this is the case) then it must follow that Hypatia is mortal (she was murdered in 415).

So the statement is a tautology. If so, the truth table would confirm it. Let $(p \wedge q) \to r$ symbolize the statement, where $r$ stands for the statement that Hypatia is mortal.

$p$	$q$	$r$	$p\wedge q$	$(p \wedge q)\to r$
$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$F$
$T$	$F$	$T$	$F$	$T$
$T$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$F$	$T$
$F$	$T$	$F$	$F$	$T$
$F$	$F$	$T$	$F$	$T$
$F$	$F$	$F$	$F$	$T$

Oh no! Our second row gives that the statement is false when $r$ is false but $p$ and $q$ are true. What gives?

Well, consider the statement “If pigs fly and the Pope turns into a bear, then Bob will earn an A on the exam.” Now it is not so clear that this is a tautology, because pigs, the Pope, and Bob’s grade presumably have nothing to do with one another.

But Hypatia and the mortality of women do. What we will need is the ability to signify that two statements are related, whether in subject (e.g. Hypatia) or predicate (e.g. mortality). This is where predicate logic comes in to help.

Definition 3.1.1. A predicate is a function $P:\Omega \to \{T,F\}$ that takes one or more subjects (members of some domain $\Omega$) and assigns to them all either true $T$ or false $F$.

Predicates are typically denoted with capital letters like $P$, $Q$, and $R$. Subjects that are known are given lowercase letters like $a$, $b$, and $c$, unless there is something more reasonable to pick like $h$ for Hypatia. Subjects whose values are unknown or arbitrary are denoted with lowercase $x$, $y$, $z$, etc.

The definition of predicate above is much more complicated than it needs to be; this is so that we can take the central idea (a function) and continue using it throughout the book. You know a function: an assigment $f(x)$ that gives every input $x$ exactly one output $f(x)$. We write $f:X \to Y$ to signify that $f$ is a function whose inputs are elements of the set $X$ and whose outputs are elements of the set $Y$.

So, in the above definition, the predicate $P$ is a function that takes a subject, a member of the set $\Omega$, and assigns it exactly one truth value.

(Take note that propositions, which you studied in the last chapter, may be regarded as constant predicates – functions whose value is the same regardless of the input, like $f(x)=3$.)

Examples. Letting $W(x)$ be the predicate "$x$ is a woman" on the domain of humans and $h$ stand for Hypatia, $W(h)$ is the statement “Hypatia is a woman.” Since this statement is true, the function $W$ assigns $T$ to $h$.

Let $P(x)$ be the predicate “$x + 3 = 5$” on the domain $\mathbf{Z}$ and let $Q(x,y)$ be the predicate "$x$ orbits $y$" on the domain of celestial objects in the sky. The statement $P(2)$ is true, but $P(3)$ is false. If $e$ stands for the earth and $s$ for the sun, then $Q(s,e)$ is false but $Q(e,s)$ is true.

A predicate, once evaluated to a subject, is a statement. Therefore, these statements may be combined into compound statements using the logical connectives we have just studied.

Examples. As before let $P(x)$ be the predicate “$x + 3 = 5$” on the domain $\mathbf{Z}$ and let $Q(x,y)$ be the predicate "$x$ orbits $y$" on the domain of celestial objects in the sky, where $e$ stands for the earth and $s$ for the sun.

The statements $P(2) \vee Q(s,e)$, $\neg P(3)$, and $Q(s,e) \to P(2)$ are true.

The statements $P(2) \wedge Q(s,e)$ and $P(2) \to Q(s,e)$ ae false.

3.2 Quantifiers

This is all well and good, you think, but what about the statement “All women are mortal”? How can we make “all women” the subject of a statement?

Quantifiers allow us to say that a predicate is true for all, or for at least one undetermined, object in its domain.

Definition 3.2.1 Let $P(x)$ be a predicate. The universal statement $\forall x P(x)$ says that $P(x)$ is true for all $x$ in its domain. The symbol $\forall$ (“for all”) is called the universal quantifier.

Example. The domain is very important. If $P(x)$ is the predicate "$x$ takes discrete math" then $\forall x P(x)$ – “Everyone takes discrete math” – is true on the domain of computer science students at Coastal Carolina, but not, say, on the domain of all people in South Carolina.

Definition 3.2.2 Let $P(x)$ be a predicate. The existential statement $\exists x P(x)$ says that $P(x)$ is true for at least one $x$ in its domain. The symbol $\exists$ (“there exists”) is called the existential quantifier.

Example. Again let $P(x)$ be the predicate "$x$ takes discrete math". The existential statement $\exists x P(x)$ says “Someone takes discrete math.” This is now true for people in South Carolina – pick a student at Coastal, or Clemson, or USC – but not true on the domain of dogs. Wouldn’t that be cute, though?

The statement operated on by a quantifier is called its scope. Without parentheses, a quantifier is considered to apply only to the statement it is next to and no others.

Examples. Let $P(x)$ be the predicate "$x$ takes discrete math" and $Q(x)$ be the predicate "$x$ is a math major".

• The statement $\exists x (P(x) \wedge Q(x))$ means “There is someone who is taking discrete math and is a math major.” Both $P$ and $Q$ apply to the same $x$.
• The statement $\exists x P(x) \wedge \exists x Q(x)$ says “Someone is taking discrete math and someone is a math major.” The subjects of $P$ and $Q$ are possibly different.
• The expression $\exists x P(x) \wedge Q(x)$ is not a statement at all, because $Q(x)$ is not a statement. It needs either a quantifier, or for $x$ to refer to a specific, known member of the domain.

There are two important quantified statements: “All $P$'s are $Q$'s” and "Some $P$ is a $Q$". These statements are all over the place in mathematics. We like to characterize mathematical objects by saying all objects of one type also belong to another; or, by saying we can find an object of one type that is another type.

In “All $P$'s are $Q$'s”, the word “all” suggests that the universal quantifier is appropriate. What connective should be used to combine the predicates? Observe that the statement $\forall x (P(x) \wedge Q(x))$ says that every $x$ is both a $P$ and a $Q$. This isn’t what we mean to say; we mean to say if something is a $P$ then it will also be a $Q$. So, the correct rendering of “All $P$'s are $Q$'s” is $\forall x (P(x) \to Q(x))$.

For the statement “Some $P$'s are $Q$'s”, we mean to say that there is an object that is at once a $P$ and a $Q$. Therefore, this time the conjunction is appropriate: we write $\exists x [P(x) \wedge Q(x)]$.

Statement	Implementation
“All $P$'s are $Q$'s”	$\forall x (P(x) \to Q(x))$
“Some $P$'s are $Q$'s”	$\exists x (P(x) \wedge Q(x))$

Finally, what is to be done with statements with two or more subjects? The ordering of the quantifiers matters. Here are the four possible combinations of universal and existential quantifiers for two subjects, as well as a diagram corresponding to each.

Examples. Let $R(x,y)$ be the predicate "$x$ and $y$ are classmates" over the domain of students at some school. Note that, in this case, the order of the subjects does not affect the truth of the statement.

The statement $\exists xy R(x,y)$ means “There are two students who are classmates.” In other words, there is at least one student who is paired with at least one other student. Some writers say $\exists x \exists y R(x,y)$ instead, but when the quantifiers are the same we will “collapse” the notation.

The statement $\exists x \forall y R(x,y)$ means “There is a student who is classmates with every student.” We have one student who (somehow!) is classmates with the entire student body.

The statement $\forall x \exists y R(x,y)$ means “Every student has a classmate.” Notice that their classmate need not be the same person. If we quantify universally first, then each existential object may be different. In the preceding example, we quantified existentially first, so that one person was classmates with everybody.

The statement $\forall xy R(x,y)$ means “Every student is classmates with every other student.” Every object in our domain is paired up with every other object in the domain, including themselves! (Don’t think too hard about that for this example.)

3.3 Inferences and equivalences for quantifiers

Quantifiers evaluated on a predicate are statements, since they are functions to $\{T,F\}$. Therefore, some quantified statements imply others, and some pairs imply each other. In this section we will learn a few important rules for quantifiers, before finally proving that our opening statement about Hypatia is indeed a tautology.

Theorem 3.3.1 (DeMorgan’s laws) Let $P(x)$ be a predicate. Then $\neg \forall x P(x) \equiv \exists x \neg P(x)$ and $\neg \exists x P(x) \equiv \forall x \neg P(x)$.

Does that name look familiar? Here is our second application of DeMorgan’s laws. (The third will appear in the exercises.) You will see how they are used in the proof.

Proof. Consider the universal statement $\forall x P(x)$ on the domain $\Omega = \{x_1, x_2, \ldots x_n\}$. We may rewrite $\forall x P(x) = P(x_1) \wedge P(x_2) \wedge \cdots \wedge P(x_n)$
and $\exists x P(x) = P(x_1) \vee P(x_2) \vee \cdots \vee P(x_n).$
Therefore, $\neg \forall x P(x) = \neg (P(x_1) \wedge P(x_2) \wedge \cdots \wedge P(x_n)).$
Using DeMorgan’s law, $\neg \forall x P(x) = \neg P(x_1) \vee \neg P(x_2) \vee \cdots \vee \neg P(x_n)),$
which is the same as the statement $\exists x \neg P(x)$.
That $\neg \exists x P(x) \equiv \forall x \neg P(x)$ may be proven in the same way. $\square$

The idea is that a universal statement is a “big conjunction” and an existential statement is a “big disjunction.” The proof follows from the DeMorgan’s laws you learned in the preceding chapter .

The next two theorems deal with how universal and existential statements may imply one another.

Theorem 3.3.2 (Universal instantiation) If $a$ is a member of the domain of the predicate $P$, then $\forall x P(x) \Rightarrow P(a)$.

Proof. If $P$ is true for every member of its domain and $a$ is a member of said domain, $P$ must be true for $a$. $\square$

Theorem 3.3.3 (Existential generalization) If $a$ is a member of the domain of the predicate $P$, then $P(a) \Rightarrow \exists x P(x)$.

Proof. Let $a$ be in the domain of $P$. If $P(a)$ is true, then $P$ is true for some member of its domain. $\square$

There are two comments to make about these two theorems. First, universal generalization and existential instantiation are not valid:

Examples. “I was able to easily pay off my college loans, therefore everyone can” is an example of invalid universal generalization.

“Someone in this room killed the wealthy magnate, so it must have been you!” is an example of invalid existential instantiation.

Finally, transitivity gives us that a universal statement implies an existential one: $\forall x P(x) \Rightarrow P(a) \Rightarrow \exists x P(x)$.

We are ready to prove our tautology is, in fact, a tautology. Remember that the statement was “If Hypatia is a woman and all women are mortal, then Hypatia is mortal.”

We have seen that “Hypatia is a woman” may be rendered as $W(h)$ for the predicate $W(x)$ being "$x$ is a woman" and $h$ being Hypatia. Likewise, “Hypatia is mortal” could be rendered $M(h)$ where $M(x)$ is "$x$ is mortal". Finally, the statement “All women are mortal” would be $\forall x (W(x) \to M(x))$.

Theorem 3.3.4 The statement $[P(a) \wedge \forall x (P(x) \to Q(x))] \to Q(a)$ is a tautology.

We have changed our labeling to the more standard $P$, $Q$, and $a$ to emphasize that this statement is always true no matter what we are talking about.

Proof. Suppose that for some predicate $P$ and some $a$ in the domain of $P$ that $P(a)$ is true, and that for some predicate $Q$ the statement $\forall x (P(x) \to Q(x))$ is true.

By universal instantiation, $\forall x (P(x) \to Q(x))$ means that $P(a) \to Q(a)$ is true.

By modus ponens on $P(a)$ and $P(a) \to Q(a)$, we know $Q(a)$ must be true.

Therefore, $[P(a) \wedge \forall x (P(x) \to Q(x))] \to Q(a)$ is always true. $\square$

Takeaways

• If we need to communicate that two statements talk about the same thing, propositional logic won’t cut it: we need predicates.
• A predicate is a function that takes an input and returns true or false. The predicate itself isn’t a statement, but it is once it’s evaluated on a subject.
• A quantifier yields a statement that a predicate is true for some, or all, objects in its domain.
• "Every – is a – " is a universal conditional statement. "Some – is a – " is an existential conjunction.
• A universal statement implies a specific one, which implies an existential statement.
• The negation of a universal statement is an existential statement and vice-versa.

Chapter 3 problems

Proofs

Review:

• Chapter 2: Inferences and equivalences for conditional and biconditional statements
• Chapter 3: Inferences and equivalences for quantifiers

Videos:

• Direct proofs
• A direct proof involving divisibility
• Indirect proofs

Now we have things to talk about – sets and their elements – and ways of talking about those things – propositional and predicate logic. This opens the door to the true game of mathematics: proof.

Mathematics stands apart from the natural sciences because its facts must be proven. Whereas theories in the natural sciences can only be supported by evidence, mathematical facts can be shown to be indisputably true based on the agreed definitions and axioms.

For example, once you have agreed upon the definitions of “integer,” “even,” and the rules of arithmetic, the statement “An even integer plus an even integer is an even integer” is without doubt. In fact, you will prove this statement yourself in the exercises to this chapter.

Now, this introduction is not meant to imply that mathematical epistemology (the study of knowledge) is without its issues. For example: What definitions and axioms are good ones? (“Is there such a thing as a real number?” can entertain you for a while.) What sorts of people decide which mathematical research is worth doing, and who decides which proofs are convincing? Are all published mathematical proofs correct? (They aren’t.) What is the role of computers in mathematical proof?

Fortunately for us, we don’t have to worry about these questions. (Unless we want to. They’re quite interesting.) In this chapter we will simply learn what a mathematical proof is, learn some basic facts about the integers, and practice writing direct and indirect proofs about mathematical facts that are not particularly in dispute.

4.1 Direct proofs

What is a proof? In this book we will adopt Cathy O’Neil’s position that a proof is a social action between speaker/writer and listener/reader that convinces the second party that a statement is true.

Several proofs have been written in this book so far. Many begin with an italicized Proof. and end in a little $\square$, as a way to set them off from definitions, theorems, comments, and examples. Hopefully they have all been convincing to you. (DW: If not, my e-mail address is somewhere on this webpage.)

As you practice writing your own proofs, take for an audience someone else in your position: a new student of discrete mathematics. Imagine the reader knows slightly less than you do. A good proof gently guides the reader along, making them feel smart when they anticipate a move.

It is also this book’s position that talking about proofs is nearly useless. They must be read and practiced. With that in mind, let’s get to writing some proofs about integers.

We will take for granted that sums, differences, products, and powers of integers are still integers. (Depending on how the set of integers is defined, these qualities may be “baked in” to the definition.) Every other fact will either be stated as a definition or a theorem, and proven in the latter case.

Definition 4.1.1. An integer $n$ is even if there exists an integer $k$ such that $n=2k$.

Definition 4.1.2. An integer $n$ is odd if there exists an integer $k$ such that $n=2k+1$.

For examples, $28=2(14)$, and $39=2(19)+1$.

Theorem 4.1.3. If an integer $n$ is odd, so is $n^2$.

This statement may be obvious to you. If so, great; but we are trying to learn about the writing, so it is best to keep the mathematics simple. (It will only get a little more challenging by the end of the chapter.) To prove this statement, we must start with an arbitrary odd integer and prove that its square is odd. The integer in question must be arbitrary: if we prove the statement for 3, then we must justify 5, 7, 9, and so on.

Proof. Let $n$ be an odd integer.

The first step in the proof is to assume any of the theorem’s hypotheses. The theorem says that if we have an odd integer, its square we will be odd; so, we are entitled to assume an odd integer. However, there is nothing more we may assume. Fortunately, we know what it means for an integer to be odd.

That means there exists an integer $k$ such that $n=2k+1$.

A great second step is to “unpack” any definitions involved in the assumptions made. We assumed $n$ was odd. Well, what does that mean? However, now we are “out of road.” Let’s turn our attention to the object we mean to say something about; $n^2$.

Therefore, $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1,$ which is an odd number by definition.

Remember: sums, powers and products of integers are integers – this is the only thing we take for granted, other than, y’know, arithmetic – and so $2k^2 + 2k$ is an integer, call it $m$. Then $2m+1$ is odd. The final step – obviously rendering the result in the explicit form of an odd number – is a good one to take because we assume our reader to be as new at this as we are. They likely recognize $4k^2+4k+1$ is odd, but we take the additional step to ensure maximum clarity.

Thus, if $n$ is an odd integer so is its square. $\square$

Definition 4.1.4. Let $a$ be a nonzero integer and let $n$ be an integer. We say $a$ divides $n$ or that $n$ is divisible by $a$ if there exists an integer $k$ such that $n=ak$. We write $a|n$ when this is the case.

Theorem 4.1.5. Divisibility has the following three properties:

• For all integers $n$, $n|n$. (reflexiveness)
• For all positive integers $m$ and $n$, if $m|n$ and $n|m$ then $m=n$. (antisymmetry)
• For all integers $\ell$, $m$, and $n$, if $\ell|m$ and $m|n$ then $\ell|n$. (transitivity)

(These three properties together define something called a partial order, which is studied in the last chapter. Foreshadowing!)

You will prove two of these properties for yourself in the exercises. Here is a demonstration of the proof of the second property.

Proof. Suppose that $m$ and $n$ are positive integers where $m|n$ and $n|m$.

As before, we are assuming only what is assumed in the statement of the theorem: that $m$ and $n$ are positive divide one another. By the way: why did we have to say they are positive?

That means that there exist integers $k_1$ and $k_2$ such that $n=k_1m$ and $m=k_2n$.

The second step is usually to apply relevant definitions.

Combining these two statements, we have $m=(k_1k_2)m$. Since $m$ is not zero, we see $1=k_1k_2$. Because $k_1$ and $k_2$ must be integers by definition, the only way that $k_1k_2=1$ is for $k_1=k_2=1$.

If we didn’t have the restriction that $k_1$ and $k_2$ were integers, then $k_1=1/k_2$. However, this is only possible for integers when both numbers are one.

Therefore, if $m$ and $n$ are positive integers that divide one another, then $m=n$. $\square$

In the next section we will explore indirect proofs and, from there, bidirectional proofs. You are highly recommended to try some exercises before moving on.

4.2 Indirect and bidirectional proofs

Consider the following theorem.

Theorem 4.2.1 If $n$ is an integer such that $n^2$ is odd, then $n$ is odd.

This theorem may seem the same as Theorem 4.1.3, but note carefully that it is not: it is the converse $Q(n) \to P(n)$ to the previous theorem’s $P(n) \to Q(n)$.

Let’s try to imagine a direct proof of this theorem. Since $n^2$ is odd, there exists an integer $k$ such that $n^2 = 2k+1$. And then, seeking to prove a fact about $n$, we take the positive square root of each side: $n = \sqrt{2k+1}$. And…ew. Have we even proven anything about square roots? (We haven’t, and we won’t.)

We shall, instead, employ some sleight of hand. Recall from Chapter 2 that a conditional statement $p \to q$ is equivalent to its contrapositive $\neg q \to \neg p$.

Proof (of Theorem 4.2.1). Suppose that $n$ is even. Then there exists an integer $k$ such that $n=2k$. In that case, $n^2 = (2k)^2 = 4k^2 = 2(2k^2),$ which is even. Therefore for $n^2$ to be odd, $n$ must also be odd. $\square$

Another equivalence from Chapter 2 was that $p \to q$ and $q \to p$ combine to create $p \leftrightarrow q$. That is, we can prove an “if and only if” statement by proving both the “forward” and “backward” directions (which is which is a matter of perception). Therefore, in this chapter we have proven the following statement:

Theorem 4.2.2 An integer $n$ is odd if and only if $n^2$ is.

Remember that an “if and only if” statement is true if the component statements are both true or both false. So, this theorem also tells us that an integer is even if and only if its square is.

Theorem 4.2.3 Let $n$ be an integer. The integer $n$ is odd if and only if $n^2+4n+1$ is even.

Proof. Let $n$ be an integer. First, suppose $n$ is odd. That means that there exists an integer $k$ where $n=2k+1$. So, $n^2 + 4n +1 = (2k+1)^2 + 4(2k+1) + 1 = 4k^2 + 4k + 1 + 8k + 4 + 1,$which may be written as $2(2k^2 + 6k + 3),$ which is even. Therefore if $n$ is odd then $n^2+4n+1$ is even.

Conversely, suppose $n$ is even. That means that $n=2k$ for some integer $k$. In that case, $n^2 + 4n + 1 = (2k)^2 + 4(2k) + 1,$which is$2(2k^2+4k)+1,$ which is odd. Therefore for $n^2+4n+1$ to be even, $n$ must be odd.

So, $n$ is odd if and only if $n^2+4n+1$ is even. $\square$

4.3 Counterexamples

When proving a universal statement on a domain, it never suffices to just do examples (unless you do every example, which is usually not feasible or possible). However, remember from Chapter 3 that the negation of a universal statement is an existential one. You can prove that "every $P$ is a $Q$" is false by finding just one $P$ that isn’t a $Q$.

Examples. The statement “all prime numbers are odd” is false because $2$ is prime and even.

The statement “all odd numbers are prime” is false because $9$ is odd and not prime.

Takeaways

• A proof is a social action between speaker and listener. Keep your audience in mind as you write - try to make them feel smart! If you are taking a class, your proofs should be written for your classmates.
• If you are trying to prove that a statement is true for every object of a particular type, it is never appropriate to just do a couple of examples.
• In a direct proof of $p \to q$, you should start by assuming any hypotheses and unpacking the relevant definitions before arriving at the conclusion via valid reasoning.
• Sometimes it is hard to prove $p \to q$ directly, in which case maybe you should try proving the contrapositive $\neg q \to \neg p$.
• You can prove $p \leftrightarrow q$ by proving $p \to q$ and $q \to p$.
• You have to practice proof writing a lot. (DW: I wasn’t a good proof writer until the end of graduate school, and one may argue I am still not a good proof writer.)

Chapter 4 problems

5. Recursion and integer representation

Videos:

• Introduction to recursion
• Binary numbers
• Octal and hexadecimal numbers

One of the most important ideas in discrete mathematics is that of recursion, which we will explore in one way or another for many of the remaining chapters in the course. In this chapter, we will explore it through the idea of integer representation; representing integers in bases other than the common base 10. Bases you are likely to encounter in computer science contexts are base 2 (binary), base 8 (octal), and base 16 (hexadecimal). We will learn how to represent an integer in binary using a recursive algorithm, and then we will cheat our way into octal and hexadecimal.

5.1 Recursion

Recursion is when an algorithm, object, or calculation is constructed recursively.

Just kidding. Reread this joke after the chapter and it’ll make more sense.

Recursion means that an algorithm, object, or calculation is written, defined, or performed by making reference to itself. It is something more easily understood by example, and there will be plenty as we proceed. For now, consider the following example.

Definition 5.1.1 Let $n$ be a positive integer. Then $n!$ ("$n$ factorial") is the product of all positive integers at most $n$: $n! = 1 \times 2 \times \cdots \times n = n!$ Furthermore, we define $0!=1$.

Anyone questioning the usefulness of $n!$ will have their questions answered in excruciating detail over the course of Chapters 9-13. If the reader has had calculus, then they may recognize $n!$ as the denominator of the terms in the Taylor expansion of the function $e^x$; it is good for “absorbing” constants created by taking derivatives. However, we are not interested in any of its uses right now.

Example. Here are the values of a few factorials: $0!=1$, $1!=1$, $2!=2\times 1 = 2$, $3!=3\times 2 \times 1 = 6$, $4!=4 \times 3 \times 2 \times 1 = 24$, and $5!=5\times 4\times 3 \times 2 \times 1=120$.

You may have already noticed the recursion at work. Take for instance $5!=5 \times 4 \times 3 \times 2 \times 1$. We see the value of $4!$ lurking here: $5!=5 \times 4!$.

In fact, for all positive $n$, we can make the alternative (usually more useful) definition $n!=n(n-1)!$. This is the recursive defintion of the factorial, because we are defining the factorial in terms of the factorial.

Why is this okay? Well, we’re really collapsing a lot of work into two lines: it may make more sense to break it down one step at a time. First, define $0!=1$. This definition will make sense in a later chapter, but remember that mathematical definitions don’t necessarily need to “make sense.”

Next, define $1!=1 \times 0!$. This definition is valid, because the number $1$, the operation $\times$, and the number $0!$ have all been defined. And when we go to define $2!=2 \times 1!$, we have already defined all of these objects as well. And so on. Therefore, the following definition is a valid one.

Definition 5.1.2 Let $n$ be a natural number. Then $n!$ is equal to 1 when $n=0$, and $n(n-1)!$ otherwise.

5.2 Binary numbers

Now that we know how recursion works (or at least have more of an inkling than we did upon starting the chapter), we will see another example of it in the calculation of the binary representation of a number.

When we speak of the number one thousand five hundred eight or $1,508$, we are implicitly talking about the composition of the number in terms of powers of 10: $1,508 = 1\times 10^3 + 5 \times 10^2 + 0 \times 10^1 + 8 \times 10^0,$ remembering that $b^0=1$ for all nonzero $b$.

African and Asian mathematicians were writing in base-10, or decimal notation, as early as 3,000 BCE. Presumably the prevalence of decimal notation throughout human history is due to the fact that most of us have ten fingers and ten toes, making the base convenient. However, computers only have two fingers and two toes.

That last line is a joke, but here’s the idea: Computers read information by way of electrical signals, which are either on or off. So the simplest way for a computer to process information is in terms of two states. Here is a higher-level example: suppose you are writing some code. Is it easier to have a single if-then statement (two possible states), or nine (ten possible states)? This is why base-2, or binary numbers, are so prevalent in computer science.

The first step to becoming adept with binary numbers is to know many powers of $2$. Fortunately, powers of $2$ are easy to calculate: simply multiply the last value by $2$ to get the next one. (This is a recursive definition for $2^n$!)

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$
$2^n$	$1$	$2$	$4$	$8$	$16$	$32$	$64$	$128$	$256$	$512$

Algorithm 5.2.1 Let $n$ be a natural number. To write the $d$-digit binary expansion $(a_{d-1}a_{d-2}\ldots a_1a_0)_2$ of $n$:

• If $n=0$, its binary expansion is $(0)_2$.
• If $n=1$, its binary expansion is $(1)_2$.
• If $n \ge 1$, find the highest number $d$ such that $2^{d-1} \le n$. This is the number of binary digits of $n$. Then, the binary expansion of $n$ is $(1a_{d-2}\ldots a_1a_0)_2$. The remaining digits $a_{d-2}$, $a_{d-3}$, $\ldots$, $a_0$, are the digits of binary expansion of $n-2^{d-1}$, or $0$ if the binary expansion of $n-2^{d-1}$ does not contain that digit.

This is perhaps a little intimidating at first glance, so let’s press on with an example.

Example. Let’s calculate the binary expansion of $n=1,508$. Our target $n$ is neither $0$ nor $1$, so we must find the highest power of $2$ that is no more than $n$. This number is $2^{10}=1,024$. Therefore, our binary number will have eleven digits, and right now it looks like $(1a_9a_8\ldots a_1a_0)_2.$

To find the values of the remaining digits $a_9$, $a_8$, etc., let’s find the binary expansion of the remainder $1,508 - 1,024 = 484$.

Here’s the recursion, by the way: to find the binary expansion of $n$, we must find the binary expansion of a smaller number.

We repeat the process. The highest power of $2$ that divides $484$ is $2^8=256$. So, the binary expansion of $484$ is the nine-digit number $(1a_7a_6\ldots a_1a_0)_2.$ Be aware that it is okay to reuse the names $a_i$ for the unknown digits, because the algorithm says they are the same for both numbers.

Next, we find the second remainder $484-256=228.$ The highest power of 2 dividing 228 is $2^7=128.$ Continue the example and see for yourself that the binary expansion of $228$ is $(11100100)_2$. (Your remainders after $228$ will be $100$, $36$, $4$, and $0$.)

Now, the binary expansion of $484$ is $(111100100)_2$ and the binary expansion of $1,508$ is $(1a_9111100100)_2.$

The algorithm tells us what to do with our missing $a_9$: since it does not appear in the expansions of any of our remainders, it is 0. Therefore, $1,508 = (10111100100)_2.$

This examples was made much more tedious than it needed to be so that the recursive steps were laid bare. In practice, you will simply continue subtracting off powers of $2$ until none of the target number remains, writing a $1$ if you subtracted a particular power of $2$ and a $0$ if you didn’t. Since we had to subtract $1,024$, $256$, $128$, $64$, $32$, and $4$, we write a $1$ for the eleventh, ninth, eighth, seventh, sixth, and third digits, and a $0$ everywhere else.

You have no doubt noticed that our binary numbers are all enclosed in the notation $()_2$. This is to signify that the $(101)_2$, for example, is referring to the number five and not the number one hundred one.

5.3 Octal and hexadecimal numbers

The word octal refers to the base-8 system and hexadecimal refers to the base-16 system. These two bases are useful abbreviations of binary numbers: octal numbers are used to modify permissions on Unix systems, and hexadecimal numbers are used to encode colors in graphic design.

We say “abbreviation” because of the following algorithm.

Algorithm 5.3.1 Suppose $n$ is an integer with a base $b$ representation and we desire to know its base $b^k$ representation, for some integer $k > 1$. Then we may group the digits of $n$ in base $b$ into groups of $k$ and rewrite each group as a digit in base $b^k$. The resulting string is the binary expansion of $n$ in base $b^k$.

The idea is that it is easy to go from some base to a base that is a power of the original base. Consider the following example.

Example. Write the number $236$ in octal and in hexadecimal.

The starting point will be to write $236$ in binary. Since $236=128+64+32+8+4,$ its binary expansion is $(11101100)_2$.

To write $236$ in octal, we will regroup the binary digits of $236$ by threes because $8=2^3$. However, there are eight digits. No worries; we will simply add a meaningless $0$ as the leftmost digit of the binary expansion. Those groups are: $011$, $101$, and $100$ from left to right. In order, those numbers are $3$, $5$, and $4$; so, $236$ is $(354)_8$.

Observe that in a base $b$ number system, the digits are $0, 1, 2, \ldots, b-1$. Therefore the highest digit we will see in octal is $7$.

However – what about hexadecimal? Its set of digits is larger than our usual base-10 set. It is standard usage to use $A$ through $F$ to represent $10$ through $15$.

Decimal digit	$10$	$11$	$12$	$13$	$14$	$15$
Hexadecimal digit	$A$	$B$	$C$	$D$	$E$	$F$

Since $16=2^4$, to write $236$ in hexadecimal we will group the digits in its binary expansion by fours this time. Those groups are $1110$ and $1100$, which represent fourteen and twelve respectively. So, $236=(EC)_{16}$.

To summarize our example, here are four different representations of the number $236$.

System	Decimal	Binary	Octal	Hexadecimal
	$236$	$(11101100)_2$	$(354)_8$	$(EC)_{16}$

Takeaways

• Recursion is when something is defined or implemented in terms of its own definition or implementation. Recursion is incredibly useful both mathematically and programmatically.
• Given a positive integer $n$, its factorial $n!$ – the product of all positive integers at most $n$ – may be recursively expressed as $n(n-1)!$. Meanwhile, $0!=1$.
• Binary numbers are convenient in programming. We may write a binary number by recursively writing a smaller number in binary first.
• We may express a binary number in octal or hexadecimal by grouping its digits by threes or fours.

Chapter 5 problems

6. Sequences and sums

Videos:

• Introduction to sequences
• Recurrence relations
• Directly calculating sums
• Indirectly calculating sums

6.1 Sequences

Remember that a set has no order. For example, $\{1,2\}$ and $\{2,1\}$ are the same set. Often, we care about the order objects are in. Enter the sequence.

Definition 6.1.1 Let $I \subseteq \mathbf{N}$ and $X$ be some set. A sequence is a function $a:I \to X$. We write $a_n$ instead of $a(n)$. Here, $n$ is the index and $a_n$ is the term. We denote the entire sequence as $(a_n)$ (when the start and endpoints are stated elsewhere or are unimportant), $(a_n)_{n=k}^\infty$ (for an infinite sequence starting with $a_k$), or $(a_n)_{n=k}^m$ (for a finite sequence starting at $a_k$ and ending at $a_m$). A finite sequence is called a word from the alphabet $X$.

Once again we have chosen a more technical, functional definition where we instead could have said “a sequence is a totally ordered list of objects.” It is worth considering the way in which a function can “port structure” from one set to another. If we wanted a totally ordered set it is hard to imagine a better candidate than $\mathbf{N}$. The sequence transfers the order structure from $\mathbf{N}$ into whatever set $X$ we like.

Example. Consider the sequence $(a_n)_{n=1}^\infty = (1, 4, 9, 16, 25, \ldots).$ Observing that each term is the square of its index, this sequence may be represented in closed form by writing $a_n=n^2$.

Not every sequence may be so easily identified in closed form.

Example. Consider the sequence $(F_n)_{n=0}^\infty = (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots).$ You may recognize this sequence as the famous Fibonacci sequence. There is a closed-form expression for $F_n$, but you are unlikely to see it by visual inspection. However, notice that each term in the sequence is equal to the sum of the preceding two terms: for instance, $13=8+5$.

Therefore instead we can represent the Fibonacci sequence recursively with a recurrence relation: $F_n = \begin{cases} F_{n-1} + F_{n-2}, & n > 1 \\ 1, & n = 1\\ 0, & n = 0 \end{cases}$

Once a recurrence relation is established, the terms of a sequence may be calculated iteratively or recursively. Each method has its strengths and weaknesses depending on the context; typically, recursive calculations are more difficult but require storing less information.

Example. Consider the sequence $(x_n)$ where $x_n = \begin{cases} x_{n-1} - 2x_{n-2}, & n > 2 \\ 1 & n = 2, \\ -1 & n = 1 \end{cases}$

To calculate $x_4$ iteratively, we simply calculate each term of $(x_n)$ until we arrive at $x_4$. So: $x_1=-1$, and $x_2 = 1$. Then $x_3 = x_2 - 2x_1 = 1 - 2(-1) = 3,$ and $x_4 = x_3 - 2x_1 = 3 - 2(1) = 1.$ Thus, $x_4 = 1$.

In the recursive calculation, we will begin with $x_4$ and repeatedly apply the recurrence relation until we have only known values of the sequence: so, $x_2$ and $x_1$. First, $x_4 = x_3 - 2x_2.$ However, we “don’t know” what $x_3$ is, so we repeat the recursion: $x_4 = (x_2 - 2x_1) - 2x_2.$ Now we substitute in the given values: $x_4 = (1 - 2(-1)) - 2(1) = 1.$ It is important that we arrive at the same value both ways!

6.2 Sums

Given a sequence, a natural course of action is to add its terms together. To avoid writing a bunch of plus signs, we write $\sum_{n=k}^m a_n = a_k + a_{k+1} + \cdots + a_{m-1} + a_m$ for the sum of the members of $(a_n)$, starting with the $k$-th member and ending with the $m$-th member.

Example. Consider the sum $\sum_{i=1}^4 i^2.$ Notice that $i$ is being used for the index rather than $n$. That’s okay! The sum’s value is $\sum_{i=1}^4 i^2 = 1^2 + 2^2 + 3^2 + 4^2 = 30.$

We can have sums of sums, and sums of sums of sums, etc. Double sums are common in computer science when evaluating the runtimes of doubly-nested for loops.

Example. Consider the sum $\sum_{m=1}^3 \sum_{n=2}^4 (m+n).$ This sum is rectangular in the sense that the bounds of one sum are not determined by the other, and so we could do this sum in either order: $\sum_{m=1}^3 [(m+2) + (m+3) + (m+4)]$ or $\sum_{n=2}^4 [(1+n) + (2+n) + (3+n)].$ Either way, the sum’s value is $45$.

For another example, take $\sum_{i=1}^4 \sum_{j=1}^i 2^{i+j}.$ Because the bounds of the $j$-sum are dependent on the value of $i$, we should iterate over $i$ first: $\sum_{j=1}^1 2^{j+1} + \sum_{j=1}^2 2^{j+2} + \sum_{j=1}^3 2^{j+3} + \sum_{j=1}^4 2^{j+4}.$

Each of these sums must be done separately. The first sum, of just one term, is equal to $4$. The second sum is $24$, the third is $112$, and the fourth is $480$; so altogether the sum is $620$.

We will end on two theorems that are important for manipulating sums, the second of which will be very useful later.

Theorem 6.2.1 [Linear property of summation] Let $(a_n)$ and $(b_n)$ be sequences and $c$ be a constant value. Then, $\sum_{n=k}^m (a_n + b_n) = \sum_{n=k}^m a_n + \sum_{n=k}^m b_n$ and $\sum_{n=k}^m ca_n = c\sum_{n=k}^m a_n.$

Proof. The associative property of addition – $(x+y)+z = x+(y+z)$ – and the distributive property – $c(x+y) = cx+cy$ – guarantee this theorem. $\square$

Example. Suppose we know that $\sum_{n=2}^{38} a_n = 14 \qquad \text{and} \qquad \sum_{n=2}^{38} b_n = 19.$ Then the value of the sum $\sum_{n=2}^{38} (a_n+2b_n)$ is $\sum_{n=2}^{38} a_n + 2 \sum_{n=2}^{38} b_n = 14 + 2(19) = 52.$ Notice that both sums must start and end on the same index.

Theorem 6.2.2 [Recursive property of summation] Let $(a_n)$ be a sequence. Then $\sum_{n=k}^m a_n = \left( \sum_{n=k}^{m-1} a_n \right) + a_m = a_k + \left( \sum_{n=k+1}^{m} a_n \right).$

Proof. By definition, $\sum_{n=k}^m a_n = a_k + a_{k+1} + \cdots + a_{m-1} + a_m.$ By the associative property of addition we may rewrite this as either $(a_k + a_{k+1} + \cdots + a_{m-1}) + a_m = \left( \sum_{n=k}^{m-1} a_n \right) + a_m$ or $a_k + (a_{k+1} + \cdots + a_{m-1} + a_m) = a_k + \left( \sum_{n=k+1}^{m} a_n \right),$ proving the theorem. $\square$

Example. Suppose it is known that $b_{107} = 72$ and that $\sum_{k=1}^{106} b_k = 291.$ Then, $\sum_{k=1}^{107} b_k = 363.$

Takeaways

• A sequence is a (possibly infinite) ordered collection of objects.
• Terms of a sequences may be defined in closed form, via a formula, or recursively based on prior terms of the sequence.
• Sums may be calculated directly or indirectly, using linearity or recursiveness.

Chapter 6 problems

7. Asymptotics

Videos:

• Asymptotics
• Asymptotics examples

Consider the following example of two programs, $A$ and $B$, that process some data. The following table provides the number of computations taken by each program to process $n$ data points.

$n$	Program $A$	Program $B$
1	1	58
10	100	508
20	400	1008
50	2500	2508
60	3600	3008
100	10,000	5008

At first, Program $A$ looks much better than Program $B$. However, as $n$ increases, it becomes clear that $A$ is worse at handling large quantities of data than $B$. If $(A_n)$ and $(B_n)$ represent sequences of the numbers of steps taken by each program, then $A_n=n^2$ and $B_n = 50n+8$. The way we quantify the relationship between the two sequences is by saying $A_n$ is “big-O” of $B_n$.

7.1 Growth bounds on sequences

Definition 7.1.1 Let $a_n$ and $b_n$ be terms of sequences. We say $a_n$ is big-O of $b_n$ if there exist a real number $C$ and an integer $k$ such that for all $n > k$, $|a_n| \le Cb_n.$ We write $a_n = O(b_n)$, even if the equals sign is technically incorrect.

This is another technical definition that can be hard to parse, but the idea is that eventually (after the $k$-th term of the sequence) $a_n$ does not grow faster than $b_n$. In this way, $b_n$ serves as an upper bound on the growth of $a_n$.

As we will see again in Chapter 18, there may be many upper bounds. For example in a classroom of twenty-nine students I may say “Here are fewer than thirty students” or “Here are fewer than a million students.” The first statement is obviously more informative. So often you will be asked to find the least upper bound on the growth of $a_n$; this is usually a $b_n$ that is the simplest and is itself big-O of all the other options.

Theorem 7.1.2 Any non-negative sequence is big-O of itself.

Proof. Let $(a_n)$ be a non-negative sequence; that is, $a_n \ge 0$ for all $a_n$. Then the statement $|a_n| \le a_n$ is satisfied by equality since $|a_n| = a_n$. If we put $C=k=1$, then this statement implies that $a_n = O(a_n)$. $\square$

We can form a basic hierarchy of sequences and their big-O relationships. In the below table, a sequence $a_n$ appearing to the left of a sequence $b_n$ means that $a_n=O(b_n)$.

Slowest							Fastest
$1$	$\log n$	$n$	$n \log n$	$n^2$	$n^3$	$2^n$	$n!$

At the left-most end of the chart, the slowest-growing sequence is $(a_n) = (1, 1, 1, \ldots)$. It is slowest-growing because it does not grow at all! In fact, any constant sequence is big-O of any other sequence.

Next is the sequence $(\log n)$. In this book, $\log n$ refers to the base-2 logarithm that you might have elsewhere seen written as $\log_2 n$. Here are a couple of ways to conceptualize this sequence and its relevance to computer science.

• $\log n$ is big-O of the number of digits in the binary expansion of $n$.
• $\log n$ is roughly the number of times a finite sequence of length $n$ can be cut in half.

The rest of the functions in the list should be familiar. Notice that all polynomial functions of higher degrees appear between $n^3$ and $2^n$, and higher-order exponential functions like $e^n$ occur between $2^n$ and $n!$.

Now we know where basic functions fit into the big-O hierarchy, but what about more complicated expressions like $50n+8$? The following theorem will help.

Theorem 7.1.3 Let $(a_n)$ and $(b_n)$ be sequences.

• If $c$ is a nonzero constant, then $ca_n = O(a_n)$.
• Suppose there exists a sequence $c_n$ such that $a_n = O(c_n)$ and $b_n=O(c_n)$. Then, $a_n+b_n$ is big-O of $c_n$ as well.
• Suppose there exist sequences $A_n$ and $B_n$ such that $a_n=O(A_n)$ and $b_n=O(B_n)$. Then, $a_nb_n = O(A_nB_n)$.

In plain English, this theorem says:

• Constant multiples do not affect growth rate.
• When adding two sequences, the larger absorbs the smaller. In other words, one must only look at the highest-order term of a sum.
• Growth rates are multiplicative; “big-O of the product is the product of the big-O’s,” though that language is very informal.

It is worthwhile to read the below proof of the theorem, but do not worry if you don’t understand it. Read it once, then skip it until after Chapter 8. You can work the problems at the end of the chapter even if you don’t totally understand the following proof.

Proof. To prove the addition rule (second bullet point), suppose $a_n = O(c_n)$ and $b_n = O(c_n)$. That means there exist witnesses $k_1, k_2, C_1,$ and $C_2$ where $|a_n| \le C_1c_n$ for all $n > k_1$ and $|b_n| \le C_2c_n$ for all $n > k_2$. Then, $a_n + b_n \le C_1c_n + C_2c_n = (C_1+C_2)c_n$ for all $n > \text{max}\{k_1,k_2\}$. In other words, this inequality holds for all $n$ far enough along that both the big-O relationships hold. By definition, this means $a_n + b_n$ is big-O of $c_n$.

To prove the multiplication rule (third bullet point), suppose there exist sequences $A_n$ and $B_n$ such that $a_n=O(A_n)$ and $b_n=O(B_n)$. Therefore there exist witnesses $k_1, k_2, C_1,$ and $C_2$ where $|a_n| \le C_1A_n$ for all $n > k_1$ and $|b_n| \le C_2B_n$ for all $n > k_2$, so that for all $n > \text{max}\{k_1, k_2\}$, $|a_nb_n| \le (C_1A_n)(C_2B_n) = (C_1C_2)A_nB_n.$

To prove the theorem about constant multiples (first bullet point), apply the multiplication rule where $(b_n)$ is the constant sequence $(c, c, c, \ldots)$. Observe that this sequence is big-O of the sequence $(1)$ by taking $k=0$ and $C=1/c$. So, since $a_n = O(a_n)$ and $c = O(1)$, $ca_n = O(1\times a_n) = O(a_n)$ as claimed. $\square$

Finally, we have enough tools to do some examples!

Examples. Consider the sequence whose terms are given by the formula $a_n = n^2 + 5n + 7$. We would like to find the simplest function $b_n$ of lowest order such that $a_n=O(b_n)$.

Notice that $a_n$ is a sum of three terms: $n^2$, $5n$ which is big-O of $n$, and $7$ which is big-O of $1$. Only the highest-order of these matters; both the constant term and the linear term $n$ are big-O of $n^2$, but not the other way around. Therefore $a_n = O(n^2)$.

What is the simplest and lowest-order function $b_n$ such that $(1 + 5n + 2n^2)(\log n + 3n \log n)$ is big-O of $b_n$?

Theorem 7.1.3 says we only need the highest-order term of each factor, and then we must multiply those terms together. The highest-order term of the first factor is big-O of $n^2$ and the second factor is big-O of $n \log n$; so, the whole sequence is big-O of $n^3 \log n$.

7.2 Other growth relationships

We will briefly mention two other growth relationships here. Recall that saying $a_n = O(b_n)$ is to say that $b_n$ is an upper bound on the growth rate of $a_n$. Then saying $a_n = \Omega(b_n)$ (big-Omega) is to say that $b_n$ is a lower bound on the growth rate of $a_n$, and $a_n = $\Theta(b_n)$ (big-Theta) is to say that $a_n$ and $b_n$ grow in the same way.

Definition 7.2.1 Let $(a_n)$ and $(b_n)$ be sequences. Then

• $a_n = \Omega(b_n)$ if $b_n = O(a_n)$, and
• $a_n = \Theta(b_n)$ if $a_n = O(b_n)$ and $b_n = O(a_n)$.

Takeaways

• “Big-O” relationships are a way to quantify when one sequence is eventually bounded in its growth by another.
• There is a hierarchy of basic sequences that may be committed to memory.
• Beyond the basic sequences, three rules govern the relationships between more complicated functions: constant multiples do not matter; addition is absorptive; and multiplication is, well, multiplicative.

Chapter 7 problems

8. Proof by induction

Review.

• Basic algebra! This is probably the most algebraically taxing chapter in the book.
• Chapter 4: Proofs and the definition of divisibility.
• Chapter 5: Recursion.
• Chapter 6: Sequences and sums, particularly sigma notation and the recursive property of summation.

It is time to come full circle on our discussion of proofs and recursion to establish the recursive proof technique, proof by induction.

What are the two ingredients to knocking over a line of domino tiles? Each domino must be sufficiently close to the next, and you must tip over the first one.

Proof by induction proceeds in much the same way. We want to prove some statement $P(n)$ holds for every natural number $n$ past a base value $n_0$. We prove the following two claims:

• The base case: That $P(n_0)$ is true. The base case is easy to prove - just plug in $n_0$ and make sure the statement is true!
• The inductive step: That the inductive hypothesis, $P(k)$, for some integer $k \ge n_0$, implies $P(k+1)$.

Once both of these statements are proven we will have $P(n_0)$, $P(n_0+1)$, $P(n_0+2)$, and so on; we will know $P(n)$ to be true for all $n \ge n_0$.

8.1 Inductive proofs involving sums

We will discuss three types of inductive proofs in this chapter. The first type involve proving facts about sums. Recall the recursive property of summation from Chapter 6, which will mostly look like this now: $\sum_{i=1}^{k+1} a_i = \left( \sum_{i=1}^{k} a_i \right) + a_{k+1}.$

Theorem 8.1.1 For all $n \ge 1$, $\sum_{i=1}^n i = \frac{n(n+1)}{2}.$

Proof. First, check the base case. Since $\sum_{i=1}^1 i = 1 = \frac{1(1+1)}{2},$ the statement is true in the base case.

Next, suppose that for some integer $k \ge 1$ that $\sum_{i=1}^k i = \frac{k(k+1)}{2}$ (this is the inductive hypothesis). We claim that $\sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2}.$ This statement is $P(k+1)$–notice that $k+1+1$ is $k+2$. We say up front that we “claim” it so that our reader knows where we are headed.

The preceding part of the proof is basically the same for all proofs by induction you’ll do. The next part is where the real work comes in, and it depends on what sort of thing you’re doing induction on. Since this is a sum, we will use the recursive property.

We may rewrite $\sum_{i=1}^{k+1} i$ as $\left( \sum_{i=1}^k i \right) + (k+1).$ Notice that the sum is known by the inductive hypothesis; so, this is $\frac{k(k+1)}{2} + (k+1).$ We put the fractions over common denominators: $\sum_{i=1}^{k+1} i = \frac{k(k+1)}{2} + \frac{2(k+1)}{2}.$ Then, we regroup the fractions: $\sum_{i=1}^{k+1} i = \frac{(k+2)(k+1)}{2},$ as claimed.

Therefore by induction, $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ for all $n \ge 1$. $\square$

If desired, you could expand out $k(k+1)$ and $2(k+1)$ and add them together and check the result against the expansion of $(k+1)(k+2)$. Instead, we noted that $(k+2)(k+1)=k(k+1)+2(k+1)$. Factoring!

8.2 Inductive proofs involving divisibility

Remember that $a$ divides $n$ (or $a|n$) means that there exists an integer $k$ such that $n=ak$. Induction may be used to prove that every element of a sequence is divisible by some number.

Theorem 8.2.1 If $n \ge 1$, then $3|(4^n+5)$.

Proof. Observe that when $n=1$, $4^n+5=9$, which is divisible by 3. So, the statement is true in the base case.

Assume that for some integer $k \ge 1$ that $3|(4^k+5)$. We mean to show that $3|(4^{k+1}+5)$.

Observe that $4^{k+1}+5$ may be rewritten as $4\cdot 4^k + 5.$ This is the same as $3\cdot 4^k + 4^k + 5.$ The assumption that $3|(4^k+5)$ means there exists an integer $m$ such that $4^k+5 = 3m$. So, $3\cdot 4^k + 4^k + 5 = 3 \cdot 4^k + 3m = 3(4^k+m),$ implying that $3|(4^{k+1}+5)$ as desired.

Therefore, by induction, $3|(4^n+5)$ for all $n \ge 1$. $\square$

The key calculation, that $4^{k+1} = 3\cdot 4^k + 4^k$, may merit some discussion. Recall that $4^{k+1} = 4 \cdot 4^k$; this is the “addition rule” for exponents. Then we observe that $4=3+1$ and apply the distributive property. In general, we may say that $a^{k+1} = (a-1)a^k + a^k$ for all real numbers $a$; this fact will be helpful when you do these types of proofs on your own.

8.3 Inductive proofs involving inequality

Remember the definition of big-O involves the key line $|a_n| \le Cb_n$ for sequences $(a_n)$ and $(b_n)$ and a real number $C$. So, computer scientists are often interested in justifying that an inequality is true past some given threshold.

Before we begin, we should discuss some tips for manipulating inequalities. They are much more flexible than equalities; this is both a positive and a negative in the sense that it is sometimes difficult to know the next step to take! So, outside of the proof we will “work backwards” to see if that illuminates the process; more on this in a moment.

Theorem 8.3.1 Suppose that $a$, $b$, $c$, and $d$ are positive real numbers satisfying $a \le b$ and $c \le d$. Then $a + c \le b + d$ and $ac \le bd.$

To get an idea of what sort of “scratch work” is helpful or appropriate, take the following theorem.

Theorem 8.3.2 If $n \ge 5$, then $2n^2 + 4n + 1 \le 3n^2$.

Notice that this statement is a proof that $2n^2 + 4n + 1$ is big-O of $n^2$. (Do you see why?)

In a proof, it is not valid to imagine that the desired statement is true and work backwards. However, working these “backwards” steps can give us a crucial idea as to what the valid, forward-thinking proof should look like. Knowing how proof by induction works, we will assume that $2k^2 + 4k + 1 \le 3k^2$ and hope to claim that $2(k+1)^2 + 4(k+1) + 1 \le 3(k+1)^2.$ How to prove such a claim? Well, if we expand the desired statement, we see $2k^2 + 4k + 2 + 4k + 4 + 1 \le 3k^2 + 6k + 3.$ Using Theorem 8.3.1, we can cancel the terms of the inductive hypothesis to arrive at $4k + 6 \le 6k + 3.$ This is nearly an obvious statement – because $k \ge 5$ we know $4k+6$ is at least 26 and $6k+3$ is at least 33, and the latter grows faster – but we can rewrite it as $3 \le 2k,$ which is clear for $k \ge 5$.

Having done this work now, we know exactly what do in our proof. Crucially, all of the above steps are reversible!

Proof. The statement is true in the base case because $2(5)^2 + 4(5) + 1 = 71 \le 75 = 3(5)^2.$

Assume that for some integer $k \ge 5$ that $2k^2 + 4k + 1 \le 3k^2$. We aim to show that $2(k+1)^2 + 4(k+1) + 1 \le 3(k+1)^2.$

First, since $k \ge 5$, we know that $3 \le 2k,$ and that this implies (by adding $4k+3$ to both sides) that $4k+6 \le 6k+3$.

Having assumed $2k^2 + 4k + 1 \le 3k^2$, we may combine both inequalities: $2k^2 + 4k + 1 + 4k + 3 \le 3k^2 + 6k + 3,$ which may be regrouped and rearranged into $2(k+1)^2 + 4k + 1 \le 3(k+1)^2,$ as claimed.

Therefore, by induction $2n^2 + 4n + 1 \le 3n^2$ for all $n \ge 5$. $\square$

Proofs involving sums and divisors are relatively straightforward to do without scratch work, because there is only one way to manipulate an equality. There are many ways to manipulate inequalities, and so the scratch work can point you in the right direction.

Takeaways

• Proof by induction is a recursive proof technique where $P(n)$ is proven for all $n \ge n_0$ by proving (1) $P(n_0)$ is true and (2) $P(k+1)$ follows from $P(k)$.
• The type of work involved in the proof varies depending on what sort of structure the theorem is about. Sum and divisibility proofs involve exploiting the recursiveness of the sum or the exponential function.
• When proving an inequality, it is often useful to “work backward” first (but not within the proof!) to see what steps should be taken.
• Again: practice, practice, practice.

Chapter 8 problems

Interlude

At this point in the book you have been exposed to the basics of formal mathematics: sets, logic, and proof. The motivated independent student could quit here and go off and read something else; you now know enough to read introductory books in various mathematical topics such as algebra, topology, and analysis (though calculus will help with the latter two).

The second half of this book will deal with two topics in discrete math: combinatorics, or methods to solve counting problems; and relations, a subset of graph theory that touches on the areas of functions, orders, and equivalences. Familiarity with all of the previous material, especially sets, logic, proofs, sums, and recursion will be necessary.

9. Introduction to combinatorics

Review.

• Chapter 1: Sets, unions, products, and cardinality
• Chapter 5: Recursion and factorials
• Chapter 8: Proof by induction

The time has come to learn how to count. Counting problems that require more sophisticated methods than simple listing include knowing how a program’s computation time scales with more data or counting the number of objects or structures of a particular type. In this chapter we will familiarize ourselves with the basics of counting: enumeration, addition, and multiplication.

9.1 Enumeration

In blatant disregard for the previous paragraph, a powerful tool in combinatorics is enumeration: systematically listing the objects to be counted. If the target set is small and finite, enumeration is perfectly fine. When the target set is cumbersomely large, enumeration can still help give an idea of how the elements are generated so that formal rules can give their number without the need to fully list them.

Example. How many ways are there to shuffle a deck of 52 cards?

It will be impossible to fully enumerate the space of objects to be counted (we will discuss just how impossible once we have an answer). However, let’s pretend the deck has just four cards: $A$, $B$, $C$, and $D$.

Now it is possible to systematically list out all possible shuffles of the deck. Let’s arrange them into a table where each column corresponds to a different card on top of the deck. For example, we will list the two decks where $AB$ are on top; then, we will list the two decks where $AC$ is on top; then the two decks with $AD$ on top. Here is the full list of decks:

$A$ on top	$B$ on top	$C$ on top	$D$ on top
$ABCD$	$BACD$	$CABD$	$DABC$
$ABDC$	$BADC$	$CADB$	$DACB$
$ACBD$	$BCAD$	$CBAD$	$DBAC$
$ACDB$	$BCDA$	$CBDA$	$DBCA$
$ADBC$	$BDAC$	$CDAB$	$DCAB$
$ADCB$	$BDCA$	$CDBA$	$DCBA$

There are $24$ such shuffles.

Another enumeration technique is the “tree diagram.” The tree diagram for all possible shuffles of four cards is pictured below.

We have enough information here to figure out how many shuffles there are of a deck of $52$ cards. However, we need a theorem first.

9.2 Addition and multiplication principles

In combinatorics we count the number of outcomes that lead to an event coming to pass. In the previous example, “a deck of four cards is shuffled” is the event and the outcome $BCDA$ is an outcome. We may phrase this set-theoretically by saying an event is a set and that the outcomes are the elements of that set. So, $BCDA \in \text{A Deck Of Four Cards Is Shuffled}.$

With this in mind we have already seen the addition and multiplication rules for counting!

Theorem 9.2.1 Let $E$ and $F$ be events. Then the event "$E$ or $F$" has $|E \cup F|=|E| + |F| - |E \cap F|$ outcomes and the event "$E$ and $F$" and $|E \times F|=|E|\cdot |F|.$

Example. A particular restaurant sells many varieties of burritos. Of the selections, seven burritos are spicy and six are vegetarian. Two vegetarian burritos are spicy. How many burritos are spicy or vegetarian?

Letting $S$ be the set of spicy burritos and $V$ be the set of vegetarian burritos, we are looking for $|S \cup V| = |S| + |V| - |S \cap V|,$ which is $7+6-2$ or $11$.

Example. How many ways are there to shuffle a deck of 52 cards?

Again we will consider the example of the four card deck $A$, $B$, $C$, and $D$. Some card must go first; there are four such choices. Then a card must go second, for which there are three choices. Then two, then one.

To give an example of how set theory is relevant, we may decompose the set $\text{Deck Is Shuffled}$ into a product of four sets: $\text{Deck Shuffled} = \text{First Card} \times \text{Second Card} \times \text{Third Card} \times \text{Fourth Card},$ where the content of (for instance) $\text{Third Card}$ depends on the choices of the first and second cards.

By the multiplication rule, there are $4 \cdot 3 \cdot 2 \cdot 1$ ways to shuffle this deck. Fortunately for us this is $24$, which was the answer we got last time!

You may have noticed we have done this calculation before. The product $4 \cdot 3 \cdot 2 \cdot 1$ is exactly $4!$. By similar reasoning, there are $52!$ ways to shuffle a deck of standard size: there are $52$ choices for the top card, then $51$ choices for the next card, then (etc.)

In fact the following theorem may be proven by induction.

Theorem 9.2.2 There are $n!$ ways to order a set of $n$ elements. Such an ordering is called a permutation of the set.

The first line of the following proof finally gives some intuition as to why $0!=1$ is a good definition.

Proof. Observe that there is one ordering of the elements of $\varnothing$: the empty ordering $\{ \}$. Since $0!=1$, the statement is true in the base case.

Suppose there are $k!$ permutations of a $k$-element set. Consider then a set with $k+1$ elements. We must choose an element to be first in the permutation; there are $(k+1)$ choices. After doing so we are left to permute the remaining $k$ elements; by the inductive hypothesis there are $k!$ ways to do so. Using the multiplicative principle of counting there must be $(k+1) k! = (k+1)!$ permutations of the $(k+1)$-element set, so the theorem is true by induction. $\square$

To get an idea of how mind-blowingly large factorials can become, check out this article about how long it would take for $52!$ seconds to go by.

Takeaways

• Some basic tools in the combinatorist’s kit are enumeration, addition, and multiplication. Another is correspondence, which will be developed slowly over the course of the chapters. A very exciting fifth tool, called the generating function, will be introduced in Chapter 11.
• Enumeration is not just listing the elements of a set; it is systematically listing them so that the set’s structure may be better understood.
• Addition is used to count elements of “or” events and multiplication to counts elements of “and” events.
• Factorials are big.

Chapter 9 problems