Homogeneous relation

From Wikipedia, the free encyclopedia

Template:Short description 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 × XScript error: No such module "Check for unknown parameters"..[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 (x is R-related to y) 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.

Particular homogeneous relations

Some particular homogeneous relations over a set X (with arbitrary elements x1Script error: No such module "Check for unknown parameters"., x2Script error: No such module "Check for unknown parameters".) are:

Empty relation
E = ∅Script error: No such module "Check for unknown parameters".;
that is, x1Ex2Script error: No such module "Check for unknown parameters". holds never;
Universal relation
U = X × XScript error: No such module "Check for unknown parameters".;
that is, x1Ux2Script error: No such module "Check for unknown parameters". holds always;
Identity relation (see also Identity function)
I = {(x, x) | x ∈ XScript error: No such module "Check for unknown parameters".};
that is, x1Ix2Script error: No such module "Check for unknown parameters". holds if and only if x1 = x2Script error: No such module "Check for unknown parameters"..

Example

Matrix representation of the relation "is adjacent to" on the set of tectonic plates
Af An Ar Au Ca Co Eu In Ju NA Na Pa Ph SA Sc So
African Af Yes Yes Yes No No No Yes No No Yes No No No Yes No Yes
Antarctic An Yes Yes No Yes No No No No No No Yes Yes No Yes Yes Yes
Arabian Ar Yes No Yes No No No Yes Yes No No No No No No No Yes
Australian Au No Yes No Yes No No Yes Yes No No No Yes No No No Yes
Caribbean Ca No No No No Yes Yes No No No Yes Yes No No Yes No No
Cocos Co No No No No Yes Yes No No No Yes Yes Yes No No No No
Eurasian Eu Yes No Yes Yes No No Yes Yes No Yes No No Yes No No No
Indian In No No Yes Yes No No Yes Yes No No No No No No No Yes
Juan de Fuca Ju No No No No No No No No Yes Yes No Yes No No No No
North american NA Yes No No No Yes Yes Yes No Yes Yes No Yes Yes Yes No No
Nazca Na No Yes No No Yes Yes No No No No Yes Yes No Yes No No
Pacific Pa No Yes No Yes No Yes No No Yes Yes Yes Yes Yes No No No
Philippine Ph No No No No No No Yes No No Yes No Yes Yes No No No
South american SA Yes Yes No No Yes No No No No Yes Yes No No Yes Yes No
Scotia Sc No Yes No No No No No No No No No No No Yes Yes No
Somali So Yes Yes Yes Yes No No No Yes No No No No No No No Yes
The binary relation that describes whether two tectonic plates are in contact is a homogenous relation, because both the first and second argument are from the same set, that is the set of tectonic plates on Earth.

Sixteen 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 (depicted "") indicating contact and 0 ("") no contact. This example expresses a symmetric relation.

Properties

Script error: No such module "Labelled list hatnote". Some important properties that a homogeneous relation R over a set X may have are:

Reflexive
for all x ∈ XScript error: No such module "Check for unknown parameters"., xRxScript error: No such module "Check for unknown parameters".. For example, ≥ is a reflexive relation but > is not.
Irreflexive (or strict)
for all x ∈ XScript error: No such module "Check for unknown parameters"., not xRxScript error: No such module "Check for unknown parameters".. For example, > is an irreflexive relation, but ≥ is not.
Coreflexive
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". then x = yScript error: No such module "Check for unknown parameters"..[7] For example, the relation over the integers in which each odd number is related to itself is a coreflexive relation. The equality relation is the only example of a both reflexive and coreflexive relation, and any coreflexive relation is a subset of the identity relation.
Left quasi-reflexive
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". then xRxScript error: No such module "Check for unknown parameters"..
Right quasi-reflexive
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". then yRyScript error: No such module "Check for unknown parameters"..
Quasi-reflexive
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". then xRxScript error: No such module "Check for unknown parameters". and yRyScript error: No such module "Check for unknown parameters".. A relation is quasi-reflexive if, and only if, it is both left and right quasi-reflexive.

The previous 6 alternatives are far from being exhaustive; e.g., the binary relation xRyScript error: No such module "Check for unknown parameters". defined by y = x2Script error: No such module "Check for unknown parameters". is neither irreflexive, nor coreflexive, nor reflexive, since it contains the pair (0, 0)Script error: No such module "Check for unknown parameters"., and (2, 4)Script error: No such module "Check for unknown parameters"., but not (2, 2)Script error: No such module "Check for unknown parameters"., respectively. The latter two facts also rule out (any kind of) quasi-reflexivity.

Symmetric
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". then yRxScript error: No such module "Check for unknown parameters".. For example, "is a blood relative of" is a symmetric relation, because x is a blood relative of y if and only if y is a blood relative of x.
Antisymmetric
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". and yRxScript error: No such module "Check for unknown parameters". then x = yScript error: No such module "Check for unknown parameters".. For example, ≥ is an antisymmetric relation; so is >, but vacuously (the condition in the definition is always false).[8]
Asymmetric
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". then not yRxScript error: No such module "Check for unknown parameters".. A relation is asymmetric if and only if it is both antisymmetric and irreflexive.[9] For example, > is an asymmetric relation, but ≥ is not.

Again, the previous 3 alternatives are far from being exhaustive; as an example over the natural numbers, the relation xRyScript error: No such module "Check for unknown parameters". defined by x > 2Script error: No such module "Check for unknown parameters". is neither symmetric nor antisymmetric, let alone asymmetric.

Transitive
for all x, y, z ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". and yRzScript error: No such module "Check for unknown parameters". then xRzScript error: No such module "Check for unknown parameters".. A transitive relation is irreflexive if and only if it is asymmetric.[10] For example, "is ancestor of" is a transitive relation, while "is parent of" is not.
Antitransitive
for all x, y, z ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". and yRzScript error: No such module "Check for unknown parameters". then never xRzScript error: No such module "Check for unknown parameters"..
Co-transitive
if the complement of R is transitive. That is, for all x, y, z ∈ XScript error: No such module "Check for unknown parameters"., if xRzScript error: No such module "Check for unknown parameters"., then xRyScript error: No such module "Check for unknown parameters". or yRzScript error: No such module "Check for unknown parameters".. This is used in pseudo-orders in constructive mathematics.
Quasitransitive
for all x, y, z ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". and yRzScript error: No such module "Check for unknown parameters". but neither yRxScript error: No such module "Check for unknown parameters". nor zRyScript error: No such module "Check for unknown parameters"., then xRzScript error: No such module "Check for unknown parameters". but not zRxScript error: No such module "Check for unknown parameters"..
Transitivity of incomparability
for all x, y, z ∈ XScript error: No such module "Check for unknown parameters"., if x and y are incomparable with respect to R and if the same is true of y and z, then x and z are also incomparable with respect to R. This is used in weak orderings.

Again, the previous 5 alternatives are not exhaustive. For example, the relation xRyScript error: No such module "Check for unknown parameters". if (y = 0Script error: No such module "Check for unknown parameters". or y = x+1Script error: No such module "Check for unknown parameters".) satisfies none of these properties. On the other hand, the empty relation trivially satisfies all of them.

Dense
for all x, y ∈ XScript error: No such module "Check for unknown parameters". such that xRyScript error: No such module "Check for unknown parameters"., there exists some z ∈ XScript error: No such module "Check for unknown parameters". such that xRzScript error: No such module "Check for unknown parameters". and zRyScript error: No such module "Check for unknown parameters".. This is used in dense orders.
Connected
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., if x ≠ yScript error: No such module "Check for unknown parameters". then xRyScript error: No such module "Check for unknown parameters". or yRxScript error: No such module "Check for unknown parameters".. This property is sometimesScript error: No such module "Unsubst". called "total", which is distinct from the definitions of "left/right-total" given below.
Strongly connected
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., xRyScript error: No such module "Check for unknown parameters". or yRxScript error: No such module "Check for unknown parameters".. This property, too, is sometimesScript error: No such module "Unsubst". called "total", which is distinct from the definitions of "left/right-total" given below.
Trichotomous
for all x, y ∈ XScript error: No such module "Check for unknown parameters"., exactly one of xRyScript error: No such module "Check for unknown parameters"., yRxScript error: No such module "Check for unknown parameters". or x = yScript error: No such module "Check for unknown parameters". holds. For example, > is a trichotomous relation on the real numbers, while the relation "divides" over the natural numbers is not.[11]
Right Euclidean (or just Euclidean)
for all x, y, z ∈ XScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". and xRzScript error: No such module "Check for unknown parameters". then yRzScript error: No such module "Check for unknown parameters".. For example, = is a Euclidean relation because if x = yScript error: No such module "Check for unknown parameters". and x = zScript error: No such module "Check for unknown parameters". then y = zScript error: No such module "Check for unknown parameters"..
Left Euclidean
for all x, y, z ∈ XScript error: No such module "Check for unknown parameters"., if yRxScript error: No such module "Check for unknown parameters". and zRxScript error: No such module "Check for unknown parameters". then yRzScript error: No such module "Check for unknown parameters"..
Well-founded
every nonempty subset S of X contains a minimal element with respect to R. Well-foundedness implies the descending chain condition (that is, no infinite chain ... xnR...Rx3Rx2Rx1Script error: No such module "Check for unknown parameters". can exist). If the axiom of dependent choice is assumed, both conditions are equivalent.[12][13]

Moreover, all properties of binary relations in general also may apply to homogeneous relations:

Set-like
for all x ∈ XScript error: No such module "Check for unknown parameters"., the class of all y such that yRxScript error: No such module "Check for unknown parameters". is a set. (This makes sense only if relations over proper classes are allowed.)
Left-unique
for all x, z ∈ XScript error: No such module "Check for unknown parameters". and all y ∈ YScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". and zRyScript error: No such module "Check for unknown parameters". then x = zScript error: No such module "Check for unknown parameters"..
Univalent
for all x ∈ XScript error: No such module "Check for unknown parameters". and all y, z ∈ YScript error: No such module "Check for unknown parameters"., if xRyScript error: No such module "Check for unknown parameters". and xRzScript error: No such module "Check for unknown parameters". then y = zScript error: No such module "Check for unknown parameters"..[14]
Total (also called left-total)
for all x ∈ XScript error: No such module "Check for unknown parameters". there exists a y ∈ YScript error: No such module "Check for unknown parameters". such that xRyScript error: No such module "Check for unknown parameters".. This property is different from the definition of connected (also called total by some authors).Script error: No such module "Unsubst".
Surjective (also called right-total)
for all y ∈ YScript error: No such module "Check for unknown parameters"., there exists an x ∈ XScript error: No such module "Check for unknown parameters". such that xRy.

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,Script error: No such module "Unsubst". is a relation that is reflexive, antisymmetric, and transitive. A strict partial order, also called strict order,Script error: No such module "Unsubst". 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.

A univalent relation may also be called a partial function. A (total) function is a partial function that is left-total. An injective function (or partial function) is one whose inverse is univalent. A surjective function is one that is right-total.

Implications and conflicts between properties of homogeneous binary relations
Implications (blue) and conflicts (red) between properties (yellow) of homogeneous binary relations. For example, every asymmetric relation is irreflexive ("Page Template:Color/styles.css has no content.ASym Page Template:Color/styles.css has no content.⇒ Page Template:Color/styles.css has no content.Irrefl"), and no relation on a non-empty set can be both irreflexive and reflexive ("Page Template:Color/styles.css has no content.Irrefl Page Template:Color/styles.css has no content.# Page Template:Color/styles.css has no content.Refl"). Omitting the red edges results in a Hasse diagram.

Operations

If R is a homogeneous relation over a set X then each of the following is a homogeneous relation over X:

Reflexive closure, R=
Defined as R= = {(x, x) | x ∈ X} ∪ RScript error: No such module "Check for unknown parameters". or the smallest reflexive relation over X containing R. This can be proven to be equal to the intersection of all reflexive relations containing R.
Reflexive reduction, R≠
Defined as R≠ = R \ {(x, x) | x ∈ XScript error: No such module "Check for unknown parameters".} or the largest irreflexive relation over X contained in R.
Transitive closure, R+
Defined as the smallest transitive relation over X containing R. This can be seen to be equal to the intersection of all transitive relations containing R.
Reflexive transitive closure, R*
Defined as R* = (R+)=Script error: No such module "Check for unknown parameters"., the smallest preorder containing R.
Reflexive transitive symmetric closure, R≡
Defined as the smallest equivalence relation over X containing R.

All operations defined in Script error: No such module "Section link". also apply to homogeneous relations.

Homogeneous relations by property
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

Enumeration

The set of all homogeneous relations ℬ(X) over a set X is the set 2X×XScript error: No such module "Check for unknown parameters"., 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 ℬ(X), 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 2n2Script error: No such module "Check for unknown parameters". (sequence A002416 in the OEIS):

Number of n-element binary relations of different types
Elem­ents 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 Script error: No such module "val". Script error: No such module "val". Script error: No such module "val". Script error: No such module "val". 355 219 75 24 15
n 2n2 2n(n−1) 2n(n+1)/2 ∑Script error: No such module "Su". k!S(n, k) n! ∑Script error: No such module "Su". 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 number of irreflexive relations is the same as that of reflexive relations.
  • The number of strict partial orders (irreflexive transitive relations) is the same as that of partial orders.
  • The number of strict weak orders is the same as that of total preorders.
  • The total orders are the partial orders that are also total preorders. The number of preorders that are neither a partial order nor a total preorder is, therefore, the number of preorders, minus the number of partial orders, minus the number of total preorders, plus the number of total orders: 0, 0, 0, 3, and 85, respectively.
  • The number of equivalence relations is the number of partitions, which is the Bell number.

The homogeneous relations can be grouped into pairs (relation, complement), except that for n = 0Script error: No such module "Check for unknown parameters". the relation is its own complement. The non-symmetric ones can be grouped into quadruples (relation, complement, inverse, inverse complement).

Examples

Generalizations

  • A binary relation in general need not be homogeneous, it is defined to be a subset R ⊆ X × Y for arbitrary sets X and Y.
  • A finitary relation is a subset R ⊆ X1 × ... × Xn for some natural number n and arbitrary sets X1, ..., Xn, it is also called an n-ary relation.

References

Page Template:Reflist/styles.css has no content.

  1. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  2. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  3. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  4. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  5. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  6. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  7. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  8. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  9. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found..
  10. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found. Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".
  11. ↑ Since neither 5 divides 3, nor 3 divides 5, nor 3=5.
  12. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  13. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  14. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  15. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.
  16. ↑ Lua error in package.lua at line 80: module 'Module:Citation/CS1/Configuration' not found.

Script error: No such module "Check for unknown parameters".

Retrieved from "http://cosmopedia.co/index.php?title=Homogeneous_relation&oldid=4422441"