HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, especially in
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 intr ...
, a preorder or quasiorder is a
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
that is reflexive and transitive. Preorders are more general than
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
s and (non-strict)
partial 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 ...
s, both of which are special cases of a preorder: an antisymmetric (or
skeletal A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...
) preorder is a partial order, and a symmetric preorder is an equivalence relation. The name comes from the idea that preorders (that are not partial orders) are 'almost' (partial) orders, but not quite; they are neither necessarily antisymmetric nor asymmetric. Because a preorder is a binary relation, the symbol \,\leq\, can be used as the notational device for the relation. However, because they are not necessarily antisymmetric, some of the ordinary intuition associated to the symbol \,\leq\, may not apply. On the other hand, a preorder can be used, in a straightforward fashion, to define a partial order and an equivalence relation. Doing so, however, is not always useful or worthwhile, depending on the problem domain being studied. In words, when a \leq b, one may say that ''b'' ''a'' or that ''a'' ''b'', or that ''b'' to ''a''. Occasionally, the notation ← or → or \,\lesssim\, is used instead of \,\leq. To every preorder, there corresponds a directed graph, with elements of the set corresponding to vertices, and the order relation between pairs of elements corresponding to the directed edges between vertices. The converse is not true: most directed graphs are neither reflexive nor transitive. In general, the corresponding graphs may contain cycles. A preorder that is antisymmetric no longer has cycles; it is a partial order, and corresponds to a
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...
. A preorder that is symmetric is an equivalence relation; it can be thought of as having lost the direction markers on the edges of the graph. In general, a preorder's corresponding directed graph may have many disconnected components.


Formal definition

Consider a
homogeneous relation 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 ...
\,\leq\, on some given
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
P, so that by definition, \,\leq\, is some subset of P \times P and the notation a \leq b is used in place of (a, b) \in \,\leq. Then \,\leq\, is called a or if it is reflexive and transitive; that is, if it satisfies: # Reflexivity: a \leq a for all a \in P, and # Transitivity: if a \leq b \text b \leq c \text a \leq c for all a, b, c \in P. A set that is equipped with a preorder is called a preordered set (or proset). For emphasis or contrast to strict preorders, a preorder may also be referred to as a non-strict preorder. If reflexivity is replaced with irreflexivity (while keeping transitivity) then the result is called a strict preorder; explicitly, a on P is a homogeneous binary relation \,<\, on P that satisfies the following conditions:
  1. Irreflexivity or Anti-reflexivity: a < a for all a \in P; that is, \,a < a is for all a \in P, and
  2. Transitivity: if a < b \text b < c \text a < c for all a, b, c \in P.
A
binary relation In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
is a strict preorder if and only if it is a strict partial order. By definition, a strict partial order is an asymmetric strict preorder, where \,<\, is called if a < b \text \textit \ b < a for all a, b. Conversely, every strict preorder is a strict partial order because every transitive irreflexive relation is necessarily asymmetric. Although they are equivalent, the term "strict partial order" is typically preferred over "strict preorder" and readers are referred to the article on strict partial orders for details about such relations. In contrast to strict preorders, there are many (non-strict) preorders that are (non-strict)
partial 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 ...
s.


Related definitions

If a preorder is also antisymmetric, that is, a \leq b and b \leq a implies a = b, then it is a
partial 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 ...
. On the other hand, if it is symmetric, that is, if a \leq b implies b \leq a, then it is an
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
. A preorder is total if a \leq b or b \leq a for all a, b \in P. The notion of a preordered set P can be formulated in a
categorical framework In Immanuel Kant's philosophy, a category (german: Categorie in the original or ''Kategorie'' in modern German) is a pure concept of the understanding (''Verstand''). A Kantian category is a characteristic of the appearance of any object in gener ...
as a thin category; that is, as a category with at most one morphism from an object to another. Here the
objects Object may refer to: General meanings * Object (philosophy), a thing, being, or concept ** Object (abstract), an object which does not exist at any particular time or place ** Physical object, an identifiable collection of matter * Goal, an ai ...
correspond to the elements of P, and there is one morphism for objects which are related, zero otherwise. Alternately, a preordered set can be understood as an
enriched category In category theory, a branch of mathematics, an enriched category generalizes the idea of a category by replacing hom-sets with objects from a general monoidal category. It is motivated by the observation that, in many practical applications, the ho ...
, enriched over the category 2 = (0 \to 1). A preordered class is a
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 differently ...
equipped with a preorder. Every set is a class and so every preordered set is a preordered class.


