In
mathematics, a homogeneous relation (also called endorelation) over a set ''X'' is a
binary relation over ''X'' and itself, i.e. it is a subset of the Cartesian product .
This is commonly phrased as "a relation on ''X''" or "a (binary) relation over ''X''". An example of a homogeneous relation is the relation of
kinship, where the relation is over people.
Common types of endorelations include
orders,
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
s, and
equivalences
Equivalence or Equivalent may refer to:
Arts and entertainment
*Album-equivalent unit, a measurement unit in the music industry
*Equivalence class (music)
*''Equivalent VIII'', or ''The Bricks'', a minimalist sculpture by Carl Andre
*'' Equival ...
. Specialized studies
order theory
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article int ...
and
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
have developed understanding of endorelations. Terminology particular for graph theory is used for description, with an ordinary graph presumed to correspond to a
symmetric relation, and a general endorelation corresponding to a
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
. An endorelation ''R'' corresponds to a
logical matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
Matrix representation ...
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 theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.
In the special case of a finite simp ...
in graph terminology.
Particular homogeneous relations
Some particular homogeneous relations over a set ''X'' (with arbitrary elements , ) are:
*Empty relation
*:;
that is, holds never;
*Universal relation
*:;
that is, holds always;
*Identity relation (see also
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
)
*:;
that is, holds if and only if .
Example
![Plates_tect2_en](https://upload.wikimedia.org/wikipedia/commons/8/8a/Plates_tect2_en.svg)
Fifteen large
tectonic plate
Plate tectonics (from the la, label=Late Latin, tectonicus, from the grc, τεκτονικός, lit=pertaining to building) is the generally accepted scientific theory that considers the Earth's lithosphere to comprise a number of large te ...
s of the Earth's crust contact each other in a homogeneous relation. The relation can be expressed as a
logical matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1) matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets.
Matrix representation ...
with 1 indicating contact and 0 no contact. This example expresses a symmetric relation.
Properties
Some important properties that a homogeneous relation over a set may have are:
; : for all , . For example, ≥ is a reflexive relation but > is not.
; (or ): for all , not . For example, > is an irreflexive relation, but ≥ is not.
; : for all , if then . 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.
; : for all , if then .
; : for all , if then .
; : for all , if then and . 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 red binary relation is neither irreflexive, nor coreflexive, nor reflexive, since it contains the pair , and , but not , respectively. The latter two facts also rule out (any kind of) quasi-reflexivity.
; : for all , if then . For example, "is a blood relative of" is a symmetric relation, because is a blood relative of if and only if is a blood relative of .
; : for all , if and then . For example, ≥ is an antisymmetric relation; so is >, but
vacuously (the condition in the definition is always false).
; : for all , if then not . A relation is asymmetric if and only if it is both antisymmetric and irreflexive. 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 defined by is neither symmetric nor antisymmetric, let alone asymmetric.
; : for all , if and then . A transitive relation is irreflexive if and only if it is asymmetric. For example, "is ancestor of" is a transitive relation, while "is parent of" is not.
; : for all , if and then never .
; : if the complement of ''R'' is transitive. That is, for all , if , then or . This is used in
pseudo-orders in constructive mathematics.
; : for all , if and but neither nor , then but not .
; : for all , if and are incomparable with respect to and if the same is true of and , then and are also incomparable with respect to . This is used in
weak ordering
In mathematics, especially order theory, a weak ordering is a mathematical formalization of the intuitive notion of a ranking of a set, some of whose members may be tied with each other. Weak orders are a generalization of totally ordered ...
s.
Again, the previous 5 alternatives are not exhaustive. For example, the relation if ( or ) satisfies none of these properties. On the other hand, the empty relation trivially satisfies all of them.
; : for all such that , there exists some such that and . This is used in
dense orders.
; : for all , if then or . This property is sometimes called "total", which is distinct from the definitions of "left/right-total" given below.
; : for all , or . This property, too, is sometimes called "total", which is distinct from the definitions of "left/right-total" given below.
; : for all , exactly one of , or holds. For example, > is a trichotomous relation, while the relation "divides" over the natural numbers is not.
; (or just ): for all , if and then . For example, = is a Euclidean relation because if and then .
; : for all , if and then .
; : every nonempty subset of contains a
minimal element
In mathematics, especially in order theory, a maximal element of a subset ''S'' of some preordered set is an element of ''S'' that is not smaller than any other element in ''S''. A minimal element of a subset ''S'' of some preordered set is defin ...
with respect to . Well-foundedness implies the
descending chain condition In mathematics, the ascending chain condition (ACC) and descending chain condition (DCC) are finiteness properties satisfied by some algebraic structures, most importantly ideals in certain commutative rings.Jacobson (2009), p. 142 and 147 These con ...
(that is, no infinite chain ... can exist). If the
axiom of dependent choice is assumed, both conditions are equivalent.
Moreover, all properties of binary relations in general also may apply to homogeneous relations:
; :for all , the
class
Class or The Class may refer to:
Common uses not otherwise categorized
* Class (biology), a taxonomic rank
* Class (knowledge representation), a collection of individuals or objects
* Class (philosophy), an analytical concept used differentl ...
of all such that is a set. (This makes sense only if relations over proper classes are allowed.)
; : for all and all , if and then .
; : for all and all , if and then .
; (also called left-total): for all there exists a such that . This property is different from the definition of ''connected'' (also called ''total'' by some authors).
; (also called right-total): for all , there exists an such that ''xRy''.
A is a relation that is reflexive and transitive. A , also called or , is a relation that is reflexive, transitive, and connected.
A , also called , is a relation that is reflexive, antisymmetric, and transitive. A , also called , is a relation that is irreflexive, antisymmetric, and transitive. A , also called , , or , is a relation that is reflexive, antisymmetric, transitive and connected. A , also called , , or , is a relation that is irreflexive, antisymmetric, transitive and connected.
A is a relation that is symmetric and transitive. An 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.
Operations
If ''R'' is a homogeneous relation over a set ''X'' then each of the following is a homogeneous relation over ''X'':
; , ''R''
=: Defined as
''R''= = ∪ ''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''.
; , ''R''
≠: Defined as
''R''≠ = ''R'' \ or the largest
irreflexive
In mathematics, a binary relation ''R'' on a set ''X'' is reflexive if it relates every element of ''X'' to itself.
An example of a reflexive relation is the relation " is equal to" on the set of real numbers, since every real number is equal ...
relation over ''X'' contained in ''R''.
; , ''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''.
; , ''R''*: Defined as , the smallest
preorder containing ''R''.
; , ''R''
≡: Defined as the smallest
equivalence relation over ''X'' containing ''R''.
All operations defined in also apply to homogeneous relations.
:
Enumeration
The set of all homogeneous relations
over a set ''X'' is the set which is a
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas i ...
augmented with the
involution
Involution may refer to:
* Involute, a construction in the differential geometry of curves
* '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
of mapping of a relation to its
converse relation
In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent&n ...
. Considering
composition of relations as a
binary operation on
, it forms a
monoid with involution In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an Involution (mathematics), involutive anti-automorphism, which—roughly speaking—brings it closer to a group (mathematic ...
where the identity element is the identity relation.
The number of distinct homogeneous relations over an ''n''-element set is :
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
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
s, which is the
Bell number
In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy ...
.
The homogeneous relations can be grouped into pairs (relation,
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-clas ...
), except that for the relation is its own complement. The non-symmetric ones can be grouped into
quadruple
Quadruple may refer to:
* 4-tuple, an ordered list of elements, with four elements
* Quad (figure skating), a figure skating jump
* Quadruple (computing), a term used as alternative for nibble in some contexts
* Quadruple-precision floating-point ...
s (relation, complement,
inverse, inverse complement).
Examples
*
Order relation
Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article int ...
s, including
strict order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary r ...
s:
**
Greater than
In mathematics, an inequality is a relation which makes a non-equal comparison between two numbers or other mathematical expressions. It is used most often to compare two numbers on the number line by their size. There are several different n ...
** Greater than or equal to
**
Less than
** Less than or equal to
**
Divides
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
(evenly)
**
Subset of
*
Equivalence relations:
**
Equality
Equality may refer to:
Society
* Political equality, in which all members of a society are of equal standing
** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elit ...
**
Parallel
Parallel is a geometric term of location which may refer to:
Computing
* Parallel algorithm
* Parallel computing
* Parallel metaheuristic
* Parallel (software), a UNIX utility for running programs in parallel
* Parallel Sysplex, a cluster of ...
with (for
affine space
In mathematics, an affine space is a geometric structure that generalizes some of the properties of Euclidean spaces in such a way that these are independent of the concepts of distance and measure of angles, keeping only the properties related ...
s)
**
Equinumerosity
In mathematics, two sets or classes ''A'' and ''B'' are equinumerous if there exists a one-to-one correspondence (or bijection) between them, that is, if there exists a function from ''A'' to ''B'' such that for every element ''y'' of ''B'', t ...
or "is in
bijection with"
**
Isomorphic
**
Equipollent line segments
*
Tolerance relation
In universal algebra and lattice theory, a tolerance relation on an algebraic structure is a reflexive symmetric relation that is compatible with all operations of the structure. Thus a tolerance is like a congruence, except that the assumption ...
, a reflexive and symmetric relation:
**
Dependency relation
In computer science, in particular in concurrency (computer science), concurrency theory, a dependency relation is a binary relation on a finite domain \Sigma, symmetric relation, symmetric, and reflexive relation, reflexive; i.e. a finite toleran ...
, a finite tolerance relation
**
Independency relation
In computer science, in particular in concurrency (computer science), concurrency theory, a dependency relation is a binary relation on a finite domain \Sigma, symmetric relation, symmetric, and reflexive relation, reflexive; i.e. a finite toleran ...
, the complement of some dependency relation
*
Kinship relations
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
In mathematics, a finitary relation over sets is a subset of the Cartesian product ; that is, it is a set of ''n''-tuples consisting of elements ''x'i'' in ''X'i''. Typically, the relation describes a possible connection between the elemen ...
is a subset ''R'' ⊆ ''X''
1 × ... × ''X''
''n'' for some
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal ...
''n'' and arbitrary sets ''X''
1, ..., ''X''
''n'', it is also called an ''n''-ary relation.
References
{{reflist
Binary relations