A relation can be said to generalize the concept of a function. A relation is some kind of relationship between two elements in a set, which may or may not hold.
Let A be a set. A relation R on the set A is a subset of the cartesian product A \times A.
We can also define a relation over two sets A and B, where R is a subset of the cartesian product A \times B.
Any pair of elements a,b \in A is either belonging to R or not. If (a,b) \in R, we say “a is in the relation R to b”.
It is common to use \sim as a general relation symbol, and we almost always use infix notation for relations, and write a \sim b to mean {(a,b) \in\, \sim}. When (a,b) \not \in\, \sim we write a \not \sim b.
Properties
Relations have many properties, the following three being the most useful.
Let \sim be a relation on a set A.
- We call \sim reflexive if for all a \in A
a \sim a.
- We call \sim symmetric if for all a,b \in A
a \sim b \implies b \sim a.
- We call \sim transitive if for all a,b \in A
a \sim b \text{ and } b \sim c \implies a \sim c
There are also special properties when a relation is never reflexive, symmetric, or transitive.
Let \sim be a relation on a set A.
- We call \sim anti-reflexive if for all a\in A,
a \not \sim a.
- We call \sim anti-symmetric if for all a,b \in A,
a \sim b \implies b \not \sim a.
- We call \sim anti-transitive if for all a,b,c \in A,
a \sim b \text{ and } b \sim c \implies a \not \sim c.
Equivalence Relations
An equivalence relation on a set A is a relation \sim such that \sim is reflexive, symmetric, and transitive.
Equivalence relations are (not surprisingly) related to equality, and cover notions like equivalence and congruency.
Let \sim be an equivalence relation on a set A. Let [a] be a subset of A determined by the equation
[a] = \{x \mid a \sim x\}.
We call [a] the equivalence class of A generated by a.
While context is usually enough to know which relation an equivalence class is referring to, [a]_\sim is used to mean the equivalence class of A generated by a with the relation \sim.
Equivalence classes have the following properties:
Let \sim be an equivalence relation on a set A. Then the equivalence class [a] will always contain a as an element.
Because \sim is an equality relation, it is reflexive by definition. Therefore a \sim a, and thus a \in [a].
Let \sim be an equivalence relation on a set A. Then the equivalence classes [a] and [b] are either disjoint or equal.
If [a] \cap [b] is empty, then the equivalence classes are disjoint.
If instead there exists some element c \in [a] \cap [b], then by definition we have a \sim c and b \sim c. Using the symmetrical property of our relation, b \sim c implies c \sim b, and then by transitivity we have a \sim c and c \sim b implies a \sim b.
Suppose [a] contains some element a_2. Then we have a \sim a_2, which via symmetry gives a_2 \sim a, transitivity with a \sim b implies a_2 \sim b, and symmetry again gives b \sim a_2. Thus a_2 \in [b]. Since then every element in [a] belongs to [b], we have [a] \subseteq [b].
Similarly, this can be repeated to show [b] \subseteq [a], and thus [a] = [b]. Therefore, two equivalence classes are either disjoint, or equivalent.
Using these theorems, we can show that the collection of equivalence classes formed by an equivalence relation have a special property.
Let \sim be an equivalence relation on A. The collection of equivalence classes of A form disjoint subsets of A whose union is all of A.
Let \sim be an equivalence relation on a set A, and let \mathcal{E} be the collection of all the equivalence classes determined by this relation
\mathcal{E} = \{[x] \mid x \in A\}.
By Theorem 1.2.2, distinct elements of \mathcal{E} are disjoint. And furthermore by Lemma 1.2.1, the union of elements of \mathcal{E} is equal to A, since each element of A belongs to an equivalence class. Thus the collection of equivalence classes of A are disjoint and have a union of A.
The collection of equivalence classes is a partitcular example of what is called a partition.
Partitions
A partition of a set A is a collection of disjoint subsets of A whose union is all of A.
We proved the set of equivalence classes forms a partition. It is true also that given any partition P on a set A, there is exactly one equivalence relation \sim from which P is derived. (TO-DO PROOF)