- Elementary discrete mathematics
- 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
- Part 3 videos
- 9. Introduction to combinatorics
- 10. Ordered samples
- 11. Unordered samples
- 12. Multinomial coefficients
- 13. Probability
- PART 4: RELATIONS
- Part 4 videos
- 14. Boolean matrices
- 15. Relations
- 16. Closure and composition
- 17. Equivalence relations
- 18. Partial orders
- EPILOGUE

- 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

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.

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.

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.

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.

– 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.

**Videos:**

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.

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!

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$

*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$.

- 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.

**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.

**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.

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.

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.

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 |

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.

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$

- 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.

**Videos:**

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

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.

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.)

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$

- 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.

**Review:**

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

**Videos:**

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.

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.

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$

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.

- 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.)

**Videos:**

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.

**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.

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.

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}$ |

- 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.

**Videos:**

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

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