A question about “Discrete Mathematics” and “Countability”

In the mathematical literature, discrete mathematics has been characterized as the branch of mathematics dealing with “Countable Sets”. On the other hand, it is well-known that “discreteness” and “countability” are two different mathematical concepts.

Now, one may ask why “discrete” mathematics is defined on the basis of “countable” sets?




Where have you seen this definition of discrete math? Personally I think it’s only somewhat correct.
– Noah Schweber
2 days ago



@Noah Schweber Many references, for example: Biggs, Norman L. (2002), “Discrete mathematics”, Oxford Science Publications (2nd ed.), New York.
– user.3710634
2 days ago


2 Answers


I think we shouldn’t stick too closely at the mathematical definitions of the terms discreteness and countability in order to grasp what the discipline discrete mathematics constitutes. The discipline is broad and comprises both terms discreteness as well as countability.

Here are some examples which provides some information regarding characterisation of discrete mathematics. In fact they show that discrete and countable are central to discrete mathematics opposite to continuous and uncountable.

We can read in chapter I Introduction of

Discrete Mathematics: Elementary and Beyond by L. Lovأ،cz, J. Pelikأ،n and K. Vesztergombi

… There are many success stories of applied mathematics outside calculus. A recent hot topic is mathematical cryptography, which is based on number theory (the study of positive integers, 1,2,3,…1,2,3,…1,2,3,\ldots), and is widely applied, among others in computer security and electronic banking. Other important areas in applied mathematics include linear programming, coding theory, theory of computing.

The mathematics in these applications is collectively called discrete mathematics. (Discrete here is used as the opposite of continuous; it is also often used in the more restrictive sense of finite.) …

There is a famous book with a title containing a made-up word which directly addresses the connection of discrete versus continuous, called

Concrete Mathematics: A Foundation for Computer Science by R.L. Graham, D.E. Knuth and O. Patashnik

… But what exactly is Concrete Mathematics? It is a blend of CONtinuous and disCRETE mathematics…

Here are some text examples pointing to continuous on the one hand versus discrete on the other hand

… People who have been raised on calculus instead of discrete mathematics tend to be more familiar with ∫\int than with ∑\sum …
… when xx is an integer, and f(x)=11+12+⋯+1xf(x)=\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{x} is just the harmonic number HxH_x … Thus HxH_x is the discrete analog of the continuous lnx\ln x.

We can also read at the beginning of chapter 33 something about countable sets resp. structures.

… WHOLE NUMBERS constitute the backbone of discrete mathematics, and we often need to convert from fractions or arbitrary real numbers to integers.

So, when considering structures in discrete mathematics, we are talking about integers, which are a countable set opposite to continuous mathematics, where uncountable sets as R,C\mathbb{R}, \mathbb{C}, etc. are the backbone of continuous mathematics.

There is a well known classic Enumerativ Combinatorics written by one of the authors of the following book. Here we can find another interesting characterisation of discrete mathematics.

A combinatorial miscellany by A. Bjأ¶rner and R.P. Stanley

… In mathematics the words continuous and discrete have technical meanings that are quite opposite.

Typical examples of continuous objects are curves and surfaces in ordinary 33-dimensional space (or suitable generalizations in
higher dimensions). A characteristic property is that each point on such an object is surrounded by some neighborhood of other points, containing points that are in a suitable sense near to it. The area within mathematics that deals with the study of continuity is called topology.

The characteristic property of discrete objects, on the other hand, is that each point is isolated — there is
no concept of points being near.

Combinatorics is the area that deals with discreteness in its purest form, particularly in the study of finite structures of various kinds…

Finally another classic of discrete mathematics. We can read in section I.1 Symbolic enumeration methods a short characteristic of discrete objects:

Analytic Combinatorics by P. Flajolet and R. Sedgewick

… First and foremost, combinatorics deals with discrete objects, that is, objects that can be finitely described by construction rules.

… Examples are words, trees, graphs, permutations, allocations, functions from a finite set into itself, … A major question is to enumerate such objects according to some characteristic parameter(s).



Thank you for nice explanation!
– user.3710634
4 hours ago



@user.3710634: You’re welcome! 🙂
– Markus Scheuer
4 hours ago

This is at most a partial answer.

Definition: A probability measure PP is discrete if and only if there is some set SS for which ∑s∈SP({s})=1.\sum_{s\in S} P(\{s\}) = 1.
Proposition: A probability measure is discrete if and only if its range (not quite the same thing as its support) is finite or countably infinite.

Some books take the latter characterization to be the definition, but in my opinion that is a definition by non-essentials.

The equivalence of the two typographically bulleted statements may be viewed by some as partially justifying the identification of “discrete” with “countable”.

(The difference between “range” and “support” is that the range of a discrete probability distribution PP is the set {s:P({s})>0}\{s : P(\{s\}) > 0\}, and the support is the set {s:For every open neighborhood G of s (no matter how small), we have P(G)>0.}.\{ s : \text{For every open neighborhood } G \text{ of } s \text{ (no matter how small), we have } P(G)>0.\}. Thus for example, if each of the points 1, 1/2, 1/3,…, 1/n,…1,\ 1/2,\ 1/3, \ldots,\ 1/n, \ldots gets positive probability, then 00 is in the support but not in the range. The support is always a closed set. If positive probability is assigned to every rational number between 00 and 11, then the support is the uncountable set [0,1][0,1], but the range is still countable and the distribution is discrete.)



The Definition and the Proposition aren’t supposed to go together, are they? What about a probability measure such that P({s})=0P(\{s\})=0 for every point s,s, while the range of PP is {0,1}?\{0,1\}? I.e. an Ulam measure.
– bof
5 hours ago