Section 0.1 What is Discrete Mathematics?
dis·crete / dis’krët.
Adjective: Individually separate and distinct.
Synonyms: separate - detached - distinct - abstract.
Defining discrete mathematics is hard because defining mathematics is hard. What is mathematics? The study of numbers? In part yes, but you also study functions and lines and triangles and parallelepipeds and vectors and …. Or perhaps you want to say that mathematics is a collection of tools that allow you to solve problems. What sort of problems? Well, those that involve numbers, functions, lines, triangles, …. Whatever your conception of what mathematics is, try applying the concept of “discrete” to it, as defined above. Some math fundamentally deals with stuff that is individually separate and distinct.
In an algebra or calculus class, you might have found a particular set of numbers (perhaps they constitute the range of a function). You would represent this set as an interval: \([0,\infty)\) is the range of \(f(x) = x^2\) since the set of outputs of the function are all real numbers 0 and greater. This set of numbers is NOT discrete. The numbers in the set are not separated by much at all. In fact, take any two numbers in the set and there are infinitely many more between them that are also in the set.
Discrete math could still ask about the range of a function, but the set would not be an interval. Consider the function that gives the number of children of each person reading this. What is the range? I’m guessing it is something like \(\{0, 1, 2, 3, 4\}\text{.}\) Maybe 5 or 6 is in there too. But certainly nobody reading this has 1.32419 children. This output set is discrete because the elements are separate. The inputs to the function also form a discrete set because each input is an individual person.
There are many discrete mathematical objects besides sets of numbers; we will introduce some of these in
Section 0.2. Studying these discrete
structures is the main focus of discrete mathematics and this book. However, the reason we want to study these structures is because they provide a way to model “real-world” problems.
To get a feel for the subject, let’s consider the types of problems you solve in discrete math. Here are a few simple examples:
Investigate!
Note: Throughout the book you will see Investigate! activities like this one. Answer the questions in these as best you can to give yourself a feel for what is coming next.
The most popular mathematician in the world is throwing a party for all of his friends. To kick things off, they decide that everyone should shake hands. Assuming all 10 people at the party each shake hands with every other person (but not themselves, obviously) exactly once, how many handshakes take place?
At the warm-up event for Oscar’s All-Star Hot Dog Eating Contest, Al ate one hot dog. Bob then showed him up by eating three hot dogs. Not to be outdone, Carl ate five. This continued with each contestant eating two more hot dogs than the previous contestant. How many hot dogs did Zeno (the 26th and final contestant) eat? How many hot dogs were eaten in total?
-
After excavating for weeks, you finally arrive at the burial chamber. The room is empty except for two large chests. On each is carved a message (strangely in English):
Exactly one of these chests contains a treasure, while the other is filled with deadly immortal scorpions.
For either chest, if the chest’s message is true, then the chest contains treasure.
The problem is, you don’t know whether the messages are true or false. What do you do?
Back in the days of yore, five small towns decided they wanted to build roads directly connecting each pair of towns. While the towns had plenty of money to build roads as long and as winding as they wished, it was very important that the roads not intersect with each other (as stop signs had not yet been invented). Also, tunnels and bridges were not allowed, for moral reasons. Is it possible for each of these towns to build a road to each of the four other towns without creating any intersections?
As you consider the problems above, don’t worry if it is not obvious to you what the solutions are. We are more interested here in what sort of information we need to be able to answer the questions. How can we represent the situation using individually separate and distinct objects? Don’t read on until you have thought about at least this for each of the questions.
Ready? Here are some things you might have thought about:
-
The people at the party are individuals. We can consider the set of people. We can also consider sets of pairs of people, since it takes exactly two people to shake hands. So the question is really about, how many pairs can you make using elements from a 10-element set?
For example, if there were three people at the party, conveniently named \(1\text{,}\) \(2\text{,}\) and \(3\text{,}\) then the pairs would be \((1,2)\text{,}\) \((1,3)\text{,}\) and \((2,3)\text{.}\) Or should we include \((2,1)\text{,}\) \((3,1)\text{,}\) and \((3,2)\) as well?
-
To count the number of hot dogs eaten, either by an individual or in total, we could use a sequence of integers (whole numbers). The \(n\)th term in the sequence might represent the number of hot dogs eaten by the \(n\)th contestant. We can consider a second sequence, also of integers, that gives the total number of hot dogs eaten by the first \(n\) contestants combined.
The solution to the problem will then be the value of the 26th term in the sequence. To help us find this, we could consider the rate of growth of the sequences, as well as how these two sequences relate to each other.
Logic questions also belong under the discrete math umbrella: each statement can have a value of True or False (and there is nothing in-between). To answer questions like that of the chests of scorpions, we must understand the structure of the statements, and how the truth values of the parts of the statements interact to determine the truth value of the whole statement.
The last question is about a discrete structure called a graph, not to be confused with a graph of a function or set of points. We can use a graph to represent which elements of a set (or towns) are related to each other (or connected by a road). In this case, the question becomes, can we draw a graph with five vertices (towns) and ten edges (roads) such that no two edges intersect?
The four problems above illustrate the four main topics of this book: combinatorics (the theory of ways things combine; in particular, how to count these ways), sequences, symbolic logic, and graph theory. However, there are other topics that are also considered part of discrete mathematics, including computer science, abstract algebra, number theory, game theory, probability, and geometry (some of these, particularly the last two, have both discrete and non-discrete variants).
Ultimately the best way to learn what discrete math is about is to do it. Let’s get started! Before we can begin answering more complicated (and fun) problems, we will consider a very brief overview of the types of discrete structures we will be using.
Reading Questions Reading Questions
Each section of the book will end with a small number of Reading Questions like the ones below. These are designed to help you reflect on what you have read. In particular, the final reading question asks you to ask a question of your own. Thinking about what you don’t yet know is a wonderful way to further your understanding of what you do.
1.
Right now, how would you describe what discrete mathematics is about, if you were telling your friends about the class you are in? Write one or two sentences.
2.
What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.
