Steven Strogatz wrote a series of math related articles on the New York Times website one of which is called "Rock Groups" where he looks at adding integers visually and with respect to odd and even and ventures into the territory of triangles and squares and visually portrays the closed formula for computing triangular numbers. My previous post on triangular numbers in some ways parallels his "Rock Groups" article at least in respect to the visual portrayal of triangular numbers. This post also parallels ideas in that article, in contrast his observations are geometric, these are algebraic observations about, among other things, adding and multiplying even and odd numbers, which work as follows:
+ | * |
Even + Even = Even | Even * Even = Even |
Odd + Even = Odd | Odd * Even = Even |
Odd + Odd = Even | Odd * Odd = Odd |
Now this doesn’t really give one a sense of what is going on here, however, by using a Cayley Table it can also be called an operation table in that it shows the details of an operator. It becomes more interesting we now have a better depiction of the Group for Addition (+) with Even as the Identity Element and the Monoid for Multiplication (*) with Odd as the Identity Element:
+ | Even | Odd |
Even | Even | Odd |
Odd | Odd | Even |
* | Even | Odd |
Even | Even | Even |
Odd | Even | Odd |
Now that still may not be very intuitive, however, if you convert Even to Zero (0) and Odd to One (1) you get the following, possibly more familiar Group with 0 as the identity and the Monoid respectively with 1 as the identity:
+ | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 0 |
* | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
The Group has 1 as is its own inverse 1 + 1 = 0. In general these "types" of Algebraic structures consist of a binary operator and a set that is closed under the operation so I am using the notation (Operator, {Set}) to denote these and since the sets are small I can just list the elements, but you could also write (+, Z) where Z is the set of integers and in fact this is a well known group: addition on the set of integers, but the set is infinite in this case in contrast to our finite sets. We can describe the above as the Group (+, Z2) and the Monoid (*, Z2) where Z2 is the set {0,1} of the Integers Modulo 2, or simply the Binary digits which are Base 2.
Now let’s do another transformation on our Monoid and Group, we will now map Zero (0) to False (F) and One (1) to True (T) . We will also change our operators, + now becomes Exclusive-Or and * now becomes Logical Conjunction aka Logical And.
Xor | F | T |
F | F | T |
T | T | F |
And | F | T |
F | F | F |
T | F | T |
All of these transformations are actually Isomorphisms and the two structures combine to form a Ring this is also a Field, the smallest Finite Field GF(2). I have a follow up for this post and I will get into these and other ideas in more detail.
Some basic algebraic structures are:
Magma or Groupoid – A closed binary operation on a set.
Semigroup – A closed binary operation on a set, with associatively. (An associative Groupoid)
Monoid – A closed binary operation on a set, with associatively and an identity element. (A Semigroup with an identity element)
Group – A closed binary operation on a set, with associatively and an identity element. Each element has an inverse element. (A Monoid with inverses)
Commutative (Abelian) – used to describe any of the above with the commutative property, these two terms are interchangeable but term abelian1 in abstract algebra is used mostly just for groups.
| Closed | Associative | Identity | Inverse |
Magma | X |
|
|
|
Semigroup | X | X |
|
|
Monoid | X | X | X |
|
Group | X | X | X | X |
Now Commutative is more of a property of the above, as we saw the String Monoid is not or Non-Commutative where as the Group (+, Z2) and the Monoid (*, Z2) are both Commutative.
Going back to Boolean Logic, if you have had any exposure to Boolean Logic things now may look amiss in regards to operators: such as what about the Or operator? Actually Xor can be defined in terms of Logical Conjunction and Logical Disjunction as follows:
Our Cayley Table for Logical Disjunction (Or) is:
Or | F | T |
F | F | T |
T | T | T |
Now this table is almost the same as Xor with one exception (T or T) = T vs. (T Xor T) = F. We can still call F an identity since it combines with T to give T, but you can see with that one change we lost our inverse for T so this is a now "downgraded" to Monoid status.
Now if we add Logical Conjunction (And) back we get the familiar values in Caley tables:
Or | F | T |
F | F | T |
T | T | T |
And | F | T |
F | F | F |
T | F | T |
Above we noted that the Group (+, Z2) and the Monoid (*, Z2) formed a Ring. Since Or is a Monoid these now combine to form a slightly different structure, a SemiRing.
Another interesting observation about these sets of operators comes from a logical standpoint. The combination of these two operators are what’s known as not being functionally complete, which means that there exists truth functional statements that cannot be expressed by these two operators alone, this can be fixed by adding negation which yields a truth functionally complete set of two dyadic and one monadic2 operators: {And, Or, Not}, which is a pretty well known and familiar set of logical operators. The Ring operators from above {Xor, And} also form a functionally complete set. It turns out that just {And, Not} and just {Or, Not} are also each functionally complete sets as are the one element operator sets {Nand} and {Nor}, this is why digital logic circuits can be constructed solely with Nand Gates.
The thing that bothered me the most was the fact that And and Xor had this nice mapping from Boolean Logic with {T,F} to Binary Integer Arithmetic {0,1} but Or seemed to be an oddball and then I realized that you can remap both Logical Conjunction and Logical Disjunction to the Numerical functions Min and Max, respectively:
Max(0,0) = 0
Max(0,1) = Max(1,0) =1
Max(1,1) =1
Min(0,0) = 0
Min(0,1) = Min(1,0) =0
Min(1,1) =1
In Caley table form which better shows the isomorphisms (≅ means bidirectionally isomorphic to) from our Caley tables above: (And, {T,F}) ≅ (Min, Z2) and (Or, {T,F}) ≅ (Max, Z2):
Max | 0 | 1 |
0 | 0 | 1 |
1 | 1 | 1 |
Min | 0 | 1 |
0 | 0 | 0 |
1 | 0 | 1 |
Interestingly this mapping is the effectively definition of Fuzzy Logic mapped to the discrete cases (two value logic). Boolean Logic also maps to Lattices with disjunction being meet and conjunction being join, the min and max ideas give a nice intuition in relation to ordering.
To recap we saw a number of Group and Monoid Isomorphisms (remember Z2 = {0, 1}), we saw:
(+, Z2) ≅ (+, {Odd, Even})
(*, Z2) ≅ (*, {Odd, Even})
(+, Z2) ≅ (Xor, {F, T})
(*, Z2) ≅ (And, {F, T})
(Or, {F, T}) ≅ (Max, Z2)
(And, {F, T}) ≅ (Min, Z2)
We also saw Ring Isomorphisms and a Semiring Isomorphism:
[(+, Z2), (*, Z2))] ≅ [(+, {Odd, Even}), (*, {Odd, Even})]
[(+, Z2), (*, Z2))] ≅ [(Xor, {F, T}), (And, {F, T})]
[(Or, {F, T}), (And, {F, T})] ≅ [(Max, Z2), (Min, Z2))]
I have always felt that examples are helpful and I think these give some sense of the diversity that can be found in just a small little corner of math. In researching this I came across some interesting facts which also highlight this diversity, for example the Nand operation is not associative but is commutative so it’s a commutative Groupoid. The Octonions, which are hypercomplex numbers,are neither associative nor commutative under multiplication but have an identity of 1 making it a non commutative Groupoid with an identity, so my point here is that the above table of basic algebraic structures that makes everything look so hierarchical is deceiving as the diversity does not seem to be constrained in any way, as far as I can tell.
1 This term is named after the Norwegian mathematician Niels Henrik Abel who developed Group Theory independently of Galois and like Galois tragically died young(<30).
2 Dyadic means takes two operators, e.g. (And, Or) and monadic means takes one operand, in this case the negation (Not) operator, this should not be confused with other uses of the term Monad.
No comments:
Post a Comment