Equivalence Relations
Equivalence relations permeate mathematics with several salient examples readily available:
 Residue classes [a]_{N} consist of all numbers congruent (equivalent) modulo N
 a negative number is a set of all equivalent pairs
(a, b) of integers witha < b, where two pairs(a, b) and(c, d) belong to the same set (equivalence class) iffa + d = b + c  a rational number is a set of all equivalent pairs
(a, b) of integers, where two pairs(a, b) and(c, d) are equivalent iffad = bc  an irrational number is an equivalence class of sequences r_{1}, r_{2}, r_{3}, ... of
rational numbers, where two sequences {r_{i}} and {s_{i}} are equivalent iff they there difference converges
{r_{i}  s_{i}} to 0 as i→∞.
Examples are many and one may be inclined to think that the reason I do not cite more is that the level of abstraction of such examples rises so quickly as to make them incomprehensible to a casual reader. This is quite possible. Why make it difficult? However, I'd like to give one additional example. What's really interesting about it is that every one knows about it, learns it starting, say, at the age of 5, uses it virtually every minute. As a matter of fact, you came across it as you were reading the previous sentence.
What is this equivalence relation? This ubiquitous abstraction is the notion of integer as used in counting. Assume, in a foreign country whose language you do not speak (and starving for this reason), you ran into a McDonald's. You rush in but even in a foreign country not all of them are geniuses. The fellow there appears to react correctly to the word "hamburger" but you do not know how to say 5. What do you do? I bet you'll raise an open hand and turn the palm towards the fellow so that she'll see all your spread fingers clearly. And the fellow, an unlikely genius, will understand you perfectly well. Unlike a mathematical concept, this one is not strictly defined, but is used so universally we forget what counting and numbers are about.
Somehow, by the age of five, we know that
is equivalent to 
while
is not equivalent to 
But then again
is equivalent to 
You can put it in many different ways. For example, you can say that
 5 is a common something that five bear cubs and five sea otters got but six otters did not. (The something at hand is often called the property of fiveness.)
 5 is what some sets have in common with the number of fingers on my hand
 5 is the set of all sets that could be put into a 11 correspondence with the set of fingers on the picture above and to the right
 5 is the set of all sets that are equivalent to the set of fingers on my hand, where two sets are called equivalent when a 11 correspondence exists between their elements
Mathematicians prefer the last two definitions. The last one enables me to point out how omnipresent equivalence relations actually are. People invent symbols (known as words) to denote some objects. Mathematicians also invent words, but, in addition, they attempt to explain the meaning they input to the word. They try to make it intuitive. They achieve this by distilling common usage into a simple, intuitive abstraction. Compare:
What's a cow? Here what Webster's New Collegiate Dictionary says:  Equivalence relation is a binary (in the sense that it relates two elements) relation that satisfies the following three properties:  
1. the mature female of cattle (genus Bos) or of any animal the male of which
is called bull (as the moose) 2. a domestic bovine animal regardless of sex or age 

Now you know that when you call somebody a cow the age does not count (although, why would you be talking to a cow?) On the other hand, if it came to your needing to look up the word cow in the first place, do you have a notion of what cattle, bovine, genus, moose are? Can you be sure that Bos is not a typo and the word Boss has been actually meant?
In math you may want to ask why these three properties have been selected to represent equivalence between sets? If you are indeed curious, try to think of other properties common to all equivalence relations you may think of. I can only offer a very lame excuse: over manymany years mathematicians agreed that the above three are the simplest and the commonest.
An important fact about equivalence relations is expressed by the following
Theorem
Let ∼ be an equivalence relation defined between elements of a set A. Then the set A can be written as a union ∪A_{ t} of pairwise disjoint subsets
a∼b iff there exists A_{ t} such that a∈A_{ t} and b∈A_{ t}.
There are several ways to express the fact that a ∼ b. For example:
 a is equivalent to b.
 a and b are equivalent.
 a and b belong to the same equivalence class.
 Modular Arithmetic
 Chinese Remainder Theorem
 Euclid's Algorithm
 Pick's Theorem
 Fermat's Little Theorem
 Wilson's Theorem
 Euler's Function
 Divisibility Criteria
 Examples
 Equivalence relations
 A real life story
Contact Front page Contents Algebra
Copyright © 19962018 Alexander Bogomolny