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.

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

(a)   R1 = { (1,1), (2,6), (6,1) } is a relation on S.
(b)   R1 is not reflexive, not symmetric and not transitive.
(c)   R2 = { (1,1), (2,6), (6,1), (2,1) } is a relation on S.
(d)   R2 is transitive but not reflexive and not symmetric.

Let S be a set.

(a)   Let S be a set and let be an equivalence relation on S.
(a)   Then the set of equivalence classes of the relation is a partition of S.
(b)   Let S be a set and let {Sα} be a partition of S.
(b)   Then the relation defined by st if s and t are in the same Sα is an equivalence relation on S.

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

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

15, 23, 910,
17, 58, 104,
Since we are requiring that is an equivalence relation, we are assuming that we have all the other relations we need such that is reflexive, symmetric and transitive;
11, 22, 99, 1010,
57, 78, 75, 51,
The equivalence classes are given by [1] =[5]=[7] =[8] = {1,5,7,8}, [2]=[3] = {2,3}, [6] = {6},and [4]=[9]= [10] = {4,9,10}, and the sets S1 ={1,5,7,8}, S2 ={2,3}, S3 = {6}, and S4 = {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