Let $G$ be the set of all (finite) binary strings. Let $\oplus$ be the XOR operator defined component wise on the strings. For example $1011 \oplus 0110 = 1101$. Then $(G, \oplus)$ forms a group, where $0$ is the identity and every element has order 2, i.e. $\forall\alpha \in G$, $\alpha^{2} = \alpha \oplus \alpha = 0$

Also, if we let $+$ be binary addition, then $(G, +)$ forms a commutative monoid.

Is there some algebraic structure that $(G, \oplus, +)$ could fall under? It's close to being a semi-ring, but distribution doesn't hold and the additive identity doesn't annihilate the entire set under the multiplication.

I'm kind of skeptical at this point of this forming anything interesting since distributivity with XOR doesn't hold for any binary operation, so there is no way to really "weave" the two operations together, but I'm still curious.

  • $\begingroup$ $(G, \oplus)$ doesn't quite form a group: there isn't a well defined way to form products of strings of different lengths. Instead, it forms a groupoid, a structure similar to a group in which multiplication may be a partial function. $\endgroup$ – William Ballinger Oct 29 '13 at 3:34
  • $\begingroup$ Ah I didn't even notice that, guess I got ahead of myself. Would it help if we fixed the length of the strings in $G$? I think the problem with that would be that it might not be closed under the $+$ operation as there could be carries. Interesting though. $\endgroup$ – Kafka Oct 29 '13 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.