Definition:Partially Ordered Set
Definition
A partially ordered set is a relational structure $\struct {S, \preceq}$ such that $\preceq$ is a partial ordering.
The partially ordered set $\struct {S, \preceq}$ is said to be partially ordered by $\preceq$.
Partial vs. Total Ordering
It is not demanded of an ordering $\preceq$, defined in its most general form on a set $S$, that every pair of elements of $S$ is related by $\preceq$.
They may be, or they may not be, depending on the specific nature of both $S$ and $\preceq$.
If it is the case that $\preceq$ is a connected relation, that is, that every pair of distinct elements is related by $\preceq$, then $\preceq$ is called a total ordering.
If it is not the case that $\preceq$ is connected, then $\preceq$ is called a partial ordering.
Beware that some sources use the word partial for an ordering which may or may not be connected, while others insist on reserving the word partial for one which is specifically not connected.
It is wise to be certain of what is meant.
As a consequence, on $\mathsf{Pr} \infty \mathsf{fWiki}$ we resolve any ambiguity by reserving the terms for the objects in question as follows:
- Partial ordering: an ordering which is specifically not total
- Total ordering: an ordering which is specifically not partial.
Also known as
The word poset is frequently to be found in the literature, but this is frequently understood to mean a general ordered set which may be either partial or total.
Some sources use the term partly ordered set.
Also see
- Definition:Strictly Ordered Set
- Definition:Strictly Partially Ordered Set
- Definition:Strictly Totally Ordered Set
- Definition:Strictly Well-Ordered Set
- Results about partial orderings can be found here.
Internationalization
Partially ordered set is translated:
In German: | teilweise geordnete Menge |
Sources
- 1948: Garrett Birkhoff: Lattice Theory (2nd ed.)
- 1960: Paul R. Halmos: Naive Set Theory ... (previous) ... (next): $\S 14$: Order
- 1971: Gaisi Takeuti and Wilson M. Zaring: Introduction to Axiomatic Set Theory: $\S 6.18$
- 1975: T.S. Blyth: Set Theory and Abstract Algebra ... (previous) ... (next): $\S 7$