Partial order: Difference between revisions

Browse history interactively ← Previous editContent deleted Content addedVisual WikitextInline

Revision as of 00:16, 9 January 2003 editAxelBoldt (talk \| contribs)Administrators44,502 edits incidence algebra; Euler characteristic← Previous edit		Latest revision as of 18:59, 2 September 2024 edit undoTule-hog (talk \| contribs)Extended confirmed users4,451 edits add rcat
(42 intermediate revisions by 20 users not shown)
Line 1:		Line 1:
			#REDIRECT ]
	A '''partial order''' <= on a ] ''X'' is a ] that is '''reflexive''', '''antisymmetric''' and '''transitive''', i.e., it holds for all ''a'', ''b'' and ''c'' in ''X'' that:
	* (reflexivity) ''a'' <= ''a''
	* (antisymmetry) if ''a'' <= ''b'' and ''b'' <= ''a'' then ''a'' = ''b''
	* (transitivity) if ''a'' <= ''b'' and ''b'' <= ''c'' then ''a'' <= ''c''

			{{Rcatsh\|
	A set with a partial order on it is called a '''partially ordered set''', or '''poset'''. We can then also define an irreflexive relation <, where ''a'' < ''b'' if and only if ''a'' <= ''b'' and ''a'' ≠ ''b''. Every poset (''X'',<=) has a unique dual poset (''X'',>=), where we define ''a'' >= ''b'' if and only if ''b'' <= ''a''.
			{{R to section}}
			{{R with Wikidata item}}
			{{R with history}}
			}}

			{{Authority control}}
	Examples of partial orders include implications and inclusions ("is a subset of" and the more general "is a subobject of" in the sense of ]) as well as ] of ]s and ]s.

	Finite posets are most easily visualized as ''Hasse diagrams'', that is, ]s where the ] are the elements of the poset and the ordering relation is indicated by ]s and the relative positioning of the vertices. The element ''x'' is smaller than ''y'' if and only if there exists a path from ''x'' to ''y'' always going upwards. This can be generalized: any poset can be represented by a ], where the nodes are elements of the poset and there is a directed path from ''a'' to ''b'' if and only if ''a''<=''b''.

	A subset of a partially ordered set inherits a partial order. New partially ordered sets can also be constructed by cartesian products, disjoint unions and other set-theoretic operations.

	If ''S'' is a subset of the poset ''X'', we say that
	* the element ''m'' of ''S'' is a ''maximal element of S'' if the only element ''s'' of ''S'' with ''m''<=''s'' is ''s''=''m''.
	* the element ''u'' of ''X'' is ''an upper bound for S'' if ''s''<=''u'' for all ''s'' in ''S''
	* the element ''l'' is the ''largest element in S'' if ''l'' is an upper bound for ''S'' and an element of ''S''.
	There can be many maximal elements but at most one largest element of ''S''; if a largest element exists, then it is the unique maximal element of ''S''. Minimal elements, lower bounds and smallest elements are defined analogously.

	Special cases of partially ordered sets are
	*], where for any pair of elements ''a'',''b'', either ''a''<=''b'' or ''b''<=''a''. For example the real numbers with the usual order relation ≤ form a totally ordered set. Another name for totally ordered set is "linearly ordered set". A '''chain''' is a linearly ordered subset of a poset.
	*], where any two elements have both a greatest lower bound (infimum) and a least upper bound (supremum). Lattices are considered ] with the operations "sup" and "inf".
	*'''bounded posets''', which have a largest and a smallest element.

	A related concept is that of a ], where every finite subset has an upper bound. Directed sets are not required to have the antisymmetric property, so they are not necessarily posets.

	A partially ordered set is ''complete'' if every one of its subsets has a least upper bound and a greatest lower bound. Various types of complete partially ordered sets are used in, for example, ]. The best-known type of complete partially ordered sets are the ]. These structures are important in that they constitute a ] and in that they provide a natural theory of approximations.
	That the class of Scott-Ershov domains is cartesian closed category enables the solution of so-called domain equations, e.g., ''D'' = , where the right-hand side denotes the space of all continuous functions on ''D''.

	Partially ordered sets can be given a ], for example, the Alexandrov topology, consisting of all upwards closed subsets. A subset ''U'' of a partially ordered set is ''upwards closed'' if ''x'' in ''U'' and ''x'' <= ''y'' implies that ''y'' belongs to ''U''. For special types of partially ordered sets other topologies may be more interesting. For example, the natural topology on Scott-Ershov domains is the Scott topology.

	A poset is '''locally finite''' if every closed ] in it is ]. Locally finite posets give rise to ]s which in turn can be used to define the Euler characteristic of finite bounded posets.

Latest revision as of 18:59, 2 September 2024

Redirect to:

Partially ordered set#Partial order

This page is a redirect. The following categories are used to track and monitor this redirect:

To a section: This is a redirect from a topic that does not have its own page to a section of a page on the subject. For redirects to embedded anchors on a page, use {{R to anchor}} instead.

From a cross-project redirect: This is a redirect from a title linked to an item on Wikidata. The Wikidata item linked to this page is partial order (Q1069998).
- Use this template only on hard redirects – for soft redirects use {{Soft redirect with Wikidata item}}.

With history: This is a redirect from a page containing substantive page history. This page is kept as a redirect to preserve its former content and attributions. Please do not remove the tag that generates this text (unless the need to recreate content on this page has been demonstrated), nor delete this page.
- This template should not be used for redirects having some edit history but no meaningful content in their previous versions, nor for redirects created as a result of a page merge (use {{R from merge}} instead), nor for redirects from a title that forms a historic part of Misplaced Pages (use {{R with old history}} instead).

When appropriate, protection levels are automatically sensed, described and categorized.