Scribd
Upload
532 views1 page

Relations, Equivalence Relations, and Partitions

The document discusses relations, equivalence relations, partitions, and the fundamental theorem connecting equivalence relations and partitions. It defines relations as subsets of Cartesian products of sets, and equivalence relations as relations that are reflexive, symmetric, and transitive. Equivalence classes are defined as sets of elements related by an equivalence relation. The document provides examples of the congruence relation modulo m and its equivalence classes. It defines partitions as collections of nonempty sets with no overlaps whose union is the original set. The fundamental theorem states that the equivalence classes of an equivalence relation form a partition, and a partition defines an equivalence relation based on elements belonging to the same subset.

Uploaded by

Mohammad Reza Khalili Shoja
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
532 views1 page

Relations, Equivalence Relations, and Partitions

The document discusses relations, equivalence relations, partitions, and the fundamental theorem connecting equivalence relations and partitions. It defines relations as subsets of Cartesian products of sets, and equivalence relations as relations that are reflexive, symmetric, and transitive. Equivalence classes are defined as sets of elements related by an equivalence relation. The document provides examples of the congruence relation modulo m and its equivalence classes. It defines partitions as collections of nonempty sets with no overlaps whose union is the original set. The fundamental theorem states that the equivalence classes of an equivalence relation form a partition, and a partition defines an equivalence relation based on elements belonging to the same subset.

Uploaded by

Mohammad Reza Khalili Shoja
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Math 347

Relations, Equivalence Relations, and Partitions

A.J. Hildebrand

Relations, Equivalence Relations, and Partitions


[See also the beginning of Chapter 7, pp. 140141, of the text.]

Relations
A relation from a set S to a set T is a subset of S T .
A relation on a set S is a relation from S to S, i.e., a subset of S S.
Notation: Given a relation R on S (i.e., a subset R S S), we write x y if (x, y) R. A relation can
be described by specifying the meaning of x y.
Example: Congruence relation modulo m. Given a positive integer m, the congruence relation modulo
m is the relation on the set S = Z defined by x y x y mod m , or equivalently, by the subset R =
{(x, y) Z Z : x y mod m} of Z Z.

Equivalence relations and equivalence classes


Equivalence relation on a set S: A relation on S that satisfies the following properties:
Reflexive: For all x S, x x.
Symmetric: For all x, y S, x y implies y x.
Transitive: For all x, y, z S, x y and y z implies x z.
Equivalence classes: If is an equivalence relation on S and x S, the set
Ex = {y S : x y}
is called the equivalence class of x. Other notations for the equivalence class Ex of x are the bracket and bar
notations, [x] and, x.
Example: Congruence relation modulo 3. The congruence relation modulo 3 is an equivalence relation
with the following equivalence classes:
E0 = 0 = {0, 3, 6, 9, . . . , 3, 6, 9, . . . },
E1 = 1 = {1, 4, 7, 10, . . . , 2, 5, 8, . . . },
E2 = 2 = {2, 5, 8, 11, . . . , 1, 4, 7, . . . }.
Every integer belongs to exactly one of these three classes, and any other equivalence class x is equal to one of
the above classes. For example, the equivalence class of 3, i.e., 3, is the same as 0.

Partitions of a set
Let S be a set. A collection of (finitely or infinitely many) nonempty subsets A1 , A2 , . . . of S is called a partition of
S if it has the following properties:
No overlaps: The sets Ai are pairwise disjoint; i.e., Ai Aj = if i 6= j.
Union is all of S: The union of all the sets Ai in the partition is S, i.e., A1 A2 A3 = S.

Equivalence relations and partitions: The Fundamental Theorem


The following fundamental result connects the seemingly unrelated concepts of an equivalence relation on a set S
(which, formally, is a subset of S S with certain properties) and a partition on S (which is a collection of subsets of
S with certain properties).
From equivalence relations to partitions: Given an equivalence relation on a set S, the set of distinct
equivalence classes forms a partition of S. That is, we have: (i) For any x, y S, the associated equivalence
classes Ex and Ey are either equal (i.e., Ex = Ey ) or disjoint (i.e., Ex Ey = ). (ii) For any x S there exists
an equivalence class that contains x (namely, the class Ex ).
From partitions to equivalence relations: Given a partition of S into sets A1 , A2 , . . . , An , the relation
defined by x y x and y belong to the same set Ai from the partition is an equivalence relation on
S.

You might also like