Discrete Mathematics: An Open Introduction, 4th edition

We are taking a problem-solving approach to discrete mathematics: we will consider a large variety of questions that have a discrete feel to them, and consider how to answer those questions (and prove that our answers are correct). This is not the only way to study discrete math. Another approach would be to study the tools used to solve the problems. If we were art students, we could study paintbrushes and easels and the composition of paint, which would be interesting for sure, but I think it is more enjoyable to actually paint those happy little trees.

That said, understanding your tools does help you use them, so in this section, we will consider some basic tools used in discrete mathematics. We will come back to these throughout our studies and understand them better as we need to.

The tools in our subject are called discrete structures. They are the mathematical objects that we use to represent parts of the problems we are solving. “Structure” is a good word here, since these “things” have fairly rigid constraints that make them what they are, just like an apartment building is going to have different characteristics than an airplane hangar or a suspension bridge (these types of physical structures, not mathematical structures, just to be overly clear and destroy the metaphor).

The structures we will use most in discrete math are sets, functions, sequences, relations, and graphs. We now briefly preview each of these. As we progress through our studies, each will be explored in more detail.

A set is an unordered collection of elements. This is fairly vague, but unless we want to spend a whole book trying to understand sets more precisely, it will be good enough for us. It is possible to define all of mathematics using just sets (even numbers can be thought of as sets themselves), but this is also not what we will do. Rather, we want to be able to talk about collections of numbers and other objects, and we will collect them in something we call a set.

We can describe sets by saying exactly what elements are members of the set. We could specify this membership in words (e.g., Let \(A\) be the set of all natural numbers less than 10), or by explicitly listing all the elements (e.g., \(A = \{3, 5, 7\}\)), or using something called set comprehension (also called set builder notation). An example of this is \(A = \{x \in \N \st x \lt 10\}\text{.}\) We would read that as “\(A\) is the set of natural numbers that satisfy the property that they are less than 10.” More precisely, the \(\N\) symbol represents the natural numbers, which is itself a set: \(\N = \{0, 1, 2, 3, \ldots\}\) (this shows another way to describe a set). The \(\in\) symbol means “is an element of”. The \(\st\) is read “such that” and tells us that what comes next is the condition that must be true of the set’s elements.

There are lots of things you can do with sets, which we will consider in more detail as we need to. We will see that it is often helpful to build new sets from ones we already have (by taking the union or intersection of sets, for example), to compare sets (asking if one set is a subset of another), and to find the number of elements of a set (called its cardinality). We might also want to match up elements of one set with another: to do this, we might use a function, which we will discuss next. Awesomely, we can also use sets themselves to describe functions. Let’s check it out.

One way to define a function is as a rule that assigns each input exactly one output. The output is called the image of the input. Functions also come equipped with a domain, the set of all inputs, and codomain, the set of all allowable outputs. You might also speak of the range of the function, which is the set of all actual outputs, or put another way, the set of all images of elements from the domain.

We write \(f:X \to Y\) to describe a function with name \(f\text{,}\) domain \(X\) and codomain \(Y\text{.}\) This does not tell us which function \(f\) is though. To define the function, we must describe the rule. Often this is done with a formula (for example, \(f(x) = x^2\) says that each element of the domain is mapped to its square), or in words (like how we just described the squaring function). We could also define a function with a table or a graph.

The key thing that makes a rule a function is that there is exactly one output for each input. That is, the rule must be a good rule. What output do we assign to the input 7? There can only be one answer for any particular function.

Since a function maps one set (the domain) to another set (the codomain), there is an obvious connection between sets and functions. There is another connection worth considering though: the graph of a function is often described as a set of points. Here is an example.

Of course, we are using a mathematical object here: an ordered pair. This is not a set (since sets are unordered). How should we talk about ordered things? We will take this question up in the next section.

