Equivalence Relations

Equivalence relations permeate mathematics with several salient examples readily available:

1. Residue classes [a]_N consist of all numbers congruent (equivalent) modulo N
2. a negative number is a set of all equivalent pairs (a,b) of integers with a<b, where two pairs (a,b) and (c,d) belong to the same set (equivalence class) iff a + d = b + c
3. a rational number is a set of all equivalent pairs (a,b) of integers, where two pairs (a,b) and (c,d) are equivalent iff ad = bc
4. an irrational number is an equivalence class of sequences r₁, r₂, r₃, ... of rational numbers, where two sequences {r_i} and {s_i} are equivalent iff they have limits as i and their limits coincide.

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

1. 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.)
2. 5 is what some sets have in common with the number of fingers on my hand
3. 5 is the set of all sets that could be put into a 1-1 correspondence with the set of fingers on the picture above and to the right
4. 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 1-1 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:

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 your neededing 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 many-many 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 _tA such that

ab iff there exists A _t such that aA _t and bA _t

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

Copyright © 1996-2008 Alexander Bogomolny