Examples


Graph theory

* (see figure above) By ''x'' //4 is meant the greatest integer that is less than or equal to ''x'' divided by ''4'', thus ''1'' //4 is ''0'', which is certainly less than or equal to ''0'', which is itself the same as ''0'' //4. * The reachability relationship in any directed graph (possibly containing cycles) gives rise to a preorder, where x \leq y in the preorder if and only if there is a path from ''x'' to ''y'' in the directed graph. Conversely, every preorder is the reachability relationship of a directed graph (for instance, the graph that has an edge from ''x'' to ''y'' for every pair with x \leq y. However, many different graphs may have the same reachability preorder as each other. In the same way, reachability of
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...
s, directed graphs with no cycles, gives rise to
partially ordered set 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 ...
s (preorders satisfying an additional antisymmetry property). * The graph-minor relation in
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 ...
.


Computer science

In computer science, one can find examples of the following preorders. * Asymptotic order causes a preorder over functions f: \mathbb \to \mathbb. The corresponding equivalence relation is called
asymptotic equivalence In mathematical analysis, asymptotic analysis, also known as asymptotics, is a method of describing limiting behavior. As an illustration, suppose that we are interested in the properties of a function as becomes very large. If , then as beco ...
. *
Polynomial-time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
, many-one (mapping) and Turing reductions are preorders on complexity classes. * Subtyping relations are usually preorders. *
Simulation preorder In theoretical computer science a simulation is a relation between state transition systems associating systems that behave in the same way in the sense that one system ''simulates'' the other. Intuitively, a system simulates another system if it ...
s are preorders (hence the name). * Reduction relations in
abstract rewriting system In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated ARS) is a formalism that captures the quintessential notion and properties of rewriting s ...
s. * The encompassment preorder on the set of terms, defined by s \leq t if a subterm of ''t'' is a substitution instance of ''s''. * Theta-subsumption, which is when the literals in a disjunctive first-order formula are contained by another, after applying a
substitution Substitution may refer to: Arts and media *Chord substitution, in music, swapping one chord for a related one within a chord progression *Substitution (poetry), a variation in poetic scansion * "Substitution" (song), a 2009 song by Silversun Pic ...
to the former.


Other

