Go up to 7.1 Equivalence Relations and PartitionsGo forward to 7.1.2 Modular Arithmetic |

Ris reflexive onS: <=>forallxinS: <x,x> inR;Ris symmetric onS: <=>forallx,y: <x,y> inR=> <y,x> inR;Ris transitive onS: <=>forallx,y,z: (<x,y> inR/\ <y,z> inR) => <x,z> inR.

Ris equivalence relation onS: <=>RsubsetSxS/\Ris reflexive onS/\Ris symmetric onS/\Ris transitive onS.

- = (equality) is an equivalence relation on every set.
- Let
`p`(`x`,`y`) : <=>`x`+`y`is even. Then`p`is an equivalence relation on**N**. - Let
`q`(`x`,`y`) : <=>`x`mod 5 = y mod 5. Then`q`is an equivalence relation on**N**. - Let
`r`(`x`,`y`) : <=>`x`_{0}+`y`_{0}=`x`_{1}+`y`_{1}. Then`r`is an equivalence relation on**R**x**R**. - Let
`s`(`x`,`y`) : <=>`x`is parallel to (or coincides with)`y`. Then`s`is an equivalence relation on the set of all lines in the plane. - Let
`t`(`x`,`y`) : <=>`x`has the same age as`y`. Then`t`is an equivalence relation on the set of all people.

The visualization of an equivalence relation by a directed graph has the following properties:

- every node has an arrow to itself (reflexivity),
- if there is an arrow from node
`a`to node`b`, then there is also an arrow from`b`to`a`(symmetry), - if there is an arrow from node
`a`to node`b`and an arrow from`b`to some node`c`, then there is also an arrow from`a`to`c`(transitivity).

The equivalence relation imposed on the set of six nodes determines three partitions in each of which every node is connected to every other node. Actually, there is a close relationship between equivalence relations and set partitions that will be elaborated later.

We demonstrate how to prove that a relation is an equivalence relation.

`p`is clearly a binary relation on**N**.- We prove
`p`is reflexive on**N**. Take arbitrary`x`in**N**. We have to show`x`+`x`is even, i.e, 2`x`is even, which clearly holds. - We prove
`p`is symmetric on**N**. Take arbitrary`x`in**N**and`y`in**N**. We assume`x`+`y`is even. Then`y`+`x`is even, because`x`+`y`=`y`+`x`. - We prove
`p`is transitive on**N**. Take arbitrary`x`in**N**,`y`in**N**, and`z`in**N**. We assume(1)

We have to show`x`+`y`is even /\`y`+`z`is even.(2)

From (1), we have some`x`+`z`is even`a`in**N**and`b`in**N**such that(3) 2

Thus we know`a`=`x`+`y`/\ 2`b`=`y`+`z`.`x`+`z`= (`x`+`y`) + (`y`+`z`) - 2`y`= 2`a`+ 2`b`- 2`y`= 2(`a`+`b`-`y`)

**Logic Evaluator** Above definitions can be implemented as
shown below, see Appendix * equiv.txt*.

We may construct the group of all objects that are related to some object.

[ x]_{R}:= {yin range(R): <x,y> inR}.

We may just write [`x`], if `R` is clear from the context. If
`R` is an equivalence relation, we call [`x`]_{R} the
*equivalence class (Äquivalenzklasse)* of `x` with respect to
`R`.

In the visualization of an (equivalence) relation by a directed graph, the (equivalence) class of a node is the set of all nodes to which the node is connected:

By the reflexivity of an equivalence relation, we have the following result.

forallS,R:Ris equivalence class onR=>xin [x]_{R}.

- Let
`p`subset**N**x**N**such that`p`(`x`,`y`) <=>`x`+`y`is even. Then we have

We see that [[ `0`]_{p}= {0, 2, 4, 6, 8, 10, ...}, [ `1`]_{p}= {1, 3, 5, 7, 9, 11, ...}, [ `2`]_{p}= {0, 2, 4, 6, 8, 10, ...}, [ `3`]_{p}= {1, 3, 5, 7, 9, 11, ...}, [ `4`]_{p}= {0, 2, 4, 6, 8, 10, ...}, ... `0`]_{p}union [`1`]_{p}=**N**and [`0`]_{p}intersection [`1`]_{p}=**0**. - Let
`q`subset**N**x**N**such that`q`(`x`,`y`) <=>`x`mod 5 = y mod 5. Then we have

We see that [[ `0`]_{q}= {0, 5, 10, 15, 20, 25, ...}, [ `1`]_{q}= {1, 6, 11, 16, 21, 26, ...}, [ `2`]_{q}= {2, 7, 12, 17, 22, 27, ...}, [ `3`]_{q}= {3, 8, 13, 18, 23, 28, ...}, [ `4`]_{q}= {4, 9, 14, 19, 24, 29, ...}, [ `5`]_{q}= {0, 5, 10, 15, 20, 25, ...}, ... `0`]_{q}union [`1`]_{q}union [`2`]_{q}union [`3`]_{q}union [`4`]_{q}=**N**and that any two of these sets are disjoint. - Let
`r`subset**R**x**R**such that`r`(`x`,`y`) <=>`x`_{0}+`x`_{1}=`y`_{0}+`y`_{1}. Then we have

i.e.,[ `a`]_{r}= {`b`in**R**x**R**:`a`_{0}+`a`_{1}=`b`_{0}+`b`_{1}}

If we consider[ `a`]_{r}= {`b`in**R**x**R**:`b`_{1}= -`b`_{0}+(`a`_{0}+`a`_{1})}**R**x**R**as the set of all points in the plane, then [`a`]_{r}denotes the line with slope -1 that goes through`a`:

We thus have**R**x**R**=**union**_`a`in**R**x**R**[`a`]_{r}

