{"history":[],"article":{"id":"d7a74c84-07f9-4770-b3bb-9cf731d095f3","title":"Preorder","slug":"preorder","content":":::summary\n:::\n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), especially in [order theory](https://bliptext.com/articles/order-theory), a **preorder** or **quasiorder** is a [binary relation](https://bliptext.com/articles/binary-relation) that is [reflexive](https://bliptext.com/articles/reflexive-relation) and [transitive](https://bliptext.com/articles/transitive-relation).\nThe name is meant to suggest that preorders are almost [partial orders](https://bliptext.com/articles/partial-order), but not quite, as they are not necessarily [antisymmetric](https://bliptext.com/articles/antisymmetric-relation).\nA natural example of a preorder is the [divides relation](https://bliptext.com/articles/divisor) \"x divides y\" between integers, [polynomials](https://bliptext.com/articles/polynomial), or elements of a [commutative ring](https://bliptext.com/articles/commutative-ring).\nFor example, the divides relation is reflexive as every integer divides itself.\nBut the divides relation is not antisymmetric, because 1 divides -1 and -1 divides 1.\nIt is to this preorder that \"greatest\" and \"lowest\" refer in the phrases \"[greatest common divisor](https://bliptext.com/articles/greatest-common-divisor)\" and \"[lowest common multiple](https://bliptext.com/articles/lowest-common-multiple)\" (except that, for integers, the [greatest common divisor](https://bliptext.com/articles/greatest-common-divisor) is also the greatest for the natural order of the integers).\nPreorders are closely related to [equivalence relations](https://bliptext.com/articles/equivalence-relation) and (non-strict) partial orders.\nBoth of these are special cases of a preorder: an anti[symmetric](https://bliptext.com/articles/symmetric-relation) preorder is a partial order, and a [symmetric](https://bliptext.com/articles/symmetric-relation) preorder is an equivalence relation.\nMoreover, a preorder on a set X can equivalently be defined as an equivalence relation on X, together with a partial order on the set of equivalence class.\nLike partial orders and equivalence relations, preorders (on a nonempty set) are never [asymmetric](https://bliptext.com/articles/asymmetric-relation).\nA preorder can be visualized as a [directed graph](https://bliptext.com/articles/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.\nThe converse is not true: most directed graphs are neither reflexive nor transitive.\nA preorder that is antisymmetric no longer has cycles; it is a partial order, and corresponds to a [directed acyclic graph](https://bliptext.com/articles/directed-acyclic-graph).\nA 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.\nIn general, a preorder's corresponding directed graph may have many disconnected components.\nAs a binary relation, a preorder may be denoted or \\,\\leq\\,.\nIn words, when one may say that b a or that a b, or that b to a.\nOccasionally, the notation ← or → is also used.\n# [Hasse diagram of the preorder x R y defined by x//4≤y//4 on the natural numbers. Equivalence classes (sets of elements such that x R y and y R x) are shown together as a single node. The relation on equivalence classes is a partial order. | upload.wikimedia.org/wikipedia/commons/c/c4/Preorder.png]\n\n# Definition\nLet be a binary relation on a [set](https://bliptext.com/articles/set-mathematics) P, so that by definition, is some sub[set](https://bliptext.com/articles/set-mathematics) of P \\times P and the notation is used in place of Then is called a **' or **' if it is [reflexive](https://bliptext.com/articles/reflexive-relation) and [transitive](https://bliptext.com/articles/transitive-relation); that is, if it satisfies:\nA set that is equipped with a preorder is called a **preordered set** (or **proset**).\n\n# Preorders as partial orders on partitions\nGiven a preorder on S one may define an [equivalence relation](https://bliptext.com/articles/equivalence-relation) \\,\\sim\\, on S such that\nThe resulting relation \\,\\sim\\, is reflexive since the preorder is reflexive; transitive by applying the transitivity of twice; and symmetric by definition.\nUsing 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 classes](https://bliptext.com/articles/equivalence-class) of \\,\\sim.\nIf the preorder is denoted by R^{+=}, then S / \\sim is the set of R-[cycle](https://bliptext.com/articles/cycle-graph-theory) equivalence classes:\nx \\in [y] 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 if and only if That this is well-defined, meaning that its defining condition does not depend on which representatives of [x] and [y] are chosen, follows from the definition of \\,\\sim.\\, It is readily verified that this yields a partially ordered set.\nConversely, from any partial order on a partition of a set S, it is possible to construct a preorder on S itself.\nThere is a [one-to-one correspondence](https://bliptext.com/articles/one-to-one-correspondence) between preorders and pairs (partition, partial order).\nThe relation is a preorder on S because always holds and whenever and both hold then so does\nFurthermore, for any A, B \\in S, A \\sim B if and only if ; that is, two sentences are equivalent with respect to if and only if they are [logically equivalent](https://bliptext.com/articles/logically-equivalent).\nThis 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.\nThe equivalence class of a sentence A, denoted by [A], consists of all sentences B \\in S that are logically equivalent to A (that is, all B \\in S such that A \\iff B).\nThe partial order on S / \\sim induced by which will also be denoted by the same symbol is characterized by if and only if where the right hand side condition is independent of the choice of representatives A \\in [A] and B \\in [B] of the equivalence classes.\nAll that has been said of so far can also be said of its [converse relation](https://bliptext.com/articles/converse-relation)\nThe preordered set is a [directed set](https://bliptext.com/articles/directed-set) because if A, B \\in S and if denotes the sentence formed by [logical conjunction](https://bliptext.com/articles/logical-conjunction) \\,\\wedge,\\, then and where C \\in S. The partially ordered set is consequently also a [directed set](https://bliptext.com/articles/directed-set).\nSee [Lindenbaum–Tarski algebra](https://bliptext.com/articles/lindenbaum-tarski-algebra) for a related example.\n\n# Relationship to strict partial orders\n****I****f**** ****r****e****f****l****e****x****i****v****i****t****y**** ****i****s**** ****r****e****p****l****a****c****e****d**** ****w****i****t****h**** ****i****r****r****e****f****l****e****x****i****v****i****t****y**** ****(****w****h****i****l****e**** ****k****e****e****p****i****n****g**** ****t****r****a****n****s****i****t****i****v****i****t****y****)**** ****t****h****e****n**** ****w****e**** ****g****e****t**** ****t****h****e**** ****d****e****f****i****n****i****t****i****o****n**** ****o****f**** ****a**** ****s****t****r****i****c****t**** ****p****a****r****t****i****a****l**** ****o****r****d****e****r**** ****o****n**** ****P****.**** ****F****o****r**** ****t****h****i****s**** ****r****e****a****s****o****n****,**** ****t****h****e**** ****t****e****r****m**** **** ****i****s**** ****s****o****m****e****t****i****m****e****s**** ****u****s****e****d**** ****f****o****r**** ****a**** ****s****t****r****i****c****t**** ****p****a****r****t****i****a****l**** ****o****r****d****e****r****.****\nThat is, this is a binary relation \\,<\\, on P that satisfies:\n

[Irreflexivity](https://bliptext.com/articles/irreflexive-relation) or anti-reflexivity: a < a for all a \\in P; that is, \\,a < a is for all a \\in P, and
[Transitivity](https://bliptext.com/articles/transitive-relation): if for all

\n\n## Strict partial order induced by a preorder\nAny preorder gives rise to a strict partial order defined by a < b if and only if and not.\nUsing the equivalence relation \\,\\sim\\, introduced above, a < b if and only if and so the following holds\nThe relation \\,<\\, is a [strict partial order](https://bliptext.com/articles/strict-partial-order) and [strict partial order](https://bliptext.com/articles/strict-partial-order) can be constructed this way.\nthe preorder is [antisymmetric](https://bliptext.com/articles/antisymmetric-relation) (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:\nBut 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 ) because if the preorder is not antisymmetric then the resulting relation \\,<\\, would not be transitive (consider how equivalent non-equal elements relate).\nThis 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\n\n## Preorders induced by a strict partial order\nUsing 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:\nIf a \\leq b then\nThe converse holds (that is, ) if and only if whenever a \\neq b then a < b or b < a.\n\n# Examples\n\n## Graph theory\n\n## Computer science\nIn computer science, one can find examples of the following preorders.\n\n## Category theory\n\n## Other\nFurther examples:\nExample of a [total preorder](https://bliptext.com/articles/strict-weak-ordering):\n\n# Constructions\nEvery binary relation R on a set S can be extended to a preorder on S by taking the [transitive closure](https://bliptext.com/articles/transitive-closure) and [reflexive closure](https://bliptext.com/articles/reflexive-closure), R^{+=}.\nThe transitive closure indicates [path](https://bliptext.com/articles/path-graph-theory) connection in R : x R^+ y if and only if there is an R-[path](https://bliptext.com/articles/path-graph-theory) from x to y.\n**Left residual preorder induced by a binary relation**\nGiven a binary relation R, the [complement](https://bliptext.com/articles/complement-set-theory)ed composition forms a preorder called the [left residual](https://bliptext.com/articles/heterogeneous-relation), where denotes the [converse relation](https://bliptext.com/articles/converse-relation) of R, and denotes the [complement](https://bliptext.com/articles/complement-set-theory) relation of R, while \\circ denotes [relation composition](https://bliptext.com/articles/relation-composition).\n\n# Related definitions\nIf a preorder is also [antisymmetric](https://bliptext.com/articles/antisymmetric-relation), that is, and implies a = b, then it is a [partial order](https://bliptext.com/articles/partially-ordered-set).\nOn the other hand, if it is [symmetric](https://bliptext.com/articles/symmetric-relation), that is, if implies then it is an [equivalence relation](https://bliptext.com/articles/equivalence-relation).\nA preorder is [total](https://bliptext.com/articles/total-preorder) if or for all a, b \\in P.\nA [preordered class](https://bliptext.com/articles/preordered-[class](https://bliptext.com/articles/class-mathematics)) is a [class](https://bliptext.com/articles/class-mathematics) equipped with a preorder.\nEvery set is a class and so every preordered set is a preordered class.\n\n# Uses\nPreorders play a pivotal role in several situations:\n\n# Number of preorders\nAs explained above, there is a 1-to-1 correspondence between preorders and pairs (partition, partial order).\nThus the number of preorders is the sum of the number of partial orders on every partition.\nFor example:\n\n# Interval\nFor the [interval](https://bliptext.com/articles/interval-mathematics) [a, b] is the set of points x satisfying and also written It contains at least the points a and b.\nOne may choose to extend the definition to all pairs (a, b) The extra intervals are all empty.\nUsing 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.\nAlso [a, b) and (a, b] can be defined similarly.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T16:45:23.720Z","updated_at":"2025-01-25T16:45:23.720Z","search_vector":"'preorder':1","search_content":" \n \n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), especially in [order theory](https://bliptext.com/articles/order-theory), a **preorder** or **quasiorder** is a [binary relation](https://bliptext.com/articles/binary-relation) that is [reflexive](https://bliptext.com/articles/reflexive-relation) and [transitive](https://bliptext.com/articles/transitive-relation).\nThe name is meant to suggest that preorders are almost [partial orders](https://bliptext.com/articles/partial-order), but not quite, as they are not necessarily [antisymmetric](https://bliptext.com/articles/antisymmetric-relation).\nA natural example of a preorder is the [divides relation](https://bliptext.com/articles/divisor) \"x divides y\" between integers, [polynomials](https://bliptext.com/articles/polynomial), or elements of a [commutative ring](https://bliptext.com/articles/commutative-ring).\nFor example, the divides relation is reflexive as every integer divides itself.\nBut the divides relation is not antisymmetric, because 1 divides -1 and -1 divides 1.\nIt is to this preorder that \"greatest\" and \"lowest\" refer in the phrases \"[greatest common divisor](https://bliptext.com/articles/greatest-common-divisor)\" and \"[lowest common multiple](https://bliptext.com/articles/lowest-common-multiple)\" (except that, for integers, the [greatest common divisor](https://bliptext.com/articles/greatest-common-divisor) is also the greatest for the natural order of the integers).\nPreorders are closely related to [equivalence relations](https://bliptext.com/articles/equivalence-relation) and (non-strict) partial orders.\nBoth of these are special cases of a preorder: an anti[symmetric](https://bliptext.com/articles/symmetric-relation) preorder is a partial order, and a [symmetric](https://bliptext.com/articles/symmetric-relation) preorder is an equivalence relation.\nMoreover, a preorder on a set X can equivalently be defined as an equivalence relation on X, together with a partial order on the set of equivalence class.\nLike partial orders and equivalence relations, preorders (on a nonempty set) are never [asymmetric](https://bliptext.com/articles/asymmetric-relation).\nA preorder can be visualized as a [directed graph](https://bliptext.com/articles/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.\nThe converse is not true: most directed graphs are neither reflexive nor transitive.\nA preorder that is antisymmetric no longer has cycles; it is a partial order, and corresponds to a [directed acyclic graph](https://bliptext.com/articles/directed-acyclic-graph).\nA 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.\nIn general, a preorder's corresponding directed graph may have many disconnected components.\nAs a binary relation, a preorder may be denoted or \\,\\leq\\,.\nIn words, when one may say that b a or that a b, or that b to a.\nOccasionally, the notation ← or → is also used.\n# [Hasse diagram of the preorder x R y defined by x//4≤y//4 on the natural numbers. Equivalence classes (sets of elements such that x R y and y R x) are shown together as a single node. The relation on equivalence classes is a partial order. | upload.wikimedia.org/wikipedia/commons/c/c4/Preorder.png]\n\n# Definition\nLet be a binary relation on a [set](https://bliptext.com/articles/set-mathematics) P, so that by definition, is some sub[set](https://bliptext.com/articles/set-mathematics) of P \\times P and the notation is used in place of Then is called a **' or **' if it is [reflexive](https://bliptext.com/articles/reflexive-relation) and [transitive](https://bliptext.com/articles/transitive-relation); that is, if it satisfies:\nA set that is equipped with a preorder is called a **preordered set** (or **proset**).\n\n# Preorders as partial orders on partitions\nGiven a preorder on S one may define an [equivalence relation](https://bliptext.com/articles/equivalence-relation) \\,\\sim\\, on S such that\nThe resulting relation \\,\\sim\\, is reflexive since the preorder is reflexive; transitive by applying the transitivity of twice; and symmetric by definition.\nUsing 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 classes](https://bliptext.com/articles/equivalence-class) of \\,\\sim.\nIf the preorder is denoted by R^{+=}, then S / \\sim is the set of R-[cycle](https://bliptext.com/articles/cycle-graph-theory) equivalence classes:\nx \\in [y] 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 if and only if That this is well-defined, meaning that its defining condition does not depend on which representatives of [x] and [y] are chosen, follows from the definition of \\,\\sim.\\, It is readily verified that this yields a partially ordered set.\nConversely, from any partial order on a partition of a set S, it is possible to construct a preorder on S itself.\nThere is a [one-to-one correspondence](https://bliptext.com/articles/one-to-one-correspondence) between preorders and pairs (partition, partial order).\nThe relation is a preorder on S because always holds and whenever and both hold then so does\nFurthermore, for any A, B \\in S, A \\sim B if and only if ; that is, two sentences are equivalent with respect to if and only if they are [logically equivalent](https://bliptext.com/articles/logically-equivalent).\nThis 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.\nThe equivalence class of a sentence A, denoted by [A], consists of all sentences B \\in S that are logically equivalent to A (that is, all B \\in S such that A \\iff B).\nThe partial order on S / \\sim induced by which will also be denoted by the same symbol is characterized by if and only if where the right hand side condition is independent of the choice of representatives A \\in [A] and B \\in [B] of the equivalence classes.\nAll that has been said of so far can also be said of its [converse relation](https://bliptext.com/articles/converse-relation)\nThe preordered set is a [directed set](https://bliptext.com/articles/directed-set) because if A, B \\in S and if denotes the sentence formed by [logical conjunction](https://bliptext.com/articles/logical-conjunction) \\,\\wedge,\\, then and where C \\in S. The partially ordered set is consequently also a [directed set](https://bliptext.com/articles/directed-set).\nSee [Lindenbaum–Tarski algebra](https://bliptext.com/articles/lindenbaum-tarski-algebra) for a related example.\n\n# Relationship to strict partial orders\n****I****f**** ****r****e****f****l****e****x****i****v****i****t****y**** ****i****s**** ****r****e****p****l****a****c****e****d**** ****w****i****t****h**** ****i****r****r****e****f****l****e****x****i****v****i****t****y**** ****(****w****h****i****l****e**** ****k****e****e****p****i****n****g**** ****t****r****a****n****s****i****t****i****v****i****t****y****)**** ****t****h****e****n**** ****w****e**** ****g****e****t**** ****t****h****e**** ****d****e****f****i****n****i****t****i****o****n**** ****o****f**** ****a**** ****s****t****r****i****c****t**** ****p****a****r****t****i****a****l**** ****o****r****d****e****r**** ****o****n**** ****P****.**** ****F****o****r**** ****t****h****i****s**** ****r****e****a****s****o****n****,**** ****t****h****e**** ****t****e****r****m**** **** ****i****s**** ****s****o****m****e****t****i****m****e****s**** ****u****s****e****d**** ****f****o****r**** ****a**** ****s****t****r****i****c****t**** ****p****a****r****t****i****a****l**** ****o****r****d****e****r****.****\nThat is, this is a binary relation \\, \n [Irreflexivity](https://bliptext.com/articles/irreflexive-relation) or anti-reflexivity: a \n [Transitivity](https://bliptext.com/articles/transitive-relation): if for all \n \n\n## Strict partial order induced by a preorder\nAny preorder gives rise to a strict partial order defined by a < b if and only if and not.\nUsing the equivalence relation \\,\\sim\\, introduced above, a < b if and only if and so the following holds\nThe relation \\,<\\, is a [strict partial order](https://bliptext.com/articles/strict-partial-order) and [strict partial order](https://bliptext.com/articles/strict-partial-order) can be constructed this way.\nthe preorder is [antisymmetric](https://bliptext.com/articles/antisymmetric-relation) (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:\nBut 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 ) because if the preorder is not antisymmetric then the resulting relation \\,<\\, would not be transitive (consider how equivalent non-equal elements relate).\nThis 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\n\n## Preorders induced by a strict partial order\nUsing 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:\nIf a \\leq b then\nThe converse holds (that is, ) if and only if whenever a \\neq b then a < b or b < a.\n\n# Examples\n\n## Graph theory\n\n## Computer science\nIn computer science, one can find examples of the following preorders.\n\n## Category theory\n\n## Other\nFurther examples:\nExample of a [total preorder](https://bliptext.com/articles/strict-weak-ordering):\n\n# Constructions\nEvery binary relation R on a set S can be extended to a preorder on S by taking the [transitive closure](https://bliptext.com/articles/transitive-closure) and [reflexive closure](https://bliptext.com/articles/reflexive-closure), R^{+=}.\nThe transitive closure indicates [path](https://bliptext.com/articles/path-graph-theory) connection in R : x R^+ y if and only if there is an R-[path](https://bliptext.com/articles/path-graph-theory) from x to y.\n**Left residual preorder induced by a binary relation**\nGiven a binary relation R, the [complement](https://bliptext.com/articles/complement-set-theory)ed composition forms a preorder called the [left residual](https://bliptext.com/articles/heterogeneous-relation), where denotes the [converse relation](https://bliptext.com/articles/converse-relation) of R, and denotes the [complement](https://bliptext.com/articles/complement-set-theory) relation of R, while \\circ denotes [relation composition](https://bliptext.com/articles/relation-composition).\n\n# Related definitions\nIf a preorder is also [antisymmetric](https://bliptext.com/articles/antisymmetric-relation), that is, and implies a = b, then it is a [partial order](https://bliptext.com/articles/partially-ordered-set).\nOn the other hand, if it is [symmetric](https://bliptext.com/articles/symmetric-relation), that is, if implies then it is an [equivalence relation](https://bliptext.com/articles/equivalence-relation).\nA preorder is [total](https://bliptext.com/articles/total-preorder) if or for all a, b \\in P.\nA [preordered [class](https://bliptext.com/articles/class-mathematics)](https://bliptext.com/articles/preordered-[class](https://bliptext.com/articles/class-mathematics)) is a [class](https://bliptext.com/articles/class-mathematics) equipped with a preorder.\nEvery set is a class and so every preordered set is a preordered class.\n\n# Uses\nPreorders play a pivotal role in several situations:\n\n# Number of preorders\nAs explained above, there is a 1-to-1 correspondence between preorders and pairs (partition, partial order).\nThus the number of preorders is the sum of the number of partial orders on every partition.\nFor example:\n\n# Interval\nFor the [interval](https://bliptext.com/articles/interval-mathematics) [a, b] is the set of points x satisfying and also written It contains at least the points a and b.\nOne may choose to extend the definition to all pairs (a, b) The extra intervals are all empty.\nUsing 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.\nAlso [a, b) and (a, b] can be defined similarly.","revisionCount":0},"hasMore":false,"nextCursor":null}

History