Hubbry Logo
Homogeneous relationHomogeneous relationMain
Open search
Homogeneous relation
Community hub
Homogeneous relation
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Homogeneous relation
Homogeneous relation
Homogeneous relation
View on Wikipedia
from Wikipedia

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 (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

[edit]

Some particular homogeneous relations over a set X (with arbitrary elements x1, x2) are:

Empty relation
E = ∅;
that is, x1Ex2 holds never;
Universal relation
U = X × X;
that is, x1Ux2 holds always;
Identity relation (see also Identity function)
I = {(x, x) | x ∈ X};
that is, x1Ix2 holds if and only if x1 = x2.

Example

[edit]
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

[edit]
See also: Category:Binary relations

Some important properties that a homogeneous relation R over a set X may have are:

Reflexive
for all x ∈ X, xRx. For example, ≥ is a reflexive relation but > is not.
Irreflexive (or strict)
for all x ∈ X, not xRx. For example, > is an irreflexive relation, but ≥ is not.
Coreflexive
for all x, y ∈ X, if xRy then x = y.[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 ∈ X, if xRy then xRx.
Right quasi-reflexive
for all x, y ∈ X, if xRy then yRy.
Quasi-reflexive
for all x, y ∈ X, if xRy then xRx and yRy. 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 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.

Symmetric
for all x, y ∈ X, if xRy then yRx. 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 ∈ X, if xRy and yRx then x = y. For example, ≥ is an antisymmetric relation; so is >, but vacuously (the condition in the definition is always false).[8]
Asymmetric
for all x, y ∈ X, if xRy then not yRx. 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 xRy defined by x > 2 is neither symmetric nor antisymmetric, let alone asymmetric.

Transitive
for all x, y, z ∈ X, if xRy and yRz then xRz. 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 ∈ X, if xRy and yRz then never xRz.
Co-transitive
if the complement of R is transitive. That is, for all x, y, z ∈ X, if xRz, then xRy or yRz. This is used in pseudo-orders in constructive mathematics.
Quasitransitive
for all x, y, z ∈ X, if xRy and yRz but neither yRx nor zRy, then xRz but not zRx.
Transitivity of incomparability
for all x, y, z ∈ X, 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 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.

Dense
for all x, y ∈ X such that xRy, there exists some z ∈ X such that xRz and zRy. This is used in dense orders.
Connected
for all x, y ∈ X, if x ≠ y then xRy or yRx. This property is sometimes[citation needed] called "total", which is distinct from the definitions of "left/right-total" given below.
Strongly connected
for all x, y ∈ X, xRy or yRx. This property, too, is sometimes[citation needed] called "total", which is distinct from the definitions of "left/right-total" given below.
Trichotomous
for all x, y ∈ X, exactly one of xRy, yRx or x = y 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 ∈ X, if xRy and xRz then yRz. For example, = is a Euclidean relation because if x = y and x = z then y = z.
Left Euclidean
for all x, y, z ∈ X, if yRx and zRx then yRz.
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...Rx3Rx2Rx1 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 ∈ X, the class of all y such that yRx is a set. (This makes sense only if relations over proper classes are allowed.)
Left-unique
for all x, z ∈ X and all y ∈ Y, if xRy and zRy then x = z.
Univalent
for all x ∈ X and all y, z ∈ Y, if xRy and xRz then y = z.[14]
Total (also called left-total)
for all x ∈ X there exists a y ∈ Y such that xRy. This property is different from the definition of connected (also called total by some authors).[citation needed]
Surjective (also called right-total)
for all y ∈ Y, there exists an x ∈ X 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,[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.

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 ("ASym ⇒ Irrefl"), and no relation on a non-empty set can be both irreflexive and reflexive ("Irrefl # Refl"). Omitting the red edges results in a Hasse diagram.

Operations

[edit]

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} ∪ R 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 ∈ X} 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+)=, the smallest preorder containing R.
Reflexive transitive symmetric closure, R≡
Defined as the smallest equivalence relation over X containing R.

All operations defined in Binary relation § Operations 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

[edit]

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):

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 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 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 = 0 the relation is its own complement. The non-symmetric ones can be grouped into quadruples (relation, complement, inverse, inverse complement).

Examples

[edit]

Generalizations

[edit]
  • 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

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Homogeneous relation

View on Grokipedia
from Grokipedia
In , a homogeneous relation (also known as an endorelation) on a set XX is a from XX to itself, formally defined as a of the X×XX \times X. This structure captures pairwise relationships among elements of the same set, distinguishing it from heterogeneous relations that connect distinct sets. Homogeneous relations exhibit key that classify their behavior and utility. A relation is reflexive if every element relates to itself (∀a∈X,aRa\forall a \in X, aRa); symmetric if aRbaRb implies bRabRa; antisymmetric if aRbaRb and bRabRa imply a=ba = b; and transitive if aRbaRb and bRcbRc imply aRcaRc. Additional include antireflexivity (no element relates to itself) and completeness (for all distinct elements, at least one relates to the other). Combinations of these yield significant structures: for instance, reflexive, symmetric, and transitive relations form equivalence relations, which partition sets into classes, while reflexive, antisymmetric, and transitive relations define partial orders, modeling hierarchies like divisibility on natural numbers or the less-than-or-equal-to relation on integers. These relations are foundational in , appearing in as adjacency relations (where edges represent relatedness) and in for studying lattices and posets. They can be represented via directed graphs or matrices, facilitating computational analysis and visualization of relational properties.

Definition and Fundamentals

Formal Definition

In , a homogeneous relation, also known as an endorelation, on a set AA is formally defined as a R⊆A×AR \subseteq A \times A, where A×AA \times A is the Cartesian product of AA with itself.\] This formulation emphasizes the homogeneity, as both the domain and codomain of the relation are identical, namely the carrier set $A$.\[ For elements a,b∈Aa, b \in A, the pair (a,b)∈R(a, b) \in R indicates that aa is related to bb under the relation RR; otherwise, they are not related.$$] Trivial cases of homogeneous relations include the empty relation ∅⊆A×A\emptyset \subseteq A \times A, which relates no elements, and the full relation A×AA \times A, which relates every pair of elements in AA.[$$ These extremes illustrate the range of possible homogeneous relations on a given carrier set. Homogeneous relations provide a framework for modeling intra-set connections, as a special case of binary relations where the domain and codomain are the same set, thus differing from heterogeneous binary relations that connect distinct sets, and relaxing conditions like totality or single-valuedness found in functions on the same set.$$]

