14
$\begingroup$

I am studying computer science and this has me absolutely flummoxed. The definition I can find is that discrete data is countable and that continuous is uncountable.

Examples are given stating that integers are discrete, and real numbers are continuous. Rationals it states are controversial.

I understand topics that fall within the category of discrete mathematics, I don't get why they do. Especially set theory, what if my universal set is the real numbers? How can I have a continuous realm of values and consider my structure to be discrete?

Considering both integers and reals belong to an unlimited realm of possibilities, I fail to see how either one is considered countable; they are both infinite. How would you define discrete mathematics and how would someone recognize discrete or continuous mathematics when faced with it?

Note: My knowledge of mathematics is discrete and very limited so please explain this as you would to a 6 year old.

$\endgroup$
5
  • $\begingroup$ I'm not sure I understand your question...you don't get why integers and rational numbers are countable? Is that the problem? $\endgroup$ Commented Jan 31, 2014 at 14:33
  • $\begingroup$ @Zado I don't get what defines something as discrete. Discrete was defined to me as countable, it still doesn't make sense. The integers 1->10 are clearly countable, there is 10 of them. The integers are not countable as far as I'm concerned, there are an infinite number of them. Why are they considered discrete? $\endgroup$ Commented Jan 31, 2014 at 14:36
  • $\begingroup$ The integers and rational numbers are countable! Everything that has a bijection with the natural numbers is considered countable (en.wikipedia.org/wiki/Countable). I wouldn't consider rational numbers as discrete though, as they are dense over the real numbers. However, on further though I must say I've never heard a formal definition of discrete... $\endgroup$ Commented Jan 31, 2014 at 14:43
  • 1
    $\begingroup$ The difference between discrete and non-discrete mathematics is much more than considering countable and uncountable sets or anything within that realm. And that could be a reason why the OP is confused to begin with $\endgroup$ Commented Jan 31, 2014 at 14:53
  • $\begingroup$ @Zado I was using reals in my example, my source correctly identifies rationals as countable but doesn't know if they are discrete. The only definition of discrete I can find is non-continuous, which just seems like circular logic to me. $\endgroup$ Commented Jan 31, 2014 at 14:57

5 Answers 5

Reset to default
5
$\begingroup$

The difference between countable and uncountable sets is well formalized and there is never any doubt. These are two different "sizes of infinity". You can read this page for more information on why countable is not the same as uncountable: http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

But I think one intuition which is really helpful, and also linking this with computer science, is the fact that a countable set is a set whose elements are finitely describable. For instance each integer can be written on a piece of paper, so the set of integers is countable. This makes integers manageable by computers: since you can completely describe an integer in a finite way, you can always pass it to a computer, as a finite sequence of $0$'s and $1$'s. This is also why reals are not countable: you might need to write down all the decimals, that is an infinite sequence. This makes "continuous mathematics" not well-suited for automatic treatment by computers.

Of course this is very schematic and can be further detailed, but this intuition is very important. It is possible to formally prove: "every element of $E$ contains a finite amount of information $\implies$ $E$ is countable".

Following this intuition, rationals are countable, because a rational $r$ can be given by two integers $a,b$ with $r=a/b$. This does not prevent rationals to be an important tool of analysis, because reals can be approached by rationals arbitrarily close (we say $\mathbb Q$ is $dense$ in $\mathbb R$). But most computer algorithms dealing with "arbitrary" numbers actually deal with only rational numbers.

As for the classification of maths into "discrete" and "continuous", the frontiers are really not well-defined, and everything interacts with everything else, so it is almost impossible to give a sound definition. A big part of it is subjective. At best, you have a "flavour" in some fields that is mostly discrete (like graph theory) or continuous (analysis), but in both cases, you might need also to consider the other side in order to get a good understanding (like using probability theory in graph theory).

