Equivalence Relations and Partitions

Manuel Kauers

TSW-Homework

1 Introduction

Mathematicians are always interested in studying relations among certain objects. From an abstract point of view, elements of a set might be related to each other in an arbitrary complicated way, and it is hard to find interesting properties that describe the behaviour of relations in general. On the other hand, if the attention is focussed to a somewhat restricted kind of relations, things might become easier.

In this paper, we will study a special kind of relations, which are at the same time reflexive, transitive, and symmetric. Relations with these properties will be called equivalence relations. We will formally introduce the notion of an equivalence relation and study general properties of these relations.

We assume familiarity with the notions of set, in particular with the element of predicate ∈, the cartesian product ×, the subset predicate ⊆ and the operations union ∪ and intersection ∩. We will use infix notation for the binary predicates ∈ and ⊆ as well as for the the binary function symbols ×, ∪, and ∩. By ∅, we will denote the empty set.

By lowercase letters x, y, … we will denote basic elements, capital letters A, B, … will denote sets, and calligraphic letters A, B, … will denote families of sets. The elements of a cartesian product A × B will be denoted by pairs ⟨a, b⟩ (a ∈ A, b ∈ B).

2 Relations

We start by defining the notion of a relation.

Def. 2.1

1. Let S be a set and R be a subset of S × S. Then R is called a relation on S, formally

∀_{S,R} ( isRelation[R, S] ↔ R ⊆ S × S).

If R is a relation on S then S is called a base set of R.

2. More general, R is called a relation, if R is a relation on some set S, i.e.

∀_{R} ( isRelation[R] ↔ ∃_{S} isRelation[R, S]).

3. If R is a relation, then the smallest base set of R is called the domain of R, denoted by dom[R]:

dom[R] := {x : ∃_{⟨x,y⟩}⟨x, y⟩ ∈ R ∨ ⟨x, y⟩ ∈ R}.

If R is a relation on some set S, we will write aRb as a shortcut of ⟨a, b⟩ ∈ R, and we may say “R relates a to b” if aRb is true.

Ex. 2.1 Let S = {1, 2, 3, 4} and R = {⟨1, 2⟩, ⟨2, 3⟩, ⟨3, 1⟩}.

• R is a relation on S.

• R is a relation, since R is a relation on S.

• dom[R] = {1, 2, 3}.

• dom[∅] = ∅.

We proceed to consider relations that have special properties.

Def. 2.2

1. Let S be a set and R a relation on S. R is called symmetric on S, if xRy implies yRx for all x, y ∈ S, formally

∀_{S,R isRelation[R,S]} ( isSymm[R, S] ↔ ∀_{x,y∈S}(xRy → yRx)).

2. A relation R is called symmetric, if xRy implies yRx for all x, y, formally

∀_{R isRelation[R]} ( isSymm[R] ↔ ∀_{x,y}(xRy → yRx)).

In fact, it is easy to prove that these two notions of symmetry are equivalent in the sense that a relation is symmetric if and only if it is symmetric on all of its base sets.

Prop. 2.1

∀_{R} ( isSymm[R] ↔ ∀_{S isRelation[R,S]} isSymm[R, S]).

Proof. Let R be an arbitrary relation. (If R is not a relation, the scope of the first quantifier amounts to false ↔ false, i.e. it is nothing to prove.)

“→” Assume that R is symmetric, i.e. assume

∀_{x,y}(xRy → yRx).  (A1)

by Def. 2.2.2. We have to show that R is symmetric for each base set S, i.e.

∀_{S isRelation[R,S]} isSymm[R, S].  (G1)

So let S be an arbitrary but fixed base set of R. Then, using Def. 2.2.1, it remains to show

∀_{x,y∈S}(xRy → yRx).  (G2)

For arbitrary x, y ∈ S this statement is already asserted by A1.

“←” Assume that R is symmetric for all base sets S, i.e. assume

∀_{S isRelation[R,S]} isSymm[R, S].  (A2)

We have to show

