Why Discrete Math Is Important

https://artofproblemsolving.com/articles/discrete-math

by jaoo • 9 years ago

297 124 9 years ago

comstock• 9 years ago

I 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• 9 years ago

What 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.

andars2• 9 years ago

In 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.

ginnungagap2• 9 years ago

Every 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.

kccqzy3• 9 years ago

I 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• 9 years ago

He did elsewhere suggest teaching calculus by Big O notation: http://www.ams.org/notices/199806/commentary.pdf

I would be excited to see someone try that.

gizmo6862• 9 years ago

Discrete 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

vidanay• 9 years ago

I literally just stopped working on my discreet math homework tonight before loading HN and seeing this article.

craigching2• 9 years ago

I 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?

gizmo6862• 9 years ago

It 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.

dcow2• 9 years ago

That was not my experience despite it being a requirement for the CS major.

dagw• 9 years ago

At the university I went to both the math and CS departments offered discrete math courses with slightly different focuses.

kccqzy3• 9 years ago

Discrete 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• 9 years ago

That'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...

smadge• 9 years ago

A survey "Discrete Mathematics" course is definitely a mishmash. But every topic in discrete mathematics is rich enough to study in it's own 4 credit 1 quarter undergraduate course: Set Theory, Combinatorics, Graph Theory, Formal Logic, etc.

JonathonW• 9 years ago

It's hard to place a particular "context" for discrete math; it really is a hodgepodge of topics, loosely linked because they deal with discrete structures (integers, graphs, logic statements) rather than continuous ones (real/complex numbers).

It's particularly relevant to computer science because, in CS, we're dealing with discrete structures almost exclusively. The rise of computers and of CS is both what led to the current interest in discrete math subjects as a research field and what led to the development of university curricula in the topic.

So, really, discrete math (as a university course) exists mostly to teach some CS-relevant topics that don't necessarily get much dedicated time in the "standard" algebra->geometry->calc progression, because they're more concerned with continuous phenomena. It's sort of a parallel and independent track from the "standard" math sequence.

craigching2• 9 years ago

So all responses thus far have been great, I think the thing I struggled with in HS and into university is trying to place everything and see what the current math leads to. So, responding here, but upvoting those that responded to me at this time because all provided me with insight. Thanks!

luckyt• 9 years ago

I disagree that CS deals only with discrete math. Machine learning makes heavy use of linear algebra, with a decent amount of calculus to model statistical phenomena. All of this uses continuous variables, not discrete.

bordercases2• 9 years ago

It gains a bit more unity when you try to interpret it through certain lenses.

In particular, one problem with discrete mathematics as it's taught, is that it doesn't separate the methods of counting from the set of objects that you need to count.

There are a couple of ways around this. One good way is to look at all combinatoric identities as referring to the number of ways you can connect some set to some other set. Sometimes they're called "choices", "mappings", functions, whatever. You can talk about the function and sets separate from the numbers, and the numbers drop out of properties of the set. Doing this removes a layer of interpretation and guesswork even if it ups the abstraction a bit.

Additionally, discrete math just looked at as the math of algorithms also gets you far. Sedgewick's Analysis of Algorithms book is actually a discrete math book in disguise, since it gives a system of notation that can describe basically any combinatorical object separate from the counting method -- and then maps it to the counting method.

https://www.amazon.com/Introduction-Analysis-Algorithms-2nd-...

saagarjha3• 9 years ago

A common use case is prove correctness or running time of algorithms.

kqr2• 9 years ago

Prove running time as in complexity analysis is more analysis than algebra though, right?

saagarjha3• 9 years 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• 9 years ago

1) I loved my undergraduate discrete math class.

2) who can't love a class that teaches you how to understand the math behind poker :)

sidcool2• 9 years ago

My peev has been, how do I improve my problem solving skills, not necessarily Mathematics wise. But in general.

fjsolwmv4• 9 years ago

Read _How to Solve It_ by Polya

sidcool2• 8 years ago

Bought it just now.

atsushin• 9 years ago

I 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• 9 years ago

Surely, 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• 9 years ago

The Coursera/UC series on discrete mathematics [1] looks like a good introduction.

[1] https://www.coursera.org/specializations/discrete-mathematic...

enriquto8• 9 years ago

Discrete 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.

dcow2• 9 years ago

I 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?

jonsen2• 9 years ago

Discontinuous, probably.

AstralStorm2• 9 years ago

Neurons themselves are working on physics at not quite quantum scales, so probably a good model would be timewise continuous stochastic.

gosubpl• 9 years ago

Nice thing about "continuous" math is that we have so many "standardised" tools in its toolbox, contrasted with "ad-hoc-edness" of discrete math. Hence interesting is solving discrete problems with "continuous" tools - like e.g. http://ac.cs.princeton.edu/home/

enriquto8• 9 years ago

You can also see it in the opposite sense.

The continuous models are an ad-hoc, purely mental, construction. When you have to solve a PDE, you actually build a discrete model (using finite elements), and solve the discrete thing. Except in very simple toy problems, you can never "solve" anything using only continuous tools.

