[Haskell-cafe] What puts False before True?

David House dmhouse at gmail.com
Tue Jun 5 05:21:19 EDT 2007

On 05/06/07, PR Stanley <prstanley at ntlworld.com> wrote:
> Hello
> What do the ≤ symbols represent?

'Less than or equal to'. To say that x ≤ y, if x and y are numbers,
means that x is either less than y, or x and y are equal (so x cannot
exceed y). However, in the spirit of mathematics, the symbol now
actually means slightly more than just that. There's a general concept
called a "partial order" which is quite important in all of
mathematics, especially in computer science. Here ≤ still means 'less
than or equal to', but that takes on a different meaning depending on
which partial order you're talking about. For example, you can order
sets by inclusion, so that {1, 2, 3} ≤ {1, 2, 3, 4, 5, 6} because {1,
2, 3} is a subset of {1, 2, 3, 4, 5, 6}. Or you could order the
natural numbers by 'divisibility', i.e. you could say that x ≤ y if
and only if x is a factor of y (so that 2 ≤ 4, and 3 ≤ 18). You could
say that a function f ≤ another function, g, if and only if f(x) ≤
g(x) for every x. If you're familiar with denotational semantics, the
partial order on expressions used there roughly corresponds to how
many evaluation steps you've gone through, so that 1:2:<thunk> ≤
1:2:3:4:<thunk>, and (<thunk>, <thunk>) ≤ ("hello", 4.3).

The reason these are "partial" orders is because sometimes it makes no
sense to say that x ≤ y, and it makes equally little sense to say that
y ≤ x. For example, if you had the sets {1, 2} and {4, 5}, neither is
a subset of the other, so {1, 2} ≤ {4, 5} is false, but {4, 5} ≤ {1,
2} is false, too.

http://en.wikipedia.org/wiki/Partial_order contains a formal
definition and a few more examples.

-David House, dmhouse at gmail.com

More information about the Haskell-Cafe mailing list