Notation and Distinction from Binary Relations

Homogeneous relations are commonly denoted as subsets of the Cartesian square of a set, written as R⊆A×AR \subseteq A \times A or equivalently R⊆A2R \subseteq A^2, where AA is the underlying set. This notation emphasizes that the relation operates entirely within AA, with elements of RR being ordered pairs (a,b)(a, b) where both a,b∈Aa, b \in A. For convenience, membership in the relation is often expressed using infix notation: aRbaRb if and only if (a,b)∈R(a, b) \in R. When the set AA is finite, homogeneous relations can also be represented graphically as directed graphs (digraphs), where vertices correspond to elements of AA and directed edges indicate pairs (a,b)∈R(a, b) \in R. A homogeneous relation represents a special case of a , which more generally is a S⊆X×YS \subseteq X \times Y for possibly distinct sets XX and YY. In the homogeneous case, the domain and coincide as the same set AA, restricting the relation to pairs within AA; this contrasts with heterogeneous binary relations, where X≠YX \neq Y allows mappings between different sets. The terminology "relation on AA" specifically denotes a homogeneous , distinguishing it from the broader " from XX to YY." This distinction helps avoid confusion with functions, which are themselves special s (homogeneous or otherwise) where each element in the domain pairs with exactly one element in the . The term "homogeneous relation" emerged in early 20th-century to precisely specify relations confined to a single set, highlighting their uniformity in domain and compared to general binary relations.

Properties

Fundamental Properties

