Basics: Discrete vs Continuous

One thing that I frequently touch on casually as I’m writing this blog is the distinction between continuous mathematics, and discrete mathematics. As people who’ve been watching some of my mistakes in the topology posts can attest, I’m much more comfortable with discrete math than continuous.

The distinction is a very important one. Continuous mathematics is, roughly speaking, math based on the continuous number line, or the real numbers. The defining quality of it is that given any two numbers, you can always find another number between them – in fact, you can always find an infinite set of numbers between them. Building up from numbers, a function in continuous math can take the form of a perfectly smooth curve without any gaps or breaks. In theory, you can talk about a function as a set of pairs – f={(x,y) | y=f(x)} – but you can’t even show an exhaustive list of the pairs that make up the function, even over a finite section of the function.>

In discrete mathematics, you’re working with distinct values – given any two points in discrete math, there aren’t an infinite number of points between them. If you have a finite set of objects, you can describe the function as a list of ordered pairs, and present a complete list of those pairs.

The difference becomes clearer when you think about some of the deeper areas of math – which is sort of unusual. In general, getting deeper makes things harder; but here, getting deeper makes the difference easier to understand.

In continuous math, the fundamental set of numeric values that we use for proofs is the interval (0,1). We often prove various properties of sets by using mappings from values in the range (0,1). In discrete math, the fundamental set of
numeric values is the natural numbers, we prove properties of sets by using mappings from the natural numbers.

For example, one of the basic fundamental sets of concepts in math consists of
the ideas of shape, closeness, and adjacency:

disc-vs-cont.jpg

  • In continuous math, we generally
    study those ideas using topology: sets of points form topological spaces, and we often study properties of those spaces and functions over them
    by using mappings from the range (0,1) to subspaces or functions.
  • In discrete math, we study those ideas using graph theory, where
    we have a set of points where each point is connected to a specific set of
    other points by edges. We often study properties of graphs or functions over graphs using mappings from the natural numbers to subgraphs or functions.

Another very fundamental thing we do in math is study how things change. In continuous math, we do that using differential equations, which are functions that describe the rate of change of one function using another derived function. In discrete math, we do the same thing using recurrence relations, which define a the value of a function at a point in terms of one or more of the points that precede it.

For example, in continuous math, given the equation y=x2, we can say that at any x, y is changing at a rate of 2x. In discrete math, we can describe a set like the fibonacci series by saying fib(x)=fib(x-1)+fib(x-2).

I’ll close this with a personal story about differential equations and recurrence relations. Back in college, I started school as an electrical engineering major. I was a very bad electrical engineer, and I wound up basically flunking out. One of the courses that I failed in my last semester as an EE was differential equations. After that semester, I took a year off to get my head together and figure out what I wanted to do. When I came back, I decided to take differential equations again – not because I needed to, but because I wanted to prove to myself that I could do it.

For roughly the first half of the semester, I struggled. I worked my tail off, and barely managed to scrape by with Ds on my exams.

At the same time, I was taking the discrete math course required for computer science students. Around the midpoint of the semester, we we studying recurrence relations, and how to translate them into closed form – that is, a non-recurrence based equation.

One of my closest friends and I were taking both classes together, and one afternoon, we were working together on our homework in both classes. We started with diffEQs, and I got incredibly frustrated, and so we put it down, and switched to
the recurrence homework. And were zipping through the recurrence problems like nobodies business, just knocking ’em down. And as we were doing this, we noticed (or to be honest, I think she noticed) that one of the problems was almost exactly the same as one of the problems in our diffEQs homework, and that the way that I had just solved it was almost exactly the way that you’d solve the diffEQ. And I looked at it, and looked at it… And she was absolutely right. They were really pretty much the same thing: that recurrence relation was the discrete form of a differential equation. And it clicked. And from that afternoon on, I never had any more trouble with diffEQs. I ended up aceing the rest of the exams for the class, and finished with a B.

The point of that is partly how great the similarity between differential equations and recurrence relations really is; and partly to show you just what you can do to yourself when you convince yourself that you can’t do something. There was nothing about differential equations that I couldn’t do. I won’t say it was easy, but it was always, from day one, entirely within my ability to understand it and do it. But I was convinced that it was so hard that I’d never grasp it. And so I didn’t. I really believed that I was trying to – but on some level, I was so sure that I couldn’t do it that I wouldn’t let myself understand. Until my friend hit me in the face with the fact that I could do it, and in fact, already had done it.

(And as a personal aside – that friend is still one of my best friends. She was the “Best Man” at my wedding; I’m the godfather of her first son. If you’re reading this Abby, I don’t think I ever really thanked you for that blow to the head in the lecture hall at Lorree. So thanks!)

