Discrete Structures

# What Is Discrete Math?

 Last Update: 29 June 2013 Note: or material is highlighted

1. "Discrete Math" is not the name of a branch of mathematics, like number theory, algebra, calculus, etc.

Rather, it's a description of a set of branches of math that all have in common the feature that they are "discrete" rather than "continuous".

2. The members of this set include (certain aspects of):

• logic and Boolean algebra
• set theory
• relations and functions
• sequences and series (or "sums")
• algorithms and theory of computation
• number theory
• matrix theory
• induction and recursion
• counting and discrete probability
• graph theory (including trees)

3. To get a feel for what "discrete" means, here are some rough definitions that you might find useful:

1. A set is countable =def its members can be put into a 1-1 correspondence with the positive natural numbers (i.e., 1,2,3,…);
i.e., a set is countable iff its members can be counted.

• Note that the following sets are all countable:

1. W: the positive natural numbers themselves! (1,2,3…)
2. N: the natural numbers (0,1,2,3…)
3. Z: the integers (…–3,–2,–1,0,1,2,3…)
4. Q: the rational numbers (i.e., fractions, or repeating decimals)

• However, R, the real numbers (i.e., the rationals plus all the non-repeating decimals, such as π, e, √2, etc.), is not countable!

• So, one feature of being "discrete" is that discrete objects are countable.

• The study of the reals is not part of discrete math.
• But the study of how to represent reals by approximations, as computers do, could be considered part of discrete math).

2. A set is dense =def:

1. it is "totally" (or "linearly") ordered
(i.e., any two members of the set are comparable in terms of an ordering, such as a less-than relation)

and

2. for any 2 members of the set, there is a third member that is between them.

• Roughly, a totally-ordered set is dense iff, no matter how close two members are, you can always find another member squeezed in between them.

• E.g., the reals and the rationals are dense.

• However, the rational number line has "gaps":

• No matter how closely you find two rationals "squeezed" together, you'll never find π.
• You can approximate π as closely as you want (because the rationals are dense), but you'll never "hit" π.

• But the integers are not dense.

• Some people consider that the study of dense sets is not part of discrete math

3. A set is continuous =def (and this is a very rough definition!!)

1. it is dense

and

2. it has no "gaps".

• So…
• The real number line is continuous.
• It is sometimes called "the continuum" (pronounced /con-tin-you-um/).
• In fact, some mathematicians define a continuous set as just the real numbers.

• There are lots of formal ways to define the continuum; here's one:

A totally-ordered set is continuous =def any nonempty subset that has an upper bound also has a least upper bound.

Here's what this means:

