11 ms·
Why Discrete Math Is Important
- comstock 9y agoI love discrete math, it seems so much cleaner in general. I wish there were more reformulations of calculus, other numerical methods into discrete maths. I think Knuth’s concrete mathematics might have been an attempt at this, but I’ve never found time to dig into it in depth. Perhaps I should try again...
- Retra 9y agoWhat you're looking for probably either already exists, or doesn't make any sense, depending on how you clear up the ambiguities in what you've said.
- andars 9y agoIn some sense, don't the modern formulations of real analysis, etc. already start from as close to discrete maths as you can get (set theory)? Sets -> Naturals -> Rationals -> Reals I don't understand how you could reformulate study of continuous structures into discrete math in any sense other than the above.
- ginnungagap 9y agoEvery mathematical object (ok, this is false but that's not the point here) can be constructed in ZFC (the standard axiomatic framework for set theory) so you can construct the real numbers in terms of sets (if you want more precise informations on this construction look up Dedekind cuts). However this is irrelevant to, say, analysis, you could define the real numbers as the unique (up to isomorphism) complete, ordered, archimedean field and do analysis just as well, so I'd say that you are right in some sense and some formulation, but it's a bit of a stretch to consider analysis as starting from discrete maths. I also don't see how set theory fits into discrete maths, apart from the basics it seems pretty far from the common structures studied in discrete maths.
- EtDybNuvCu 9y agoPick the Grothendieck-Tarski axiom instead, and use category theory to build ZFC via topos. This path is "big" enough to handle all the interesting sets; it can't deal with proper classes, but proper classes are kind of metaphysical anyway. [0] https://en.wikipedia.org/wiki/Tarski–Grothendieck_set_theory https://en.wikipedia.org/wiki/Tarski–Grothendieck_set_theory
- ginnungagap 9y agoSure, but ZFC by itself also deals with every interesting set, I was just being nitpicky of my own assertion. I'm not familiar with TG, what's the relation between it and ZFC+some large cardinal axiom?
- andars 9y agoI understand that it's a stretch; thus the "in some sense" and "close". See my last sentence. It's not clear to me how you could reformulate analysis, which in many ways is the study of the infinite, into discrete maths in any way other than the very loose sense of starting with ZFC.
- kccqzy 9y agoI loved Knuth’s concrete mathematics too. But I don’t think it is an attempt at reformulating calculus into the discrete math framework. Instead in many places in concrete math, knowledge of calculus is assumed, especially in later chapters about generating functions etc.
- simonbyrne 9y agoHe did elsewhere suggest teaching calculus by Big O notation: http://www.ams.org/notices/199806/commentary.pdf http://www.ams.org/notices/199806/commentary.pdf I would be excited to see someone try that.
- bordercases 9y agoUPenn's Calculus I+II courses with Robert Ghrist uses this sort of notation right at the beginning (it takes the Talyor Polynomial as the natural starting point, rather than derivatives, with knocking off terms of the summation involves factoring them out into the O-notation block).
- jonsen 9y agoI found his original and not abbreviated version https://www-cs-staff.stanford.edu/~knuth/calc https://www-cs-staff.stanford.edu/~knuth/calc Now, how do I TeXify it on an iPad?
- svat 9y agoI've TeXed it a while ago; scroll down here: https://shreevatsa.wordpress.com/2014/03/13/big-o-notation-a-couple-of-sources/ https://shreevatsa.wordpress.com/2014/03/13/big-o-notation-a...
- gizmo686 9y agoDiscrete calculus is a thing [0], although it is not so much a reformutaltion of infinitesimal calculus as it is its own field that borrows heavily from calculus. [0] https://en.wikipedia.org/wiki/Finite_difference https://en.wikipedia.org/wiki/Finite_difference
- vidanay 9y agoI literally just stopped working on my discreet math homework tonight before loading HN and seeing this article.
- craigching 9y agoI have to admit, being a hybrid math/csci student, I never understood the place of discrete math in mathematics or computer science. It always seemed like a mish-mash of different topics I'd studied in algebra->geometry->calc (including mv calc, linear algebra, diff eq, and series and sequences)->real analysis. This article is a bit too brief to properly place it (at least I still don't see it), could someone provide some proper context for discrete mathematics that fits into the mold of the standard maths sequence?
- gizmo686 9y agoIt doesn't. In my experience, "Discrete Math" is not offered as a math class, but rather as a computer class. In effect, it is the "math for computer science majors" class.
- kccqzy 9y agoDiscrete math in my school is mostly about combinatorics, but also graph theory, trees, and things like that. It doesn’t really fit into the standard math sequence IMO. The standard math sequence is essentially single-variable calculus -> multi-variable calculus -> linear algebra and differential equations -> real analysis. Note that all of the above fields essentially operate on continuous things like the real numbers.
- gh02t 9y agoThat's not quite true, almost any respectable math program is gonna include a significant amount of material on finite set theory and discrete algebra (though maybe not in the non math major escalator, that usually stops at differential equations). That said, I think there is definitely a place for a "discrete math" course, which focuses on teaching things in a more computer science relevant manner. I also think numerical analysis is a much better choice than real analysis for CS majors, but that's a different topic...
- saagarjha 9y ago> Prominent math competitions such as MATHCOUNTS (at the middle school level) and the American Mathematics Competitions (at the high school level) feature discrete math questions as a significant portion of their contests. On harder high school contests, such as the AIME, the quantity of discrete math is even larger. As someone who participated in these contests, this isn't the entire story. Competitions such as these all require numerical answers, and as such skew extremely heavily towards counting and probability (as in, there's no other discrete math topics but these two). It's only when you get into proof based contents that the real meat of discrete math, namely recurrence, cardinality, graphs, etc. start showing up.
- compsciphd 9y ago1) I loved my undergraduate discrete math class. 2) who can't love a class that teaches you how to understand the math behind poker :)
- sidcool 9y agoMy peev has been, how do I improve my problem solving skills, not necessarily Mathematics wise. But in general.
- atsushin 9y agoI wish I had paid more attention to or had a better instructor for my discrete mathematics course, I find many of the topics covered in it extremely fascinating now, years later. :(
- hsrada 9y agoSurely, online resources for these courses must exist? I guess it's just about finding the will and time to put in double the effort because of a lack of instructor/conducive environment.
- mastry 9y agoThe Coursera/UC series on discrete mathematics [1] looks like a good introduction. [1] https://www.coursera.org/specializations/discrete-mathematics https://www.coursera.org/specializations/discrete-mathematic...
- enriquto 9y agoDiscrete math is important because the universe is discrete. Continuous math is an approximation that sometimes, but not always, is rather convenient. Once I wrapped my mind around this, I started to understand something. Manifolds are just graphs with many vertices. Fourier analysis studies the eigen-decomposition of the laplacian on a graph, and is used to solve heat, wave and dispersion equations. Stokes theorem (which in a discrete setting amounts to matrix associativity) is a self-evident fact. Most of applied math is thus reduced to a few lines of octave code. Only when you lose discreteness or compactness things start to get nasty. But this is just a flaw in our current definition of real numbers.
- dcow 9y agoI too have a problem with continuous math. However I have to wonder if we didn't have our senses, would our imaginations be discrete or continuous?
- jonsen 9y agoDiscontinuous, probably.
- randcraw 9y agoOr concrete, as suggested by Knuth, Graham, and Patashnik in their book, "Concrete Mathematics: A Foundation for Computer Science". https://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025 https://www.amazon.com/Concrete-Mathematics-Foundation-Compu...
- daveslash 9y agoThe "Concrete Math" book title is a play on words - combining continuous and discrete. From the preface: "When DEK taught Concrete Mathematics for the first time.... [h]e announced that, contrary to the expectations of some of his colleagues, he was _not_ going to teach the Theory of Aggregates, not Stone's Embedding Theorem, not even the Stone-Cech compactification. (Several students from the civil engineering department got up and quietly left the room). [Edit]: Typo/Spelling fix.
- hnzix 9y agoSymbolic logic / truth tables is the single most useful subject I have ever taken wrt programming. It provides an intuitive understanding of conditionals so they can be expressed simply and clearly.
- nv-vn 9y agoHighly agree. As a current high school student, I've gone out of my way to study discrete math. Though I found calculus interesting, it's not particularly applicable to any part of CS except for a few concepts. OTOH, DM is incredibly useful for practically everything, which is what led me to seek it out.
- aoki 9y agoif your interests tend toward machine learning, you may run into calculus again. in particular, if you keep going past the "train a neural network" phase (for which very basic calculus is fine) to the optimization problems that are under the hood of most ML algorithms, you wind up in the land of functional analysis.
- pimmen 9y agoThe vast majority of people who learn calculus in school will never model a changing system in their life again. The vast majority who didn't take statistics courses in college will still try to use the limited understanding they have of statistics to assess statistical claims or draw conclusions from reported figures. The vast majority of people who never took discrete mathematics courses will still face problems of figuring out the difference of combinations and permutations at some points in their life. I love calculus and I'm very happy I know it but I would be lying if I said it even approaches the importance of discrete mathematics and statistics in today's world.
- bootsz 9y ago> Many students, especially bright and motivated students, find algebra, geometry, and even calculus dull and uninspiring That was me. I grew up believing I hated math. Struggled all the way through middle & high school to AP calc and just found it incredibly boring and tedious. Ended up opting out of doing engineering/science in undergrad because I just couldn't stand doing all the math. Long story short, years later ended up going back to school for CS and took discrete math as one of my first courses, and remember being blown away by how cool it was. All this time thinking I hated math! Hard to say exactly what the difference is. Partially I think my brain just groks discrete concepts more easily. But also the class had a heavy emphasis on proofs, which I think was really important. At a certain level this type of problem-solving can start to resemble philosophy. Chugging through a proof, figuring out just the right way to construct it and slapping a triumphant "Q.E.D." at the end is an empowering experience, especially the first time. There's a world of difference between "you throw a ball, solve for its velocity at time x" and "prove that there must be a ball" (I'm embellishing of course). It's a difference between obtaining an answer for a specific instance of a situation, and shedding light on some fundamental/universal property of the world. To me that feels profound in a sense, which makes it exciting. Proofs don't belong solely to the domain of discrete math, of course, so this probably isn't as much a testament to the subject as it is to the general problem-solving approach. It would be nice if students could get exposed to this a bit earlier, I think there are many folks like myself who would realize that they can love math too.
- baldfat 9y ago> even calculus dull and uninspiring Calculus is totally based on the teacher. I had an awesome Calculus teacher (He actually was a Physicians Assistant and had degrees from Yale and Harvard but volunteered at my small Christian School). He taught me first class why calculus was awesome by challenging use that everything else in math was fake numbers. Showed us the difference between 1/3 and 0.33333 and studying the speed of two trains word problem was always wrong. He than stated that with Calculus you could see the world as we see it. We than used functions all semester long that would eventually get "exact" and it was an awesome ride. To bad we had 3 students and the other 2 were total math geniuses and got perfect math scores on their SATs. They always made me feel like an idiot.
- onychomys 9y agoEven if we don't teach a single day of number theory, I think we can all agree that modern society would be better if everybody had to have a semester of basic probability or statistics as part of their education.
- Verdex_3 9y agoNot really. You have to find a way to make the math real to your students or else it becomes just another exercise of "what set of words do I need to say in order to make the teacher happy". At least in my experience, most learning seems to be either incidental OR some sort of vestigial residue of the social component of making the system happy.
- jumpman500 9y agoWhat? You can make easily make basic statistic and probability about real problems and interesting. Talk about sports. Talk about risks of the stock market and financial planning. Talk about politics/polling. Talk about gambling/poker. Just takes an interesting teacher to make any subject interesting.
- Verdex_3 9y agoLike, I want to believe you that such a thing is easy. But I'm not really convinced by the assertion that it is followed by a non-descriptive blurb. I mean I get what you're saying, "Find what they care about and try to apply statistics to it." However, I don't believe that this process is easy. Sports is a good example of why I don't think this is easy. What exactly is the point of statistics in sports? Predicting what teams are going to win or what strategies are superior. Most children in school are not interested in sports because they're into strategy or because they're predicting who's going to win. They're interested in it for social reasons. Which team do their parents or friends want to win. Telling everyone at thanksgiving that the family team is going to lose the game will probably not go well for them. And as far as strategy goes ... I thought the statistical analysis of the extra point kick in football indicates that you should never do it. Teams rarely make use of this at the professional level. Also didn't they make a movie about how nobody pays attention to the math in baseball (Moneyball?). Anyway, if adults who have money and fame on the line can't be bothered to care about statistics in sports, then I don't see how children are going to be much different. Of course that's where you come in. You say it's easy. Personally, I would love to see why you think this because it looks hard to me. I look forward to a more in depth response from you.
- killjoywashere 9y ago> Discrete math shows up on most middle and high school math contests. That seems a terribly weak reason for anything to be important.
- baldfat 9y agoWhen funding for your school is based off of test scores in a horrible way this is what we get. My daughter is in 6th Grade and she has no Science or Social Studies this year. Reason: She has her Math and Science testing this year. When did science become the enemy of math?
- dubya 9y agoMath contests are not related to standardized testing. The contests are entirely extra-curricular, and probably mostly benefit those kids who have exhausted their school's standard curriculum.
- baldfat 9y agoI understand that BUT school administration is looking at Math contest through standardized testing outcomes.
- dbcurtis 9y agoAttention parents of "mathy" kids: A bit off topic, but I just want to put in a testimonial for AoPS online math classes. My daughter used it as the spine of her middle/high-school math education. Great program. Check it out.
- 2sk21 9y agoFully agree - the whole AoPS range of books and courses are just amazing. Highly recommended for all kids.