0 thoughts on “Basics: Discrete vs Continuous

  1. John Armstrong

    The defining quality of [the real numbers] is that given any two numbers, you can always find another number between them – in fact, you can always find an infinite set of numbers between them.

    NO! (hits you on the nose with a rolled-up issue of the Notices of the AMS)
    That property holds for rational numbers just as much as it does for real numbers, but still rational numbers are not continuous. What separates the real numbers — the continuum — is that it’s complete. That is, every sequence of real numbers that “should” converge (because the elements get closer and closer together) actually does converge to a real number. Equivalently, every set of real numbers bounded above has a least upper bound.
    To see that this doesn’t work for the rational numbers, consider the increasing sequence of fractions {3/1, 31/10, 314/100, 3141/1000, 31415/10000, …}. This sequence should converge, but the only possible limit is π, which isn’t a rational number. Equivalently, any rational upper bound has to be bigger than π, so there’s no least upper bound in the rational numbers.
    That’s the defining quality of the real number system.

    Reply
  2. clem

    Speaking of diffyq, you might be able to get an interesting article about how the emphasis in that subject has changed due to the computer revolution. I know that all math teaching has, but I find the disparity between new and old diffyq books especially striking. I taught myself ordinary differential equations from a book written, I believe, in the early nineteen sixties that I found in a secondhand store surrounded by romance novels and old almanacs. Much later, in the early nineteen eighties, I got out of the Navy and decided to take a math course to restart my mind. Diffyq I was the only course that fit my time constraints and that I was able to talk my way past the prereqs to be allowed to take it. The textbook seemed like an entirely different subject. The techniques taught, the uses demonstrated, the amount of emphasis on numerical analysis and the use of tables, and above all the use of graphics were completely alien to my memories of the old secondhand book. Incidentally, on the final day I went to the professor’s office to get my grade and saw a copy of that old book I had learned from on his bookshelf. Looking at the author’s name on the spine, I suddenly realized for the first time that my teacher had written that old book!

    Reply
  3. bigTom

    Perhaps your problem with diffEQs wasn’t psychological, but the way your brains intuition about mathematics works. I’m kinda the opposite to you, I have good intuition about continuous things, but discrete mathematics and graph theory largely escapes me. You may well have discovered how to use your talents in one area, to understand the other.

    Reply
  4. Canuckistani

    I once bought myself a slim book on linear difference equations. I found that I could cruise right through it, because I’d already learned how to solve linear differential equations in undergrad; the methods were exactly the same.

    Reply
  5. Sopoforic

    Reading your story makes me think I ought to look into diff eq again. I took a course in the subject, got an A, but I’m not sure I could solve even a simple linear ODE right now. On the other had, we spent a few days on recurrence relations in a discrete math class I took, and I think that I can find the closed form for any recurrence relation you care to name.
    Perhaps if I go at it with the knowledge that I have of recurrence relations, it’ll stick. I can always hope, anyway.

    Reply
  6. Jesse

    Hmm… this all seems very familiar. I started out in EE too, despised it, and ended up with Math & English degrees.

    Reply
  7. dileffante

    For the sake of non-math readers, I think it is important to point out the existence of many connections between discrete and continuous math, just to avoid giving the idea of two disconnected big branches. In math, no theory is an island, and as your anecdote with diffEQs shows, there are many bridges, often wide, highly trafficked and productive bridges. Sometimes you just borrow an intuition from the other side (e.g., “what if we tried to find a Lyapunov function for this discrete system?”), sometimes you use the other view (and its tools) to show something (e.g., Smale’s horseshoe and the use of symbol dynamics to prove chaos in continuous systems), sometimes you have mixed systems (e.g., iterated maps, with discrete time but continuous space), etc, etc… I chose discrete math because I liked it much more, but soon discovered that I’d never get rid of the continuum: there is only one math.

    Reply
  8. Enigman

    The rationals are not complete, as John strongly notes, but I think that there may be an interesting issue here. The rationals are not what we mean when we talk of ‘continuous mathematics’, but are they not continuous?
    Prima facie they seem to be continuous, in MarkCC’s sense (whence they would be fine for most topology; or rather some countable set of the not-too-weird reals would). Where they seem to fail to be continuous, is in having gaps where the irrational numbers are. But then, it is the presence of so many real numbers (uncountably many) that leads us to the Banach-Tarski paradox, which indicates that the real number line violates some of our intuitions about continuity. And what if actual, physical continua exist, and actually happen to have an abstract structure that includes infinitesimal quantitities (e.g. by being so smooth)? Then even the real number line would have gaps in it.
    In short, although completeness is important, lesser forms of closure could be adequate for much continuous mathematics, and continuity may not be (either conceptually or actually) the same as completeness.

    Reply
  9. Chris' Wills

    I could happily pass the maths exams in engineering, use limits etc to differentiate/integrate but didn’t really have a feel for it until we actually did graphical differentiation/integration.
    Actually drew the curves of the functions and then plotted their differentials/integrals graphically as part of the technical drawing (actually used pen & paper) course. Seeing the curve grow was wonderful and you could be as accurate or rough as required.
    Now, with all tech-drawing done on computers, this isn’t taught anymore. No more pen & paper technical drawing in engineering, a sad thing.
    Discrete mathematics only entered my life when I had to start doing some computing. It is still a confusion to me :o)

    Reply
  10. Anonymous

    Last I heard, continuity is a property of functions. On that view, asking whether the rationals are continuous is like asking whether they’re one to one.

    Reply
  11. Koray

    MarkCC: Wow. I was an EE undergrad and didn’t give a rat’s tail about differential equations, either. Similarly, I didn’t care much about control theory, laplace transforms, etc.
    However, I liked electromagnetic theory, which makes me think that classes that I didn’t like had everything to do with the instructor and not the subject. Maybe I wouldn’t have liked lambda calculus either if I hadn’t learned it myself and been taught by a jackass.

    Reply
  12. John Armstrong

    Not quite, Enigman. Banach-Tarski is a problem with our notions of set theory. Particularly, it’s connected with the acceptance of the Axiom of Choice.
    As for continuity: yes, there might be an existant realization of nonstandard analysis. However, you’re setting up a straw man. Let’s go back to the basics.
    A sequence is Cauchy if for all e>0 there is an N such that for all m,n>N we have |a_n-a_m|already have all the convergent sequences they need.
    Yes, you can define “nonstandard analyses”, but these go radically beyond the real numbers, and their topology (such as it is) is horrendous. You can’t even probe it with sequences anymore!

    Reply
  13. Doug

    In Basar and Olsder, ‘Dynamic Noncooperative Games (SIAM Classics in Applied Mathematics), 1999, discrete and continuous are an issue only with respect to time.
    Readers may “Look inside this book” at Amazon.
    http://www.amazon.com/Dynamic-Noncooperative-Classics-Applied-Mathematics/dp/089871429X/ref=pd_bbs_sr_1/102-8566474-9392927?ie=UTF8&s=books&qid=1172871188&sr=8-1
    Each author has more recent [searchable inside] books published:
    1 – Advances in Dynamic Games and Applications (Annals of the International Society of Dynamic Games) (Hardcover) by T. Basar (Editor), A. Haurie (Editor), Tamer Basar (Editor)
    2 – Mathematical Systems Theory (Paperback) by G.J. Olsder & J.W. van der Woude (Author)
    3 – Max Plus at Work: Modeling and Analysis of Synchronized Systems: A Course on Max-Plus Algebra and Its Applications (Princeton Series in Applied Mathematics) (Hardcover) by Bernd Heidergott (Author), Geert Jan Olsder (Author), Jacob van der Woude (Author) “In this book we will model, analyze, and optimize phenomena in which the order of events is crucial…” (more)

    Reply
  14. Douglas

    You might be interested in looking at Time Scales stuff – essentially, talking about difference/differential equations simultaneously, defined on sets that are have both discrete and continuous components.
    Here’s a relevant link: http://www.math.unl.edu/~apeterson1/sample_book.pdf
    Nitpicks – the real numbers are not a continuum. A continuum has to be compact. Like [0,1].
    And the defining characteristic of R is that is complete, ordered, and a field. You need all three. Complex numbers are a complete field. Surreals ( for non-standard analysis) aren’t a field. Rationals are an ordered field, but not complete.

    Reply
  15. CBBB

    Interesting story. I’m an undergraduate math major and the university I attend allows math majors to really specialize in a particular mathematical area (we have an entire faculty devoted to math rather than a department as in most universities). Any way your story about DEs and RRs is interesting because a few semesters ago I was taking a DE course since I was thinking about majoring in Applied Math (which is a math-physics focused degree) but I did horribly in the DE class (an important prerequist) at the same time I was taking an introductory class in combinatorics and we were doing RRs and I also noticed the connection between DEs and RRs. Unfortunately it didn’t help me a lot because while I did a lot better in the combinatorics class the RR part of the class was one of my weakest.

    Reply
  16. Doug

    To: Douglas
    From: Doug
    Thank you for the reference in your Post of March 2, 2007 05:31 PM.
    M Bohner, A Peterson [U-MO-Rolla]
    ‘Dynamic Equations on Time Scales’
    Chapter 1: The Time Scales Calculus
    Figure 1.5, page 20 deals with a Cantor Time Set
    Only 50 of 353 pages with 253 references
    Cantor Time Sets may be associated with the Koide relation for fermion masses.
    Y Koide, ‘Universal texture of quark and lepton mass matrices with an extended flavor 2–3 symmetry’, 2004 [one of many papers]
    http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=PRVDAQ000069000009093001000001&idtype=cvips&gifs=yes

    Reply
  17. Enigman

    The Banach-Tarski paradox is not just a problem for set theory, John, not if set theory is our way of defining the real number line. The trouble with the Axiom of Choice is that it is not particularly troubling, if a realistic view of sets is taken. (Not unless we have a potential infinity, but for the standard real number line we do not.) And of course, if we are considering mathematical continua that might be physically instantiated (e.g. as time), then we ought to take a realistic view.
    The Axiom of Choice just says, in effect, that we already have all the subsets of what we have got already. It only seems weird when it is added to a first-order and finitely-axiomatised set theory that captures at best only part of the structure of the real number line; and only then because it is telling us more about the real number line. The Axiom of Choice was being assumed implicitly by mathematicians long before it was formulated: no one had formulated it before the problems with set theory because it was NOT a problem!
    In short, the Banach-Tarski paradox really does show that the standard real number line is an implausible continuum (it is a paradox when we think of the real numbers as the structure of a physically plausible continuum; it is simply a theorem within standard real analysis). As for nonstandard analysis, since I did not mention it that must be your straw man! The “smooth” sort were implicitly implied; but I recon that both of those kinds are unrealistic. Still, what of the physical possibility of quantities that are smaller than 1/n for any natural number n? (I hope I don’t sound pedantic or bitchy. I just think that MarkCC’s highlighting of density was justified.)

    Reply
  18. Jonathan Vos Post

    “what of the physical possibility of quantities that are smaller than 1/n for any natural number n?”
    The length of time between the traffic light turning green and the car behind you honking its horn?
    Just kidding. But why worry about physical manifestations of nonstandard analysis in the midst of the debate about whther there are actually physical manifestations of the continuum?
    For that matter, how can the integer 10^10^10^100 be manifested in the physical universe?
    Or exactly PI, since the universe is not Euclidean?
    The connection between Physics and Math is somewhat slippery…

    Reply
  19. John Armstrong

    Enigman: His mention of density of the reals demonstrates the point he’s trying to make, but he’s needlessly written something that is just plain false in the process. Nobody would say that the rational numbers form a continuum, and they share that property with the reals. What sets continua apart is completeness.

    Reply
  20. Anonymous

    My earlier comment was apparently deemed unsuitable. It noted the error involved in asking of the rationals whether they are continuous. Perhaps our host, having made a similar error in the past, still feels such talk makes sense.
    It bears repeating: sets are neither continuous nor discontinuous. Continuity is a property of functions.

    Reply
  21. Mark C. Chu-Carroll

    anon:
    Perhaps a bit less paranoia might be in order?
    I’ve been busy, and forgot to check the mod queue for the last few days; in general, I’ve got things set up so that very few things get trapped by the mod queue. As I’ve said before; if there’s some comment that seems like it’s trapped in the queue, drop me an email to let me know, and I’ll clear it.
    WRT to the “sets aren’t continuous, functions are” thing: when I’m writing for this blog, I try to consider my audience. That is, who’s going to be reading a particular post? My style of writing for a basics post is pretty different from my style of writing for a topology post – because the topology posts are intended for serious math geeks; the basics posts are intended to be linked to by other SBers, and their primary audience is non-math people who want a basic understanding of some concept.
    For non-mathematicians, the distinction between “the set of real numbers is continuous”, and “the set of real numbers forms a continuum” is the kind of distinction that confuses things more than it clarifies. People have an intuitive notion of what continuity is; and when you’re talking about the distinction between discrete math and continuous math, that intuitive notion of continuity is right on-target for describing the difference.
    Someone who doesn’t already understand the distinction between continuous math and discrete math is not going to be seriously mislead in their understanding by the use of the intuitive sense of continuity; and someone who already knows the different between discrete math and continuous math really doesn’t need to read this post, and isn’t going to have their understanding of the distinction screwed up by the use of an informal intuitive description.

    Reply
  22. Boian Popunkiov

    Enigman and John
    The Banach-Tarski paradox has very little to do with (just) real numbers. It is a statement about R^3, which is false in R^2 and R. I don’t think it shows any implausibility of the real line. Perhaps it shows the implausibility of Lebesgue measure or its generality. What it does show is that non-measurable sets are very very weird and that you can’t produce them in a physically meaningful way.
    It is indeed connected to the axiom of choice, but in a very oblique way. Many things are equivalent to the axiom of choice, including the Hahn-Banach extension theorem, but they are not really set-theoretic theorems.
    Finally the Banach-Tarski paradox is much more intimately connected with how complex the group of isomorphisms of R^n is, which is basically an algebraic question.

    Reply
  23. Torbjörn Larsson

    While I have certainly not a good understanding of the differences between the discrete and the continuous, I think it is a correct and probably important observation that delving deeper into math (and physics) brings forth bridges (to use dileffante’s terms).
    The z-transform for discrete time signals and the fourier transform for periodic signals makes a connection visible. This is further elaborated in physical systems where confined systems have a discrete spectra and unbounded systems a continuous. In QM this is apparent, and while I don’t know much about Hilbert spaces I have gotten the impression that some physicists like to see them as combining and exploring the discrete and the continuous.
    About emphasis and tools in diffeq’s, it is complicated by the different classes, something I think Mark has noted before. It seems it can be an art to study some diffeq’s in some domains, the Navier-Stokes for fluids is one prominent example. This contributes to make it confusing as different books use different tools.

    Reply
  24. Torbjörn Larsson

    Convergent sequences are how we define limits of functions.

    I must thank John for his clear exposition here, since I had some vague problems in this direction with Enigman’s comment as I read it, problems I couldn’t really formulate.

    The Banach-Tarski paradox is not just a problem for set theory, John, not if set theory is our way of defining the real number line. The trouble with the Axiom of Choice is that it is not particularly troubling, if a realistic view of sets is taken.

    I think this is the third thread I have seen where Enigman whips forth Banach-Tarski paradox as a problem for the real number line and measure theory. I’m not a mathematician, but it seems to me that the paradox points out a bizarre consequence when using AC and/or non-measurable sets.
    As I understand it AC is a simplifying tool like the use of infinities. If you choose not to use one or more of them you get different types of math (such as Zermelo-Fraenkel set theory without AC or constructive math) as when you do.
    As for measure theory, the only use of AC I saw in my old book (Cohn, “Measure Theory”) was for set definition. And to show that not all subsets if R are Lebesque measurable, which can only be done by ZF set theory with AC added, apparently. Which presumably shows one eminent use of AC.
    Enigman seems to be concerned with philosophical “truth” and “the metaphysics of continuity”. I hope the above doesn’t illustrate a preconceived notion of where a problem lies, because that seems less fruitful in such a quest.

    Perhaps it shows the implausibility of Lebesgue measure or its generality.

    As I understand it, the path integral in physics isn’t Lebesque integrable, suggesting just the later problem with the Lebesgue measure, it isn’t general enough for all the things we want to do. (Already improper Riemann integrals shows that the Lebesgue measure isn’t quite enough, I think.) Apparently it is yet impossible to calculate path integrals except in very simple cases.
    I just recently learned about another integral which also seems inspired by physics namely the gauge integral, which seems somewhat easier to handle.
    From an introduction discussing its potential use in graduate classes to deepen the understanding of Lebesgue integrals: “In fact, the Henstock-Kurzweil formulation — the gauge integral — is considerably simpler than the Lebesgue idea, and its definition is only slightly different from the definition of the Riemann integral. […] For instance, every Lebesgue integrable function is also gauge integrable. […] This analogy may be helpful: The gauge integrable functions are like convergent series; then the Lebesgue integrable functions are like absolutely convergent series.” ( http://www.math.vanderbilt.edu/%7Eschectex/ccc/gauge/ )

    Reply
  25. Torbjörn Larsson

    “when using AC and/or non-measurable sets” – when using AC with non-measurable sets.

    Reply
  26. Torbjörn Larsson

    And I forgot to mention the point, which was that gauge integrals contain both Lebesgue and improper Riemann integrals, being more general.

    Reply
  27. Antendren

    Already improper Riemann integrals shows that the Lebesgue measure isn’t quite enough, I think.
    Nope. Lebesgue integration handles improper Riemann integrals exactly as you’d like it to.

    Reply
  28. Alexandre Borovik

    In my book, (Chapter 6, Encapsulation of actual infinity, and elsewhere), I attempt to suggest some possible cognitive mechanisms behind the discrete/continuous divide: roughly speaking, discrete is visual, continuous is sensorimotor. The concept of a set is visual, while that of manifold is sensorimotor.
    Of course, mathematical cognition is the synthesis of activities of various cognitive systems — perhaps, only olfaction is not involved.

    Reply
  29. John Armstrong

    Boian: That’s pretty much what I was trying to say. B-T doesn’t have anything to do with whether Mark’s statement was correct, which was my point. To bring in something like that is a straw man, and nonstandard analyses (and yes, bringing up spaces “more dense” than the reals counts even if you don’t use the words) are another.

    Reply
  30. Jonathan Vos Post

    Worth mentioning that all but a set of measure 0 of numbers on the number line are real but not rational? Or that Chaitin shows that all but a set of measure zero of reals are incompressible, random? Worth a Basic page on rational, irrational, transcendtal?
    Which reminds me:
    ================
    e: Mnemonic to the Base of Natural Logarithms
    by
    Jonathan Vos Post
    e = 2.718281828459045…
    It: natural,
    I: personal,
    so exponent
    I appraise.
    It: enabling
    logs’ table —
    logarithm,
    O base,
    amaze!
    033-0345
    2050-2100
    11 July 1983
    ================

    Reply
  31. Torbjörn Larsson

    Lebesgue integration handles improper Riemann integrals exactly as you’d like it to.

    That wasn’t what I remembered, and it is not that the gauge integral tutorial claimed.
    Now thinking on it, what was the case was that improper R.I. may have pathologies (formal expression being ill-defined) unless one takes the principal value.
    I assume that is what you mean. Yes, after that unavoidable resolution of the ambiguousness it makes them compatible as I understand it.

    Reply
  32. Davis

    That wasn’t what I remembered, and it is not that the gauge integral tutorial claimed.

    Anything Riemann integrable is Lebesgue integrable, and the Lebesgue integral gives the same value in such cases.
    The converse is false, of course — the function that’s 1 on the rationals and 0 on the irrationals is Lebesgue integrable on any interval (including the entire real line), but not Riemann integrable on any nontrivial interval.

    Reply
  33. Enigman

    Many apologies if my writing style (or lack of it) grates… Banach-Tarski is indeed not particularly relevant, but I only intended to mention it in passing (to begin with), as an example of a possible justification for something: I had only wished to say that, true enough as John’s point about the definition of the real numbers (which are also called ‘the continuum’, rather confusingly) was, the continuity of continuous mathematics is all about density, about small changes in a variable giving us only small changes to our function’s value. And that can of course be captured completely by the rational numbers, so long as our operations would not take us beyond the rationals; or by some other, more closed (but still countable) subset of the reals, if they would.
    I was going to make the same point as John (about the definition of the reals) until I saw that he had made it, so I certainly think that it was a good point, worth mentioning to the beginner. But nonetheless, why not call the latter (or even the rationals) continuous (in that sense)? Even in a space of rationals, whilst our operations would be severely restricted, we would not see any gaps, not under any magnification. It would seem continuous, it would act continuous (so long as we stayed within the space), so why not call it continuous? The point about Banach-Tarski (and it would indeed be tangential for me to defend here its use as my example) was that we only use the real number line (and its powers) in continuous mathematics because we use it everywhere, because of the ubiquity of set theory, not because it is The Continuum (so to speak); and that the extra we get with the full real number line may even be a problem; really, though it is of course heretical to say so outside a loony-bin!

    Reply
  34. Enigman

    More apologies, but I can’t after all resist responding to Torbjörn’s “I think this is the third thread I have seen where Enigman whips forth Banach-Tarski paradox as a problem for the real number line and measure theory. […] I hope the above doesn’t illustrate a preconceived notion of where a problem lies, because that seems less fruitful in such a quest.” That’s right! Wholeheartedly I must try to resist preconceptions. So I must admit that I cannot claim to possess a definitive take on Banach-Tarski. But having addressed the AC aspect above, let me say briefly why I am puzzled about the many mentions of measure theory.
    Very roughly, the Banach-Tarski paradox is that a unit sphere can be considered to be made up of five pieces, which can be rearranged to form two unit spheres. The measures of the spheres are 1, for Riemann, for Lebesgue, and for any other reasonable measure theorist. And the measures of the pieces cannot exist, in any reasonable measure theory, because what sorts of numbers could they be? If they were a, b, c, d and e, then we would have a + b + c + d + e = 1, a + b + c = 1 and d + e = 1. Prima facie, it seems that the problem is not the measure theory as such, but whatever allows us to have such pieces, and that would seem to be the sheer quantity of points in the real number line (given AC). Now, it seems to me that it is only as a corollary to that, that any measure theory based upon such quantities of points (as Lebesgue’s is) would be suspect. So simply using a different measure theory would not seem to hit the spot. (At least, prima facie. There may be much wrong with my point view, so I’d love more criticism of it, if that wouldn’t be too boring.)

    Reply
  35. Davis

    Even in a space of rationals, whilst our operations would be severely restricted, we would not see any gaps, not under any magnification.

    This is actually false. For example, basic results such as the Intermediate Value Theorem fail to hold, even if you consider only polynomials with integer coefficients. f(x)=x2-2 is a canonical example.
    You could, of course, extend to the algebraic numbers (or at least the intersection of the algebraic numbers with the reals), and consider only algebraic functions. But at that point I don’t really see that you’re gaining anything — the algebraic numbers are considerably less intuitive than the reals.

    Reply
  36. Davis

    …it seems that the problem is not the measure theory as such, but whatever allows us to have such pieces…

    I don’t really see why this is a problem at all. It’s simply a reflection of the fact that, for any reasonable measure, you’re going to have non-measurable sets.
    If anything, switching to the rationals is far, far worse, at least from a measure-theoretic perspective: you have a countable set, which will thus have measure zero under any remotely intuitive measure.

    Reply
  37. Torbjörn Larsson

    Anything Riemann integrable is Lebesgue integrable, and the Lebesgue integral gives the same value in such cases.

    Yes, that was what I concluded too, if it was unclear.
    The vague memories I had and the classifying Venn diagram on http://www.math.vanderbilt.edu/%7Eschectex/ccc/gauge/ that places some improper integrals outside Lebesgue integrals must be about the formal expression, which is ambiguous in these cases unless one uses the PV.

    The converse is false, of course

    At least probabilistically, since otherwise those distributions wouldn’t work as well. 🙂 Just kidding, measure theory is for kicks.
    Enigman:
    I’m sorry I was so negative seeing that you have some real 🙂 questions behind the B-T paradox. I guess that you easily could have answered, that this is the umpteenth thread where you have seen me grumpy. 😐

    And that can of course be captured completely by the rational numbers, so long as our operations would not take us beyond the rationals

    Another similar observation, that someone reminded me of recently, is that measurements only can yield rationals as long as we measure against normals, or that measurement approximations and computers naturally use them.
    Of course, the immediate use of intervals and probabilities to express uncertainty, averages and likelihoods pretty much destroys most of these observations too.
    I guess that if you could demonstrate a reasonable probability theory based only on rationals, it could be an argument that at least it would work. But reals are more powerful and intuitive, so I don’t see that it would be enough. As long as we discuss mathematics and applications, and not ontology or metaphysics, it seems that reals, or rather complex numbers, is the best compromise between the bother from too simple numbers and the bother from too complex constructions.

    any measure theory based upon such quantities of points

    What quantity is that? Conventional measure theory quite purposefully bases itself on the properties of sets and topology, not on putting mass or volume on abstract points.
    Intuitively that seems the correct thing to do, and considering the power of the rather economical theory it is again probably hard to demonstrate anything better.
    Now, maybe the problem you have with this is based on the use of set theory. I’m guessing you aren’t alone there. Some people even seem to consider basing mathematics on categories instead! 😮

    Reply
  38. Anonymous

    Torbjörn, I’m wondering, what is this: “I’m sorry I was so negative seeing that you have some real 🙂 questions behind the B-T paradox. I guess that you easily could have answered, that this is the umpteenth thread where you have seen me grumpy. :-|”?
    Surely it is always true (more or less) that there may be some real issues behind anything. Anyway, the reasons why I was slow in answering include (i) I have irregular and brief access to the internet, (ii) I meant it when I said “I am puzzled about the many mentions of measure theory” and when in a state of puzzlement I prefer not to reply too soon in case I have only misunderstood the issues, to avoid digging myself ever deeper… (I would suggest a Basic on measures, since I for one have found the various comments above educational, but am still a bit puzzled.)
    (iii) I haven’t “seen [you] grumpy”! I think that guessing the tone of an email is difficult at best, and did you use those partially helpful faces before? Etc… but is it really appropriate for me to give such reasons here? Probably not; but then if I don’t reply you could be negative (umpteen times) about that very lack of a reply, in the manner of the above… dilemma!
    I could ask (agressively moving beyond my dilemma), what is this apology for being prematurely negative followed by another negative? But I guess (re my (iii) above) that it is amusing? Anyway, if it is not then I would not wish to prolong this pointlessly bitchy side-issue (more apologies). So, re the main side-issue (!!!), the “quantity” I had in mind was the cardinality of the standard continuum, not any sort of physical quantity. (I had hoped that was implicit, since to add lots and lots of discriminating adjectives makes my prose really really bad. Really, the above is good, for me.)
    Also, I’m not suggesting that we drop the reals and use the rationals. (I had hoped that was obvious, but if not then I’d better not bore every other reader.)

    Reply
  39. Torbjörn Larsson

    Torbjörn, I’m wondering, what is this:

    I’m sorry, Enigman if it is you, I don’t understand the comment before “the “quantity”” et cetera. It seems to be about the tone of my comments. I’m not sure if I can make them any clearer.

    the “quantity” I had in mind was the cardinality of the standard continuum

    I’m not the right one to ask here, since I’m not much familiar with this. But it seems to me this measure would be equivalent to putting masses on points, since it seems it roughly counts “number of elements” in a set.
    If so, I can refer back to my previous comment.

    Reply
  40. Doug

    [It bears repeating: sets are neither continuous nor discontinuous. Continuity is a property of functions.]
    O.K., but for every non-empty set one can define that set by saying that it consists of a collection of elements and their respective characteristic (membership) functions. Consequently, do the characteristic functions of (crisp) sets come as continuous or discontinuous? Well, usually mathematicians talk about sets of point (like) objects instead of intervals, or else mathematicians would talk more about and use more interval arithmetic and the like as opposed to point-set topology, integer (number) theory, etc. One might counter-argue that analysis (calculus) talks about “continuous” objects, but generally point-set topology gets used (implicitly) quite a bit. So, even though sets come as neither continuous nor discontinuous, it appears that usually mathematicians talk them as discontinuous.

    Reply
  41. Enigman

    Torbjörn, it was indeed I (pseudonymly Enigman), I just forgot to enter my details in my impassionate (and consequently incoherent) response. I could make it clearer, but only via too much information.
    By “the sheer quantity of points” I meant the largeness of the number, which is what gives us sufficient points so that we can have (given AC) the (possibly weird) subsets of the Banach-Tarski sphere decomposition. If you give each point a unit mass then that would be that cardinality (presumably some aleph greater than aleph-null) of kilograms, and is that what you want?

    Reply
  42. Ørjan Johansen

    By “the sheer quantity of points” I meant the largeness of the number, which is what gives us sufficient points so that we can have (given AC) the (possibly weird) subsets of the Banach-Tarski sphere decomposition.

    I believe that you can construct the Banach-Tarski paradox on a countable set. If you use algebraic numbers for the coordinates, they are still countable, but you have enough to express the rotations needed for the proof.
    From looking at the wikipedia article I suspect even rational numbers might be enough, with some use of pythagorean triples.
    The fundamental thing that makes the proof of the paradox work is not any large cardinality of the sets (beyond basic infinity) but the fact that the rotation group of a sphere contains a free group with two generators. This requires the group being non-amenable, a stronger property than non-commutative, meaning you cannot take an average (mean) over the group’s actions. This can perfectly well happen with a countable group, such as the free group with two generators itself.

    Reply
  43. Anonymous


    Perhaps a bit less paranoia might be in order?

    I’ve been busy, and forgot to check the mod queue for the last few days; in general, I’ve got things set up so that very few things get trapped by the mod queue. As I’ve said before; if there’s some comment that seems like it’s trapped in the queue, drop me an email to let me know, and I’ll clear it.
    I wasn’t concerned until other posts turned up after mine. I guess you filter “anonymous” posts. I’ll bear that in mind.
    Someone who doesn’t already understand the distinction between continuous math and discrete math is not going to be seriously mislead in their understanding by the use of the intuitive sense of continuity; and someone who already knows the different between discrete math and continuous math really doesn’t need to read this post, and isn’t going to have their understanding of the distinction screwed up by the use of an informal intuitive description.
    This is a poor excuse for conflating distinct concepts. It wasn’t your prior behavior that prompted my post however. It was that of Enigman. His suggestion that the rationals might be continuous is just confused.
    (And, to avoid further confusion, I was the author of only the first two anonymous posts in these comments.)

    Reply
  44. Mark C. Chu-Carroll

    anon:
    The scienceblogs moveabletype installation has a bunch of spam filtering modules installed. Each comment is assigned a numeric rating by the filters, and anything with a rating above a certain threshold goes into the mod queue. I don’t entirely understand how some things are categorized as spam – usually it’s obvious, but once in a while, there are posts that get queued for moderation for no reason that I can determine.

    Reply
  45. Antendren

    I believe that you can construct the Banach-Tarski paradox on a countable set.
    It’s very important that the partitions you construct be nonmeasurable, as otherwise the “paradox” really is a paradox. You can’t find a countable, nonmeasurable set.
    Keep in mind that the rotation group of the rational (or algebraic) sphere is quite a bit smaller than that of the sphere. It must not contain a copy of a free group on multiple generators.

    Reply
  46. Enigman

    Many thanks to Ørjan and Antendren, you are helping me at least to clear up my puzzlement. And of course, there may well be nothing wrong with having measureless bits of (powers of) the real number line.
    But the Banach-Tarski paradox is, I think, evidence (just evidence) that the standard real number line is not quite the continuum (the abstract mathematical structure that would be possessed by any actual physical continuum, were there any), not a proof of that. Similarly, the coherence displayed by standard mathematics over the last hundred years is very good evidence that the standard real number line is, indeed, the continuum, but not quite a proof of that.
    Perhaps the Banach-Tarski is particularly paradoxical in 4 dimensions (but is evidence against the real number line, and all its powers). Think of an impenetrably rigid 3-dimensional sphere, made of some perfectly smooth material (which is unrealistic, but classical), in a 4-dimensional space. According to Banach-Tarski, it can be broken up into 5 similarly rigid pieces (connected subsets of points) that can be moved rigidly (in the fourth dimension, since they cannot pass through each other) to form two new spheres, each identical to the original sphere (in intuitive contravention of a conservation law).
    Some will find that paradoxical, and so may consider the standard Banach-Tarski theorem to be evidence that the standard real number line is not the continuum, but some will not. Those who do will hardly be impressed by our ability to say that the pieces lack measures, or that the Banach-Tarski theorem simply shows that some subsets of the continuum lack measures. But those who do not may well wonder what else could be said.
    I find it hard even to imagine what we would be talking about, were we able to say anything else. E.g. I recently thought that dropping one of the 5 pieces into a measuring flask would give us a more paradoxical result, whereas either the measuring fluid would be unable to fill up all the space around the piece, or the fluid would develop a weird surface. But maybe one day someone will say a bit more, in which case we might have better evidence. For now, perhaps we have some evidence (just evidence)?

    Reply
  47. Enigman

    Re Anon’s “His suggestion that the rationals might be continuous is just confused.” Not confused, but ordinary language. Yes, functions are continuous or not; and indeed, the continuum is the real number line by definition. But to say that time is continuous, for example, is not to say that time is a function, of course. Nor, I hazard to venture, is it to say that instants are isomorphic to real numbers. It is only to say that time contains no gaps, as it extends smoothly into the past and future. (et cetera ad nauseum)

    Reply
  48. Enigman

    Although the rationals contain no nonzero gaps (the absence or presence of such nonzero gaps being the continuous/discontinuous distinction here, for continuous math versus discrete math), I prefer something more like the analytics, or the computables.

    Reply
  49. Xanthir, FCD

    Enigman: Lay mathematician here, but is it really assumed that the reals are supposed to correspond to some aspect of reality? They model continua relatively well, but the fact that they have infinite density would guarantee that they are not a perfect model for anything physical, I would think. I would assume that this is obvious, but perhaps physical/mathematical thought goes in a slightly different direction.

    I recently thought that dropping one of the 5 pieces into a measuring flask would give us a more paradoxical result, whereas either the measuring fluid would be unable to fill up all the space around the piece, or the fluid would develop a weird surface.

    If the fluid is not perfectly smooth (not infinitely dense), then it would be unable to fill all the space around the piece, as the contours of the shape are infinitely detailed, similar in concept to fractals. If the fluid is perfectly smooth but still fluidic, I doubt it could be used to measure the volume of anything. It would simply flow around any objects and compress itself, maintaining a set volume (which I suspect would be 0 in any case).

    Reply
  50. Enigman

    Well Xanthir, I suspect you’re right about my useless hypothetical fluid. But there might be physical continua, e.g. space-time might be continuous (as might the quantum-mechanical wavefunctions that go through it). It is hardly mainstream that space-time is composed of atoms?
    Anyway, you ask me, “is it really assumed that the reals are supposed to correspond to some aspect of reality?” I don’t think it is, but it is assumed that there might be physical continua, and if there are then there would seem to be a truth of the matter, about whether or not our mathematical continua correspond to physical reality. So we might view the reals in that light, whether or not we are supposed to. I suspect that many physicists believe that the standard reals do give the true structure of (possible) physical continua.

    Reply
  51. Ørjan Johansen

    It’s very important that the partitions you construct be nonmeasurable, as otherwise the “paradox” really is a paradox. You can’t find a countable, nonmeasurable set.

    Actually if you demand the usual rotation or translation invariance you cannot even find a countable set of non-zero measure, in the usual sense. My comment was in the context of whether rationals could be considered continuous, which would at least require us to restrict to finitely additive measures. In that case some countable sets could very well be non-measurable, and a variation of the Banach-Tarski paradox could be proof of that.

    Keep in mind that the rotation group of the rational (or algebraic) sphere is quite a bit smaller than that of the sphere. It must not contain a copy of a free group on multiple generators.

    A free group on two generators is itself just as small. In fact I suspect that two rotations about the x and y axes respectively, with angle atan(3/5) (corresponding to the pythagorean triple (3,4,5)) do generate such a free group. I just don’t have a complete proof, but it is such a simple variation that if it is true then it must be mentioned in the litterature somewhere.

    Reply
  52. Doug

    [Lay mathematician here, but is it really assumed that the reals are supposed to correspond to some aspect of reality?]
    No. I think George Lakoff explained this best in his book on embodied mathematics Where Mathematics Comes From . More or less it got assumed prior to the invention/discovery of complex quantities that all numbers had a linear ordering to them. That is, a given number x either is greater, equal to, or less than another given number y; and that it makes sense to ask this question. Complex quantities simply cannot get linearly ordered with respect to real numbers. Thus, Descartes and others dubbed them “imaginary”, since they didn’t want to/couldn’t give up the idea that all numbers had to have a linear ordering to them.
    [I suspect that many physicists believe that the standard reals do give the true structure of (possible) physical continua.]
    I certainly don’t know how you think that when complex quantities play such a large role in the Fourier analysis (almost all wave analysis) and even more so in quantum mechanics.

    Reply
  53. Antendren

    <smacks self> I’d totally blanked on the fact that of course there’s no paradox if everything is measure 0.
    I assume you mean atan(3/4), in which case I suspect you’re right. It requires proving that atan(3/4)/pi is irrational, which I’ve spent a few minutes working on with no luck.

    Reply
  54. Ørjan Johansen

    I assume you mean atan(3/4), in which case I suspect you’re right. It requires proving that atan(3/4)/pi is irrational, which I’ve spent a few minutes working on with no luck.

    Whoops, right.
    Well, I tried now and had plenty of luck: This question is equivalent to (3+4i)^n never being real for n=1,2,…
    And then by luck it turns out that with a+bi=(3+4i)^n, a and b are always congruent to 3 and 4 (mod 10), in particular b is never 0.
    (I carelessly used 3+4i instead of 4+3i and that turned out to be lucky, too, they of course give the same answer for the question but the modulus pattern appears sooner with the first one.)

    Reply
  55. Enigman

    Complex quantities play a large role in quantum mechanics, but they are just x+iy for real x and y. The wavefunctions having complex values corresponds to the space-time in which they exist having (powers of) real values. The basic point-structure here would be that of the standard set-theoretic continuum (given that physicists have a professional regard for mathematicians, rather than philosophers).
    Incidentally, apologies for the straw man of the rational number line, but I was intrigued by why, in John’s first comment, instead of saying that “The defining quality” should have been “The relevant quality” or something like that, instead of that he said “What separates the real numbers – the continuum – is that it’s complete.”

    Reply
  56. waseem

    If out of 35 people each person like Discrete Mathematics or Data Structures ,25 like Discrete Mathematics, and 20 like Data structures then the number of people who like both Discrete and Data Structures is
    ANs:5 10 15 none

    Reply
  57. Alicia

    The continuous is where asjkfgqei[cwmdoofvuiiiiiiiiiiirjnecawesdjglvuysoHVYWAVFGL;WHFEUWGhuiodpfsheoi err err im breaking uppp………………………………………………………………………………………………………………………………………………………………..

    Reply

Leave a Reply