On 05/06/07, PR Stanley
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@gmail.com