Relations: Difference between revisions
| Line 49: | Line 49: | ||
The comparability condition, or the trichotomy law, states that for any a, b ∈ S, either <code>a R b</code> or <code>b R a</code>. | The comparability condition, or the trichotomy law, states that for any a, b ∈ S, either <code>a R b</code> or <code>b R a</code>. | ||
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. | 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. | ||
Revision as of 17:43, 31 March 2020
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 reflexive, symmetric and transitive 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 reflexive, antisymmetric and transitive 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 conditions for a partial order 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