∀_{x,y}(xRy → yRx).  (G3)

This means, for some arbitrary but fixed x, y with

xRy,  (A3)

it is to show that

yRx.  (G4)

By Def. 2.1.3 and A3, we know that

⟨x, y⟩ ∈ dom[R].  (A4)

Taking dom[R] as S in A2 and using A3 again, we obtain yRx which matches G4. This completes the proof.

Def. 2.3

1. Let S be a set and R be a relation on S. R is called transitive over S if xRy and yRz implies xRz for all x, y, z ∈ S. Formally,

∀_{R,S isRelation[R,S]} ( isTrans[R, S] ↔ ∀_{x,y,z∈S}(xRy ∧ yRz → xRz))

2. Let R be a relation. R is called transitive, if xRy and yRz implies xRz for all x, y, z. Formally,

∀_{R isRelation[R]} ( isTrans[R] ↔ ∀_{x,y,z}(xRy ∧ yRz → xRz))

Again, the two notions of transitivity are strongly related.

Prop. 2.2 (without proof)

∀_{R} ( isTrans[R] ↔ ∀_{S} isTrans[R, S]).

The proof of Prop. 2.2 is similar to the proof of Prop. 2.1 and left to the reader.

Def. 2.4 Let S be a set and R a relation on S. R is called reflexive, if it relates each element of S to itself, i.e.

∀_{S,R isRelation[R,S]} ( isRefl[R, S] ↔ ∀_{x∈S} xRx).

Note that reflexitivity is only defined with respect to a base set, but not in general. In fact, no general relation R will ever have the property

∀_{S isRelation[R,S]} isRefl[R, S],  (∗)

which would be desired for a general definition in analogy to Prop. 2.1 and Prop. 2.2. The argument is as follows.

Assume that R is a relation with the property (∗) and consider an arbitrary base set S of R. Then, R ⊆ S × S by Def. 2.1.1. By an axiom of set theory, there must be some x ∉ S. For such an x, consider S′ := S ∪{x}. Then R is also a relation on S′ by Def. 2.1.1 and the fact that A ⊆ B implies A × A ⊆ B × B. But R is not reflexive on S′ in contradiction to (∗).

This justifies that there is no serious way to define reflexivity without refering to a particular base set. As opposed to transitivity and symmetry, which are properties of the relation itself, reflexivity depends on the relation as well as on its base set.

At the end of this section, we provide the definition of an equivalence relation.

Def. 2.5 Let ∼ be a relation on S. ∼ is called an equivalence relation on S, if ∼ is reflexive, transitive, and symmetric:

∀_{∼,S isRelation[∼,S]} ( isEqRel[∼, S] ↔ (isRefl[∼, S] ∧ isSymm[∼] ∧ isTrans[∼]))

Note that being an equivalence relation is also a property which depends on the base set since reflexivity depends on the base set.

Ex. 2.2 Let S = {1, 2, 3}, and R = {⟨1, 1⟩, ⟨1, 2⟩, ⟨2, 1⟩, ⟨2, 2⟩, ⟨3, 3⟩}. Then R is an equivalence relation on S.

3 Partitions

We denote by P[S] the powerset of a set S. Recall that

∀_{S,T} (T ∈ P[S] ↔ T ⊆ S)

is the defining property of the powerset, i.e. the powerset of S is the set of all subsets of S.

Def. 3.1 A set F is called a family if F ⊆ P[S] for some set S.

∀_{F} ( isFamily[F] ↔ ∃_{S} F ⊆ P[S]).

Hence, a family is a set of sets. We proceed by considering families with special properties.

Def. 3.2 Let F be a family.

1. F is called a cover of a set S if every element x ∈ S is contained in at least one of the elements of F:

∀_{F,S ; isFamily[F]} ( isCover[F, S] ↔ ∀_{x∈S} ∃_{T ∈F} x ∈ T )

2. F is called disjoint if two distinct elements of F don’t have any element in common:

∀_{F ; isFamily[F]} ( isDisj[F] ↔ ∀_{P,Q∈F}(P ≠ Q → P ∩ Q = ∅))

