One of the things I've encountered during my physicist-in-training years is a partitioning of my social life and scientific and mathematical interests.
This partition isn't easy to overcome: Much of the mathematics one picks up along the way is so abstract and esoteric that it's beauty is hard to convey to the uninitiated. How can you talk about the spelling of a word and the structure of a sentence without your listener even knowing about the alphabet? The same applies to, say, differentiable manifolds: it's tough enough convincing some engineering friends that it can be useful rather than just interesting--or, hey, even that it's interesting--and these guys know calculus, differential equations, and linear algebra.
But I often try my best with non-mathematical friends using maddening metaphors and tortured analogies. It can be frustrating, but it can also be quite fruitful: the struggle to convey any complex idea in a clear and simple fashion does not only benefit the listener who is subject to hear about "what I did today," but ultimately clarifies my own understanding--and makes it that much easier to talk about the next time the subject is broached at a pub or party.
I don't have a lot of time tonight, so I'll go over a simple example:
Do you realize that you know modular arithmetic?
That word might be unfamiliar, but the fact that 10 + 5 = 3 shouldn't be, at least not in the counting system Z modulo 12, which we're all very comfortable with.
Don't believe me? Here's a scenario: it's 10am, you got work at 3pm, how much time do you have to complain about not wanting to go to work?
Well, it's obviously not one hour since we all know that 10 + 1 = 11. Is it three hours? You look at the clock: 10 + 3 = 1.
So it's more than three hours--but wait! Adding 3 to 10 gives you 1? Isn't that just a silly convention? Sure, this is how we talk about time on a daily basis, but does this kind of "clock arithmetic" really have any mathematical credence?
The answer is yes. This system of numbers, Z modulo 12, is just as natural as systems we are more familiar with, such as the integers, Z. (In mathematics texts we usually denote the integers by Z, the rationals by Q, the reals by R, and the complex numbers by C.) In fact, they both satisfy what are known as the group axioms, what are known as the ring axioms, and more. As far as algebraic systems go, both are simply particular examples. There exist far more.
Since you have work in five hours (10 + 5 = 3 in Z modulo 12) I think we have enough time for a little chat.
The integers, Z, is an example of what we call an additive group: a group is a "set" coupled with something we call a binary operation and a few axioms, cleverly called group axioms. 'Addition' and 'multiplication' are particular examples of a binary operation. From these two familiar examples we might deduce that a binary operation is something that eats two numbers and spits out another--and we'd be on the right track. To be thorough, though, not all sets are sets of numbers: there exists sets of functions, sets of sets, and, actually, sets of any kind of conceivable objects! (We could have the set of all annoying people in your life.) A binary operation is something that eats two objects from the set we are dealing with (two annoying people) and spits out another object from that set (another despicable cretin).
To consider Z a group (not just a set), we include with Z the binary operation called addition, denoted by "+", and call the group (Z,+) -- or simply Z if there is no confusion. To make sure (Z,+) is a group, it must satisfy the group axioms, which we now list.
Given a set S and a binary operation #, the pairing (S,#) is a group if the following criteria are satisfied:
* closure: the binary operation on the given set must never eat two set members and spit out a non-member; this is more formally written: let a, b be members of S, then a#b is also a member of S.
The operation of addition on the set of all integers satisfies closure. For example, 2+3=5. Both 2 and 3 are members of Z, thus 2+3 must also be a member of Z, which it is, namely 5. We also have an operation that satisfies this closure property on Z modulo 12, which we will get to a little later.
* associativity: let a, b, and c be members of S, then a#(b#c) = (a#b)#c.
It's easy to remember the associative law if you think of the parentheses as representing who hangs out with who: then it doesn't matter who hangs out with who! More technically, the associative law means that it doesn't matter if you first operate on b and c, then on a and b#c, or if you first operate on a and b, then operate on a#b and c; they both spit out the same answer.
Addition on the integers also satisfies the law of association (as we all pretty much know), For example, 2+(3+7) = (2+3)+7. Proof: 2+(3+7)=2+10=12 and (2+3)+7=5+7=12. (This is almost insultingly obvious, but it's an important property, especially when we begin dealing with algebraic systems not as familiar as the integers--e.g. Z modulo 12, which we're getting to.)
* existence of an identity element with respect to the binary operation: a few examples will clarify this.
If our set is the integers and our operation is addition, the identity element (which we call the "additive identity") is zero since, given any integer s, s+0 = 0+s = s. As another example, if again our set is the integers but this time our operation is multiplication, the identity element is 1, since given any integer, s*1 = 1*s = s. (Like 0 is called the additive identity, we call 1 the multiplicative identity.)
So hopefully it has become obvious that an identity element with respect to an arbitrary operation # is some member of S--call it e--such that, given any element s of S, s#e = e#s = s.
* closure under inverses: this means given any member s of S, there exists some element (call it inv(s)), also in S, such that s # inv(s) = inv(s) # s = e, the identity element of the set S with respect to #. In order for (S,#) to be a group, any given element of S must have an "inverse" that is also in S.
For the integers, we already know given any integer there exists an "additive inverse" of that integer, which is also an integer--namely it's negative; for example, the additive inverse of 10 is -10, since 10 + (-10) = 0, which is the additive identity of (Z,+) as required.
Ok, ok... Take a moment. I'm not sure if any of the above is technically difficult for a newb, so for the love of love, let's all just take a moment to recap. Given a set S, we can make it into a group (S,#)--where # is some binary operation--if this coupling satisfies closure under #, associativity, existence of a #-identity, and closure under inverses.
We have shown the set of integers Z to be a group under addition. That is, (Z,+) is a group.
Is Z also a group under multiplication? That is, is (Z,*) a group? To answer this question we simply ask: are all the group axioms satisfied with respect multiplication? (The answer is no, so the question is: can you figure out which axiom(s) fails to be satisfied by (Z,*)? We already covered that a multiplicative identity exists: 1.)
As a side note, the set of integers Z coupled with the two binary operations "addition" and "multiplication" is an algebraic entity known as a ring. So (Z,+) is a group and (Z,+,*) is a ring. Just note the terminology for now... I think I will discuss rings next week.
To wrap up this week's phase, let's address the possibility of Z modulo 12 being a group. Does there exist a binary operation that makes the set of numbers 1 through 12 a group?
To answer this, we will first construct Z modulo 12 from the integers themselves using what is known as an "equivalence relation" and forming "equivalence classes." Then we will show that these equivalence classes can be added together in a certain way and that the familiar arithmetic of clocks can be recovered.
First we should define what an "equivalence relation" is:
An equivalence relation on a set S satisfies three properties--these properties are known as "reflexivity," "symmetry," and "transitivity." Let's explore what these words mean. To do so, let ~ ("tilda") be an equivalence relation. Again we'll deal with an arbitrary set and call it S.
Reflexivity means that, if ~ is an equivalence relation on S, then given any element s of S, s~s (read "s is equivalent to s").
This sounds kind of retarded at first. In the familiar realm of Z, isn't any integer equivalent to itself? The answer depends on what relation we are considering. For example, if we are considering "equality" then, of course, 5 = 5 and 123 = 123, so "equality" is definitely reflexive. But what if the relation we are considering is "less than"? Given an integer x, is x less than x? No way. So "less than" is NOT reflexive. (And thus not all relations are equivalence relations.)
Symmetry means that if, given two elements x and y of S, that if x~y, then y~x (read "if x is equivalent to y, then y is equivalent to x").
Again, this sounds kind of silly at first--and, likewise, it's because we are most familiar with the word "equivalent" being associated with the word "equal." Let it be known that, in mathematics, these two words are not the same. Equality is a particular occurrence of an equivalence relation (that is, the relation called "equality" is reflexive, symmetric, and transitive). You can think of the concept of equivalence, though, as a generalization of the concept of equality.
So, is the relation "less than" symmetric? No, of course not: if x is less than y, then y is NOT less than x.
What is a relation besides equality that is symmetric? Well, the relation "weighs the same as" is symmetric since if Bob weighs the same as Jim, then Jim definitely weighs the same as Bob. (This relation is also reflexive, right?)
Transitivity simply means that is x~y, and y~z, then x~z (read "if x is equivalent to y and y is equivalent to z, then x is equivalent to z"), where x,y,z are all members of S.
What are some relations that are transitive? Of course equality is: if x = y and y = z, then x = z. How about the "less than" relation on the integers? If x,y,z are all integers, does x<y and y<z imply that x<z? Yes, just plug in three integers to see this clearly: if 1<3 and 3<7, then 1<7. This is true, so the "less than" relation on the integers is indeed transitive.
Another transitive relation is "weighs the same as," since if we denote this relation by ~, then if Bob~Jim and Jim~Ted, then obviously Bob~Ted. (Since we have shown "weighs the same as" to be reflexive, symmetric, and transitive, by definition it is an equivalence relation.)
There's an episode of American Dad where the character Steve touches a girl's hand and exclaims: "I touched her hand. Her hand touched her boob. By the transitive property, I got some boob. Algebra's awesome!" Is "touched her" really a transitive relation? (Figuring Steve never actually reveled in the glory associated with touching this girl's boob, I'd say no, but it's still damn funny.)
An important fact about equivalence relations is that they partition a set S.
By "partition" we mean that all the elements of S are divided into distinct subsets such that each element of S is in one subset and one subset only. For example, we can partition the set of all cars by color: each car will be exactly in one subset.
You've heard of the word MILF, right? Well, did you know we can partition the set of all mothers by this criterion? In strictly black and white terms, there'd be the MILF set and the Not-a-MILF set. These two subsets are distinct (e.g. no MILF is in the Not-a-MILF set and no Not-a-MILF is in the MILF set), so the original set {All Mothers} has been partitioned.
How does an equivalence relation partition a set? By reflexivity and symmetry of the equivalence relation, any two members of S are either equivalent or not. This means we can classify all members of S into subsets of S using the equivalence relation: we call these subsets "equivalence classes."
In the car example, the equivalence relation would be "is the same color as," then a plum-colored Altima "is the same color as" a plum-colored Altima (it's reflexive), a plum-colored Altima "is the same color as" a plum-colored Taurus implies that a plum-colored Taurus "is the same color as" a plum-colored Altima (it's symmetric), and...well, you get it. It's transitive too! It's an equivalence relation. And it partitions the set of all cars into equivalence classes.
Let's define an equivalence relation on the integers. Two integers are equivalent if both have the same remainder after being divided by 12.
Is this really an equivalence relation? Well it's reflexive, since given any integer x, x and x both have the same remainder after being divided by 12. It's symmetric since if two integers x and y have the same remainder after being divided by 12, then y and x have the same remainder after being divided by 12. And it's transitive, since if x~y, and y~z, the x~z.
This partitions Z into 12 equivalence classes, i.e. two integers either have the same remainder after being divided by 12 or they do not, they are either in the same equivalence class or they are not.
For example: 0, 12, 48, and -36 are all in the same equivalence class, since:
* 0/12 = 0 with a remainder of 0
* 12/12 = 1 with a remainder of 0
* 48/12 = 4 with a remainder of 0
* -36/12 = -3 with a remainder of 0
We will call this equivalence class for the time being [12] (we could have equally chosen it to have been [0] or [48] etc, which we'll show later; our choice is specific to the clock).
The equivalence class that contains 1 will be denoted [1] for now; it is the subset of Z that contains {..., -23, -11, 1, 13, 25, ...}, i.e. all numbers of the form n*12 +1, where n is an integer. The equivalence class that contains 2 will be denoted [2]; it is the subset of Z that contains {..., -22, -10, 2, 14, 26, ...}. Likewise, there are distinct equivalence classes [3] through [11].
Interestingly enough, we can "add" these equivalence classes; we will denote this kind of addition by ⊕ for now to emphasize that the operation isn't identically the the operation we know and love (but it has many of the same properties).
We will define this addition as follows: [a]⊕[b] is equal to the set of all numbers a+b, such that a is a member of [a] and b is a member of [b]. (For interest's sake, in set-theoretic notation, this is written: [a]⊕[b] = {a+b: a∈[a], b∈[b]}. This reads, "The set [a]⊕[b] equals the set of elements 'a+b' such that a is a member of [a] and be is a member or [b].")
This definition implies: [a] ⊕ [b] = [a+b] (Why? Think about it for yourself a little; I'll prove it shortly.)
What is [12]⊕[12]?
Answer: [12]. Why? Because [12]⊕[12] is the set of all integers a+b such that both a and b are members of [12]. Since we can write a=n*12 and b=m*12, where n and m are some integers, we can easily show that a+b = n*12 + m*12 = (n+m)*12, which is another member of [12] since it has remainder 0 when divided by 12. This works for all a,b in [12] and so [12]⊕[12] = [12].
How about [z]⊕[12]? This is the set of all integers a+b such that a ∈ [z] and b ∈ [12] (this notation reads "b a member of [12]"). So we can write a = n*12 + z, and b = m*12, such that a+b = n*12 + z + m*12 = (n+m)*12 + z. This element is a member of the equivalence class [z] since it has a remainder of z when divided by 12.
So adding [12] to any other equivalence class gives back that equivalence class: [z]⊕[12]=[z]. (This sounds like an identity element to me!)
More generally, [a]+[b] = [a+b] since any member from [a] can be written n*12+a and any member from [b] can be written m*12+b, where n and m are integers. And so any member from [a]⊕[b] has the form: n*12 + a + m*12 + b = (n+m)*12 + (a+b), which has a remainder of (a+b) when divided by 12 and thus is a part of the equivalence class denoted [a+b].
So this operation we defined to add together equivalence classes always gives us back another equivalence class. If we define a set whose elements are these equivalence classes and couple it with ⊕, the operation we've been using to "add" equivalence classes, then we have the group we call Z modulo 12 (call it "Z mod 12" to sound cool). Let's denote it Z/[12]. More technically, we would denote this group by the pairing (Z/[12],⊕). But since we're all aware that we're talking about Z/[12] as a group, the simpler notation isn't too bad, especially because, like the integers, multiplication doesn't meet the requirements of making Z/[12] a group, so Z/[12] isn't even very ambiguous concerning the group operation.
It's a finite group: it has 12 elements. Z itself is an infinite group, since its elements are never-ending. Therefore we systematically collapsed an infinite set to one of 12 elements. We rock.
How do we know Z/[12] is a group? For one, the operation meets the closure property, as shown. Two, this group has an identity, namely [12], as demonstrated above. Three, it satisfies associativity: [a]⊕([b]⊕[c]) = ([a]⊕[b])⊕[c] (can you write down a proof?). And, finally, it is closed under inverses (remember an inverse is an element such that a#inv(a) = identity). For example, the inverse of [10] is [2] since [10]⊕[2] = [12], which is the identity element of Z/[12]). What is the inverse element of [5]?
One last things brings us to the clock: simply forget about the braces and drop the funky notation for addition, we don't need 'em.
So, [a]⊕[b] --> a+b.
The braces were important so that we could remember that the elements of Z/[12] are really equivalence classes of Z. These equivalence classes were what enabled us to define an operation that makes Z/[12] a group, thus a sound mathematical system like the integers themselves. But they aren't necessary now that we know [10]⊕[5] = [2]. The braces just become cumbersome. We can just write 10+5=2, if it's clear we're working in Z/[12]. The same goes for the notation of addition in Z mod 12: at first, it reminded us that the type of addition we are using isn't the familiar one, but once we're used to that concept, we don't continually need the reminder.
So, remember, the next time it's 10am and you're telling your friend you got work in 5 hours at 3pm, just know you're adding equivalence classes of the integers in a very formal way. It is mathematically sound that 10 + 5 can equal 3, not just a wacky convention we adhere to (although, like usual with conventions, it is an arbitrary one). One thing you may have noticed: the numbers 0 through 11 in Z/[12], although represented the same, are not identical to the numbers 0 through 11 in Z. They also aren't identical to the numbers 0 through 11 in Z/[13] or Z/[25].
For example, in Z/[12], 7+7 = 2, since 7+7=14 in Z and 14 has remainder 2 when divided by 12. Also, using a generalization of multiplication (which we'll cover when we go over rings) emphasizes differences too: how about the fact that in Z/[12], 7^3 = 7. Why? Well, 7*7 = 1 since 7*7 in Z is 49 and 49 has remainder 1 when divided by 12. And so, 7^3 = (7*7)*7 = 1*7 = 7. But in Z, 7^3 = 343.
Another example: in Z an odd number times an odd number equals an odd number. But in Z/[25], 3*9 = 2. What gives!? This is the awesomeness of adding new algebraic systems to your arsenal.
Anyway! This has taken much more time to write than I imagined it would. Damn. Hopefully somebody gets something out of this. Please ask questions. I'd love to explain more or better. Next week we'll talk more about Z/[12] and in what ways it's related to Z. We'll also discuss arbitrary groups Z/[n]. We'll find out how these things are all examples of "quotient groups."
-Kevin
P.S. some further reading may include:
binary operations (1)
binary operations (2)
basic set theory
modular arithmetic
groups
equivalence relations
