Next: The equivalence relation of Up: Finiteness09february2012 Previous: Cantor's Bijection Theorem

## Relations: partial orders, equivalences

Let be a set.
• A relation on is a subset of .
• The empty relation on is the subset of .
• The full relation on is the subset of .
• The identity relation on is the subset of . Note that if , then , for a unique subset of .
If is a relation on and if , we often write .
• The transpose of a relation on is the set . Then is a relation on and we have .
We have if and only if .
• If and are relations on a set , then their composition is the set:

Then is a relation on .
We have if and only if and , for some .
We abbreviate the composition by .
The composition of relations is associative: for example, if , and are relations on we may put:

Then we have, for any relations , and on :

In general, we may compose relations successively, without using parentheses.
In particular, for any relation on and for any positive integer , we may construct the -fold composition of with itself, giving the relation , with and .
Notice that consists of chains of successively related elements of :

A relation on a set is said to be:
• Reflexive, if and only if , if and only if for all .
• Symmetric, if and only if , if and only if implies that .
• Anti-symmetric, if and only if , if and only if whenever , then .
• Transitive, if and only if , if and only if whenever and , then .
There are many special kinds of relations on a set :
• A relation on is said to be a function if and only if whenever and , then , if and only if .
Then , for some unique subset of , called the range of .
Also we have , for some unique subset of .
Then the set , called the domain of .
• If is a function on , then is said to be surjective if and only if it has range if and only if .
• If is a function on , then is said to be injective if and only if is also a function if and only if and .
• If is a function with domain and with , then is said give a well-defined function from to .
• is an surjection from to if and only if and .
• is an injection from to if and only if . and .
• is an bijection from to if and only if and . In this case is a bijection from to .
• A relation on is a bijection from to itself, if and only if we have .
• If and are functions on , so are and (although one of both of these may be empty relations).
• is a partial order if and only if is anti-symmetric and transitive.
• is a total order if and only if is a partial order and trichotomy holds: .
• is an equivalence relation if and only if is reflexive, symmetric and transitive.
Let be any relation on .
Put .
Then is symmetric and reflexive.
Then put .
Then is an equivalence relation on , called the equivalence relation generated by .
Then we have and , for any relation on . If is another relation on , then implies that .
Also is an equivalence relation if and only if .
Also if is any equivalence relation, such that , then .
So we have:

So the equivalence relation generated by is the smallest subset of that contains as a subset and is an equivalence relation. Note that if , then the relation on is symmetric and transitive and the relation is an equivalence relation on .

Let now be an equivalence relation on a set .
• For each define:

Then we have the properties:
• and .
• is a symmetric and transitive relation on .
• If and are elements of such that , or such that , then we have and .
• We have and .
So given an equivalence relation we may define:

Then we have shown that if , then is non-empty.
Also we have shown that if and are distinct elements of then .
Finally we have the formulas:

If is a non-empty set a partition of is a subset of , such that:
• If and are distinct elements of , then .
• .
• Each element of is non-empty.
If is an equivalence relation on , then we have shown above that is a partition of .

Conversely, given a partition of , define a relation on by the formula:

Then is an equivalence relation.

The main theorem is then:
• For any partition of a set , we have: .
• For any equivalence relation on a set , we have: .

Next: The equivalence relation of Up: Finiteness09february2012 Previous: Cantor's Bijection Theorem
George A. J. Sparling 2012-02-09