We can determine a "canonical representative" for each such line (the point on this line whose first coordinate is zero) and thus have**R**x**R**=**union**_`y`in**R**[<0,`y`>]_{r}

As illustrated by the example, different equivalences classes do not overlap.

forallS,R:Ris equivalence relation onS=>forallxinS,yinS:[ x]_{R}= [y]_{R}\/ [x]_{R}intersection [y]_{R}=0.

and show a contradiction. From (2), we have some

(1) [ x]_{R}!= [y]_{R},(2) [ x]_{R}intersection [y]_{R}!=0

We thus know

(3) zin [x]_{R}/\zin [y]_{R}.

We will now show

(4) < x,z> inR,(5) < y,z> inR.

which contradicts (1).

(6) [ y]_{R}subset [x]_{R},(7) [ x]_{R}subset [y]_{R}

We show (6):
From (5) and the symmetry of `R`, we know

From (4), (8), and the transitivity of

(8) < z,y> inR.

From (9) we know by the transitivity of

(9) < x,y> inR.

and therefore by definition of [

(10) forallz: <y,z> inR=> <x,z> inR

and thus by definition of [

(11) forallzin [y]_{R}: <x,z> inR

which gives us (6).

(12) forallzin [y]_{R}:zin [x]_{R}

With the same line of reasoning, we can show (7) and are done.

As a consequence of Propositions *Non-Empty Equivalence
Classes* and *Disjoint Equivalence
Classes*, we can decompose every set `S` by an
equivalence relation into a set of non-empty disjoint subsets.

S/R:= {[x]_{R}:xinS}.

**Logic Evaluator**
The quotient set construction can be implemented as shown below,
see Appendix * equiv.txt*.

We expect this decomposition to satisfy the following properties.

Dis partition ofS: <=>( forallxinD:x!=0) /\( forallxinD,yinD:x=y\/xintersectiony=0) /\unionD=S.

- We define

Then the set {`A`:= { `x`in**N**:`x`is even},`B`:= { `x`in**N**:`x`> 2 /\`x`is prime},`B`:= { `x`in**N**:`x`is odd /\`x`is not prime}.`A`,`B`,`C`} is a partition of**N**. - We define

Then the setcircle( `r`) := {`p`in**R**x**R**:`p`_{0}^{2}+`p`_{1}^{2}=`r`^{2}}.

is a partition of{circle( `r`):`r`in**R**_{ >= 0}}**R**x**R**as denoted by the following picture:

The following result shows that an equivalence relation indeed defines a partition.

forallS,R:Ris equivalence relation onS=>S/Ris partition ofS.

- Take arbitrary
`x`in`S`/`R`. By definition of`S`/`R`, we have some`a`in`S`such that`x`= [`a`]_{R}. By Proposition*Non-Empty Equivalence Classes*,`a`in [`a`]_{R}, therefore`x`!=**0**. - Take arbitrary
`x`in`S`/`R`and`y`in`S`/`R`. By definition of`S`/`R`, we have some`a`in`S`and`b`in`S`such that`x`= [`a`]_{R}and`y`= [`b`]_{R}. By Proposition*Disjoint Equivalence Classes*, [`a`]_{R}= [`b`]_{R}\/ [`a`]_{R}intersection [`b`]_{R}=**0**. - By definition of
`S`/`R`,**union**`S`/`R`subset`S`. We show`S`subset**union**`S`/`R`. Take arbitrary`x`in`S`. Then from Proposition*Non-Empty Equivalence Classes*we have`x`in [`x`]_{R}and from the definition of`S`/`R`we have [`x`]_{R}in`S`/`R`, thus`x`in**union**`S`/`R`.

We can also proceed in the other direction and construct a relation from a partition.

x~_{D}y: <=>existsdinD:xind/\yind.

The constructed relation is an equivalence relation.

forallS,D:Dis partition ofS=>~ _{D}is equivalence relation onS.

**Binary Relation**- By definition, ~
_{D}is a binary relation. If`x`~_{D}`y`, then we have some`d`in`D`such that`x`in`d`and`y`in`d`. Since**union**`D`=`S`, we have`x`in`S`and`y`in`S`and ~_{D}is a relation on`S`. **Reflexivity**-
Take arbitrary
`x`in`S`. Since**union**`D`=`S`, we have some`d`in`D`such that`x`in`d`and thus`x`~_{D}`x`. **Symmetry**-
Take arbitrary
`x`in`S`and`y`in`S`and assume`x`~_{D}`y`. Then we have some`d`in`D`such that`x`in`d`/\`y`in`d`which gives us`y`~_{d}`x`. **Transitivity**- Take arbitrary
`x`in`S`,`y`in`S`, and`z`in`S`and assume`x`~_{D}`y`and`y`~_{D}`z`. Then we have some`d`in`D`such that`x`in`d`/\`y`in`d`and some`e`in`D`such that`y`in`d`/\`z`in`d`. Since`y`in`d`and`y`in`e`, Proposition*Disjoint Equivalence Classes*gives us`d`=`e`and thus`x`~_{D}`z`.

As shown above, equivalence relations and partitions are just different notions for the same concept; we can always construct from one description the other one. Actually, each construction is the inverse of the other one as stated by the following result (which can be easily proved).

Let

forallS,R:Ris equivalence relation onS=>R= ~_{S/R}.

forallS,D:Dis partition ofS=>D=S/ ~_{D}.

**Logic Evaluator** We can implement the new notions as shown
below, see Appendix
* equiv.txt*.

The partitioning of sets into equivalence classes is an important methodology with many applications some of which are demonstrated in the following subsections.

Author: Wolfgang Schreiner

Last Modification: October 4, 1999