A homogeneous relation RR on a set AA is reflexive if every element is related to itself, formally expressed as [ \forall a \in A, (a, a) \in R. This property ensures the relation includes all self-pairs, corresponding to self-loops at every vertex in the directed graph representation of $R$.[](https://www.stat.cmu.edu/~cshalizi/networks/16-1/lectures/01/lecture-01.pdf) To verify reflexivity, one simply checks that all diagonal entries in the adjacency matrix of $R$ are present, or directly confirms the condition for each element in $A$.[](https://www.cas.mcmaster.ca/~kahl/CS2LC3/2021/COMPSCI_2LC3_Fall2021_Lecture_Slides_10up-A4.pdf) The relation $R$ is symmetric if whenever one element is related to another, the reverse holds, given by \forall a, b \in A, (a, b) \in R \implies (b, a) \in R. [Symmetry](/page/Symmetry) implies that $R$ equals its converse $R^T$, meaning the relation is bidirectional. This contrasts with irreflexivity, where no element relates to itself ($\forall a \in A, (a, a) \notin R$), and antisymmetry, where mutual relatedness forces equality ($\forall a, b \in A, (a, b) \in R \land (b, a) \in R \implies a = b$). Combined with reflexivity, [symmetry](/page/Symmetry) interprets the graph of $R$ as undirected with self-loops, as every edge appears in both directions and all vertices have loops. Verification involves checking that for every pair $(a, b) \in R$, the pair $(b, a)$ is also present.[](https://titurel.org/Papers/RelConceptsSocChoice.pdf)[](https://www.cas.mcmaster.ca/~kahl/CS2LC3/2021/COMPSCI_2LC3_Fall2021_Lecture_Slides_10up-A4.pdf)[](https://www.stat.cmu.edu/~cshalizi/networks/16-1/lectures/01/lecture-01.pdf) Asymmetry strengthens antisymmetry by prohibiting any bidirectional pairs, defined as \forall a, b \in A, (a, b) \in R \implies (b, a) \notin R. This implies both irreflexivity (no self-loops) and antisymmetry, as any self-relation or mutual pair would violate the condition. In graph terms, asymmetric relations correspond to directed graphs without self-loops or bidirectional edges. To verify, for every $(a, b) \in R$ with $a \neq b$, confirm that $(b, a) \notin R$.[](https://titurel.org/Papers/RelConceptsSocChoice.pdf)[](https://www.cas.mcmaster.ca/~kahl/CS2LC3/2021/COMPSCI_2LC3_Fall2021_Lecture_Slides_10up-A4.pdf) A homogeneous relation $R$ is connected if every pair of distinct elements is related in at least one direction: \forall a, b \in A, a \neq b \implies (a, b) \in R \lor (b, a) \in R. This ensures $R \cup R^T = A \times A \setminus \Delta$, where $\Delta$ is the diagonal, covering all off-diagonal pairs without gaps. In graphical interpretation, the underlying undirected graph of a connected relation is complete, meaning every pair of distinct vertices is connected by at least one directed edge (and exactly one if asymmetric, forming a tournament). Verification requires checking that no distinct pair lacks both directions.[](https://titurel.org/Papers/RelConceptsSocChoice.pdf) ### Composite Properties A homogeneous relation $R$ on a set $A$ is transitive if, for all $a, b, c \in A$, whenever $(a, b) \in R$ and $(b, c) \in R$, it follows that $(a, c) \in R$.[](https://proofwiki.org/wiki/Definition:Transitive_Relation/Definition_1) This property captures the idea of "chaining" elements, where direct connections can be extended through intermediate steps without breaking the relational structure. In the context of [order theory](/page/Order_theory), transitivity ensures that if elements form a [chain](/page/Chain) $a R b$ and $b R c$, then the entire chain $a R c$ holds, preserving the sequential interpretation of the relation.[](https://www.cs.fsu.edu/~lacher/courses/MAD3105/lectures/s1_4partord.pdf) When viewing a homogeneous relation as the edge set of a [directed graph](/page/Directed_graph) on vertex set $A$, transitivity corresponds to the relation being closed under paths: if there is a directed path from $a$ to $c$ via $b$, then a direct edge from $a$ to $c$ must exist.[](https://www.cs.tufts.edu/comp/150FP/archive/al-aho/transitive-reduction.pdf) This path closure property is fundamental in [graph theory](/page/Graph_theory) for modeling [reachability](/page/Reachability) and has applications in computing transitive closures via algorithms like Floyd-Warshall.[](https://www.geeksforgeeks.org/dsa/transitive-closure-of-a-graph/) For a homogeneous relation that is both reflexive and transitive—forming a [preorder](/page/Pre-order)—composition with itself yields [idempotence](/page/Idempotence): $R \circ R = R$. Reflexivity ensures $R \subseteq R \circ R$, while transitivity implies $R \circ R \subseteq R$, achieving equality under repeated application.[](https://mathoverflow.net/questions/77621/categorifying-idempotent-relations) This [idempotence](/page/Idempotence) highlights how transitivity builds on reflexivity to stabilize the relation under relational composition. A [density](/page/Density) property for homogeneous relations generalizes the notion from dense orders: for all $a, b \in A$ with $a R b$, there exists $c \in A$ such that $a R c$ and $c R b$, with $c \neq a, b$ in strict cases.[](http://www.econ2.jhu.edu/jobmarket/2023/GhoshA/NonThesisPapers/SeparateGhoshA.pdf) In order relations, this means no "gaps" between comparable elements, as seen in the rational numbers under the usual order, where between any $a < b$, there is $c$ with $a < c < b$. Such [density](/page/Density) often pairs with transitivity to ensure interpolative structures without discrete jumps. Euclidean relations provide another composite property, defined such that for all $x, y, z \in A$, if $x R y$ and $x R z$, then $y R z$.[](https://ncatlab.org/nlab/show/euclidean%2Brelation) When combined with reflexivity, Euclidean relations yield equivalence relations, as the property enforces uniformity in "reach" from any point.[](https://ncatlab.org/nlab/show/euclidean%2Brelation) These composite properties often emerge from combining fundamental ones like reflexivity, symmetry, and antisymmetry. For instance, a relation that is reflexive, transitive, and antisymmetric constitutes a partial order, enabling structured comparisons without cycles or redundancies.[](https://www.cs.fsu.edu/~lacher/courses/MAD3105/lectures/s1_4partord.pdf) However, not all combinations hold; symmetric relations need not be transitive, as illustrated by the relation on $\{1,2,3\}$ defined by $R = \{(1,2),(2,1),(2,3),(3,2)\}$, which is symmetric but fails transitivity since $1 R 2$ and $2 R 3$ yet not $1 R 3$.[](https://www.nku.edu/~longa/classes/2009spring/mat385/tablet/highlights4.1.pdf) This counterexample underscores how transitivity requires additional constraints beyond pairwise reciprocity. ## Special Types ### Equivalence Relations An equivalence relation on a set $A$ is a homogeneous relation $R \subseteq A \times A$ that is reflexive, symmetric, and transitive. Reflexivity means that for every $a \in A$, $a R a$; symmetry means that if $a R b$, then $b R a$; and transitivity means that if $a R b$ and $b R c$, then $a R c$. These properties ensure that the relation behaves analogously to equality but on a coarser scale, grouping elements into clusters where elements within a cluster are considered "equivalent" under $R$.[](https://web.math.ucsb.edu/~mpedrick/teaching/8f18/8w16_key.pdf) A fundamental theorem connects equivalence relations to partitions of the set $A$: if $R$ is an [equivalence relation](/page/Equivalence_relation) on $A$, then the equivalence classes induced by $R$ form a partition of $A$, meaning the classes are nonempty, disjoint, and their union is $A$. Conversely, every partition of $A$ determines an [equivalence relation](/page/Equivalence_relation) on $A$, where two elements are related if they belong to the same part of the partition. The [equivalence class](/page/Equivalence_class) of an element $a \in A$, denoted $_R$, is defined as _R = { b \in A \mid a R b }. Transitivity implies that each [equivalence class](/page/Equivalence_class) is closed under [chain](/page/Chain)s of the relation: if $a R b_1$, $b_1 R b_2$, ..., $b_{n-1} R b_n$, then $a R b_n$, ensuring all elements in a [chain](/page/Chain) remain within the same class. The number of distinct equivalence classes is called the index of the relation, which measures the "fineness" of the partition.[](https://www3.cs.stonybrook.edu/~cse213/slides/4equ.pdf)[](https://sites.millersville.edu/bikenaga/math-proof/equivalence-relations/equivalence-relations.html)[](https://courses.grainger.illinois.edu/cs373/fa2013/Lectures/lec11.pdf) Equivalence relations arise naturally in applications such as congruence modulo $n$ on the integers $\mathbb{Z}$, where $a \equiv b \pmod{n}$ if $n$ divides $a - b$; this relation is reflexive, symmetric, and transitive, partitioning $\mathbb{Z}$ into $n$ classes represented by the remainders $0, 1, \dots, n-1$. For example, modulo 5, the classes are $\{ \dots, -10, -5, 0, 5, 10, \dots \}$, $\{ \dots, -9, -4, 1, 6, 11, \dots \}$, and so on. Another application is the kernel of a function $f: A \to B$, defined by $a \sim b$ if and only if $f(a) = f(b)$; this kernel is an equivalence relation whose classes are the preimages $f^{-1}(y)$ for $y \in B$, partitioning $A$ according to the values of $f$. Given any partition of $A$, there exists a unique equivalence relation whose classes are exactly the blocks of that partition, established by relating elements within each block and no others.[](https://math.okstate.edu/people/binegar/3613/3613-l11.pdf)[](https://home.cs.colorado.edu/~jgrochow/Grochow_UofC_Masters_08_Equivalence_Relations.pdf) ### Order Relations A partial order on a set $X$ is a homogeneous relation $\leq$ that is reflexive, antisymmetric, and transitive.[](https://link.springer.com/chapter/10.1007/978-3-319-59495-8_2) Reflexivity ensures $x \leq x$ for all $x \in X$, antisymmetry implies $x \leq y$ and $y \leq x$ yields $x = y$, and transitivity means if $x \leq y$ and $y \leq z$, then $x \leq z$.[](https://link.springer.com/content/pdf/10.1007/978-1-4612-4052-5_8.pdf) A set equipped with a partial order is called a [partially ordered set](/page/Partially_ordered_set), or poset.[](https://link.springer.com/content/pdf/10.1007/978-1-4612-4052-5_8.pdf) Hasse diagrams provide a visual representation of posets by depicting the covering relations, where an element $y$ covers $x$ (denoted $x \prec y$) if $x < y$ and no $z$ satisfies $x < z < y$, omitting transitive edges for clarity.[](https://link.springer.com/article/10.1007/s10801-021-01038-6) A strict partial order is the irreflexive counterpart to a partial order, defined as a homogeneous relation $<$ that is irreflexive (no $x < x$) and transitive, with antisymmetry following as a consequence.[](https://link.springer.com/article/10.1007/s13222-017-0264-7) For example, the standard less-than relation $<$ on the real numbers $\mathbb{R}$ forms a strict partial order.[](https://link.springer.com/article/10.1007/s13222-017-0264-7) In general, if $\leq$ is a partial order, then the strict partial order associated with it is $<$ defined by $x < y$ if and only if $x \leq y$ and $x \neq y$. A [total order](/page/Total_order), also known as a linear order, is a partial order $\leq$ on $X$ such that every pair of elements is comparable, meaning for all $x, y \in X$, either $x \leq y$ or $y \leq x$.[](https://link.springer.com/content/pdf/10.1007/978-3-642-56893-0_4.pdf) This total comparability distinguishes total orders from general partial orders, where incomparability is possible. While linear orders ensure full comparability, lattices are partial orders that additionally require the existence of least upper bounds (suprema) and greatest lower bounds (infima) for every pair of elements. Notably, every linear order is itself a lattice, with joins and meets given by the [maximum and minimum](/page/Maximum_and_minimum), respectively.[](https://www.infinitelymore.xyz/p/lattices) Key properties of partial orders include the Dedekind-MacNeille completion, which embeds a poset into a [complete lattice](/page/Complete_lattice) by adjoining all existing suprema and infima of [subsets](/page/Subset), preserving the original order.[](https://link.springer.com/article/10.1007/s11083-024-09691-9) [Zorn's lemma](/page/Zorn's_lemma) applies to partial orders where every nonempty [chain](/page/Chain) (totally ordered subset) has an upper bound, guaranteeing the existence of maximal elements in such posets.[](https://www.ams.org/books/car/030/car030-endmatter.pdf) Covering relations in posets underpin the structure of Hasse diagrams and facilitate the study of minimal extensions or reductions in the order.[](https://link.springer.com/article/10.1007/s10801-021-01038-6) ## Examples and Applications ### Concrete Examples One concrete example of a homogeneous relation is the equality relation on the natural numbers $\mathbb{N}$, defined by $n \, R \, m$ if and only if $n = m$, or explicitly $R = \{(n, n) \mid n \in \mathbb{N}\}$. This relation is reflexive, as every natural number equals itself, and it is an equivalence relation overall, partitioning $\mathbb{N}$ into singleton sets.[](https://www.cs.yale.edu/homes/aspnes/pinewiki/Relations.html) Another example is the divisibility relation on the positive integers, where $n \, R \, m$ if and only if $n$ divides $m$ (i.e., there exists a positive integer $k$ such that $m = k n$). This relation is reflexive, since $n$ divides itself for any $n$; transitive, because if $n$ divides $m$ and $m$ divides $l$, then $n$ divides $l$; and antisymmetric, as $n$ divides $m$ and $m$ divides $n$ implies $n = m$. Thus, it forms a partial order on the positive integers, with 1 related to every element (as 1 divides all) and primes as the minimal elements above 1 (with no proper divisors other than 1).[](https://www.cs.yale.edu/homes/aspnes/pinewiki/Relations.html)[](https://pi.math.cornell.edu/~bhwang/3040/07_relations.pdf) The "less than or equal to" relation on the real numbers $\mathbb{R}$, defined by $x \, R \, y$ [if and only if](/page/If_and_only_if) $x \leq y$, provides a [total order](/page/Total_order) example. It is reflexive ($x \leq x$), transitive (if $x \leq y$ and $y \leq z$, then $x \leq z$), and antisymmetric (if $x \leq y$ and $y \leq x$, then $x = y$); moreover, for any $x, y \in \mathbb{R}$, either $x \leq y$ or $y \leq x$, ensuring totality. This relation underpins much of [real analysis](/page/Real_analysis), ordering the continuum densely without gaps.[](https://www3.cs.stonybrook.edu/~pfodor/courses/CSE215/L14-Relations.pdf)[](https://www.cs.odu.edu/~toida/nerzic/content/relation/order/order.html) In [graph theory](/page/Graph_theory), the adjacency relation on a set of vertices $V$ is given by $E \subseteq V \times V$, where $v \, R \, w$ if there is an edge connecting $v$ and $w$. For undirected graphs, this relation is symmetric (if $v \, R \, w$, then $w \, R \, v$), representing mutual connections, while directed graphs allow asymmetry. For instance, in a simple undirected graph with $V = \{a, b, c\}$ and edges $\{(a,b), (b,c)\}$, the relation includes those pairs plus possibly loops if reflexive. This models pairwise connections in networks.[](https://www-users.cse.umn.edu/classes/Spring-2019/csci8314/FILES/LecN4.pdf)[](https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/f471f7b7034fabe8bbba5507df7d307f_MIT6_042JF10_chap05.pdf) In social networks, the "friend of" relation on a set of people $P$ is often modeled as symmetric, where $p \, R \, q$ if $p$ and $q$ are mutual friends. This homogeneity captures bidirectional ties, as in datasets where friendships are confirmed reciprocally, excluding one-sided acquaintances. For example, in a network of five individuals, if A is friends with B and C, and B with C, the relation includes pairs like (A,B), (B,A), forming a [clique](/page/Clique) if fully connected. Such relations enable analysis of [community](/page/Community) structures via [symmetry](/page/Symmetry).[](https://dlab.berkeley.edu/news/concepts-and-measurements-social-network-analysis)[](https://scholar.harvard.edu/files/pgoldsmithpinkham/files/socialnetworks2.pdf) ### Abstract and Theoretical Examples In abstract settings, homogeneous relations often arise in [order theory](/page/Order_theory) and related fields, where they structure infinite or conceptual collections without relying on finite enumerations. A canonical example is the subset inclusion relation on the power set of a set $A$, denoted $\mathcal{P}(A)$, where $S \subseteq T$ for $S, T \in \mathcal{P}(A)$. This relation is reflexive, as every set includes itself; transitive, since if $S \subseteq T$ and $T \subseteq U$, then $S \subseteq U$; and antisymmetric, meaning if $S \subseteq T$ and $T \subseteq S$, then $S = T$. Thus, it forms a partial order on $\mathcal{P}(A)$, even when $A$ is infinite, providing a foundational structure for comparing arbitrary collections of elements.[](https://math.berkeley.edu/~wodzicki/H104/OrderedSets.pdf) Another theoretical example is the [lexicographic order](/page/Lexicographic_order) on the set of words over an ordered [alphabet](/page/Alphabet) $\Sigma$, such as finite sequences from $\mathbb{N}$ equipped with the usual order. For words $u = u_1 u_2 \cdots u_m$ and $v = v_1 v_2 \cdots v_n$, define $u \leq_{\lex} v$ if either $u$ is a prefix of $v$, or at the first position $i$ where they differ, $u_i < v_i$. This relation is a [total order](/page/Total_order) on the set of all finite words, extending naturally to infinite sequences or functions from $\mathbb{N}$ to $\Sigma$, and it captures hierarchical comparisons in [symbolic dynamics](/page/Symbolic_dynamics) and [formal language](/page/Formal_language) theory.[](https://sites.millersville.edu/bikenaga/math-proof/order-relations/order-relations.pdf) The pointwise order on the set of functions from a set $X$ to $\mathbb{R}$ (with the standard order on $\mathbb{R}$) provides a homogeneous relation suited to [functional analysis](/page/Functional_analysis). Define $f \leq g$ if $f(x) \leq g(x)$ for all $x \in X$, regardless of whether $X$ is finite or infinite. This is reflexive, as $f(x) \leq f(x)$ holds everywhere; transitive, since if $f \leq g$ and $g \leq h$, then $f(x) \leq h(x)$ for all $x$; and antisymmetric, yielding $f = g$ when both inequalities hold. It forms a partial order that underpins lattice structures in spaces of real-valued functions, such as in optimization over unbounded domains.[](https://healy.econ.ohio-state.edu/kcb/Notes/Lattice.pdf) In [topology](/page/Topology), the specialization preorder on a [topological space](/page/Topological_space) $X$ defines a homogeneous relation via the closure operator: $x \leq y$ if $x \in \overline{\{y\}}$, the closure of the singleton $\{y\}$. This relation is reflexive and transitive, forming a [preorder](/page/Preorder) on $X$; it becomes a partial order if $X$ is $T_0$ ([Kolmogorov space](/page/Kolmogorov_space)), distinguishing points topologically. Neighborhood relations can be abstracted similarly on the power set, where $U$ relates to $V$ if $U$ contains a neighborhood basis element of $V$, but the specialization preorder highlights how closure operators induce order structures on infinite spaces like manifolds or function spaces.[](https://people.wku.edu/tom.richmond/Papers/PartPseudoM.pdf) Group actions yield orbit equivalence as a homogeneous relation on a set $X$ acted upon by a group $G$. Two elements $x, y \in X$ satisfy $x \sim y$ if there exists $g \in G$ such that $g \cdot x = y$, partitioning $X$ into orbits. This is an [equivalence relation](/page/Equivalence_relation)—reflexive via the identity, symmetric by inverses, and transitive by composition—applicable to infinite sets, such as in dynamical systems where orbits represent trajectories under continuous group operations like rotations on the circle.[](https://www.math.northwestern.edu/~len/d70/chap2.pdf) ## Operations ### Set-Theoretic Operations Homogeneous relations on a set $A$, being subsets of $A \times A$, admit the standard set-theoretic operations of union, [intersection](/page/Intersection), and complement relative to the universal set $A \times A$. These operations treat the relations purely as sets of ordered pairs, without regard to any additional relational structure such as reflexivity or transitivity.[](https://math.libretexts.org/Bookshelves/Mathematical_Logic_and_Proof/Proofs_and_Concepts_-_The_Fundamentals_of_Abstract_Mathematics_(Morris_and_Morris)/07%3A_Equivalence_relations/7.01%3A_Binary_relations) The union of two homogeneous relations $R$ and $S$ on $A$ is defined as R \cup S = { (a, b) \in A \times A \mid aRb \lor aSb }. This operation combines all pairs related under either $R$ or $S$, resulting in another homogeneous relation on $A$. Similarly, the intersection $R \cap S$ consists of pairs related under both: R \cap S = { (a, b) \in A \times A \mid aRb \land aSb }. These definitions follow directly from the set operations on subsets of $A \times A$.[](https://math.libretexts.org/Bookshelves/Mathematical_Logic_and_Proof/Proofs_and_Concepts_-_The_Fundamentals_of_Abstract_Mathematics_(Morris_and_Morris)/07%3A_Equivalence_relations/7.01%3A_Binary_relations)[](https://www.math.hkust.edu.hk/~mabfchen/Math2343/Relation.pdf) The complement of a homogeneous relation $R$ on $A$ is the set of all ordered pairs in $A \times A$ not in $R$: \overline{R} = A \times A \setminus R = { (a, b) \in A \times A \mid \lnot aRb }. This operation inverts membership for pairs within the Cartesian product. Certain properties are preserved or inverted under complementation; for instance, if $R$ is reflexive (containing all $(a, a)$ for $a \in A$), then $\overline{R}$ is irreflexive (containing no $(a, a)$), and vice versa.[](https://math.libretexts.org/Bookshelves/Mathematical_Logic_and_Proof/Proofs_and_Concepts_-_The_Fundamentals_of_Abstract_Mathematics_(Morris_and_Morris)/07%3A_Equivalence_relations/7.01%3A_Binary_relations)[](https://courses.cs.duke.edu/spring05/cps102/notes/slides15-4up.pdf) For a subset $B \subseteq A$, the restriction of $R$ to $B$, denoted $R \vert_B$, is the homogeneous relation on $B$ obtained by intersecting $R$ with $B \times B$: R \vert_B = R \cap (B \times B) = { (a, b) \in B \times B \mid aRb }. This induces the subrelation on $B$, preserving only those pairs from $R$ where both elements lie in $B$.[](https://math.libretexts.org/Bookshelves/Mathematical_Logic_and_Proof/Proofs_and_Concepts_-_The_Fundamentals_of_Abstract_Mathematics_(Morris_and_Morris)/07%3A_Equivalence_relations/7.01%3A_Binary_relations) The collection of all homogeneous relations on $A$ forms the power set $\mathcal{P}(A \times A)$, to which basic set operations like union and intersection apply directly, enabling comparisons such as inclusion $R \subseteq S$ (where every pair in $R$ is also in $S$). These operations underpin more advanced manipulations while maintaining the set-theoretic foundation.[](https://sites.math.rutgers.edu/~saks/300S/Part9.pdf) ### Relational Operations In the context of homogeneous relations, which are binary relations on a single set $A$, several operations are defined that generate new relations while preserving the homogeneity property, meaning the resulting relation remains a subset of $A \times A$. One fundamental operation is relational composition. Given two homogeneous relations $R$ and $S$ on $A$, their composition $R \circ S$ is defined as the set of pairs $(a, c) \in A \times A$ such that there exists some $b \in A$ with $(a, b) \in R$ and $(b, c) \in S$.[](https://www.cs.cornell.edu/courses/cs6860/2019sp/Handouts/HKT1-3.pdf) This operation corresponds to connecting paths of length two in the directed graph representation of the relations and inherently preserves homogeneity since both inputs are subsets of $A \times A$.[](https://math.unm.edu/~nitsche/mctp/summer/lecturenotes/algstruc/AlgStructLN.pdf) Composition is associative, meaning $(R \circ S) \circ T = R \circ (S \circ T)$ for any homogeneous relations $R, S, T$ on $A$, which follows from the existential quantification over intermediate elements being independent of grouping.[](http://boole.stanford.edu/pub/ocbr.pdf) Another key operation is the converse, or inverse, of a relation. For a homogeneous relation $R \subseteq A \times A$, its converse $R^{-1}$ is the set $\{(b, a) \in A \times A \mid (a, b) \in R\}$, which reverses the direction of all pairs while remaining homogeneous.[](https://cs.carleton.edu/faculty/dlibenno/book/ch08_relations_2021_April_05.pdf) A homogeneous relation $R$ is symmetric if and only if $R = R^{-1}$, as this equality ensures that whenever $(a, b) \in R$, the pair $(b, a)$ is also present.[](https://ics.uci.edu/~alspaugh/cls/shr/relation.html) Closures provide ways to extend a relation to satisfy specific properties while minimally enlarging it. The transitive closure of a homogeneous relation $R$ on $A$ is the smallest transitive homogeneous relation $R^+$ such that $R \subseteq R^+$, obtained by including all pairs $(a, c)$ where there is a finite path from $a$ to $c$ through elements connected by $R$.[](https://www.cs.yale.edu/homes/aspnes/pinewiki/Relations.html) For finite sets $A$ with $|A| = n$, this can be computed efficiently using Warshall's algorithm, which iteratively builds the closure by considering each element as a potential intermediate vertex in paths; starting from the [adjacency matrix](/page/Adjacency_matrix) of $R$, it updates entries via dynamic programming in $O(n^3)$ time, where the $k$-th iteration incorporates paths using the first $k$ elements.[](https://dl.acm.org/doi/10.1145/321105.321107) The transitive closure is idempotent, satisfying $(R^+)^+ = R^+$, since adding paths to an already transitive relation yields no new pairs.[](https://fanchung.ucsd.edu/ron/papers/72_08_complements.pdf) The reflexive closure of a homogeneous relation $R$ on $A$ is the smallest reflexive homogeneous relation $R_{\text{ref}}$ containing $R$, formed by adjoining the identity relation $\Delta = \{(a, a) \mid a \in A\}$ to $R$, so $R_{\text{ref}} = R \cup \Delta$.[](https://www.cs.odu.edu/~toida/nerzic/content/relation/closure/closure.html) This operation ensures reflexivity by including all self-pairs without altering existing connections, and it remains homogeneous as $\Delta \subseteq A \times A$.[](https://www3.cs.stonybrook.edu/~cse213/slides/4relations.pdf) ## Enumeration ### Counting Homogeneous Relations A homogeneous relation on a [finite set](/page/Finite_set) $A$ with $|A| = n$ is equivalent to a [subset](/page/Subset) of the [Cartesian product](/page/Cartesian_product) $A \times A$, which contains exactly $n^2$ ordered pairs. Since the power set of a set with $m$ elements has cardinality $2^m$, the total number of homogeneous relations on $A$ is $2^{n^2}$.[](https://people.cs.pitt.edu/~milos/courses/cs441-Spring13/lectures/Class20.pdf)[](https://www.csd.uwo.ca/~mmorenom/cs2214_moreno/notes/9-handout.pdf) Among these relations, two are particularly trivial: the empty relation, which contains no ordered pairs, and the full relation, which includes all $n^2$ possible ordered pairs from $A \times A$.[](https://people.cs.pitt.edu/~milos/courses/cs441-Spring13/lectures/Class20.pdf) This counting arises from the binary choice for each of the $n^2$ possible ordered pairs—whether to include it in the relation or not—corresponding to directed graphs on $n$ labeled vertices that allow loops (one for each self-pair).[](https://dspace.mit.edu/bitstream/handle/1721.1/104426/6-042j-spring-2010/contents/readings/MIT6_042JS10_chap08.pdf) In contrast, the number of simple undirected graphs on $n$ labeled vertices (without loops or multiple edges) is $2^{n(n-1)/2}$, reflecting binary choices only for the $\binom{n}{2}$ unordered pairs $\{i, j\}$ with $i < j$.[](https://cseweb.ucsd.edu/classes/sp16/cse21-bd/slides/day20_S16_Lecture_B.pdf) The quantity $2^{n^2}$ exhibits [exponential growth](/page/Exponential_growth) in $n^2$, making the total number of homogeneous relations grow extremely rapidly as $n$ increases; asymptotically, its logarithm base 2 is precisely $n^2$. For small values of $n$, the counts are as follows: | $n$ | Number of homogeneous relations | |-------|---------------------------------| | 1 | 2 | | 2 | 16 | | 3 | 512 | | 4 | 65,536 | | 5 | 33,554,432 | These values follow directly from evaluating $2^{n^2}$.[](https://www.csd.uwo.ca/~mmorenom/cs2214_moreno/notes/9-handout.pdf) ### Relations with Specific Properties Homogeneous relations with specific properties are those that satisfy additional constraints beyond being subsets of the Cartesian product of a set with itself. These properties reduce the total number of possible relations from $2^{n^2}$ on a set with $n$ elements, leading to more structured counts that are central to combinatorics and order theory. A reflexive homogeneous relation requires that every element is related to itself, fixing the $n$ diagonal entries of the adjacency matrix to 1. The remaining $n(n-1)$ off-diagonal entries can be chosen arbitrarily as 0 or 1, yielding exactly $2^{n(n-1)}$ reflexive relations on an $n$-element set. For example, on a set with 3 elements, there are $2^{6} = 64$ reflexive relations. This count arises because reflexivity imposes a strict condition only on the self-loops, leaving the directed edges between distinct elements free. Symmetric homogeneous relations satisfy the condition that if $(x, y)$ is in the relation, then $(y, x)$ is also in the relation. In matrix terms, the relation matrix must be symmetric across the [main diagonal](/page/Main_diagonal). The $n$ diagonal entries and the $\binom{n}{2} = n(n-1)/2$ upper-triangular entries (with the lower triangle determined by symmetry) can each be chosen independently as 0 or 1, resulting in $2^{n(n+1)/2}$ symmetric relations. For $n=3$, this gives $2^{6} = 64$ symmetric relations, corresponding to all possible undirected graphs with loops on 3 vertices. These relations model undirected connections, including self-loops, and are foundational in [graph theory](/page/Graph_theory). (Kreher and Stinson, *Combinatorial Algorithms*, 1999) Transitive homogeneous relations obey the rule that if $(x, y)$ and $(y, z)$ are in the relation, then $(x, z)$ must also be in the relation. Unlike reflexive or symmetric cases, there is no known closed-form [formula](/page/Formula) for the number of transitive relations on an $n$-element set; the sequence begins 2, 13, 171, 3994 for $n=1,2,3,4$ and grows rapidly without a simple algebraic expression. Computing these requires enumerative methods, such as checking all potential relations for transitivity, and asymptotic bounds involve advanced combinatorial techniques. The difficulty stems from the global dependency imposed by transitivity, which affects potentially distant pairs. For the subclass of partial orders—reflexive, antisymmetric, and transitive relations—the count is given by OEIS A000112 (1, 3, 19, 219, 4231 for $n=1$ to 5), also without a closed form, though growth rates and bounds can be derived using Dedekind numbers, which enumerate related structures like antichains in the [Boolean](/page/Boolean) lattice. (Kung, "The number of posets on a labeled set", *Order*, 1993) Equivalence relations are reflexive, symmetric, and transitive homogeneous relations, partitioning the set into disjoint equivalence classes. The number of equivalence relations on an $n$-element set is the $n$th [Bell number](/page/Bell_number) $B_n$, which counts the partitions of the set and has no elementary closed form but satisfies the recurrence $B_n = \sum_{k=0}^{n-1} \binom{n-1}{k} B_k$ with $B_0 = 1$.[](https://oeis.org/A000110) The sequence is 1, 2, 5, 15, 52, 203 for $n=1$ to 6, reflecting the exponential growth in partitioning possibilities. Seminal work by Bell established this enumeration, with generating functions $\sum B_n x^n / n! = e^{e^x - 1}$. These relations are crucial in [quotient](/page/Quotient) structures and [symmetry](/page/Symmetry) detection. (Riordan, "An Introduction to Combinatorial Analysis", 1958) For reflexive and transitive relations (preorders), the count is the $n$th ordered Bell number (or Fubini number), $\sum_{k=0}^n k! S(n,k)$, where $S(n,k)$ are [Stirling numbers](/page/Stirling_number) of the second kind; this sums to 1, 3, 13, 75, 541 for $n=1$ to 5, again without a simple closed form but with the [generating function](/page/Generating_function) $\sum F_n x^n / n! = 1/(2 - e^x)$. Preorders generalize partial orders by allowing non-antisymmetric equivalences within levels. Recurrences for these can involve summing over possible [antichain](/page/Antichain) decompositions or level structures, where the set is partitioned into antichains ordered totally; for instance, the number of preorders equals the sum over partitions into $k$ antichains of the ways to order them, linking to combinatorial identities involving Dedekind structures for bounds on finer subclasses like posets. (Stanley, *Enumerative Combinatorics, Vol. 1*, 2nd ed., 2011) ## Generalizations ### To Heterogeneous Relations A heterogeneous binary relation generalizes the concept of a homogeneous relation by allowing the relation to connect elements from two distinct sets, defined as a subset $ R \subseteq X \times Y $ where $ X \neq Y $.[](https://ncatlab.org/nlab/show/relation)[](https://sites.math.rutgers.edu/~saks/Mathematician%27s%20Craft/COLOR/relations-color.pdf) This structure contrasts with homogeneous relations, which are confined to $ R \subseteq X \times X $, and introduces a loss of symmetry in relational composition: while homogeneous relations compose within the same set to yield another relation on that set, heterogeneous composition requires a matching codomain-domain pair across different sets, resulting in a relation from $ X $ to $ Z $ via an intermediate $ Y $.[](https://ncatlab.org/nlab/show/relation) A prominent example of a heterogeneous relation is a function $ f: X \to Y $, represented as the set of ordered pairs $ \{(x, f(x)) \mid x \in X\} \subseteq X \times Y $, which is both total (every element of $ X $ relates to exactly one in $ Y $) and functional.[](https://sites.math.rutgers.edu/~saks/Mathematician%27s%20Craft/COLOR/relations-color.pdf) Properties of relations adapt accordingly in this setting; reflexivity, which requires $ (x, x) \in R $ for all $ x $ in the domain, cannot hold for heterogeneous relations due to the mismatch between domains $ X $ and $ Y $, as elements lack a common set for self-relation.[](https://ncatlab.org/nlab/show/relation) Instead, directedness is emphasized, highlighting the oriented flow from $ X $ to $ Y $ without inherent reversibility.[](https://ncatlab.org/nlab/show/relation) Homogeneous relations represent the special case where $ X = Y $, serving as a foundational instance of the broader heterogeneous framework.[](https://ncatlab.org/nlab/show/relation) Heterogeneous relations can be derived from homogeneous ones via projections or restrictions, such as selecting a subset of pairs from $ X \times X $ where the first component is restricted to a subset of $ X $ and the second to a different set $ Y \subseteq X $.[](https://sites.math.rutgers.edu/~saks/Mathematician%27s%20Craft/COLOR/relations-color.pdf) In applications, heterogeneous relations model interactions between distinct entity types, such as bipartite graphs, where vertices partition into two sets $ X $ and $ Y $ with edges corresponding to pairs in $ R \subseteq X \times Y $, enabling analysis of connections like assignments or matchings without intra-set relations.[](https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/efac321fdc8d0b27586ca35b04aab808_MIT6_042JF10_chap07.pdf) This differs from simple graphs, which encode homogeneous relations on a unified vertex set, often assuming undirected [symmetry](/page/Symmetry) via $ R = R^{-1} $.[](https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/efac321fdc8d0b27586ca35b04aab808_MIT6_042JF10_chap07.pdf) ### To Multi-ary Relations A homogeneous n-ary relation, for $ n \geq 2 $, is a [subset](/page/Subset) $ R \subseteq A^n $ of the n-fold [Cartesian product](/page/Cartesian_product) of a set $ A $ with itself, where elements of $ R $ are ordered n-tuples from $ A $.[](https://www.rcet.org.in/uploads/academics/regulation2024/rohini_15741628328.pdf) This generalizes the binary case ($ n=2 $, $ R \subseteq A \times A $) by allowing relations to capture interactions among n elements from the same domain, often modeled in contexts like [geometry](/page/Geometry) or [databases](/page/DNA_gyrase).[](https://www.rcet.org.in/uploads/academics/regulation2024/rohini_15741628328.pdf) Properties of binary homogeneous relations, such as reflexivity and [symmetry](/page/Symmetry), extend to the n-ary setting with adaptations for multiple arguments. Reflexivity holds if every [tuple](/page/Tuple) with all identical components belongs to $ R $, i.e., $ (a, a, \dots, a) \in R $ for all $ a \in A $.[](https://www.rcet.org.in/uploads/academics/regulation2024/rohini_15741628328.pdf) [Symmetry](/page/Symmetry) generalizes to permutation invariance: for any [permutation](/page/Permutation) $ \sigma $ of $ \{1, 2, \dots, n\} $, if $ (a_1, \dots, a_n) \in R $, then $ (a_{\sigma(1)}, \dots, a_{\sigma(n)}) \in R $.[](https://www.rcet.org.in/uploads/academics/regulation2024/rohini_15741628328.pdf) Transitivity, however, lacks a universal binary analogue and requires context-specific definitions, often involving compositions of tuples that complicate verification compared to pairwise checks.[](https://www.rcet.org.in/uploads/academics/regulation2024/rohini_15741628328.pdf) A [canonical](/page/Canonical) example is the betweenness relation in [geometry](/page/Geometry), a ternary ($ n=3 $) homogeneous relation on a set $ E $ of points, denoted $ a * b * c $, meaning $ b $ lies between $ a $ and $ c $. This satisfies axioms such as [symmetry](/page/Symmetry) ($ a * b * c \iff c * b * a $) and exclusivity (at most one of $ a * b * c $, $ b * c * a $, or $ c * a * b $ holds for distinct points), as seen in ordered sets or metric spaces where $ d(a, c) = d(a, b) + d(b, c) $.[](https://link.springer.com/article/10.1007/s13366-022-00648-w) Key operations on n-ary homogeneous relations include projections, joins, and cylindrification, which facilitate reduction to lower arity or combination with other relations. Projection onto a subset of coordinates, say positions $ i_1, \dots, i_m $ with $ m < n $, yields $ \pi_{i_1, \dots, i_m}(R) = \{ (a_{i_1}, \dots, a_{i_m}) \mid \exists (a_1, \dots, a_n) \in R \} $, effectively existentially quantifying over omitted variables.[](https://sites.pitt.edu/~bonidie/cs441/relations.pdf) Joins combine compatible relations by matching on shared coordinates, generalizing binary composition to higher dimensions. Cylindrification, particularly useful for embedding or simplifying, expands the i-th coordinate: for $ R \subseteq {}^n U $, the i-th cylindrification is $ c_i(R) = \{ (a_1, \dots, a_{i-1}, u, a_{i+1}, \dots, a_n) \mid (a_1, \dots, a_n) \in R, u \in U \} $, allowing conversion to binary relations by repeating or ignoring dimensions.[](https://old.renyi.hu/pub/algebraic-logic/AMNSurvey1004.pdf) Defining transitivity for n-ary relations introduces significant challenges, as it often relies on [hypergraph](/page/Hypergraph) interpretations where hyperedges represent tuples, leading to increased [computational complexity](/page/Computational_complexity) in closure computations and property verification beyond binary cases.[](https://old.renyi.hu/pub/algebraic-logic/AMNSurvey1004.pdf) This [complexity](/page/Complexity) underscores the need for specialized algebraic frameworks, such as cylindric algebras, to handle higher-arity structures rigorously.[](https://old.renyi.hu/pub/algebraic-logic/AMNSurvey1004.pdf)
Add your contribution
Related Hubs
User Avatar
No comments yet.