Saunas and Equivalence Classes

Yesterday I went to a 岩盤浴　place called Peony with a Japanese friend I met a while back. A ganbanyoku is a sauna. You take a shower, put on a yukata-type outfit, and then go lie down on a hot rock floor for fifteen minutes. It's unbelievably hot in there, so the sweat just pours off you, but it's so humid that it doesn't evaporate, so you have to keep wiping the sweat off with a towel. Then you go rest in a normal room and drink water. Then you go back to the sauna, then rest again, and do this little cycle a few times or until your time runs up. Supposedly this detoxifies you, but I have my doubts. Anyway, it feels good. I'm sure I've retoxified my body by now, anyway, by eating Italian food. Let's talk about modular arithmetic.

The other day I was writing about equivalence relations and trying to get John to bring up modular arithmetic without mentioning it specifically, but instead he came up with a bebop equivalence relation for primes. If you recall, an equivalence relation is a relation on A X A that generalizes our idea of equivalence. One thing I didn't mention that is a direct result of equivalence relations is equivalence classes. You see, an equivalence relation on A (this is shorthand) partitions A into equivalence classes. A partition P of A is a family (just a set) of subsets of A such that:

1. If D and E are elements of P, then either D = E or D and E are disjoint (I can't make an intersect symbol because I don't know all the fancy code for that kind of thing, but disjoint means D and E share no common elements).

2. The union of all D's in P is A. Again, I can't make a proper union symbol, and here I doubt one exists because I would need a subscript.

That may seem kind of confusing, but it's actually intuitive. It just means that we are splitting A up into smaller sets, with each being separate from the other, like cutting up a pie or other delicious concoction that one might cut.

The nature of equivalence relations gives us a partition because if (a, b) in R and (b, c) not in R, then (a, c) not in R. That is, all the things that are equal will go into one and only one of these subsets in our partition. For a more concrete example, look at the non-negative integers [this is NU{0}, if you prefer]. We can partition this set using the standard equals relation. All the things will go into one and only one subset, for example 4 is a member of {4} only, 100 is a member of {100} only. In this case, each subset (an equivalence class) only has one member, but that's not necessarily true with every equivalence relation.

For example, I mentioned that similarity is an equivalence relation on the set of triangles, and walked through a proof of that. An equilateral triangle with side length 1 is "equal" under this relation to an equilateral triangle with side length 2, or with side length 3 or pi or a bazillion. All of these triangles thus fall into the equilateral equivalence class. A 3-4-5 right triangle, however, falls into a different equivalent class, the same class occupied by a 6-8-10 right triangle, as well as any other 3x-4x-5x right triangle. Every triangle falls into exactly one equivalence class, though every equivalence class contains an infinity of triangles. For those curious, each equivalence class is uncountable, and the partition itself is also uncountable. Can you picture a pie cut into an uncountable number of pieces?

So, what does modular mean, and what does arithmetic have to do with anything? Let's define an equivalence relation on the set of integers. First, we will choose arbitrarily an integer that we like. For me, such an integer is 3. If we take any integer (this includes negative integers, but you might want to consider non-negative ones first for simplicity's sake) and divide by 3, we are left with a remainder. Then let's say two integers a and b are equivalent [ (a,b) in R] if and only if the remainder they leave when divided by 3 is equal. So, 0 = 3 = 6 =...; 1 = 4 = 7 =...; 2 = 5 = 8 =...

Like a good mathematics student, we should assure ourselves and our readers that we have not in fact pulled a fast one, but that we have a bona fide equivalence relation.

1. Obviously a leaves the same remainder as a, so reflexivity on A (in this case Z) holds.

2. If a leaves the same remainder as b, obviously b leaves the same remainder as a, so symmetry is a go.

3. If a and b leave the same remainder, and b and c leave the same remainder, then a and c clearly leave the same remainder, so transitivity is also confirmed.

Following our previous reasoning, since we have an equivalence relation, we should have naturally defined equivalence classes. What are they? I've already mentioned them up above, though not explicitly. They are [0] = (0, 3, 6, ...); [1] = (1, 4, 7, ...); and [2] = (2, 5, 8, ...). It is worth noting that [0], [1], and [2] are themselves sets, so we can think of P = ([0], [1], [2]) as a space of sets on its own, and will want to.

On to the arithmetic, the queen of mathematics. Let's define arithmetical operations on this set, which I shall call Z3 for obvious reasons, in the most natural way. We'll define addition of two of these elements (the equivalence classes from above) thusly

[a] + [b] = [c + d] where c is any element of [a] and d is any element of [b]. Again, have I pulled a fast one on you? That is, is this operation well defined [can I really choose any two elements and get the same result]?

The answers are no and yes, respectively, and here's proof.

If c in [a], then c = 3n + a. Similarly, d = 3m + b. The numbers n and m stand for some integer.

Then c + d = 3(n + m) + a + b. Then [c + d] = [a + b].

We can define subtraction and multiplication the same way, it turns out, but I am not going to work that out for you.

To concretize again, what does that mean here? If I could make you a pretty chart, I would but, forgoing the bracket notation, as is standard in this case, we have

0 + 0 = 0; 0 + 1 = 1; 0 + 2 = 2

1 + 0 = 1; 1 + 1 = 2; 1 + 2 = 0 [[3] = [0], since we are concerned with the equivalence class]

2 + 0 = 2; 2 + 1 = 0; 2 + 2 =1

Some things to notice here:

0 + a = a + 0 = a. In other words, 0 is the identity element of this operation.

a + b = b + a. In other words, + is a commutative operation.

For every a in Z3, there exists an inverse of a in Z3. That is, there is c such that a + c = 0, the identity element. For a = 0, c = 0; a = 1, c = 2; a = 2, c = 1. Subtraction can be defined as the addition of the inverse, which is exactly equivalent to the intuitive way of defining subtraction.

One can also work out that + is associative, but that's rather tedious to type out. What we have here is what is called a group, but I'm not going to get into all that.

As I mentioned before, we can define multiplication intuitively, as well. So, we have

X 0 1 2
0 0 0 0
1 0 1 2
2 0 2 1

Again, we find that multiplication is commutative and associative, which should come as no surprise, since our intuitive definition here is derived from normal operations, which are themselves commutative and associative. We also notice that 0(a) = 0, regardless of a.

Under multiplication, so defined, 1 acts as the identity. That is 1(a) = a.

Another thing we might notice in Z3 is that if a is not 0, a has an inverse. We might also notice that if a and b are both non-zero, then ab is also non-zero.

That's all fine and dandy, but as you might suppose, we can generalize to positive integer here instead of 3. That is, we can create a space Zn for any positive (actually non-zero will do) integer n. The next easiest example, and one that suits my purposes, is Z4.

Addition, Z4 style

+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2

Multiplication

x 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1

Addition is all fine and dandy, and again we have a group, but take a closer look at the 2 row (or column) of the multiplication table. See anything weird?

Firstly, 2(2) = 4 = 0. That's a little odd from our usual experience with multiplication, since 2 isn't 0.

Secondly, there's no inverse for 2. That is, 1 still acts as the identity, but there's no way to get a c in Z4 such that 2c = 1. Weird, right? What this means is that for some reason Z3 is pretty while Z4 is not. In more precise terms, there are certain types of equations that are solvable in one while they are not necessarily solvable in others. So my question to you is what is the difference here? I know the answer and I'm pretty sure John does, too, but think about it.