3. F is called a partition of a set S if F is a disjoint cover of S:

∀_{F,S ; isFamily[F]} ( isPartition[F, S] ↔ isCover[F, S] ∧ isDisjoint[F])

Ex. 3.1 Let F_{1} = {{1, 2}, {2, 3}, {3, 4}}, F_{2} = {{1, 2}, {3, 4}}.

• Both F_{1} and F_{2} are covers of {1, 2, 3, 4} but not of {1, 2, 3, 4, 5}.

• Each family covers the empty set.

• F_{2} is disjoint, F_{1} is not.

• F_{2} is a partition of {1, 2, 3, 4}

• {S} is always a partition of S.

4 Equivalence Relations and Partitions

This section links the notions of equivalence relation (Def. 2.5) and of partition (Def. 3.2.3) to each other. In fact, we will see that each equivalence relation on a set S defines a partition of S, and vice versa.

Def. 4.1 Let S be a set, ∼ an equivalence relation on S, and x ∈ S. Then, the set

[x]_{∼} := {y : y ∈ S ∧ y ∼ x}

is called the equivalence class of x.

Prop. 4.1 Let S be a set, ∼ an equivalence relation on S, and x, y ∈ S with x ∼ y. Then [x]_{∼} = [y]_{∼}.

∀_{{S,∼ \atop isEqRel[∼,S]}} ∀_{x,y∈S}(x ∼ y → [x]_{∼} = [y]_{∼})

Proof. Let S be a set and ∼ be an equivalence relation on S, i.e. assume

isEqRel[∼, S]  (A1)

which by Def. 2.5 is equivalent to

isRefl[∼, S] ∧ isSymm[∼] ∧ isTrans[∼]  (A2)

which in turn yields

∀_{x∈S} x ∼ x,  (A3)
∀_{x,y}(x ∼ y → y ∼ x),  (A4)
∀_{x,y,z}(x ∼ y ∧ y ∼ z → x ∼ z)  (A5)

by definitions 2.4, 2.2.2, and 2.3.2. We have to show

∀_{x,y∈S}(x ∼ y → [x]_{∼} = [y]_{∼})  (G1)

so consider some arbitrary but fixed x, y ∈ S with the property

x ∼ y  (A6)

and show

[x]_{∼} = [y]_{∼}.  (G2)

We proceed to show that the left hand side is contained in the right hand side and vice versa.

• We show

[x]_{∼} ⊆ [y]_{∼}  (G3)

which by the definition of ⊆ means that

∀_{z}(z ∈ [x]_{∼} → z ∈ [y]_{∼})  (G4)

Consider an arbitrary but fixed

z ∈ [x]_{∼}  (A7)

and show

z ∈ [y]_{∼}.  (G5)

By A7 and Def. 4.1, we know that

z ∼ x  (A8)

and using A8, A6 and A5 we obtain

z ∼ y.  (A9)

Now G5 follows from A9 and the definition of [y]_{∼}.

• As for the other direction, we have to show

[y]_{∼} ⊆ [x]_{∼}  (G6)

which means

∀_{z}(z ∈ [y]_{∼} → z ∈ [x]_{∼})  (G7)

Take an arbitrary but fixed

z ∈ [y]_{∼}  (A10)

and show

z ∈ [x]_{∼}.  (G8)

By A10 and Def. 4.1, we know that

z ∼ y  (A11)

and using A4 and A6 it follows that

y ∼ x.  (A12)

By A11, A12, and A5 we get

z ∼ x.  (A13)

Now G8 follows from A13 and the definition of [x]_{∼}. This completes the proof.

Theorem 4.1 Let S be a set, ∼ an equivalence relation on S, and let

F = {[x]_{∼} : x ∈ S}

Then F is a partition:

∀_{{S,∼ \atop isEqRel[∼,S]}} isPartition[\{[x]_{∼} : x ∈ S\}, S].