$\endgroup$
9
  • $\begingroup$ Interesting, this helped me understand countable. In other words a range is not countable if it's members themselves are infinite, however an infinite range consisting of finite members is countable. $\endgroup$ Commented Jan 31, 2014 at 15:39
  • $\begingroup$ @GeorgeReith: I realise this question is old, and you probably know this by now, but the distinction you try to draw here is false. The real numbers are uncountable, but each individual real number is finite. I just wanted to mention this for the sake of posterity. There is still something to say though: Each rational number can be written as a finite decimal (finite 'information'), but there exist (irrational) real numbers that cannot be written as finite decimals - any decimal representation is (countably) infinitely long (infinite 'information'). $\endgroup$ Commented Jul 23, 2016 at 10:34
  • 1
    $\begingroup$ @WillR Thanks for weighing in I had forgotten about this and probably don't understand it as well as I should. What I meant at the time was that there are an infinite amount of numbers between each integer but looking back with a slightly better understanding I think what you mean and please correct me if I'm wrong is that it is continuous if there is no finite number representation e.g., 1/3 is infinite in base 10 but has a finite representation (therefore discrete), whereas pi doesn't apart from an arbitrary symbol. So real numbers are continuous because they contain numbers like pi. $\endgroup$ Commented Jul 24, 2016 at 21:19
  • $\begingroup$ @GeorgeReith: Good point, my previous comment was poorly worded and failed to take recurring decimals into account. As others have said, there is no hard and fast rule, but what you've said is probably a decent rule of thumb in my opinion. An interesting thing to reflect on is this: Every rational number is finitely long in some integer base, but every irrational number is infinitely long in every integer base. Again, checking to see if a number is irrational requires an infinite amount of information, in principle. $\endgroup$ Commented Jul 25, 2016 at 9:37
  • $\begingroup$ Isn't the set of algebraic numbers countable? It contains many irrationals. Are we saying that $\sqrt{2}$ is ok since I can write it with this finite set of symbols but something like $\ln 2$ is not? $\endgroup$ Commented Feb 1, 2024 at 3:30
3
$\begingroup$

To address two of the questions raised:

1. What is a discrete set and how is this related to discrete mathematics?

Discrete sets consist entirely of isolated points, i.e. sets for which one can find a small enough neighborhood so that only one point of the set is contained in it -- the intuition is that the points are spread apart with a minimum distance between points.

Discrete mathematics is that which is done using finite methods typically using just the integers (e.g. combinatorics, elementary number theory) or at most a finite subset of the rationals, (e.g. discrete probability theory).

2. Are the rationals a discrete set?

No, the rationals are not a discrete set even though they are countably infinite. This is because the rationals have no isolated points---you can always find a nearby rational number as close as you like. This is called the Archimedean property of the rationals, and you can see it by asking for any tiny fraction, say 1/100,000, can I find a smaller one? Sure: 1/100,000,000. So there is no neighborhood that you can put around a rational point that you could not find another rational within.

However, any finite collection of rational numbers is discrete since when you only have finitely many rationals, then there is a minimum distance between any two rationals in the set, so one can find an interval smaller than this which will guarantee only one rational is in it at any given time. This means a finite set of rationals is an isolated set, and therefore discrete.

$\endgroup$
0
$\begingroup$

Admittedly, the distinction is not always clear cut. Various fields in mathematics tend to overlap so much that it is difficult to say "this is algebra" vs. "this is topology" (or whatever). The subconscious distinction largely develops because of the techniques one uses and their "feel."

For instance, it is said that analysis is the art of taking limits. The flavor is often the same: can we do it in this simple, finite case? Yes? Apply limit theorems. Can we take this limit after this limit? No? Okay, we need more control over this error term.

Probability and PDE can also fall into the category of 'continuous' things, for obvious reasons: lots of derivatives, measure theory, infinite-dimensional spaces, and so on. Ironically, most things in modern analysis/PDE aren't continuous à priori.

Discrete math, on the other hand, can test you in very different ways. Combinatorics is a great example, because often you need very little background to understand the question, but the underlying techniques are very sophisticated and require experience. You might consider finite group theory discrete math, and this could be reasonable if you're considering the permutation group $S_n$, but much of analysis is done on (locally compact, Abelian, Hausdorff) groups. Sieve arguments (the kind used in the proof of the twin prime conjecture) are also very combinatorial.

You shouldn't worry too much about the distinction. As Feynman pointed out, knowing the name of something doesn't bring you closer to understanding it. Dabble, learn, and eventually you'll be able to say "this feels like a typical argument in discrete math."

I mean, how do you know the difference between fruits and vegetables? There are grey areas (bananas are berries, tomatoes are fruits), but if someone hands you something that is juicy, sweet, crisp and delicious, you can say "this is a fruit!" even though no one told you.

