4 ms·

Take subtraction. The binary operator - is not commutative in the sense that a - b is not equal to b - a. But a - b commutes to - b + a. Any number of +or-with-

by jonsen 8y ago

Take subtraction. The binary operator - is not commutative in the sense that a - b is not equal to b - a. But a - b commutes to - b + a. Any number of +or-with-operand can be arranged in any order. This is commutativity in general. See the start of Chapter 1 in Part 1: https://onlinebooks.library.upenn.edu/webbin/book/lookupid?key=olbp36404 https://onlinebooks.library.upenn.edu/webbin/book/lookupid?k... This is a very practical semantics of commutativity when programming. It’s unfortunately lost in most modern math expositions.

0815test 8y ago
But this relies on associativity - without associativity, you just don't have a consistent definition of e.g. (a + b + c + d) but only, e.g. + + + / \ / \ / \ + + a + a + / \ / \ / \ / \ a b c d + d b + / \ / \ b c c d and others as well. There would be practically no point in trying to find a definition of "commutative" for these structures that don't involve associativity.
- jonsen 8y ago
  -6-7-8 == -8-7-6 == -7-8-6 == ... How does this rely on associativity? It does not rely on parenthetical associativity. The operator is of course associated with an operand, but that’s not what is meant by associativity.
  - dragonwriter 8y ago
    > How does this rely on associativity? It does not rely on parenthetical associativity. It's exactly the combination of commutivity of addition, associativity of addition, and equivalence of subtraction with addition of the additive inverse, that allows the general rearrangement of symbols you are discussing.
  - deleted 8y ago
    [deleted]
- dllthomas 8y ago
  I think there may be a mismatch in terminology here. Above, "associativity" was used in the sense of "the property that any re-association produces the same answer". It's used that way when talking about properties of an operation, often in an algebraic context. I think you're using it in the sense of "an understanding of how operands should be associated". It's often used that way when describing a language in practice, like "(+) is right-associative". If we're going to be working with expressions like (a + b + c), then whenever + is not (sense 1) associative we clearly need some understanding about what that expression means. But we can restrict ourselves to dealing with fully-parenthesized expressions and not need any sort of "this associates to the left", and still properties like associativity and commutativity can be interesting. In the case of your trees, associativity means any trees with the same ordering in the leaves (with an in-order traversal) must be equivalent. Commutativity means any trees that differ by swapping the left/right children of a parent node must be equivalent. You can have neither property, either property, or both properties.
deleted 8y ago
[deleted]

by jonsen 8y ago

0815test 8y ago

But this relies on associativity - without associativity, you just don't have a consistent definition of e.g. (a + b + c + d) but only, e.g. + + + / \ / \ / \ + + a + a + / \ / \ / \ / \ a b c d + d b + / \ / \ b c c d and others as well. There would be practically no point in trying to find a definition of "commutative" for these structures that don't involve associativity.

jonsen 8y ago
-6-7-8 == -8-7-6 == -7-8-6 == ... How does this rely on associativity? It does not rely on parenthetical associativity. The operator is of course associated with an operand, but that’s not what is meant by associativity.
- dragonwriter 8y ago
  > How does this rely on associativity? It does not rely on parenthetical associativity. It's exactly the combination of commutivity of addition, associativity of addition, and equivalence of subtraction with addition of the additive inverse, that allows the general rearrangement of symbols you are discussing.
- deleted 8y ago
  [deleted]
dllthomas 8y ago
I think there may be a mismatch in terminology here. Above, "associativity" was used in the sense of "the property that any re-association produces the same answer". It's used that way when talking about properties of an operation, often in an algebraic context. I think you're using it in the sense of "an understanding of how operands should be associated". It's often used that way when describing a language in practice, like "(+) is right-associative". If we're going to be working with expressions like (a + b + c), then whenever + is not (sense 1) associative we clearly need some understanding about what that expression means. But we can restrict ourselves to dealing with fully-parenthesized expressions and not need any sort of "this associates to the left", and still properties like associativity and commutativity can be interesting. In the case of your trees, associativity means any trees with the same ordering in the leaves (with an in-order traversal) must be equivalent. Commutativity means any trees that differ by swapping the left/right children of a parent node must be equivalent. You can have neither property, either property, or both properties.

deleted 8y ago

[deleted]