Archive for July, 2008

Nothing Fuzzy About It

Jeans & Tees

\bulletBlake Stacey’s “Survey For Curmudgeons”.
\bulletEfrique Ecstathy on “Fighting Mathiness”.
\bulletTimothy Chow on “Out-of-print math books” (at What’s New).
\bulletMark C-C’s take on repeated addition.
\bulletOh, and Carnival #37, at Logic Nest.

Be Fruitful

When considering divisibility properties it is convienient to partition the set {\Bbb N} into subsets— each with some “nice” property. The reader is of course familiar with the sets E = \{ 0, 2, 4, \ldots \} and O = \{1, 3, 5 \ldots \} of even numbers and odd numbers. Together these sets form a partition of {\Bbb N}—this means that each element of \Bbb N occurs in exactly one of the given subsets (in other words, “Every natural number is either even or odd (but not both).”).

The even numbers share the property of being divisible by two (in symbols, “If n \in E, then 2 \mid n”). This is exactly what it means to be even. The odd numbers obviously share the opposite property of not being divisible by two. Another way to say the same thing is that when any element of O is divided by two, there will always be a remainder (namely 1). For that matter, we could say that the even numbers all have remainder 0. The point here is that the “even-or–oddness” (the parity) of a natural number can be thought of in terms of what happens when you divide by two—specifically, what remainder you get.

If natural numbers a and b have the same parity (both are even or both are odd), we could say they are “equivalent in ‘two-mode’.” The formal symbolism for this is a {\mathrel{\equiv_2}} b. This is pronounced “a is equivalent mod 2 to b” (or, as some authors prefer, as “a is equivalent to b (mod two)”)\null^*. It means simply that the numbers a and b have the same remainder when you divide them by two.

Footnote: \null^*The notation is essentially that of C. F. Gauss in his masterpiece Disquisitiones Arithmeticae published in 1801. Gauss wrote in Latin and used the word modulus (small measure) for the “number-to-divide-by”.
Formally, one speaks of equivalence modulo two”, but this is usually shortened to “mod two”.

Thus, for example we have 37 {\mathrel{\equiv_2}} 2001, 1776 {\mathrel{\equiv_2}}0, and 52 \not{\mathrel{\equiv_2}} 25.

Suppose we were to partition \Bbb N instead into three sets. Let’s call the sets X, Y, and Z. Imagine going through the natural numbers one at a time and “counting off”:

X Y Z
0 1 2
3 4 5
6 7 8 …

The resulting partition of \Bbb N is
X = \{ 0, 3, 6, \ldots \} \qquad Y = \{ 1, 4, 7, \ldots \} \qquad  Z = \{ 2, 5, 8, \ldots \} . Each of these sets can be characterized by looking at the remainders of its elements when divided by three—the elements of X have remainder zero, those of Y have remainder one, and those of Z have remainder two.

So to say that two natural numbers belong to the same set of the partition is the same as saying that they have the same remainder when divided by three. The notation for this is a{\mathrel {\equiv_3} } b (“a is equivalent mod three to b”). For example, 4 {\mathrel {\equiv_3} } 7, 29 {\mathrel {\equiv_3} }101, and 6 \not{\mathrel {\equiv_3} }2.

The same process we have used for the numbers (or moduli—the plural of modulus) two and three can of course be used for any larger natural number. The general notation is of course a {\mathrel {\equiv_n}} b, meaning that a and b have the same remainder when you divide each of them by n.

All of this probably seems pretty abstract and you might very well be wondering if any of it can be used for anything. But I now claim that equivalence mod twelve is very much an everyday idea! Consider the following problem: “I start work at 9 o’clock and work for 8 hours. What time is it when I finish work?” Of course the answer is not “17 o’clock” but rather “5 o’clock”, the point here being that 17 {\mathrel {\equiv_{12}} } 5. To make the connection with our earlier discussion more explicit, we can once again partition the natural numbers into sets:

12:00 = {0, 12, 24, 36, … }
01:00 = {1, 13, 25, 37, …}
02:00 = {2, 14, 26, 38, … }

Modular arithmetic is sometimes even called “clock arithmetic” because of this familiar example. What modulus should we use to consider minutes rather than hours?

Readers familiar with a certain amount of geometry might recognize another application of modular arithmetic in the concept of adding angles: 270^\circ + 180^\circ = 90^\circ,
for example, because degree measures ({}^\circ) are defined using mod 360.

Notice that these examples involve the concept of addition. How does this connect with our earlier examples? Well, the rules for addition mod two are actually quite well known: E + E = E \quad E + O = O \quad O + O = E \quad O + E = O (“Even plus even is even, …”). Any even number added to any even number gives an even answer. The point here is that whenever we have to add two numbers, we can tell which set the answer is in whenever we know which sets the original numbers are in.

The same idea can be applied for the “mod 3” sets we have called X, Y, and Z: for example, we could say that Y + Z = X, meaning that whenever we add an element of Y and an element of Z, the answer will be in X.\null^*

