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.
Equivalence relations[edit]
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.
Proof:
- 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
.
Q.E.D.
Remark. In elementary number theory we denote this relation
and say a is equivalent to b modulo p.
Equivalence classes[edit]
Let
be an equivalence relation on
. Then, for any element
we define the equivalence class of
as the subset
given by
![\left[a\right]=\left\{b\in X|a\sim b\right\}](https://wikimedia.org/api/rest_v1/media/math/render/svg/25b76ff0a2e8dd26a7da129e97e071c71527b324)
Theorem: ![b\in \left[a\right]\implies \left[b\right]=\left[a\right]](https://wikimedia.org/api/rest_v1/media/math/render/svg/59cf0ad96fe663b1fa3da0ccaa84e4cd7c9208a9)
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
.
Q.E.D.
Partitions of a set[edit]
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.
Q.E.D.
Quotients[edit]
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 much attention throughout the book.