Proof. Let S be a set and ∼ be an equivalence relation on S, i.e. assume

isEqRel[∼, S]  (A1)

and show

isPartition[{[x]_{∼} : x ∈ S}, S].  (G1)

By Def. 2.5, A1 leads to

isRefl[∼, S] ∧ isSymm[∼] ∧ isTrans[∼]  (A2)

which might be split and expanded into

∀_{x∈S} x ∼ x,  (A3)
∀_{x,y}(x ∼ y → y ∼ x),  (A4)
∀_{x,y,z}(x ∼ y ∧ y ∼ z → x ∼ z)  (A5)

using the definitions 2.4, 2.2.2, and 2.3.2. Writing F = {[x]_{∼} : x ∈ S} and using Def. 3.2.3 we can rewrite G1 as

isCover[F, S] ∧ isDisjoint[F]  (G2)

i.e. we have to show that F is a disjoint cover of S.

• We first show

isCover[F, S]  (G3)

which by Def. 3.2.1 means

∀_{x∈S} ∃_{T ∈F} x ∈ T.  (G4)

Take an arbitrary but fixed x ∈ S and show

∃_{T ∈F} x ∈ T.  (G5)

We claim that T = [x]_{∼} does the job, i.e. we claim that

x ∈ [x]_{∼}.  (G6)

By Def. 4.1 we know that

∀_{y∈S} y ∈ [x]_{∼} ↔ y ∼ x.  (A6)

Taking y = x we can conlcude

x ∈ [x]_{∼} ↔ x ∼ x.  (A7)

With the aid of A7, G6 might be rewritten as

x ∼ x.  (G7)

Since x ∈ S, G7 is asserted by A3.

• Now we prove

isDisjoint[F],  (G8)

which by Def. 3.2.2 means

∀_{P,Q∈F} P ≠ Q → P ∩ Q = ∅.  (G9)

For arbitrary [x]_{∼}, [y]_{∼} ∈ F with

[x]_{∼} ≠ [y]_{∼}  (A8)

we will prove

[x]_{∼} ∩ [y]_{∼} = ∅.  (G10)

Assume the contrary of G10, i.e. the existence of an element z with

z ∈ [x]_{∼} ∩ [y]_{∼}  (A9)

which means

z ∈ [x]_{∼}  (A10)
z ∈ [y]_{∼}.  (A11)

By Def. 4.1, this can be written as

z ∼ x  (A12)
z ∼ y.  (A13)

By A4 we can transform A13 into

y ∼ z.  (A14)

and A5 allows to conclude

x ∼ y  (A15)

from A12 and A15. Using Prop. 4.1, we arrive at

[x]_{∼} = [y]_{∼}  (A16)

which contradicts A8. Hence assumption A9 was wrong and therefore G10 must be true.

This completes the proof.

The last theorem showed that an equivalence relation on a set S defines a partition on S. We will now turn to the “reverse” statement, namely that every partition of S also defines an equivalence relation on S. This requires a little more preparation.

Prop. 4.2 Let S be a set and F be a partition of S. Then, for each x ∈ S there exists exactly one P ∈ F such that x ∈ P, i.e.

∀_{S,F isPartition[F,S]} ( ∀_{x∈S} ( ∃_{P ∈F}(x ∈ P) ∧ ∀_{P,Q∈F}(x ∈ P ∧ x ∈ Q → P = Q))).

Proof. Let S be an arbitrary set and F be an arbitrary partition of S, i.e. assume

isPartition[F, S].  (A1)

We have to show

∀_{x∈S} ( ∃_{P ∈F}(x ∈ P) ∧ ∀_{P,Q∈F}(x ∈ P ∧ x ∈ Q → P = Q)).  (G1)

First we expand the definition of partition in A1. By Def. 3.2.3 this leads to

isDisjoint[F],  (A2)
isCover[F, S],  (A3)

which in turn by Def. 3.2.1 and Def. 3.2.2 lead to

∀_{x∈S} ∃_{T ∈F} x ∈ T  (A4)
∀_{P,Q∈F}(P ≠ Q → P ∩ Q = ∅).  (A5)

