Comment by ldb
7 years ago
Thanks, that was helpful. However, I still think that having "sum(1,1,{})" returning "2" and "1+1+{}" returning "{}" can be viewed as somewhat inconsistent.
7 years ago
Thanks, that was helpful. However, I still think that having "sum(1,1,{})" returning "2" and "1+1+{}" returning "{}" can be viewed as somewhat inconsistent.
Let me make a tiny correction to the expression you wrote:
"sum({1, 1, {}})" - the function sum takes only one argument and it's a set. Because we flatten all "nested" sets, the expression "{1, 1, {}}" is equivalent to "{1} UNION {1} UNION {}".
The expression "1 + 1 + {}" albeit valid grammatically, can be equivalently re-written as "{1} + {1} +{}". At this point it should be far more obvious why "sum({1} UNION {1} UNION {})" is not the same as "{1} + {1} + {}".
Literals may be a little confusing because they look like elements, but they are still sets, singleton sets, specifically. There's practical value in simply thinking about "a bunch of things: A, B, C", where each of the A, B and C can themselves be empty, a single thing, or a bunch of things while ignoring nesting. In our case we allow duplication in these bunches (which is not part of the bunch theory: http://www.cs.toronto.edu/~hehner/bunch.pdf). However, because most people are familiar with sets we find it easier to keep using the terms "set" and "multi-set" (and stipulate that they are flattened) in explanations.
In general, the way the operator "+" works is this: A + B = {a + b : for all a in A, for all b in B}. Whereas the expression "{A, B}" is defined to be equivalent to "A UNION B".
Good explanation! (which indicates why the handling of empty sets is sometimes a bit confusing)
One more question: What was the motivation behind defining "sum({})" to be "0" rather then "{}" ?
Oh, that's simple: sum(A UNION B) should be the same as sum(A) + sum(B) for any two sets A and B (or else there would be very weird inconsistencies).
sum(A UNION {}) = sum(A) + sum({})
sum(A) = sum(A) + sum({})
0 = sum({})
Typically for any operation generalized for a set the result of op({}) should be equal to the identity for that operation (0 for sum, 1 for product, True for AND, False for OR, etc.). It's always such a value I that for any other value A, A op I = A.
5 replies →