What Is Discrete Math?

Last Update: 29 June 2013

Note: or material is highlighted

"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".
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)
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:
    Here's what this means:
  - The reals are not countable.
  - The study of continuous sets is not part of discrete math.

The above can be summarized in a chart:

Set	Name	Members	Has gaps?	Countable?	Dense?	Continuous?	Discrete?
W	positive naturals	1,2,3…	yes	yes	no	no	yes
N	naturals	0,1,2,3…	yes	yes	no	no	yes
Z	integers	…–3,–2,–1,0,1,2,3…	yes	yes	no	no	yes
Q	rationals	fractions/repeating decimals	yes	yes	yes	no	???
R	reals	all decimals, including non-repeating	no	no	yes	yes	no

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.

There are some intuitive ways of thinking about the discrete-vs.-continuous distinction:
1. A piano makes music in a "discrete" way:
  But a violin makes music in a "continuous" way:
2. An analog clock (i.e., a clock with hands) is (at least in theory) continuous:
  But a digital clock is discrete:
  - 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.
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.
2. Math Forum—Ask Dr. Math
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:
  - Haugeland, John (1981), "Analog and Analog", Philosophical Topics 12(1) (Spring): 213–225.
  - Maley, Corey J. (2011), "Analog and Digital, Continuous and Discrete", Philosophical Studies 155: 117–131 [DOI 10.1007/s11098-010-9562-8].
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."