There is one more important consideration about how we define a function with a rule. A closed formula is one in which each output is given by an explicit rule based solely on its input. This is what most of us think of as a formula. For example, \(f(n) = 3n + 1\) is a closed formula, since to find \(f(5)\) (say) we take the input 5 and do something to it: multiply it by 5 and then add 1.

What else could a formula possibly be? A recursive definition of a function tells us how to compute the output for a given input based on other outputs of the function. For example, we might insist that \(f(n) = 2\cdot f(n-1)\text{.}\) If we also specify an initial condition that \(f(0) = 3\text{,}\) then we can find \(f(1) = 2\cdot 3 = 6\text{,}\) and then \(f(2) = 2\cdot 6 = 12\text{,}\) and so on. What is \(f(5)\) here? The only way to answer that is to find \(f(4)\text{,}\) which means we need to find \(f(3)\text{,}\) which we could do, since we have computed \(f(2)\text{.}\)

Recursive definitions of functions might be less useful for finding a particular output, but they are often easier to specify for a particular application. We will explore this phenomenon more when we study sequences. Speaking of which...

Sometimes we are interested not just in a collection of numbers, but in what order those numbers appear. In such cases, we cannot use sets, since they do not distinguish between the order of their elements. Instead, we consider sequences.

We will consider both finite and infinite sequences. A finite sequence may be something as simple as \((1,2,3)\text{;}\) that is a sequence with 3 elements, in that particular order. We might also call this an ordered triple, the same way that \((7,3)\) is an ordered pair. In general, we could call this an \(n\)-tuple if it has \(n\) elements (we assume that tuples are ordered).

The key difference between the sequence \((1,2,3)\) and the set \(\{1,2,3\}\) is that we “care” about the order. That is, the sequence \((1,2,3)\) is different from the sequence \((2,3,1)\text{,}\) while the set \(\{1,2,3\}\) is identical to \(\{2,3,1\}\text{.}\)

We will often use sequences as a counting tool. For example, a very simple counting question is, “how many wheels do 100 cars have?” Instead of answering just this one question, we could generalize and ask how many wheels \(n\) cars have, and get a sequence of answers. This yields the infinite sequence \((4, 8, 12, \ldots )\text{.}\) The order these multiples of 4 appear in is important, since each number in the sequence corresponds to a specific version of the question.

If we want to be a little more precise and more abstract, we can think of a sequence as a function. The domain is the natural numbers or some subset of consecutive natural numbers (like \(\{1,2,3,4\}\)). The codomain is some set. We think of the domain as the positions in the sequence, and the image of those inputs as the terms in the sequence.

For example, we might consider the Fibonacci sequence \((f_n)_{n\ge 1}\text{,}\) which starts \(1, 1, 2, 3, 5, 8,\ldots\text{.}\) What is the 4th term in the sequence? We might say \(f_4 = 3\) (this is assuming the first 1 is the first term and not the 0th term). Note that there can only be one 4th term. There can only be one \(n\)-th term for any particular value of \(n\text{.}\) So for any input (the position of the term), there is only one output (the term). It would be perfectly reasonable to write \(f(4) = 3\text{,}\) and that really does look like a function. But we like to use subscripts.

We can also describe the terms in a sequence using a table. We might write something like the following:

This looks exactly like how you would represent a function, even though this table describes the sequence of triangular numbers (we will see why they are called this later).

Much of our effort in understanding sequences will go into taking a recursive definition and finding a closed formula for the sequence. We will study this, and everything else sequence related in Chapter 4.

How are the numbers \(2\) and \(6\) related? Oh, I know: \(2 \lt 6\text{.}\) Also, \(6\) is a multiple of \(2\text{.}\) The two numbers are also both even. And here is another fact: they are not equal. All four of these are examples of relations: less than, multiple of, both even, not equal. And there are many more (infinitely many) relations that might or might not hold of a pair of two numbers.

