We often wish to describe how two mathematical entities within a set are related. For example, if we were to look at the set of all people on Earth, we could define "is a child of" as a relationship. Similarly, the operator defines a relation on the set of integers. A binary relation, hereafter referred to simply as a relation, is a binary proposition defined on any selection of the elements of two sets.
Formally, a relation is any arbitrary subset of the Cartesian product between two sets and so that, for a relation , . In this case, is referred to as the domain of the relation and is referred to as its codomain. If an ordered pair is an element of (where, by the definition of , and ), then we say that is related to by . We will use to denote the set
In other words, is used to denote the set of all elements in the codomain of to which some in the domain is related.
To denote that two elements and are related for a relation which is a subset of some Cartesian product , we will use an infix operator. We write for some and .
There are very many types of relations. Indeed, further inspection of our earlier examples reveals that the two relations are quite different. In the case of the "is a child of" relationship, we observe that there are some people A,B where neither A is a child of B, nor B is a child of A. In the case of the operator, we know that for any two integers exactly one of or is true. In order to learn about relations, we must look at a smaller class of relations.
In particular, we care about the following properties of relations:
- Reflexivity: A relation is reflexive if for all .
- Symmetry: A relation is symmetric if for all .
- Transitivity: A relation is transitive if for all .
One should note that in all three of these properties, we quantify across all elements of the set .
Any relation which exhibits the properties of reflexivity, symmetry and transitivity is called an equivalence relation on . Two elements related by an equivalence relation are called equivalent under the equivalence relation. We write to denote that and are equivalent under . If only one equivalence relation is under consideration, we can instead write simply . As a notational convenience, we can simply say that is an equivalence relation on a set and let the rest be implied.
Example: For a fixed integer , we define a relation on the set of integers such that if and only if for some . Prove that this defines an equivalence relation on the set of integers.
- Reflexivity: For any , it follows immediately that , and thus for all .
- Symmetry: For any , assume that . It must then be the case that for some integer , and . Since is an integer, must also be an integer. Thus, for all .
- Transitivity: For any , assume that and . Then and for some integers . By adding these two equalities together, we get , and thus .
Remark. In elementary number theory we denote this relation and say a is equivalent to b modulo p.
Let be an equivalence relation on . Then, for any element we define the equivalence class of as the subset given by
Proof: Assume . Then by definition, .
- We first prove that . Let be an arbitrary element of . Then by definition of the equivalence class, and by transitivity of equivalence relations. Thus, and .
- We now prove that Let be an arbitrary element of . Then, by definition . By transitivity, , so . Thus, and .
As and as , we have .
Partitions of a set
A partition of a set is a disjoint family of sets , , such that .
Theorem: An equivalence relation on induces a unique partition of , and likewise, a partition induces a unique equivalence relation on , such that these are equivalent.
Proof: (Equivalence relation induces Partition): Let be the set of equivalence classes of . Then, since for each , . Furthermore, by the above theorem, this union is disjoint. Thus the set of equivalence relations of is a partition of .
(Partition induces Equivalence relation): Let be a partition of . Then, define on such that if and only if both and are elements of the same for some . Reflexivity and symmetry of is immediate. For transitivity, if and for the same , we neccesarily have , and transitivity follows. Thus, is an equivalence relation with as the equivalence classes.
Lastly obtaining a partition from on and then obtaining an equivalence equation from obviously returns again, so and are equivalent structures.
Let be an equivalence relation on a set . Then, define the set as the set of all equivalence classes of . In order to say anything interesting about this construction we need more theory yet to be developed. However, this is one of the most important constructions we have, and one that will be given the much attention throughout the book.