Further examples: * Every
finite topological space In mathematics, a finite topological space is a topological space for which the underlying point set is finite. That is, it is a topological space which has only finitely many elements. Finite topological spaces are often used to provide example ...
gives rise to a preorder on its points by defining x \leq y if and only if ''x'' belongs to every
neighborhood A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural area, ...
of ''y''. Every finite preorder can be formed as the
specialization preorder In the branch of mathematics known as topology, the specialization (or canonical) preorder is a natural preorder on the set of the points of a topological space. For most spaces that are considered in practice, namely for all those that satisfy th ...
of a topological space in this way. That is, there is a
one-to-one correspondence In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
between finite topologies and finite preorders. However, the relation between infinite topological spaces and their specialization preorders is not one-to-one. * A net is a
directed Director may refer to: Literature * ''Director'' (magazine), a British magazine * ''The Director'' (novel), a 1971 novel by Henry Denker * ''The Director'' (play), a 2000 play by Nancy Hasty Music * Director (band), an Irish rock band * ''D ...
preorder, that is, each pair of elements has an upper bound. The definition of convergence via nets is important in
topology In mathematics, topology (from the Greek words , and ) is concerned with the properties of a geometric object that are preserved under continuous deformations, such as stretching, twisting, crumpling, and bending; that is, without closing ...
, where preorders cannot be replaced by
partially ordered set 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 ...
s without losing important features. * The relation defined by x \leq y if f(x) \leq f(y), where ''f'' is a function into some preorder. * The relation defined by x \leq y if there exists some injection from ''x'' to ''y''. Injection may be replaced by
surjection In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
, or any type of structure-preserving function, such as
ring homomorphism In ring theory, a branch of abstract algebra, a ring homomorphism is a structure-preserving function between two rings. More explicitly, if ''R'' and ''S'' are rings, then a ring homomorphism is a function such that ''f'' is: :addition preser ...
, or
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...
. * The
embedding In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup. When some object X is said to be embedded in another object Y, the embedding is g ...
relation for countable
total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive ...
ings. * A
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally * Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
with at most one
morphism In mathematics, particularly in category theory, a morphism is a structure-preserving map from one mathematical structure to another one of the same type. The notion of morphism recurs in much of contemporary mathematics. In set theory, morphisms ...
from any object ''x'' to any other object ''y'' is a preorder. Such categories are called thin. In this sense, categories "generalize" preorders by allowing more than one relation between objects: each morphism is a distinct (named) preorder relation. Example of a total preorder: *
Preference In psychology, economics and philosophy, preference is a technical term usually used in relation to choosing between alternatives. For example, someone prefers A over B if they would rather choose A than B. Preferences are central to decision th ...
, according to common models.


Uses

Preorders play a pivotal role in several situations: * Every preorder can be given a topology, the
Alexandrov topology In topology, an Alexandrov topology is a topology in which the intersection of any family of open sets is open. It is an axiom of topology that the intersection of any ''finite'' family of open sets is open; in Alexandrov topologies the finite re ...
; and indeed, every preorder on a set is in one-to-one correspondence with an Alexandrov topology on that set. * Preorders may be used to define
interior algebra In abstract algebra, an interior algebra is a certain type of algebraic structure that encodes the idea of the topological interior of a set. Interior algebras are to topology and the modal logic S4 what Boolean algebras are to set theory and ordin ...
s. * Preorders provide the Kripke semantics for certain types of
modal logic Modal logic is a collection of formal systems developed to represent statements about necessity and possibility. It plays a major role in philosophy of language, epistemology, metaphysics, and natural language semantics. Modal logics extend ot ...
. * Preorders are used in forcing in
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
to prove
consistency In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...
and
independence Independence is a condition of a person, nation, country, or state in which residents and population, or some portion thereof, exercise self-government, and usually sovereignty, over its territory. The opposite of independence is the stat ...
results.


Constructions

Every binary relation R on a set S can be extended to a preorder on S by taking the
transitive closure In mathematics, the transitive closure of a binary relation on a set is the smallest relation on that contains and is transitive. For finite sets, "smallest" can be taken in its usual sense, of having the fewest related pairs; for infinite ...
and reflexive closure, R^. The transitive closure indicates path connection in R : x R^+ y if and only if there is an R- path from x to y. Left residual preorder induced by a binary relation Given a binary relation R, the complemented composition R \backslash R = \overline forms a preorder called the left residual,In this context, "\backslash" does not mean "set difference". where R^\textsf denotes the
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 ...
of R, and \overline denotes the complement relation of R, while \circ denotes relation composition.


Preorders and partial orders on partitions

