Formal Definition
A partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive, i.e., for all a, b, and c in P, we have that:
- a ≤ a (reflexivity);
- if a ≤ b and b ≤ a then a = b (antisymmetry);
- if a ≤ b and b ≤ c then a ≤ c (transitivity).
In other words, a partial order is an antisymmetric preorder.
A set with a partial order is called a partially ordered set (also called a poset). The term ordered set is sometimes also used for posets, as long as it is clear from the context that no other kinds of orders are meant. In particular, totally ordered sets can also be referred to as "ordered sets", especially in areas where these structures are more common than posets.
For a, b, elements of a partially ordered set P, if a ≤ b or b ≤ a, then a and b are comparable. Otherwise they are incomparable. A partial order under which every pair of elements is comparable is called a total order or linear order; a totally ordered set is also called a chain (e.g., the natural numbers with their standard order). A subset of a poset in which no two distinct elements are comparable is called an antichain.
Read more about this topic: Partially Ordered Set
Famous quotes containing the words formal and/or definition:
“The spiritual kinship between Lincoln and Whitman was founded upon their Americanism, their essential Westernism. Whitman had grown up without much formal education; Lincoln had scarcely any education. One had become the notable poet of the day; one the orator of the Gettsyburg Address. It was inevitable that Whitman as a poet should turn with a feeling of kinship to Lincoln, and even without any association or contact feel that Lincoln was his.”
—Edgar Lee Masters (1869–1950)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth man’s fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)