Relations

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last updates: 1 July 2011

Definitions

Let $S$ be a set.

• A relation on $S$ is a subset of $S\times S$. Write $s_1\sim s_2$ if the pair $(s_1,s_2)$ is in the subset.
• A relation $\sim$ on $S$ is reflexive if $\sim$ satisfies $$\text{if}s\in S\text{then}s\sim s.$$
• A relation $\sim$ on $S$ is symmetric if $\sim$ satisfies $$\text{if}{s}_1,s_2\in S\text{and}{s}_1\sim s_2\text{then}{s}_2\sim s_1.$$
• A relation $\sim$ on $S$ is transitive if $\sim$ satisfies $$\text{if}{s}_1,s_2,s_3\in S\text{and}{s}_1\sim s_2\text{and}{s}_2\sim s_3\text{then}{s}_1\sim s_3.$$
• An equivalence relation on $S$ is a relation on $S$ that is reflexive, symmetric and transitive.

Examples. Let $S$ be the set $\{1,2,6\}$.

(a)   $R_1=\left\{\right(1,1),(2,6),(6,1\left)\right\}$ is a relation on $S$.

(b)   $R_1$ is not reflexive, not symmetric and not transitive.

(c)   $R_2=\left\{\right(1,1),(2,6),(6,1),(2,1\left)\right\}$ is a relation on $S$.

(d)   $R_2$ is transitive but not reflexive and not symmetric.

Let $S$ be a set.

• Let $\sim$ be an equivalence relation on $S$ and let $s\in S$. The equivalence class of $s$ is the set $$\left[s\right]=\{t\in S|t\sim s\}.$$
• A partition of a set $S$ is a collection of subsets $S_{\alpha }$ such that

  (a)   if $s\in S$ then there exists $\alpha$ such that $s\in S_{\alpha }$, and

  (b)   if $S_{\alpha }\cap S_{\beta }\ne \varnothing$ then $S_{\alpha }=S_{\beta }$.

Proposition (eqrelptn) shows that the concepts of an equivalence relation on $S$ and of a partition on $Sare\; essentially\; the\; same.\; Each\; equivalence\; relation\; on$ S$determines\; a\; partition\; and\; vice\; versa.$

Example. Let $S=\{1,2,3,\dots ,10\}$. Let $\sim$ be the equivalence relation determined by

$1\sim 5$,	$2\sim 3$,	$9\sim 10$,
$1\sim 7$,	$5\sim 8$,	$10\sim 4$,

Since we are requiring that $\sim$ is an equivalence relation, we are assuming that we have all the other relations we need such that $\sim$ is reflexive, symmetric and transitive;

$1\sim 1$,	$2\sim 2$,	…	$9\sim 9$,	$10\sim 10$,
$5\sim 7$,	$7\sim 8$,	$7\sim 5$,	$5\sim 1$,	…

The equivalence classes are given by $$\begin{array}{rcl}\left[1\right]=\left[5\right]=\left[7\right]=\left[8\right]& =& \{1,5,7,8\},\\ \left[2\right]=\left[3\right]& =& \{2,3\},\\ \left[6\right]& =& \left\{6\right\},\text{and}\\ \left[4\right]=\left[9\right]=\left[10\right]& =& \{4,9,10\},\end{array}$$ and the sets $$S_1=\{1,5,7,8\},S_2=\{2,3\},S_3=\left\{6\right\},\text{and}{S}_4=\{4,9,10\}$$ form a partition of $S$.

Notes and References

These notes are an updated version of notes of Arun Ram from 1994.

References

[Ram] A. Ram, Notes in abstract algebra, University of Wisconsin, Madison 1993-1994.

[Bou] N. Bourbaki, Algèbre, Chapitre 9: Formes sesquilinéaires et formes quadratiques, Actualités Sci. Ind. no. 1272 Hermann, Paris, 1959, 211 pp. MR0107661.

[Ru] W. Rudin, Real and complex analysis, Third edition, McGraw-Hill, 1987. MR0924157.

page history