Given a preorder \,\lesssim\, on S one may define an
equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
\,\sim\, on S such that a \sim b \quad \text \quad a \lesssim b \; \text \; b \lesssim a. The resulting relation \,\sim\, is reflexive since the preorder \,\lesssim\, is reflexive; transitive by applying the transitivity of \,\lesssim\, twice; and symmetric by definition. Using this relation, it is possible to construct a partial order on the quotient set of the equivalence, S / \sim, which is the set of all
equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es of \,\sim. If the preorder is denoted by R^, then S / \sim is the set of R- cycle equivalence classes: x \in /math> if and only if x = y or x is in an R-cycle with y In any case, on S / \sim it is possible to define \leq /math> if and only if x \lesssim y. That this is well-defined, meaning that its defining condition does not depend on which representatives of /math> and /math> are chosen, follows from the definition of \,\sim.\, It is readily verified that this yields a partially ordered set. Conversely, from any partial order on a partition of a set S, it is possible to construct a preorder on S itself. There is a
one-to-one correspondence In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
between preorders and pairs (partition, partial order). : Let S be a formal theory, which is a set of
sentences ''The Four Books of Sentences'' (''Libri Quattuor Sententiarum'') is a book of theology written by Peter Lombard in the 12th century. It is a systematic compilation of theology, written around 1150; it derives its name from the '' sententiae'' ...
with certain properties (details of which can be found in the article on the subject). For instance, S could be a
first-order theory First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quan ...
(like
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such ...
) or a simpler zeroth-order theory. One of the many properties of S is that it is closed under logical consequences so that, for instance, if a sentence A \in S logically implies some sentence B, which will be written as A \Rightarrow B and also as B \Leftarrow A, then necessarily B \in S (by ''
modus ponens In propositional logic, ''modus ponens'' (; MP), also known as ''modus ponendo ponens'' (Latin for "method of putting by placing") or implication elimination or affirming the antecedent, is a deductive argument form and rule of inference ...
''). The relation \,\Leftarrow\, is a preorder on S because A \Leftarrow A always holds and whenever A \Leftarrow B and B \Leftarrow C both hold then so does A \Leftarrow C. Furthermore, for any A, B \in S, A \sim B if and only if A \Leftarrow B \text B \Leftarrow A; that is, two sentences are equivalent with respect to \,\Leftarrow\, if and only if they are logically equivalent. This particular equivalence relation A \sim B is commonly denoted with its own special symbol A \iff B, and so this symbol \,\iff\, may be used instead of \,\sim. The equivalence class of a sentence A, denoted by consists of all sentences B \in S that are logically equivalent to A (that is, all B \in S such that A \iff B). The partial order on S / \sim induced by \,\Leftarrow,\, which will also be denoted by the same symbol \,\Leftarrow,\, is characterized by \Leftarrow /math> if and only if A \Leftarrow B, where the right hand side condition is independent of the choice of representatives A \in /math> and B \in /math> of the equivalence classes. All that has been said of \,\Leftarrow\, so far can also be said of 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 ...
\,\Rightarrow.\, The preordered set (S, \Leftarrow) is a
directed set In mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set A together with a reflexive and transitive binary relation \,\leq\, (that is, a preorder), with the additional property that every pair of elements has ...
because if A, B \in S and if C := A \wedge B denotes the sentence formed by
logical conjunction In logic, mathematics and linguistics, And (\wedge) is the truth-functional operator of logical conjunction; the ''and'' of a set of operands is true if and only if ''all'' of its operands are true. The logical connective that represents thi ...
\,\wedge,\, then A \Leftarrow C and B \Leftarrow C where C \in S. The partially ordered set \left(S / \sim, \Leftarrow\right) is consequently also a directed set. See Lindenbaum–Tarski algebra for a related example.


Preorders and strict preorders

