Hacker News Reader

Comment by dvt | Hacker News Reader

You can prove three-term commutativity from two-term (I did it years ago, I think it looked something like this[1]), so the ordering doesn't matter.

[1] https://math.stackexchange.com/questions/785576/prove-the-co...

View on HN

I'm not talking about a universe where all elements commute, I'm talking about a situation in which A, B, and C do not necessarily commute but (AB) and C do. For a rigorous definition: given X and Y from some semigroup G, say X and Y are asynchronous if for any finite decompositions X=Z_{a_1}Z_{a_2}...Z_{a_n} and Y=Z_{b_1}Z_{b_2}...Z_{b_m} (with Z's in G) then for any permutation c_1,...,c_{n+m} of a_1,...,a_n,b_1,...,b_m that preserves the ordering of a's and the ordering of the b's has XY=Z_{c_1}Z_{c_2}...Z_{c_{n+m}}. I make the following claim: if G is commutative then all elements are asynchronous, but for a noncommutative G there can exist elements X and Y that commute (i.e. XY=YX) but X and Y are not asynchronous.

To give a concrete example, matrix multiplication is not commutative in general (AB ≠ BA), but e.g. multiplication with the identity matrix is (AI = IA). So AIB = ABI ≠ BAI.

Or applied to the programming example, the statements:

    1. Server.accept
    2. Client.connect
    3. File.write  # write to completely unrelated file

123 = 312 ≠ 321.

Strictly speaking this also requires associativity.

Reply on news.ycombinator.com