Content deleted Content added
→Extrema: added → included; spaces |
Undid revision 1305943583 by 5.45.140.111 (talk) unexplained reduplication of article text |
||
| (42 intermediate revisions by 23 users not shown) | |||
Line 1:
{{Short description|Mathematical set with an ordering}}
{{Stack|{{Binary relations}}}}
[[Image:Hasse diagram of powerset of 3.svg|right|thumb|upright=1.15|'''Fig. 1''' The [[Hasse diagram]] of the [[Power set|set of all subsets]] of a three-element set <math>\{x, y, z\},</math> ordered by [[set inclusion|inclusion]]. Sets connected by an upward path, like <math>\emptyset</math> and <math>\{x,y\}</math>, are comparable, while e.g. <math>\{x\}</math> and <math>\{y\}</math> are not.]]
In [[mathematics]], especially [[order theory]], a '''partial order''' on a [[Set (mathematics)|set]] is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements needs to be comparable; that is, there may be pairs for which neither element precedes the other. Partial orders thus generalize [[total order]]s, in which every pair is comparable.
Formally, a partial order is a [[homogeneous binary relation]] that is [[Reflexive relation|reflexive]], [[
== Partial order relations ==
Line 12:
A '''reflexive''', '''weak''',<ref name=Wallis/> or '''{{visible anchor|non-strict partial order|Non-strict partial order}}''',<ref>{{cite book|chapter=Partially Ordered Sets|title=Mathematical Tools for Data Mining: Set Theory, Partial Orders, Combinatorics|publisher=Springer|year=2008|isbn=9781848002012|chapter-url=https://books.google.com/books?id=6i-F3ZNcub4C&pg=PA127|author1=Simovici, Dan A. |author2=Djeraba, Chabane |name-list-style=amp }}</ref> commonly referred to simply as a '''partial order''', is a [[homogeneous relation]] ≤ on a [[Set (mathematics)|set]] <math>P</math> that is [[Reflexive relation|reflexive]], [[Antisymmetric relation|antisymmetric]], and [[Transitive relation|transitive]]. That is, for all <math>a, b, c \in P,</math> it must satisfy:
# [[Reflexive relation|Reflexivity]]: <math>a \leq a</math>, i.e. every element is related to itself.
# [[Antisymmetric relation|Antisymmetry]]: if <math>a \leq b</math> and <math>b \leq a</math> then <math>a = b</math>, i.e. no two distinct elements precede each other.
Line 21 ⟶ 20:
=== Strict partial orders ===
An '''irreflexive''', '''strong''',<ref name=Wallis/> or '''{{visible anchor|strict partial order|Strict partial order|Irreflexive partial order}}''' is a homogeneous relation < on a set <math>P</math> that is [[Irreflexive relation|irreflexive]], [[Asymmetric relation|asymmetric]]
# [[Irreflexive relation|Irreflexivity]]: <math>\neg\left( a < a \right)</math>, i.e. no element is related to itself (also called anti-reflexive).
# [[
# [[
A strict partial order is also known as an asymmetric [[strict preorder]].
=== Correspondence of strict and non-strict partial order relations ===
[[File:PartialOrders redundencies svg.svg|thumb|upright=1.25|'''Fig. 2''' [[Commutative diagram]] about the connections between strict/non-strict relations and their duals, via the operations of reflexive closure (''cls''), irreflexive kernel (''ker''), and converse relation (''cnv''). Each relation is depicted by its [[logical matrix]] for the poset whose [[Hasse diagram]] is depicted in the center. For example <math>3 \not\leq 4</math> so row 3, column 4 of the bottom left matrix is empty.]]
Strict and non-strict partial orders on a set <math>P</math> are closely related. A non-strict partial order <math>\leq</math> may be converted to a strict partial order by removing all relationships of the form <math>a \leq a;</math> that is, the strict partial order is the set <math>< \; := \ \leq\ \setminus \ \Delta_P</math> where <math>\Delta_P := \{ (p, p) : p \in P \}</math> is the [[identity relation]] on <math>P \times P</math> and <math>\;\setminus\;</math> denotes [[set subtraction]]. Conversely, a strict partial order < on <math>P</math> may be converted to a non-strict partial order by adjoining all relationships of that form; that is, <math>\leq\; := \;\Delta_P\; \cup \;<\;</math> is a non-strict partial order. Thus, if <math>\leq</math> is a non-strict partial order, then the corresponding strict partial order < is the [[irreflexive kernel]] given by
Line 42 ⟶ 40:
{{Main|Duality (order theory)}}
The ''dual'' (or ''opposite'') <math>R^{\text{op}}</math> of a partial order relation <math>R</math> is defined by letting <math>R^{\text{op}}</math> be the [[converse relation]] of <math>R</math>, i.e. <math>x R^{\text{op}} y</math> if and only if <math>y R x</math>. The dual of a non-strict partial order is a non-strict partial order,{{sfnp|Davey|Priestley|2002|pp=[https://books.google.com/books?id=vVVTxeuiyvQC&pg=PA14
== Notation ==
Given a set <math>P</math> and a partial order relation, typically the non-strict partial order <math>\leq</math>, we may uniquely extend our notation to define four partial order relations <math>\leq,</math> <math><,</math> <math>\geq,
The term ''ordered set'' is sometimes used as a shorthand for ''partially ordered set'', as long as it is clear from the context that no other kind of order is meant. In particular, [[Total order|totally ordered sets]] can also be referred to as "ordered sets", especially in areas where these structures are more common than posets. Some authors use different symbols than <math>\leq</math> such as <math>\sqsubseteq</math><ref>{{cite web |last1=Rounds |first1=William C. |title=Lectures slides |url=http://www.eecs.umich.edu/courses/eecs203-1/203-Mar7.pdf |website=EECS 203: DISCRETE MATHEMATICS |access-date=23 July 2021 |date=7 March 2002}}</ref> or <math>\preceq</math><ref>{{cite book |last1=Kwong |first1=Harris |title=A Spiral Workbook for Discrete Mathematics |date=25 April 2018 |url=https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/A_Spiral_Workbook_for_Discrete_Mathematics_(Kwong)/07%3A_Relations/7.04%3A_Partial_and_Total_Ordering |access-date=23 July 2021 |language=en |chapter=7.4: Partial and Total Ordering}}</ref> to distinguish partial orders from total orders.
Line 54 ⟶ 52:
== Alternative definitions ==
Another way of defining a partial order, found in [[computer science]], is via a notion of [[Comparability|comparison]]. Specifically, given <math>\leq, <, \geq, \text{ and } ></math> as defined previously, it can be observed that two elements ''x'' and ''y'' may stand in any of four [[mutually exclusive]] relationships to each other: either {{nowrap|''x''
Wallis defines a more general notion of a ''partial order relation'' as any [[homogeneous relation]] that is [[Transitive relation|transitive]] and [[Antisymmetric relation|antisymmetric]]. This includes both reflexive and irreflexive partial orders as subtypes.<ref name=Wallis>{{cite book |last1=Wallis |first1=W. D. |title=A Beginner's Guide to Discrete Mathematics |date=14 March 2013 |publisher=Springer Science & Business Media |isbn=978-1-4757-3826-1 |page=100 |url=https://books.google.com/books?id=ONgRBwAAQBAJ&dq=%22partial%20order%20relation%22&pg=PA100 |language=en}}</ref>
Line 62 ⟶ 60:
== Examples ==
[[File:Division relation 4.
Standard examples of posets arising in mathematics include:
* The [[real number]]s, or in general any totally ordered set, ordered by the standard ''less-than-or-equal'' relation ≤, is a partial order.
* On the real numbers <math>\mathbb{R}</math>, the usual [[less than]] relation < is a strict partial order. The same is also true of the usual [[greater than]] relation > on <math>\R</math>.
* By definition, every [[strict weak order]] is a strict partial order.
* The set of [[subset]]s of a given set (its [[power set]]) ordered by [[subset|inclusion]] (see Fig. 1). Similarly, the set of [[sequence]]s ordered by [[subsequence]], and the set of [[string (computer science)|string]]s ordered by [[substring]].
* The set of [[natural number]]s equipped with the relation of [[divisor|divisibility]]. (see Fig. 3 and Fig. 6)
* The vertex set of a [[directed acyclic graph]] ordered by [[reachability]].
* The set of [[Linear subspace|subspaces]] of a [[vector space]] ordered by inclusion.
* For a partially ordered set ''P'', the [[sequence space]] containing all [[sequence]]s of elements from ''P'', where sequence ''a'' precedes sequence ''b'' if every item in ''a'' precedes the corresponding item in ''b''. Formally, <math>\left(a_n\right)_{n \in \N} \leq \left(b_n\right)_{n \in \N}</math> if and only if <math>a_n \leq b_n</math> for all <math>n \in \N</math>; that is, a [[componentwise order]].
* For a set ''X'' and a partially ordered set ''P'', the [[function space]] containing all functions from ''X'' to ''P'', where {{nowrap|''f'' ≤ ''g''}} if and only if {{nowrap|''f''(''x'') ≤ ''g''(''x'')}} for all <math>x \in X.</math>
* A [[Fence (mathematics)|fence]], a partially ordered set defined by an alternating sequence of order relations {{nowrap|''a'' < ''b'' > ''c'' < ''d'' ...}}
* The set of events in [[special relativity]] and, in most cases,{{efn|See
One familiar example of a partially ordered set is a collection of people ordered by [[genealogy|genealogical]] descendancy. Some pairs of people bear the descendant-ancestor relationship, but other pairs of people are incomparable, with neither being a descendant of the other.
=== Orders on the Cartesian product of partially ordered sets ===
{{multiple image
| align = right
Line 90 ⟶ 87:
| caption2 = '''Fig. 4b''' Product order on <math>\N \times \N</math>
| image3 = Strict product order on pairs of natural numbers.svg|
| caption3 = '''Fig. 4c''' Reflexive closure of strict direct product order on <math>\N \times \N.</math> Elements [[#Formal definition|covered]] by {{nowrap|(3, 3)}} and covering {{nowrap|(3, 3)}} are highlighted in green and red, respectively.
}}
In order of increasing strength, i.e., decreasing sets of pairs, three of the possible partial orders on the [[Cartesian product]] of two partially ordered sets are (see Fig. 4):
* the [[lexicographical order]]: {{nowrap|(''a'', ''b'') ≤ (''c'', ''d'')}} if {{nowrap|''a'' < ''c''}} or ({{nowrap|1=''a'' = ''c''}} and {{nowrap|''b'' ≤ ''d''}});
* the [[product order]]: (''a'', ''b'') ≤ (''c'', ''d'') if ''a'' ≤ ''c'' and ''b'' ≤ ''d'';
* the [[reflexive closure]] of the [[Direct product#Direct product of binary relations|direct product]] of the corresponding strict orders: {{nowrap|(''a'', ''b'') ≤ (''c'', ''d'')}} if ({{nowrap|''a'' < ''c''}} and {{nowrap|''b'' < ''d''}}) or ({{nowrap|1=''a'' = ''c''}} and {{nowrap|1=''b'' = ''d''}}).
All three can similarly be defined for the Cartesian product of more than two sets.
Line 105 ⟶ 102:
=== Sums of partially ordered sets ===
{{anchor|sum}}
Another way to combine two (disjoint) posets is the '''ordinal sum'''<ref>
{{citation | last1 = Neggers | first1 = J.
| last2 = Kim | first2 = Hee Sik
Line 113 ⟶ 111:
| publisher = World Scientific
| title = Basic Posets
| year = 1998
* ''a'', ''b'' ∈ ''X'' with ''a'' ≤<sub>''X''</sub> ''b'', or
* ''a'', ''b'' ∈ ''Y'' with ''a'' ≤<sub>''Y''</sub> ''b'', or
Line 124 ⟶ 123:
== Derived notions ==
The examples use the poset <math>(\mathcal{P}(\{x, y, z\}),\subseteq)</math> consisting of the [[Power set|set of all subsets]] of a three-element set <math>\{x, y, z\},</math> ordered by set inclusion (see Fig. 1).
* ''a'' is ''related to'' ''b'' when ''a'' ≤ ''b''. This does not imply that ''b'' is also related to ''a'', because the relation need not be [[Symmetric relation|symmetric]]. For example, <math>\{x\}</math> is related to <math>\{x, y\},</math> but not the reverse.
* ''a'' and ''b'' are ''[[Comparability|comparable]]'' if {{nowrap|''a'' ≤ ''b''}} or {{nowrap|''b'' ≤ ''a''}}. Otherwise they are ''incomparable''. For example, <math>\{x\}</math> and <math>\{x, y, z\}</math> are comparable, while <math>\{x\}</math> and <math>\{y\}</math> are not.
* A ''[[Totally ordered set|total order]]'' or ''linear order'' is a partial order under which every pair of elements is comparable, i.e. [[Trichotomy (mathematics)|trichotomy]] holds. For example, the natural numbers with their standard order.
* A ''[[Chain (order theory)|chain]]'' is a subset of a poset that is a totally ordered set. For example, <math>\{ \{\,\}, \{x\}, \{x, y, z\} \}</math> is a chain.
* An ''[[antichain]]'' is a subset of a poset in which no two distinct elements are comparable. For example, the set of [[Singleton (mathematics)|singleton]]s <math>\{\{x\}, \{y\}, \{z\}\}.</math>
* An element ''a'' is said to be ''strictly less than'' an element ''b'', if ''a'' ≤ ''b'' and <math>a \neq b.</math> For example, <math>\{x\}</math> is strictly less than <math>\{x, y\}.</math>
* An element ''a'' is said to be ''[[Covering relation|covered]]'' by another element ''b'', written ''a'' ⋖ ''b'' (or ''a'' <: ''b''), if ''a'' is strictly less than ''b'' and no third element ''c'' fits between them; formally: if both ''a'' ≤ ''b'' and <math>a \neq b</math> are true, and ''a'' ≤ ''c'' ≤ ''b'' is false for each ''c'' with <math>a \neq c \neq b.</math> Using the strict order <, the relation ''a'' ⋖ ''b'' can be equivalently rephrased as "{{nowrap|''a'' < ''b''}} but not {{nowrap|''a'' < ''c'' < ''b''}} for any ''c''". For example, <math>\{x\}</math> is covered by <math>\{x, z\},</math> but is not covered by <math>\{x, y, z\}.</math>
=== Extrema ===
Line 151 ⟶ 149:
| total_width = 580
| image1 = Monotonic but nonhomomorphic map between lattices.gif
| caption1 = '''Fig. 7a''' Order-preserving, but not order-reflecting (since {{nowrap|''f''(''u'') ≼ ''f''(''v'')}}, but not u {{small|<math>\leq</math>}} v) map.
| image2 = Birkhoff120.svg
| caption2 = '''Fig. 7b''' Order isomorphism between the divisors of 120 (partially ordered by divisibility) and the divisor-closed subsets of {{nowrap|{{mset|2, 3, 4, 5, 8}}}} (partially ordered by set inclusion)
}}
Given two partially ordered sets {{math|1=(''S'', ≤)}} and {{math|(''T'', ≼)}}, a function <math>f : S \to T</math> is called '''[[order-preserving]]''', or '''[[Monotonic function#In order theory|monotone]]''', or '''isotone''', if for all <math>x, y \in S,</math> <math>x \leq y</math> implies {{math|1=''f''(''x'') ≼ ''f''(''y'')}}.
Line 159 ⟶ 157:
A function <math>f : S \to T</math> is called '''order-reflecting''' if for all <math>x, y \in S,</math> {{math|1=''f''(''x'') ≼ ''f''(''y'')}} implies <math>x \leq y.</math>
If {{mvar|f}} is both order-preserving and order-reflecting, then it is called an '''[[order-embedding]]''' of {{math|1=(''S'', ≤)}} into {{math|1=(''T'', ≼)}}.
In the latter case, {{mvar|f}} is necessarily [[injective]], since <math>f(x) = f(y)</math> implies <math>x \leq y \text{ and } y \leq x</math> and in turn <math>x = y</math> according to the antisymmetry of <math>\leq.</math> If an order-embedding between two posets ''S'' and ''T'' exists, one says that ''S'' can be '''embedded''' into ''T''. If an order-embedding <math>f : S \to T</math> is [[bijective]], it is called an '''[[order isomorphism]]''', and the partial orders {{math|1=(''S'', ≤)}} and {{math|1=(''T'', ≼)}} are said to be '''isomorphic'''. Isomorphic orders have structurally similar [[Hasse diagram]]s (see Fig. 7a). It can be shown that if order-preserving maps <math>f : S \to T</math> and <math>g : T \to U</math> exist such that <math>g \circ f</math> and <math>f \circ g</math> yields the [[identity function]] on ''S'' and ''T'', respectively, then ''S'' and ''T'' are order-isomorphic.{{sfnp|Davey|Priestley|2002|pp=23–24}}
For example, a mapping <math>f : \N \to \mathbb{P}(\N)</math> from the set of natural numbers (ordered by divisibility) to the [[power set]] of natural numbers (ordered by set inclusion) can be defined by taking each number to the set of its [[prime divisor]]s. It is order-preserving: if {{mvar|x}} divides {{mvar|y}}, then each prime divisor of {{mvar|x}} is also a prime divisor of {{mvar|y}}. However, it is neither injective (since it maps both 12 and 6 to <math>\{2, 3\}</math>) nor order-reflecting (since 12 does not divide 6). Taking instead each number to the set of its [[prime power]] divisors defines a map <math>g : \N \to \mathbb{P}(\N)</math> that is order-preserving, order-reflecting, and hence an order-embedding. It is not an order-isomorphism (since it, for instance, does not map any number to the set <math>\{4\}</math>), but it can be made one by [[Injective function#Injections may be made invertible|restricting its codomain]] to <math>g(\N).</math> Fig. 7b shows a subset of <math>\N</math> and its isomorphic image under {{mvar|g}}. The construction of such an order-isomorphism into a power set can be generalized to a wide class of partial orders, called [[distributive lattice]]s; see ''[[Birkhoff's representation theorem]]''.
== Number of partial orders ==
Sequence [{{fullurl:OEIS:A001035}} A001035] in [[On-Line Encyclopedia of Integer Sequences|OEIS]] gives the number of partial orders on a set of ''n'' labeled elements:
Line 171 ⟶ 169:
If the count is made only [[up to]] isomorphism, the sequence 1, 1, 2, 5, 16, 63, 318, ... {{OEIS|A000112}} is obtained.
== Subposets ==
A poset <math>P^*=(X^*, \leq^*)</math> is called a '''subposet''' of another poset <math>P=(X, \leq)</math> provided that <math>X^*</math> is a [[subset]] of <math>X</math> and <math>\leq^*</math> is a subset of <math>\leq</math>. The latter condition is equivalent to the requirement that for any <math>x</math> and <math>y</math> in <math>X^*</math> (and thus also in <math>X</math>), if <math>x \leq^* y</math> then <math>x \leq y</math>.
If <math>P^*</math> is a subposet of <math>P</math> and furthermore, for all <math>x</math> and <math>y</math> in <math>X^*</math>, whenever <math>x \leq y</math> we also have <math>x \leq^* y</math>, then we call <math>P^*</math> the subposet of <math>P</math> '''induced''' by <math>X^*</math>, and write <math>P^* = P[X^*]</math>.
== Linear extension ==
A partial order <math>\leq^*</math> on a set <math>X</math> is called an '''extension''' of another partial order <math>\leq</math> on <math>X</math> provided that for all elements <math>x, y \in X,</math> whenever <math>x \leq y,</math> it is also the case that <math>x \leq^* y.</math> A [[linear extension]] is an extension that is also a linear (that is, total) order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order. Every partial order can be extended to a total order ([[order-extension principle]]).<ref>{{cite book |last=Jech |first=Thomas |author-link=Thomas Jech |title=The Axiom of Choice |year=2008 |orig-year=1973 |publisher=[[Dover Publications]] |isbn=978-0-486-46624-8}}</ref>▼
▲A partial order <math>\leq^*</math> on a set <math>X</math> is an '''extension''' of another partial order <math>\leq</math> on <math>X</math> provided that for all elements <math>x, y \in X,</math> whenever <math>x \leq y,</math> it is also the case that <math>x \leq^* y.</math> A [[linear extension]] is an extension that is also a linear (that is, total) order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order. Every partial order can be extended to a total order ([[order-extension principle]]).<ref>{{cite book |last=Jech |first=Thomas |author-link=Thomas Jech |title=The Axiom of Choice |year=2008 |orig-year=1973 |publisher=[[Dover Publications]] |isbn=978-0-486-46624-8}}</ref>
In [[computer science]], algorithms for finding linear extensions of partial orders (represented as the [[reachability]] orders of [[directed acyclic graph]]s) are called [[topological sorting]].
== In category theory ==
{{main|Posetal category}}
Every poset (and every [[Preorder|preordered set]]) may be considered as a [[Category (mathematics)|category]] where, for objects <math>x</math> and <math>y,</math> there is at most one [[morphism]] from <math>x</math> to <math>y.</math> More explicitly, let {{nowrap|1=hom(''x'', ''y'') = {{mset|(''x'', ''y'')}}}} if {{nowrap|''x'' ≤ ''y''}} (and otherwise the [[empty set]]) and <math>(y, z) \circ (x, y) = (x, z).</math> Such categories are sometimes called ''[[Posetal category|posetal]]''.
Posets are [[Equivalence of categories|equivalent]] to one another if and only if they are [[Isomorphism of categories|isomorphic]]. In a poset, the smallest element, if it exists, is an [[initial object]], and the largest element, if it exists, is a [[terminal object]]. Also, every preordered set is equivalent to a poset. Finally, every subcategory of a poset is [[isomorphism-closed]].
▲Every poset (and every [[Preorder|preordered set]]) may be considered as a [[Category (mathematics)|category]] where, for objects <math>x</math> and <math>y,</math> there is at most one [[morphism]] from <math>x</math> to <math>y.</math> More explicitly, let hom(''x'', ''y'') = {(''x'', ''y'')} if ''x'' ≤ ''y'' (and otherwise the [[empty set]]) and <math>(y, z) \circ (x, y) = (x, z).</math> Such categories are sometimes called ''[[Posetal category|posetal]]''. In differential topology, homology theory (HT) is used for classifying equivalent smooth manifolds M, related to the geometrical shapes of M.
== Partial orders in topological spaces ==
{{Main|Partially ordered space}}
If <math>P</math> is a partially ordered set that has also been given the structure of a [[topological space]], then it is customary to assume that <math>\{ (a,b) : a \le b \}</math> is a [[Closed (mathematics)|closed]] subset of the topological [[product space]] <math>P \times P.</math> Under this assumption partial order relations are well behaved at [[Limit of a sequence|limits]] in the sense that if <math>\lim_{i \to \infty} a_i = a,</math> and <math>\lim_{i \to \infty} b_i = b,</math> and for all <math>i,</math> <math>a_i \leq b_i,</math> then <math>a \leq b.</math><ref name="ward-1954">{{Cite journal|first=L. E. Jr|last=Ward|title=Partially Ordered Topological Spaces|journal=Proceedings of the American Mathematical Society|volume=5 |year=1954|pages= 144–161|issue= 1|doi=10.1090/S0002-9939-1954-0063016-5|hdl=10338.dmlcz/101379|doi-access=free}}</ref>
== Intervals ==
{{See also|Interval (mathematics)}}
Line 197 ⟶ 199:
An '''interval''' in a poset ''P'' is a subset that can be defined with interval notation:
* For ''a'' ≤ ''b'', the ''closed interval'' {{closed-closed|''a'', ''b''}} is the set of elements ''x'' satisfying {{nowrap|''a'' ≤ ''x'' ≤ ''b''}} (that is, {{nowrap|''a'' ≤ ''x''}} and {{nowrap|''x'' ≤ ''b''}}). It contains at least the elements ''a'' and ''b''.
* Using the corresponding strict relation "<", the ''open interval'' {{open-open|''a'', ''b''}} is the set of elements ''x'' satisfying {{nowrap|''a'' < ''x'' < ''b''}} (i.e. {{nowrap|''a'' < ''x''}} and {{nowrap|''x'' < ''b''}}). An open interval may be empty even if {{nowrap|''a'' < ''b''}}. For example, the open interval {{open-open|0, 1}} on the integers is empty since there is no integer {{mvar|x}} such that {{math|0 < {{var|x}} < 1}}.
* The ''half-open intervals'' {{closed-open|''a'', ''b''}} and {{open-closed|''a'', ''b''}} are defined similarly.
Whenever {{nowrap|''a'' ≤ ''b''}} does not hold, all these intervals are empty. Every interval is a convex set, but the converse does not hold; for example, in the poset of divisors of 120, ordered by divisibility (see Fig. 7b), the set {{mset|1, 2, 4, 5, 8}} is convex, but not an interval.
An interval {{mvar|I}} is bounded if there exist elements <math>a, b \in P</math> such that {{math|{{var|I}} ⊆ {{closed-closed|''a'', ''b''}}}}. Every interval that can be represented in interval notation is obviously bounded, but the converse is not true. For example, let {{math|1=''P'' = {{open-open|0, 1}} ∪ {{open-open|1, 2}} ∪ {{open-open|2, 3}}}} as a subposet of the real numbers. The subset {{open-open|1, 2}} is a bounded interval, but it has no [[infimum]] or [[supremum]] in
A poset is called [[Locally finite poset|locally finite]] if every bounded interval is finite. For example, the integers are locally finite under their natural ordering. The lexicographical order on the cartesian product <math>\N \times \N</math> is not locally finite, since {{math|(1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1)}}.
Line 211 ⟶ 213:
== See also ==
{{div col|colwidth=27em}}
* [[Antimatroid]], a formalization of orderings on a set that allows more general families of orderings than posets
Line 232 ⟶ 233:
* {{annotated link|Semilattice}}
* {{annotated link|Semiorder}}
* [[Szpilrajn extension theorem]]
* {{annotated link|Stochastic dominance}}
* [[Strict weak ordering]] – strict partial order "<" in which the relation {{nowrap|"neither ''a'' < ''b''}} {{nowrap|nor ''b'' < ''a''"}} is transitive.
* {{annotated link|Total order}}
* {{annotated link|Zorn's lemma}}
{{div col end}}
== Notes ==
{{notelist}}
== Citations ==
{{reflist}}
== References ==
{{refbegin}}
* {{cite book |last1=Davey |first1=B. A. |last2=Priestley |first2=H. A. |title=Introduction to Lattices and Order |edition=2nd |___location=New York |publisher=Cambridge University Press |year=2002 |isbn=978-0-521-78451-1 |title-link= Introduction to Lattices and Order}}
* {{Cite journal|first=Jayant V. |last=Deshpande|title=On Continuity of a Partial Order|journal=Proceedings of the American Mathematical Society|volume=19|year=1968|pages=383–386|issue=2 |doi=10.1090/S0002-9939-1968-0236071-7 |doi-access= free}}
Line 256 ⟶ 255:
* {{cite book|first=S.|last=Eilenberg|author-link=N. Steenrod|title=Foundations of Algebraic Topology|publisher=Princeton University Press|year=2016}}
* {{cite journal|first=G.|last=Kalmbach|title=Extension of Homology Theory to Partially Ordered Sets|journal=J. Reine Angew. Math.|volume=280|year=1976|pages=134–156}}
{{refend}}
==External links==▼
▲== External links ==
{{Commons category inline|Hasse diagrams}}; each of which shows an example for a partial order
{{refbegin}}
* {{OEIS el|1=A001035|2= Number of posets with ''n'' labeled elements|formalname=Number of partially ordered sets ("posets") with n labeled elements (or labeled acyclic transitive digraphs)}}
* {{OEIS el|1=A000112|2=Number of partially ordered sets ("posets") with n unlabeled elements.}}
{{refend}}
{{Order theory}}
Line 267 ⟶ 269:
[[Category:Order theory]]
[[Category:Binary relations]]
| |||