$\endgroup$
1
  • $\begingroup$ Although fruit has a clear scientific definition "the seed-bearing structure of a plant". Knowing the name doesn't change anything no but knowing the definition does. If I say that is a fruit to someone who does not know what a fruit is it means nothing, if I say it to someone who does they instantly know it is the seed bearing area of the plant. If there is no definition, who has the final word on what is discrete maths and what isn't and why do we bother categorizing to something which means nothing anyway? $\endgroup$ Commented Jan 31, 2014 at 15:19
0
$\begingroup$

According to my dictionary, "discrete" means "constituting a separate entity or part", and I think the same usage is meant when we talk of "discrete mathematics". The best way to know what discrete mathematics is about is probably just to study some texts or papers in discrete mathematics. Some people like discrete mathematics more than continuous mathematics, and others have a mindset suited more towards continuous mathematics - people just have different taste and interests.

On the other hand, the different areas of mathematics are intimately related to each other, and the boundaries between disciplines are created artificially. You might want to read an article (available online) by Laszlo Lovasz titled "Discrete and continuous: two sides of the same?"

$\endgroup$
1
  • $\begingroup$ In the strict sense of discrete meaning separate or distinct, pi and e are distinct. The Lovasz paper is a nice reference - an interesting and relevant point that I caught from it is that in computer science we often discretize a continuum, or in quantum mechanics, what we thought was a continuum seems actually to be discrete, in the sense of being made up of individual quanta. But it may be that the discretisation is arbitrary (rounding algorithm) or that the quanta lack identity (twinning being the exception). In other words it is a matter of choice of model or theory. $\endgroup$ Commented May 8, 2014 at 14:43
0
$\begingroup$

To be rather indiscrete, different areas of science and mathematics, let different aspects of everyday life, use words in contradictory ways. Look up any word in the dictionary and the chances are you will see a dozen meanings. Furthermore anytime you are told X means Y you should suspend belief: Almost certainly the statement is false. Different words exist to have different meanings and nuances. They may coincide in referent or truth value at times, but still have different meaning.

Different words get different formal definitions in different parts of science and mathematics. For example words like significance and confidence have different meanings in different papers on machine learning and data mining. Different theories of sets mean that the word "set" has a different meaning in each theory.

The functional idea of continuity concerns a mapping from a domain to a range, and constraints such as 1. (continuous range) that between any two values, the range in between contains other values in the range; 2. (continuous function) that between any two values in the domain closer than some delta, all mappings of the intervening values in a continuous domain will lie in the range between.

Considering sqr: rationals -> rationals, this works fine and there is a rational between any two rationals, etc. Of course sqrt: rationals -> rationals, has a problem with irrational roots and a second problem with imaginary roots for the negative part of the domain (complex range needed). So there is no problem with rationals being countable and continuous.

Discrete means individual, separate, distinguishable implying discontinuous or not continuous, so integers are discrete in this sense even though they are countable in the sense that you can use them to count. In fact the formal definition of countable is anything you can count with the integers in the sense of defining a (bijective) function from the integers to the set (and vice-versa).

In computer science, machine learning, data mining, etc. What is important is how you treat an attribute. A data mining text may actually distinguish categorical, discrete, enumerated and nominal, but then treat them alike for most purposes/algorithms - as discrete/separate things without any idea of there being things in between. But enumeration also implies an ordering, because the values needs to be able to be counted (enumerated) with integers (numbered). However, for some purposes it may be a taxonomy is defined showing relationships between the discrete items (like cards having suit and colour and face value, number cards vs royal/picture cards, etc.). Similarly for some purposes an ordering is needed (of a range of integers, of the suits for a card game, of fuzzy terms like small, medium, large, etc.).

From the computer science perspective there is no difference between reals and rationals as we can't represent an arbitrary real, and we tend to use decimal representations, or sometimes rational representations, or surd representations if we really have to, or representations including pi, e, phi and other constants we don't want to try to represent. Thus the idea that you can count it maps nicely to the idea of discrete in one sense, but in practice the rationals and the reals won't be regarded as discrete, and by discrete we would normally mean whole numbers or integers. This reflects another idea of discrete meaning whole or entire and denying the possibility of subdividing it. This comes back to the functional idea of continuity having things between, or equivalently being able to subdivide intervals, by having some concept of fractions (rationals). Of course real and complex number are a much later invention that lie outside our intuitive everyday framework, and can't directly be represented as full ranges in computer science.

In fact what you have stated as a definition is more like a useful assumption or axiom for computer science.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.