Equivalence relations

Abbreviation: EqRel

Definition

An equivalence relation is a structure $\mathbf{X}=\langle X,\equiv\rangle$ such that $\equiv$ is a binary relation on $X$ (i.e. $\equiv\ \subseteq X\times X$) that is

reflexive: $x\equiv x$

symmetric: $x\equiv y\Longrightarrow y\equiv x$

transitive: $x\equiv y\text{ and }y\equiv z\Longrightarrow x\equiv z$

Remark: This is a template. If you know something about this class, click on the ``Edit text of this page'' link at the bottom and fill out this page.

It is not unusual to give several (equivalent) definitions. Ideally, one of the definitions would give an irredundant axiomatization that does not refer to other classes.

Morphisms

Let $\mathbf{X}$ and $\mathbf{Y}$ be equivalence relations. A morphism from $\mathbf{X}$ to $\mathbf{Y}$ is a function $h:A\rightarrow B$ that is a homomorphism: $x\equiv^{\mathbf X} y\Longrightarrow h(x)\equiv^{\mathbf Y}h(y)$

Definition

An equivalence relation is a qoset that is symmetric: $x\equiv y\Longrightarrow y\equiv x$

Examples

Example 1:

Basic results

Equivalence relations are in 1-1 correspondence with partitions.

Properties

Finite members

$\begin{array}{lr} f(1)= &1\\ f(2)= &2\\ f(3)= &3\\ f(4)= &5\\ f(5)= &7\\ \end{array}$ $\begin{array}{lr} f(6)= &11\\ f(7)= &15\\ f(8)= &22\\ f(9)= &30\\ f(10)= &42\\ \end{array}$

The number of (labelled) equivalance relations on an $n$ element set given by a sum of Stirlings formula (of the second kind).

see also http://www.research.att.com/projects/OEIS?Anum=A000110

The number of (nonisomorphic) equivalence relations is the number of partition patterns (= number of integer partitions).

see also http://www.research.att.com/projects/OEIS?Anum=A000041

Subclasses

Superclasses

[[Preordered sets]] supervariety

References