Consider the real number line.
Locate π on it.
Now consider the set of all numbers ≤ π.
Some upper bounds of this set are: π, 3.1415926536, 3.15, 3.2, 4, 4.1, 4.10938571023987, etc.
However, the smallest (i.e., the "least") of these upper bounds is π.
If we had been considering the subset of rationals that are ≤ π,
then π would not be a member of this subset (because it's not a rational).
But if the subset is continuous, then π is a member.

I.e., continuous sets have no gaps.

• The reals are not countable.

• The study of continuous sets is not part of discrete math.

4. The above can be summarized in a chart:

Set Name Members Has gaps? Countable? Dense? Continuous? Discrete?
Wpositive naturals1,2,3…yesyesno no yes
Nnaturals 0,1,2,3…yesyesno no yes
Zintegers…–3,–2,–1,0,1,2,3…yesyesno no yes
Qrationalsfractions/repeating decimalsyesyesyesno ???
Rrealsall decimals, including non-repeatingno no yesyesno

From this, we can see that W, N, and Z are clearly "discrete" and that R is clearly not discrete.

But Q stands somewhere in the middle:

• It is countable and "gappy", but also dense.

5. There are some intuitive ways of thinking about the discrete-vs.-continuous distinction:

1. A piano makes music in a "discrete" way:
On a piano, there is no note between C and C#.

But a violin makes music in a "continuous" way:
There are (in theory at least) a continuum of notes between C and C#.

2. An analog clock (i.e., a clock with hands) is (at least in theory) continuous:
The set of times that it can show is not only dense, but it can even tell you when it is π o'clock!

But a digital clock is discrete:
In a typical digital clock, there is no time between 3:14 PM and 3:15 PM.

• Here is an interesting comment on the trade-off between the discrete and the continuous (also called "analog[ue]"):

• "A distinction is sometimes made between digital and analogical signs. Indeed, Anthony Wilden declares that ‘no two categories, and no two kinds of experience are more fundamental in human life and thought than continuity and discontinuity’ (Wilden 1987, 222). Whilst we experience time as a continuum, we may represent it in either analogue or digital form. A watch with an analogue display (with hour, minute and second hands) has the advantage of dividing an hour up like a cake (so that, in a lecture, for instance, we can ‘see’ how much time is left). A watch with a digital display (displaying the current time as a changing number) has the advantage of precision, so that we can easily see exactly what time it is ‘now’." (Chandler, Daniel (2009), Semiotics for Beginners, "Signs".)

3. Discrete math concerns sets of objects that are countable.
Continuous math concerns sets of objects that are "measurable".

4. A film, with "frames", is discrete.
The real events depicted on the film are continuous.

6. To find other explanations, do a Google search on "discrete math", "discrete vs. continuous", and "discrete math vs. continuous".

The following are especially good:

1. Introduction—Continuous vs. Discrete Data
• An illustration of the film analogy mentioned above.
3. Discrete Mathematics—from Wolfram MathWorld
4. Continuous vs. Discrete Mathematics:

• In case the above link disappears again, here's what it says:

"Continuous vs. Discrete Mathematics

The world of mathematics can be divided roughly into two realms: the continuous and the discrete. The difference is nicely illustrated by wristwatches. Continuous mathematics corresponds to analog watches - the kind with separate hour, minute, and second hands. The hands move smoothly over time. From an analog watch perspective, between 12:02 P.m. and 12:03 P.m. there are infinitely many possible different times as the second hand sweeps around the watch face. Continuous mathematics studies concepts that are infinite in scope, where one object can blend smoothly into the next. The real-number system lies at the core of continuous mathematics and - just like the watch - between any two real numbers, there is an infinity of real numbers. Continuous mathematics provides excellent models and tools for analysing real-world phenomena that change smoothly over time, including the motion of planets around the sun or the flow of blood through the body.

Discrete mathematics, on the other hand, is comparable to a digital watch. On a digital watch, there are only finitely many possible different times between 12:02 P.m. and 12:03 P.m. A digital watch does not acknowledge split seconds! There is no time between 12:02:03 and 12:02:04. The watch leaps from one time to the next. A digital watch can show only finitely many different times, and the transition from one time to the next is sharp and unambiguous. Just as the real-number system plays a central role in continuous mathematics, integers are the primary tool of discrete mathematics. Discrete mathematics provides excellent models and tools for analysing real-world phenomena that change abruptly and that lie clearly in one state or another. Discrete mathematics is the tool of choice in a host of applications, from computers to telephone call routing and from personnel assignments to genetics.

Edward R. Scheinerman, Mathematics, A Discrete Introduction (Brooks/Cole, Pacific Grove, CA, 2000): xvii–xviii."

5. On the differences between discrete/digital and analog, see:

6. Bell, John L. (2005), The Continuous and the Infinitesimal in Mathematics and Philosophy

• See especially Chapter 1: "The Continuous and the Discrete in Ancient Greece, the Orient, and the European Middle Ages"

7. Bell, John L. (2005), "Oppositions and Paradoxes in Mathematics and Philosophy", Axiomathes 15: 165–180.

• Just read pp. 1–16 of the online version.

8. Tong, David (2012), "The Unquantum Quantum", Scientific American 307(6) (December): 46–49.

• "Quantum theorists often speak of the world as being pointillist [i.e., discrete] ast the smallest scales. Yet a closer look at the laws of nature suggests that the physical world is actually continuous—more analog than digital." 