The examples above are all binary relations in that they relate two elements. You could also consider relations between more than two elements. For example, we could consider the relation “Pythagorean triple” that holds of three numbers precisely if they are the side lengths of a right triangle. So the relation is true of the triple \((3,4,5)\text{,}\) but not of \((4,5,6)\) (since \(3^2 + 4^2 = 5^2\) but \(4^2 + 5^2 \ne 6^2\)).

Notice that we can talk about a pair or triple satisfying a relation. We might say that a pair belongs to the relation. The careful and formal way to define a relation is as a set of ordered pairs (or triples, etc.). Consider the (infinite) set of all ordered pairs \((a,b)\) such that \(a \lt b\text{.}\) Every element of this set contains numbers for which the relation “less than” is true, and every pair of numbers for which the relation is true is a pair in the set. So we can say that this set of pairs is the relation.

Relations can have some standard properties, and deciding whether a particular relation has a given property can often help us understand the relation better. The less-than relation is, for example, irreflexive because there are no elements that are less than themselves. It is also antisymmetric since there are no distinct numbers \(a\) and \(b\) such that \(a \lt b\) and \(b \lt a\text{.}\) It is also transitive since if \(a \lt b\) and \(b \lt c\) then it must follow that \(a \lt c\text{.}\) These are just a few examples of relation properties though.

Why would we care about these properties? It turns out that some groups of properties happen together frequently, and for such collections of properties, we can prove general results about the relations that satisfy them. So if we can prove that a given relation is reflexive, symmetric, and transitive (whatever those mean), then we know the relation is an equivalence relation, and therefore we know it has a bunch of other properties. A large portion of discrete mathematics is about studying particular types of relations. One of my favorites is a relation that gives us a graph.

Consider the set \(V = \{1, 2, 3, 4, 5, 6\}\text{.}\) Which pairs of numbers from that set add up to 7? We could have \(\{1,6\}\) or \(\{2, 5\}\) or \(\{3,4\}\text{.}\) We can picture the set and the interesting (unordered) pairs (i.e., two-element subsets) as a picture called a graph:

On the other hand, we might want to consider pairs of numbers whose sum is even. Then, we would get the following picture.

We call these discrete structures graphs. A graph is a type of relation, one that is symmetric (if \(a\) is related to \(b\text{,}\) then \(b\) is related to \(a\)) and irreflexive (no element is related to itself).

However, we mostly think of graphs as the drawings of dots and lines, or more precisely as a set of vertices together with a set of edges, where each edge is a two-element subset of the vertices. Notice that even here, we are using the structure set to define the structure graph.

Graphs show up in all sorts of real-world applications: in a class, some students are friends with each other, so take the students to be the vertices and the edges to be the friendships. In geography, some countries share a border, so take the countries to be the vertices and connect a pair of vertices with an edge if the countries share a border. Perhaps you are planning a trip and want to fly from Denver to Paris. Is there a direct flight, or must you stop in Newark? That is, does the graph of flights have an edge between Denver and Paris or only between Denver and Newark and between Newark and Paris? When your Amazon driver delivers packages to 10 houses in your neighborhood, how does her app know in which order to deliver the packages? Graph theory!

The study of graphs is a subject in its own right, in which many mathematicians hold doctorate degrees and write hundreds of papers each year. We will scratch the surface of this fascinating subject in Chapter 2

Our list of structures could go on and on, but we will stop here. We will spend just a little time looking at multisets, which are just like sets except can have repeated elements. Since this is not a geometry class, we will not consider finite geometries, or designs (which are somewhere between graphs and geometries). Discrete structures are useful in computer science, but we will stop short of studying linked lists or red-black trees. Although abstract algebra is a fascinating subject, we will not get to groups or rings or metroids or POSets or Boolean algebras or ... These are examples of sets on which we define additional operations and study the algebraic structure of how the sets and operations interact.

The point is, discrete mathematics is awesome and you can spend multiple lifetimes studying it. So what are we waiting for? Let’s dive in and solve some problems.