Edit made on July 18, 2009 by ColinWright at 18:57:59
Deleted text in red /
Inserted text in green
WW
HEADERS_END
An Equivalence Relation is a binary relation * on a set A which has the following properties:
An Equivalence Relation is a binary relation EQN:\equiv on a set A which has the following properties:
For all a, b and c EQN:\epsilon A
Transitivity: if a * b and b * c then a * c
* Transitivity: if EQN:a\equiv{b} and EQN:b\equiv{c} then EQN:a\equiv{c}
* Symmetry: if EQN:a\equiv{b} then EQN:b\equiv{a}
* Reflexivity: EQN:a\equiv{a}
Reflexivity: a * a
Once you have an equivalance relation on a set, you can take one element (say, x) and look at all
the elements that are equivalent to it. This is called the !/ equivalence class !/ of x.
Symmetry: if a * b then b * a
* EQN:E(x)=\{y\in{A}:~y{\equiv}x~\}
It's clear that a finite set can be divided up into a finite number of non-empty, disjoint
sets, each of which is an equivalence class (of some element). Most people would agree that
a countably infinite set can also be divided up into equivalence classes.
It's less clear that dividing up an uncountably infinite set can always be accomplished.
This has a connection with the Axiom of Choice.