In mathematics, a homogeneous relation (also called endorelation) on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. [1] [2] [3] This is commonly phrased as "a relation on X" [4] or "a (binary) relation over X". [5] [6] An example of a homogeneous relation is the relation of kinship, where the relation is between people.
Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations. Terminology particular for graph theory is used for description, with an ordinary (undirected) graph presumed to correspond to a symmetric relation, and a general endorelation corresponding to a directed graph. An endorelation R corresponds to a logical matrix of 0s and 1s, where the expression xRy corresponds to an edge between x and y in the graph, and to a 1 in the square matrix of R. It is called an adjacency matrix in graph terminology.
Some particular homogeneous relations over a set X (with arbitrary elements x1, x2) are:
Fifteen large tectonic plates of the Earth's crust contact each other in a homogeneous relation. The relation can be expressed as a logical matrix with 1 indicating contact and 0 no contact. This example expresses a symmetric relation.
Some important properties that a homogeneous relation R over a set X may have are:
The previous 6 alternatives are far from being exhaustive; e.g., the binary relation xRy defined by y = x2 is neither irreflexive, nor coreflexive, nor reflexive, since it contains the pair (0, 0), and (2, 4), but not (2, 2), respectively. The latter two facts also rule out (any kind of) quasi-reflexivity.
Again, the previous 3 alternatives are far from being exhaustive; as an example over the natural numbers, the relation xRy defined by x > 2 is neither symmetric nor antisymmetric, let alone asymmetric.
Again, the previous 5 alternatives are not exhaustive. For example, the relation xRy if (y = 0 or y = x+1) satisfies none of these properties. On the other hand, the empty relation trivially satisfies all of them.
Moreover, all properties of binary relations in general also may apply to homogeneous relations:
A preorder is a relation that is reflexive and transitive. A total preorder, also called linear preorder or weak order, is a relation that is reflexive, transitive, and connected.
A partial order, also called order,[ citation needed] is a relation that is reflexive, antisymmetric, and transitive. A strict partial order, also called strict order,[ citation needed] is a relation that is irreflexive, antisymmetric, and transitive. A total order, also called linear order, simple order, or chain, is a relation that is reflexive, antisymmetric, transitive and connected. [15] A strict total order, also called strict linear order, strict simple order, or strict chain, is a relation that is irreflexive, antisymmetric, transitive and connected.
A partial equivalence relation is a relation that is symmetric and transitive. An equivalence relation is a relation that is reflexive, symmetric, and transitive. It is also a relation that is symmetric, transitive, and total, since these properties imply reflexivity.
Implications and conflicts between properties of homogeneous binary relations |
---|
If R is a homogeneous relation over a set X then each of the following is a homogeneous relation over X:
All operations defined in Binary relation § Operations also apply to homogeneous relations.
Reflexivity | Symmetry | Transitivity | Connectedness | Symbol | Example | |
---|---|---|---|---|---|---|
Directed graph | → | |||||
Undirected graph | Symmetric | |||||
Dependency | Reflexive | Symmetric | ||||
Tournament | Irreflexive | Asymmetric | Pecking order | |||
Preorder | Reflexive | Transitive | ≤ | Preference | ||
Total preorder | Reflexive | Transitive | Connected | ≤ | ||
Partial order | Reflexive | Antisymmetric | Transitive | ≤ | Subset | |
Strict partial order | Irreflexive | Asymmetric | Transitive | < | Strict subset | |
Total order | Reflexive | Antisymmetric | Transitive | Connected | ≤ | Alphabetical order |
Strict total order | Irreflexive | Asymmetric | Transitive | Connected | < | Strict alphabetical order |
Partial equivalence relation | Symmetric | Transitive | ||||
Equivalence relation | Reflexive | Symmetric | Transitive | ~, ≡ | Equality |
The set of all homogeneous relations over a set X is the set 2X×X, which is a Boolean algebra augmented with the involution of mapping of a relation to its converse relation. Considering composition of relations as a binary operation on , it forms a monoid with involution where the identity element is the identity relation. [16]
The number of distinct homogeneous relations over an n-element set is 2n2 (sequence A002416 in the OEIS):
Elements | Any | Transitive | Reflexive | Symmetric | Preorder | Partial order | Total preorder | Total order | Equivalence relation |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 8 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 65,536 | 3,994 | 4,096 | 1,024 | 355 | 219 | 75 | 24 | 15 |
n | 2n2 | 2n(n−1) | 2n(n+1)/2 | ∑n k=0 k!S(n, k) |
n! | ∑n k=0 S(n, k) | |||
OEIS | A002416 | A006905 | A053763 | A006125 | A000798 | A001035 | A000670 | A000142 | A000110 |
Note that S(n, k) refers to Stirling numbers of the second kind.
Notes:
The homogeneous relations can be grouped into pairs (relation, complement), except that for n = 0 the relation is its own complement. The non-symmetric ones can be grouped into quadruples (relation, complement, inverse, inverse complement).
In mathematics, a homogeneous relation (also called endorelation) on a set X is a binary relation between X and itself, i.e. it is a subset of the Cartesian product X × X. [1] [2] [3] This is commonly phrased as "a relation on X" [4] or "a (binary) relation over X". [5] [6] An example of a homogeneous relation is the relation of kinship, where the relation is between people.
Common types of endorelations include orders, graphs, and equivalences. Specialized studies of order theory and graph theory have developed understanding of endorelations. Terminology particular for graph theory is used for description, with an ordinary (undirected) graph presumed to correspond to a symmetric relation, and a general endorelation corresponding to a directed graph. An endorelation R corresponds to a logical matrix of 0s and 1s, where the expression xRy corresponds to an edge between x and y in the graph, and to a 1 in the square matrix of R. It is called an adjacency matrix in graph terminology.
Some particular homogeneous relations over a set X (with arbitrary elements x1, x2) are:
Fifteen large tectonic plates of the Earth's crust contact each other in a homogeneous relation. The relation can be expressed as a logical matrix with 1 indicating contact and 0 no contact. This example expresses a symmetric relation.
Some important properties that a homogeneous relation R over a set X may have are:
The previous 6 alternatives are far from being exhaustive; e.g., the binary relation xRy defined by y = x2 is neither irreflexive, nor coreflexive, nor reflexive, since it contains the pair (0, 0), and (2, 4), but not (2, 2), respectively. The latter two facts also rule out (any kind of) quasi-reflexivity.
Again, the previous 3 alternatives are far from being exhaustive; as an example over the natural numbers, the relation xRy defined by x > 2 is neither symmetric nor antisymmetric, let alone asymmetric.
Again, the previous 5 alternatives are not exhaustive. For example, the relation xRy if (y = 0 or y = x+1) satisfies none of these properties. On the other hand, the empty relation trivially satisfies all of them.
Moreover, all properties of binary relations in general also may apply to homogeneous relations:
A preorder is a relation that is reflexive and transitive. A total preorder, also called linear preorder or weak order, is a relation that is reflexive, transitive, and connected.
A partial order, also called order,[ citation needed] is a relation that is reflexive, antisymmetric, and transitive. A strict partial order, also called strict order,[ citation needed] is a relation that is irreflexive, antisymmetric, and transitive. A total order, also called linear order, simple order, or chain, is a relation that is reflexive, antisymmetric, transitive and connected. [15] A strict total order, also called strict linear order, strict simple order, or strict chain, is a relation that is irreflexive, antisymmetric, transitive and connected.
A partial equivalence relation is a relation that is symmetric and transitive. An equivalence relation is a relation that is reflexive, symmetric, and transitive. It is also a relation that is symmetric, transitive, and total, since these properties imply reflexivity.
Implications and conflicts between properties of homogeneous binary relations |
---|
If R is a homogeneous relation over a set X then each of the following is a homogeneous relation over X:
All operations defined in Binary relation § Operations also apply to homogeneous relations.
Reflexivity | Symmetry | Transitivity | Connectedness | Symbol | Example | |
---|---|---|---|---|---|---|
Directed graph | → | |||||
Undirected graph | Symmetric | |||||
Dependency | Reflexive | Symmetric | ||||
Tournament | Irreflexive | Asymmetric | Pecking order | |||
Preorder | Reflexive | Transitive | ≤ | Preference | ||
Total preorder | Reflexive | Transitive | Connected | ≤ | ||
Partial order | Reflexive | Antisymmetric | Transitive | ≤ | Subset | |
Strict partial order | Irreflexive | Asymmetric | Transitive | < | Strict subset | |
Total order | Reflexive | Antisymmetric | Transitive | Connected | ≤ | Alphabetical order |
Strict total order | Irreflexive | Asymmetric | Transitive | Connected | < | Strict alphabetical order |
Partial equivalence relation | Symmetric | Transitive | ||||
Equivalence relation | Reflexive | Symmetric | Transitive | ~, ≡ | Equality |
The set of all homogeneous relations over a set X is the set 2X×X, which is a Boolean algebra augmented with the involution of mapping of a relation to its converse relation. Considering composition of relations as a binary operation on , it forms a monoid with involution where the identity element is the identity relation. [16]
The number of distinct homogeneous relations over an n-element set is 2n2 (sequence A002416 in the OEIS):
Elements | Any | Transitive | Reflexive | Symmetric | Preorder | Partial order | Total preorder | Total order | Equivalence relation |
---|---|---|---|---|---|---|---|---|---|
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 2 | 1 | 2 | 1 | 1 | 1 | 1 | 1 |
2 | 16 | 13 | 4 | 8 | 4 | 3 | 3 | 2 | 2 |
3 | 512 | 171 | 64 | 64 | 29 | 19 | 13 | 6 | 5 |
4 | 65,536 | 3,994 | 4,096 | 1,024 | 355 | 219 | 75 | 24 | 15 |
n | 2n2 | 2n(n−1) | 2n(n+1)/2 | ∑n k=0 k!S(n, k) |
n! | ∑n k=0 S(n, k) | |||
OEIS | A002416 | A006905 | A053763 | A006125 | A000798 | A001035 | A000670 | A000142 | A000110 |
Note that S(n, k) refers to Stirling numbers of the second kind.
Notes:
The homogeneous relations can be grouped into pairs (relation, complement), except that for n = 0 the relation is its own complement. The non-symmetric ones can be grouped into quadruples (relation, complement, inverse, inverse complement).