Now let x ∈ S be arbitrary but fixed. We have to show

∃_{P ∈F} x ∈ P  (G2)
∀_{P,Q∈F}(x ∈ P ∧ x ∈ Q → P = Q).  (G3)

G2 is immediate by assumption A4. As for G3, consider arbitrary but fixed P, Q ∈ F and assume

x ∈ P ∧ x ∈ Q,  (A6)

which is equivalent to x ∈ P ∩ Q. It remains to show that

P = Q.  (G4)

By A5, we know

P ≠ Q → P ∩ Q = ∅  (A7)

Assuming that G4 does not hold, A7 leads to the conclusion P ∩Q = ∅ in contradiction to A6. Thus, G4 holds which completes the proof.

The fact that every element x ∈ S is contained in exactly one element of a partition F of S shows that the following notion is well defined.

Def. 4.2 Let S be a set, F a partition of S, and x ∈ S. The home of x with respect to F, denoted by home[x, F], is defined as the uniquely determined element P ∈ F with x ∈ P:

∀_{S,F isPartition[F,S]} ( ∀_{x∈S} ∀_{P ∈F} P = home[x, F] ↔ x ∈ P ).

Theorem 4.2 Let S be a set and F be a partition of S. Furthermore, let

∼ := {⟨x, y⟩ : x, y ∈ S ∧ home[x, F] = home[y, F]}.

Then ∼ is an equivalence relation.

∀_{S,F isPartition[F,S]} isEqRel[{⟨x, y⟩ : x, y ∈ S ∧ home[x, F] = home[y, F]}, S].

Proof. Let S be a set and F be a partition of S, i.e. assume

isPartition[F, S]  (A1)

which by Def. 3.2.3 means

isDisj[F]  (A2)
isCover[F, S]  (A3)

which by Def. 3.2.1 and Def. 3.2.2 means

∀_{P,Q∈F} P ≠ Q → P ∩ Q = ∅  (A4)
∀_{x∈S} ∃_{P ∈F} x ∈ P.  (A5)

We have to prove

isEqRel[{⟨x, y⟩ : x, y ∈ S ∧ home[x, F] = home[y, F]}, S].  (G1)

Using the abbreviation

R := {⟨x, y⟩ : x, y ∈ S ∧ home[x, F] = home[y, F]}  (A6)

and Def. 2.5, G1 is equivalent to

isRefl[R, S] ∧ isSymm[R] ∧ isTrans[R].  (G2)

We prove the three properties separately.

• Reflexivity. We prove

isRefl[R, S]  (G3)

which means

∀_{x∈S} xRx  (G4)

by Def. 2.4. Let x ∈ S be arbitrary but fixed and prove

xRx,  (G5)

which by A6 is equivalent to

home[x, F] = home[x, F]  (G6)

which is obviously the case.

• Symmetry. We prove

isSymm[R]  (G7)

which means

∀_{x,y} xRy → yRx.  (G8)

Now take x, y arbitrary, assume

xRy  (A7)

and show

yRx.  (G9)

By the definition of R (A6), A7 is equivalent to

home[x, F] = home[y, F]  (A8)

and G9 is equivalent to

home[y, F] = home[x, F].  (G10)

G10 is obtained by A8 using the symmetry of “=.”

• Transitivity. We prove

isTrans[R]  (G11)

which means

∀_{x,y,z} xRy ∧ yRz → xRz.  (G12)

Now take x, y, z arbitrary, assume

xRy,  (A9)
yRz,  (A10)

and prove

xRz.  (G13)

By the definition of R (A6), A9 and A10 yield the equivalent statements

home[x, F] = home[y, F],  (A11)
home[y, F] = home[z, F],  (A12)

while

home[x, F] = home[z, F]  (G14)

remains to be proven. A11 and A12 together with the transitivity of “=” give G14.

Finally, we have shown that R is reflexive, symmetric and transitive, thus R is an equivalence relation.