Relation

Definition


A relation {% R %} is a subset of {%A \times B%}. It is sometimes called a relation from {%A%} to {%B%}, in order to specify the ordering.
{% R \subset A \times B %}

Equivalence Relation


An equivalence relation {% R %} on a set {% S %} is a relation. Two elements of {% S %} that

  • {% (a, a) \in R %}
  • if {% (a, b) \in R %} then {% (b,a) \in R %}
  • if {% (a, b) \in R %} and {% (b,c) \in R %} then {% (a, c) \in R %}


{% (a,b) \in R %} is often written as
{% a \sim b %}

Partitions


A partition of a st {% S %} is a collection of disjoint sets {% A_i %} whose union is {% S %}
{% S = \bigcup_i A_i %}


Theorem
The equivalence classes of a given equivalence relation for a partition of the set over which the relation is defined.