Strict preorder induced by a preorder Given a preorder \,\lesssim, a new relation \,<\, can be defined by declaring that a < b if and only if a \lesssim b \text b \lesssim a. Using the equivalence relation \,\sim\, introduced above, a < b if and only if a \lesssim b \text a \sim b; and so the following holds a \lesssim b \quad \text \quad a < b \; \text \; a \sim b. The relation \,<\, is a strict partial order and strict partial order can be constructed this way. the preorder \,\lesssim\, is antisymmetric (and thus a partial order) then the equivalence \,\sim\, is equality (that is, a \sim b if and only if a = b) and so in this case, the definition of \,<\, can be restated as: a < b \quad \text \quad a \leq b \; \text \; a \neq b \quad\quad (\text \lesssim \text). But importantly, this new condition is used as (nor is it equivalent to) the general definition of the relation \,<\, (that is, \,<\, is defined as: a < b if and only if a \lesssim b \text a \neq b) because if the preorder \,\lesssim\, is not antisymmetric then the resulting relation \,<\, would not be transitive (consider how equivalent non-equal elements relate). This is the reason for using the symbol "\lesssim" instead of the "less than or equal to" symbol "\leq", which might cause confusion for a preorder that is not antisymmetric since it might misleadingly suggest that a \leq b implies a < b \text a = b. Preorders induced by a strict preorder Using the construction above, multiple non-strict preorders can produce the same strict preorder \,<,\, so without more information about how \,<\, was constructed (such knowledge of the equivalence relation \,\sim\, for instance), it might not be possible to reconstruct the original non-strict preorder from \,<.\, Possible (non-strict) preorders that induce the given strict preorder \,<\, include the following: * Define a \leq b as a < b \text a = b (that is, take the reflexive closure of the relation). This gives the partial order associated with the strict partial order "<" through reflexive closure; in this case the equivalence is equality \,=, so the symbols \,\lesssim\, and \,\sim\, are not needed. * Define a \lesssim b as "\text b < a" (that is, take the inverse complement of the relation), which corresponds to defining a \sim b as "neither a < b \text b < a"; these relations \,\lesssim\, and \,\sim\, are in general not transitive; however, if they are then \,\sim\, is an equivalence; in that case "<" is a strict weak order. The resulting preorder is connected (formerly called total); that is, a total preorder. If a \leq b then a \lesssim b. The converse holds (that is, \,\lesssim\;\; = \;\;\leq\,) if and only if whenever a \neq b then a < b or b < a.


Number of preorders

As explained above, there is a 1-to-1 correspondence between preorders and pairs (partition, partial order). Thus the number of preorders is the sum of the number of partial orders on every partition. For example:


Interval

For a \lesssim b, the interval , b/math> is the set of points ''x'' satisfying a \lesssim x and x \lesssim b, also written a \lesssim x \lesssim b. It contains at least the points ''a'' and ''b''. One may choose to extend the definition to all pairs (a, b) The extra intervals are all empty. Using the corresponding strict relation "<", one can also define the interval (a, b) as the set of points ''x'' satisfying a < x and x < b, also written a < x < b. An open interval may be empty even if a < b. Also , b) and (a, b/math> can be defined similarly.


See also

*
Partial 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 ...
– preorder that is antisymmetric *
Equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relatio ...
– preorder that is symmetric * Total preorder – preorder that is total *
Total order In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X: # a \leq a ( reflexive ...
– preorder that is antisymmetric and total *
Directed set In mathematics, a directed set (or a directed preorder or a filtered set) is a nonempty set A together with a reflexive and transitive binary relation \,\leq\, (that is, a preorder), with the additional property that every pair of elements has ...
* Category of preordered sets *
Prewellordering In set theory, a prewellordering on a set X is a preorder \leq on X (a transitive and strongly connected relation on X) that is wellfounded in the sense that the relation x \leq y \land y \nleq x is wellfounded. If \leq is a prewellordering o ...
*
Well-quasi-ordering In mathematics, specifically order theory, a well-quasi-ordering or wqo is a quasi-ordering such that any infinite sequence of elements x_0, x_1, x_2, \ldots from X contains an increasing pair x_i \leq x_j with i x_2> \cdots) nor infinite seque ...


Notes


References

* Schmidt, Gunther, "Relational Mathematics", Encyclopedia of Mathematics and its Applications, vol. 132, Cambridge University Press, 2011, * {{Order theory Binary relations Order theory