EquivalenceRelation

An Equivalence Relation is a binary relation $\equiv$ on a set A which has the following properties:

For all a, b and c $\epsilon$ A

Transitivity: if $a\equiv{b}$ and $b\equiv{c}$ then $a\equiv{c}$
Symmetry: if $a\equiv{b}$ then $b\equiv{a}$
Reflexivity: $a\equiv{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.

$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.

Last change to this page
Full Page history
Links to this page

Edit this page
(with sufficient authority)
Change password

Recent changes
All pages
Search

Equivalence Relation

Navigation