- #1
- 19,851
- 10,885
Definition/Summary
A relation on a set A is a set of ordered pairs (a,b) of elements ofA (a subset of A \times A).
An equivalence relation \sim\ \subseteq A \times A is a relation which is reflexive, symmetric and transitive.
In other words, the relation \sim on A is an equivalence relation if, for all elements a\ b\text{ and }c:
1)(a,a)\in\ \sim (the relation is reflexive: a\sim a)
2)(a,b)\in\ \sim\ \Rightarrow (b,a)\in\ \sim (the relation is symmetric: a\sim b\ \Rightarrow b\sim a)
3)(a,b)\in\ \sim \text{ and } (b,c)\in\ \sim\ \Rightarrow (a,c)\in\ \sim (the relation is transitive: a\sim b\text{ and } b\sim c \Rightarrow a\sim c)
The equivalence class containing a is the subset [a]\ =\ \{b\in\ A\ :\ b\sim\ a\}, of all elements related to a.
Each element belongs to exactly one equivalence class: in other words, the equivalence classes are a partition of the whole set.
The set of all equivalence classes is called the quotient set, A/\sim.
The projection induced by \sim is the function \pi:\ A\rightarrow\ A/\sim defined by \pi (a)\ =\ [a], mapping each element to its equivalence class.
A congruence relation on a set with algebraic structure is an equivalence relation which is compatible with that structure.
Equations
Extended explanation
Sameness:
There is an equivalence relation between two elements if they are in some sense the same, if they are the same with respect to some property. Indeed, an equivalence relation is a generalisation of equality
Trivial equivalence relations:
Equality itself is an equivalence relation, but it is a trivial one, since the equivalence classes each have only one element, and the quotient set A/= is the set A itself.
Common membership of the set is also a trivial equivalence relation: there is only one equivalence class, the trivial subset A itself, and so the quotient set has only one element.
Examples of Equivalence Relations:
1) Modular arithmetic: Define the relation \equiv on the set \mathbb{N} of natural numbers by: a\equiv b \Leftrightarrow a\text{ and }b\text{ have the same remainder when divided by 3}. This defines an equivalence relation, often written a\equiv b\text{ (mod 3)}. (Is there anything special about the number 3 here?
)
Then there are three equivalence classes, namely the subsets:
R_0 = \{ 0,3,6,9,\ldots \} = \{ n\in \mathbb{N}: n\equiv 0\}
R_1 = \{ 1, 4, 7, \ldots \} = \{ n\in \mathbb{N}: n\equiv 1\}
R_2 = \{ 2, 5, 8,\ldots \} = \{ n\in \mathbb{N}: n\equiv 2\}
Note that these equivalence classes form a partition, since they are disjoint, and their union is \mathbb{N}.
The quotient set \mathbb{N}/\equiv is the set \{R_0,R_1,R_2\}.
The projection induced by \equiv is the function Rem:\ \mathbb{N}\rightarrow\mathbb{N}/\equiv which maps each number onto its equivalence class.
So two numbers are equivalent to each other (mod 3) if they have the same remainder (on division by 3): the quotient set may be thought of as the set of possible remainders, and the projection as the function Rem(n) which gives the remainder.
Since, for example, Rem(a) + Rem(b) = Rem(a+b) and Rem(a)Rem(b) = Rem(ab) , \mathbb{N}/\equiv has the same algebraic structure as \mathbb{N} , and so \equiv is a congruence relation.
2) Let A be the set of all triangles, and the relation ~ be defined: a\sim b \Leftrightarrow a and b have the same area.
3) Let A be the set of all straight lines in the plane, and define the relation ~ by: a\sim b \Leftrightarrow a and b are parallel.
4) Let A = \mathbb{N}\times \mathbb{N} and define the relation: (m,n)\sim (s,t) \Leftrightarrow ns = mt.
5) As one last example, consider the set A of a child's play things, e.g. blocks, balls, cars etc., and each toy has one colour. We may ask the child to pile together those objects of the same colour. This would be teaching the child to work with the equivalence relation that two toys are equivalent if they are of the same colour. An equivalence class would be a pile of toys of the same colour. Each toy falls into one pile, all the piles together make up all the child's toys, and no toy belongs to more than one pile (equivalence classes are disjoint).
* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!
A relation on a set A is a set of ordered pairs (a,b) of elements ofA (a subset of A \times A).
An equivalence relation \sim\ \subseteq A \times A is a relation which is reflexive, symmetric and transitive.
In other words, the relation \sim on A is an equivalence relation if, for all elements a\ b\text{ and }c:
1)(a,a)\in\ \sim (the relation is reflexive: a\sim a)
2)(a,b)\in\ \sim\ \Rightarrow (b,a)\in\ \sim (the relation is symmetric: a\sim b\ \Rightarrow b\sim a)
3)(a,b)\in\ \sim \text{ and } (b,c)\in\ \sim\ \Rightarrow (a,c)\in\ \sim (the relation is transitive: a\sim b\text{ and } b\sim c \Rightarrow a\sim c)
The equivalence class containing a is the subset [a]\ =\ \{b\in\ A\ :\ b\sim\ a\}, of all elements related to a.
Each element belongs to exactly one equivalence class: in other words, the equivalence classes are a partition of the whole set.
The set of all equivalence classes is called the quotient set, A/\sim.
The projection induced by \sim is the function \pi:\ A\rightarrow\ A/\sim defined by \pi (a)\ =\ [a], mapping each element to its equivalence class.
A congruence relation on a set with algebraic structure is an equivalence relation which is compatible with that structure.
Equations
Extended explanation
Sameness:
There is an equivalence relation between two elements if they are in some sense the same, if they are the same with respect to some property. Indeed, an equivalence relation is a generalisation of equality
Trivial equivalence relations:
Equality itself is an equivalence relation, but it is a trivial one, since the equivalence classes each have only one element, and the quotient set A/= is the set A itself.
Common membership of the set is also a trivial equivalence relation: there is only one equivalence class, the trivial subset A itself, and so the quotient set has only one element.
Examples of Equivalence Relations:
1) Modular arithmetic: Define the relation \equiv on the set \mathbb{N} of natural numbers by: a\equiv b \Leftrightarrow a\text{ and }b\text{ have the same remainder when divided by 3}. This defines an equivalence relation, often written a\equiv b\text{ (mod 3)}. (Is there anything special about the number 3 here?
)Then there are three equivalence classes, namely the subsets:
R_0 = \{ 0,3,6,9,\ldots \} = \{ n\in \mathbb{N}: n\equiv 0\}
R_1 = \{ 1, 4, 7, \ldots \} = \{ n\in \mathbb{N}: n\equiv 1\}
R_2 = \{ 2, 5, 8,\ldots \} = \{ n\in \mathbb{N}: n\equiv 2\}
Note that these equivalence classes form a partition, since they are disjoint, and their union is \mathbb{N}.
The quotient set \mathbb{N}/\equiv is the set \{R_0,R_1,R_2\}.
The projection induced by \equiv is the function Rem:\ \mathbb{N}\rightarrow\mathbb{N}/\equiv which maps each number onto its equivalence class.
So two numbers are equivalent to each other (mod 3) if they have the same remainder (on division by 3): the quotient set may be thought of as the set of possible remainders, and the projection as the function Rem(n) which gives the remainder.
Since, for example, Rem(a) + Rem(b) = Rem(a+b) and Rem(a)Rem(b) = Rem(ab) , \mathbb{N}/\equiv has the same algebraic structure as \mathbb{N} , and so \equiv is a congruence relation.
2) Let A be the set of all triangles, and the relation ~ be defined: a\sim b \Leftrightarrow a and b have the same area.
3) Let A be the set of all straight lines in the plane, and define the relation ~ by: a\sim b \Leftrightarrow a and b are parallel.
4) Let A = \mathbb{N}\times \mathbb{N} and define the relation: (m,n)\sim (s,t) \Leftrightarrow ns = mt.
5) As one last example, consider the set A of a child's play things, e.g. blocks, balls, cars etc., and each toy has one colour. We may ask the child to pile together those objects of the same colour. This would be teaching the child to work with the equivalence relation that two toys are equivalent if they are of the same colour. An equivalence class would be a pile of toys of the same colour. Each toy falls into one pile, all the piles together make up all the child's toys, and no toy belongs to more than one pile (equivalence classes are disjoint).
* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!