BeetleB3• 9 years ago

Hence interesting is solving discrete problems with "continuous" tools - like e.g. http://ac.cs.princeton.edu/home/

I'm often interested in the opposite: Solving continuous problems by going to the discrete domain.

I'm not a mathematician, but I did enjoy taking math courses and dabbling a little.

My personal highlight was when I was struggling for months to solve a continuous variable problem, but then one day I decided to "pixelate" it and converted it to a discrete problem. I solved the discrete problem, and got the answer to the continuous problem by taking the limit of the solution.

The problem was: If you choose n numbers at random (uniformly) in the interval (0,1), what is the expected value of the maximum?

I showed this problem to a number of people (including math professors) who struggled with it. Finally, one day, a colleague solved the problem in 5 minutes and 3 lines using continuous math. (It's not a clever solution either - surprising so many people missed it).

Still, I feel content with my discrete proof (which was about 2 pages). Since then I've often thought I should collect interesting continuous problems solved this way and put them on a web site, but never did. :-(

wslh• 9 years ago

Discrete math is important because the universe is discrete.

Is time discrete?

lmm2• 9 years ago

Unknown. There's at least one approach to quantum gravity based on the idea that it is (causal sets), but we haven't proven it one way or another.

CogitoCogito• 9 years ago

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.

What "flaw" are you referring to? Also you're certainly free to use other definitions for real numbers, if you feel they better capture "reality".

enriquto8• 9 years ago

All definitions of real numbers are equivalent, as far as I know. And as much as I love the definitions of R as a crowning achievement of human civilization, they lead to some infuriating paradoxes, especially in measure theory (e.g., freiling's axiom of symmetry).

VyseofArcadia• 9 years ago

The problem I've always had with real numbers is that the vast majority (i.e. uncountably many) of them are not computable, and only countably many of them are computable.

That means that almost every real number, all but a vanishingly small subset, cannot be represented by any means whatsoever. No formulas, no algorithms, nothing. On top of which, they're surprisingly complicated to construct. There's several different ways of doing it, and they're all complicated.

At some point you've got to ask yourself, "are they really even there?" (Of course, those who already have non-Platonic leanings will find that question amusing.) I start to think that maybe we'd be better served by dropping all the non-computable numbers and start doing almost everything in the field of computables.

ChrisLomont5• 9 years ago

because the universe is discrete

Many aspects of the universe are not known to be discrete, such as space, time, energy, and much, much more. It's not unreasonable that there are discrete and continuous aspects to the universe.

Many things that pop science treats as discrete, such as an electron, are most accurately described as interactions of a continuous fields via topological quantum field theories. Treating the electron as a discrete thing only works for some experiments. Treating it as a field works for all experiments.

Chris20483• 9 years ago

"not known to be discrete" does not imply "It's not unreasonable that there are discrete and continuous aspects to the universe"; it is not known that anything is continuous either.

mabbo• 9 years ago

But this is just a flaw in our current definition of real numbers.

The distance between discrete infinite sets (countable) and continuous infinite sets (uncountable) is a pretty large gap. Are you saying that there is no gap? There are pretty well studied proofs showing that uncountable sets are much bigger than countable.

What's your take on this? Got a counter proof to Cantor?

enriquto8• 9 years ago

What's your take on this? Got a counter proof to Cantor?

As much as I am a fan of all things about cardinals, measure and category (Oxtoby's booklet on this stuff has been on my nightstand for several months, to a great pleasure), I still fail to recognize its technological and physical implications.

My take on this is modelled after the famous article "The dawning of the age of stochasticity" by David Mumford, where he argues that the current definition of real numbers leads to infuriating contradictions, especially in the light of probability theory. This article left me with the impression that in a near future, we will see a clever definition of "real-valued random variable" that does not depend on the definition of real numbers and avoids all kind of disgusting paradoxes.

woopwoop3• 9 years ago

Manifolds are just graphs with many vertices.

Okay, I'll bite. How? What is the definition of the tangent space? Dimension?

contravariant2• 9 years ago

Yeah you'll want hypergraphs (or even better simplicial complexes) in general but you can make sense of manifolds as discrete objects. In fact I'm fairly sure you can triangulate any (smooth?) manifold.

The tangent space can be defined in terms of derivations, as soon as you define what a smooth function on the 'discrete' manifold should look like (you may have to define the derivative at a face, rather than a vertex, or have the function take values on faces rather than vertices).

enriquto8• 9 years ago

the tangent space is the set of edges

vector fields (sections of the tangent bundle) correspond to real-valued functions defined on edges

dimension is always 2 ;)

if you want higher dimension you have to consider higher-dimensional cliques beyond edges (that are 2-cliques): triangles, tetrahedra, and so on. But very often this is not necessary, even when discretizing 3d stuff. For example, for Poisson equation, and the associated classical pde, you only need the laplacian, which acts on functions, regardless of the dimension.

gjm112• 9 years ago

I am intrigued by your ideas and wish to subscribe to your newsletter. How does Stokes' theorem in a discrete setting just amount to associativity?

(I wondered about the sort of discrete differential geometry found e.g. here https://www.cs.cmu.edu/~kmcrane/Projects/DDG/paper.pdf and here https://arxiv.org/pdf/math/0508341.pdf but in that setting the situation seems to be more "Stokes' theorem is true by definition".)

enriquto8• 9 years ago

I am intrigued by your ideas and wish to subscribe to your newsletter.

Lol, this is not the first time that I am mocked here :)

How does Stokes' theorem in a discrete setting just amount to associativity?

Manifolds are modeled by graphs, and calculus on manifolds becomes linear algebra using the matrices naturally associated to these graphs.

Consider a graph with n vertices and m edges.

The most important matrix is the oriented incidence matrix B, of size mxn, that has a single +1 and a single -1 on each row, indicating the vertices connected by the corresponding edge.

Scalar fields := functions defined over the vertices = vectors of R^n

Vector fields := functions defined over the edges = vectors of R^m

When you interpret matrices as linear operators:

    B     : R^n -> R^m is the gradient operator
    -B'   : R^m -> R^n is the divergence operator
    -B'.B : R^n -> R^n is the laplacian

A subset of the vertices is given by a binary vector M \in R^n. The integral of a scalar field f over M is M'.f

The outwards boundary of a subset M is -B.M. The flux of a vector field F through this boundary is (-B.M)'.F

Stokes theorem is thus the trivial identity (-B.M)'.F = M'.(-B'.F)

(I use a dot for matrix products because the star breaks the formatting. You can also define the divergence without the minus sign, but I like my laplacians to be negative-definite, it feels weird otherwise.)

BeetleB3• 9 years ago

Hello Doron Zeilberger. Did not know you read HN.

dubya2• 9 years ago

Apart from his interesting ideas about infinity, Zeilberger has things to say about math contests. See http://sites.math.rutgers.edu/~zeilberg/Opinion71.html I'd love to find a modern equivalent of the "gilyonot lematematika" he mentions.

crimsonalucard• 9 years ago

Discrete math is important because the universe is discrete. Continuous math is an approximation that sometimes, but not always, is rather convenient.

This is not true. There are "things" in the universe that are discrete (for example: matter). But whether the universe itself is discrete is something we don't know.

What is the smallest discrete measurable length in the universe? We don't know.

dbcurtis3• 9 years ago

Would you concede that the Planck length is a good approximation of the smallest measurable length in the universe?

hnzix• 9 years ago

Symbolic 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• 9 years ago

Highly 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.

aoki2• 8 years ago

if 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• 9 years ago

The 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.

bootsz2• 9 years 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.

baldfat3• 9 years 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.

whatshisface• 9 years ago

What you're describing is the basic shift between what lower-ed science/math is like and what "real" (college) science/math is like. The problem is that everything they teach in highschool and below needs to have an escape hatch for "what if they have anti-ADHD* but no clue what's going on?" That's why you were able to solve for v without obtaining any knowledge about the universe, and why taking discrete math did what they claimed geometry would do.

* It's kind of a stupid way to put it, but by anti-ADHD I mean sufficiently controlled behavior combined with the ability to focus on any rote task until it is completely learned (basically, whatever traits or life conditions you need to have the opposite of ADHD). No matter what, you're not allowed to fail that group.

leetcrew• 9 years ago

anti-ADHD

awkward way to put it (although i dunno how else to describe them), but i think everyone knows the students you are talking about. these people are the reason why highschool math/science is hell, and you can't get away from them by taken honors or AP courses.

jacobolus2• 9 years ago

Don't worry, algebra, systems of linear equations, synthetic geometry, analytic geometry, infinite series, differential and integral calculus, etc. can also be made 'cool' and intellectually stimulating. Likewise discrete math can be made dull and lifeless. The difference has much more to do with quality of problems and teaching than with your brain.

kqr2• 9 years ago

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.

They're also completely different questions in the sense of what you mean when you say "this result is correct."

The ball velocity is really a simplified model that gives you a correspondence truth (you verify by running the experiment and taking a measurement.) The exidtence proof gives you a coherence truth, i.e. there are no unknown factors and ur statement is absolutely true.

Just giving terminology to your intuition: coherence truth vs correspondence truth.

bootsz2• 8 years ago

That's a great way of putting it!

onychomys• 9 years ago

Even 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_32• 9 years ago

Not 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.

jumpman5002• 9 years ago

What? 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.

e12e• 9 years ago

You propose we stop teaching children to count? That two comes after one, is one more than one etc? I don't think we can get away from all discreet math... ;-)

dorgo• 9 years ago

Just pretend the numbers are real :P

killjoywashere• 9 years ago

Discrete math shows up on most middle and high school math contests.

That seems a terribly weak reason for anything to be important.

baldfat3• 9 years ago

When 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?

dubya2• 9 years ago

Math 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.

dbcurtis3• 9 years ago

Attention 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• 9 years ago

Fully agree - the whole AoPS range of books and courses are just amazing. Highly recommended for all kids.

Why Discrete Math Is Important

Related Stories