\null^*Look at enough examples to become convinced or consider the following
Proof:
Let y \in Y and z \in Z.
Then there exist n \in {\Bbb N} and m \in {\Bbb N} such that y = 3n + 1 and z = 3m + 2 (i.e., y is one more than a some multiple of 3 and z is two more than some multiple of three).
We then have
y+z = 3n+1 + 3m+2
=3n+3m+3
=3(n+m+1).
This number is a multiple of three, so y + z \in X.

The first mathematics we learned as children was how to count: “One, two, three. . .” (or “Un, deux, trois. . .” or what have you). Only later did we learn about other kinds of numbers: fractions and negative numbers, for example. The counting numbers are thus the most “natural”, and the set \{1, 2, 3, \ldots\} is sometimes called the set of natural numbers. However, for certain technical reasons it’s convenient to include zero and so we define the set of natural numbers as {\Bbb N} = \{ 0, 1, 2, \ldots \}.

The set brackets “\{” and “\}” tell us to consider the collection of things between them as one object—namely a set. The symbol “{\Bbb N}” is just an abbreviation to allow us to refer to this object concisely. The elements of a set are the “things” in the collection. The symbol “\in” is pronounced “is an element of”, so for example 37 \in {\Bbb N} is an abbreviation for the sentence “Thirty-seven is an element of the set of natural numbers.”.

The ellipses ( … ) in the definition of {\Bbb N} tell us to continue the pattern displayed. The result is an infinite set—one with no last element. Ellipses are also sometimes used in defining finite sets, for example the familiar A = \{ a, b, c, \ldots , z \}.

The usual convention is to use capital letters to refer to sets. To read the definition {\Bbb N} = \{0, 1, 2, \ldots \} out loud, you could say, “{\Bbb N} is the set whose elements are zero, one, two, and so on forever.” The formal way to pronounce the symbol {\Bbb N} is “the set of natural numbers”. Usually, unless there is some need to be precise, one simply says “en”.

This can be trickier than it might appear because it’s common to use “n” as a variable. The convention here is that lower-case letters refer to numbers. So one can say, for example, “If n \in {\Bbb N}, then n must be either even or odd”. This should be pronounced “If en is a natural number, then …”.

The slash “/” is used to denote negation, as in 1 \not= 2. This idea is common even outside of mathematics, where we find “\oslash” (meaning “no”) on street signs, for example. So it shouldn’t come as any surprise that {1 \over 2} \not\in {\Bbb N} stands for the (true) sentence “One-half is not an element of the set of natural numbers.” (or just “one-half isn’t in {\Bbb N}” or some such variation).

There are several other common ways to say “{1 \over 2} \not\in {\Bbb N}”: for example, “Two doesn’t go into one” or “One is not a multiple of two”. Here is another way: 2 \not | 1. This is pronounced “Two does not divide one”. In general, whenever we have natural numbers n and m we can say that n divides m, and write n \mid m, whenever {m \over n} \in {\Bbb N}. We can also say in this case that n is a factor of m, or that n is a divisor of m.

Thus, for example, 11 \mid 209, because {209 \over 11} = 19 and 19 \in {\Bbb N}. This can be rephrased slightly as “because 209 = 11 \cdot 19 and 19 is a natural number”. But 11 \not | 73 because there is no natural number j with 73 = 11 \cdot j. In other words, because {73 \over 11} \not\in {\Bbb N}.

Two special cases involve zero. Suppose we have n \in {\Bbb N} and n \not= 0. Then 0 \not | n and n | 0. To confirm these facts, look at the definition of “|”: since {0 \over n} = 0 and 0 \in {\Bbb N}, we get n|0 as advertised. But {n \over 0} \not\in {\Bbb N}. In fact {n \over 0} isn’t a number at all! Be careful when working with 0 to avoid thinking of the wrong special case.

In the original version [~1995] of this piece, several exercises follow (of course!). As of this moment, they’re too much trouble to reproduce here. Exercise: find an expert user of the various notations and discuss.

Back From The Dead

Nonblogs

\bulletBrian Rude doesn’t know where to put the hyperlinks. So what. Plenty of good math-ed stuff there anyhow. I first spotted this a couple years ago while reading HOLD’s Ten Myths page.
\bulletI already cited Jerome Dancis a while back. So I’m putting the link here with the others so I’ll know where to find it later.
\bulletThen there’s Lee Lady. I seem to’ve started with this longish memoir; you could do worse. Spotted at D. R. Wilkins’s links page.
\bulletI found out about Steele’s Rants over at Isabel’s a while back.

Egosurfing

\bulletThe Arte y Pico award (aka an Interesting Blogroll) at WWIUT?.
\bulletComments on an announcement of the Riemann Hypothesis at GPD.
\bulletDenise Let’s Play! surveys Math History on the Net.
\bulletHere in honor of the upcoming ICME are newsletters for the HPM Group (History and Pedagogy of Maths). Spotted at convergence.