Relations
Internal
Overview
A binary relation R on two sets A and B is a subset of the Cartesian product A x B. If (a, b) belongs to the subset of the Cartesian product that defines the relation, we write a R b.
A binary relation R on a set A is a subset of the Cartesian product A x A.
A n-ary relation on sets A1, A2, .... An is a subset of the Cartesian product A1 x A2 x ... x An.
An example of a binary relation on a finite set is the edge set of a graph.
Binary Relation Properties
A binary relation R ⊆ A x A is reflexive if a R a for all a ∈ A.
A binary relation R ⊆ A x A is symmetric if a R b implies b R a for all a, b ∈ A.
A binary relation R ⊆ A x A is transitive if a R b and b R c implies a R c for all a, b, c ∈ A.
A binary relation R ⊆ A x A is antisymmetric if a R b and b R a imply a = b. For example, the "≤" relation on natural numbers is antisymmetric, since a ≤ b and b ≤ a imply a = b.
Equivalence
A relation that is:
is an equivalence relation. For example, "=" is an equivalence relation on the natural numbers.
Equivalence class. If R is an equivalence relation on the set A, then for a ∈ A, the equivalence class of a is the set [a] = {b ∈ A, where a R b}. In other words, the equivalence set of a is the set of all elements equivalent to a, relative to relation R.
Theorem: An equivalence relation is the same as a partition. The equivalence classes of any equivalence relation R on a set A for a partition of A, and any partition of A determines an equivalence relation on A for which the sets in the partition are the equivalence classes.
Partial Order
A relation that is:
is a partial order. We call a set on which a partial order is defined a partially ordered set.
For example, the relation "is a descendant of" is a partial order on the set of all people, if we allow that individuals are being their own descendants.
In a partially ordered set, there may be no single "maximum" element a such that b R a for all b ∈ A. Instead, the set may contain several maximal elements a such that for no b ∈ A, where b ≠ a, is it the case that a R b.
Total Relation
A relation R on a set A is a total relation if for all a, b ∈ A, we have a R b or b R a, or both. In other words, every pairing of elements of A is related by R. This is also known as the comparability condition or the trichotomy law.
Total Order
A total order (or linear order, totally ordered set, linearly ordered set) is a set plus a relation on the set, called a "total order", that satisfies the axioms of the partial order (reflexivity, antisymmetry and transitivity) plus an additional condition known as the comparability condition or the trichotomy law.
The comparability condition, or the trichotomy law, states that for any a, b ∈ S, either a R b or b R a.
For example, the relation "≤" is a total order on the natural numbers, but the "is a descendant of" relation is not a total order on the set of all people, since there are individuals neither of whom is descendant of the other.
A total relation that is transitive, but not necessarily reflexive and antisymmetric is a total preorder.
TODO
CLRS page 1163