Order theory for computer scientists

http://matt.might.net/articles/partial-orders/?

by llambda • 15 years ago

40 5 15 years ago

matt.might.net

nhaehnle• 15 years ago

Summaries like this would gain tremendously if they were augmented with some useful examples of where taking the partial order / lattice perspective of the world actually helps you in understanding what is going on. Let me play devil's advocate a bit.

I've always felt that order theory, like category theory, lacks reasonably strong theorems. Perhaps that's because the corresponding objects simply don't have enough structure to be interesting of themselves. However, I've known several people who were raving on about how great especially categories are.

Now there are strong results that are formulated in the language of category theory, for example the theorems of homological algebra. Then again, those results cannot really be attributed to category theory: they only hold for categories that have a pretty strong additional structure to begin with; what's more, this structure (abelian categories) is something that comes from mathematics, but does not really seem applicable to computer science.

There is an argument that one should know the language of order theory, the basic definitions of preorders and lattices and so on, simply because they are useful for communication. But the same can be said about set theory, and nobody is raving about how great set theory is (well, except some of those really "out there" people who are studying axioms on crazily large cardinals, but they are typically self-aware of the fact that what they're doing tends to be uninteresting to the rest of the world).

What this boils down to, I guess, is that looking at order theory as an end to itself is not useful for a majority of the population. But if you want to use order theory as a language, you'd better introduce it together with some examples of how it can be used.

chalst• 15 years ago

Right. Seeing something like how to model the denotational semantics of the space of functions between two finite datatypes is easy to do in Haskell and really illuminating.

A long list of unmotivated definitions is not.

tinco• 15 years ago

I know set theory has some very real world applications, like formulating a data query in set notation. Applying set transformations to it to get a more optimized query and then transposing that to SQL to get a correct and performant sql query.

How do order theory and category theory have practical effects on computing? At university we learn this to explain how RSA works, but besides having funky properties that are nice for implementing asymmetrical encryption, it left me confused about their use in everyday computing.

ggchappell• 15 years ago

> I've always felt that order theory, like category theory, lacks reasonably strong theorems. Perhaps that's because the corresponding objects simply don't have enough structure to be interesting of themselves. However, I've known several people who were raving on about how great especially categories are.

I think that, from the point of view of computer science, these ideas are not primarily useful as theories, but as languages: ways to think and talk about things.

For example, any decent programmer has some kind of concept in his head that corresponds to the mathematical idea of a function, another for the special case of a function with a finite domain, and yet another for the special-special case of a finite sequence. They know implementations for these, time-space trade-offs & whatnot. That doesn't mean they need to study any subject with a name like "Theory of Functions". It does mean that familiarity with mathematical concepts like "function" and "domain" is going to be useful in the programming field.

Similarly, it would be good to be able to toss around concepts like "lattice" and "Cartesian product" and "monoid". But I'm not sure how much of the theory a programmer really needs to know.

By the way, I don't agree with your assessment of order theory and its lack of theorems. Check out -- for example -- Dilworth's Theorem and the generalizations by Greene and Kleitman, for some terribly strong statements about partial orders. OTOH I have no idea what connection these might have to computing. (And as far as I know, you are quite correct about category theory.)

> Summaries like this would gain tremendously if they were augmented with some useful examples of where taking the partial order / lattice perspective of the world actually helps you in understanding what is going on.

Definitely.

eldina• 15 years ago

As a toy example showing that knowing even just basic ideas and techniques from this area can be useful, play around with designing a purely functional algorithm for the Stable Marriage Problem. Please report back if you come up with something efficient :) Of course, we would have to agree on the target audience to make sense of what useful means.

Order theory for computer scientists

Related Stories