| << Chapter < Page | Chapter >> Page > |
Definition(partial order): A binary relation R on a set A is a partial order if and only if it is
(1) reflexive,
(2) antisymmetric, and
(3) transitive.
The ordered pair<A, R>is called a poset (partially ordered set) when R is a partial order.
Example 1: The less-than-or-equal-to relation on the set of integers I is a partial order, and the set I with this relation is a poset.
Example 2: The subset relation on the power set of a set, say {1, 2}, is also a partial order, and the set {1, 2} with the subset relation is a poset.
Definition(total order): A binary relation R on a set A is a total order if and only if it is
(1) a partial order, and
(2) for any pair of elements a and b of A, <a, b>∈R or<b, a>∈R.
That is, every element is related with every element one way or the other. A total order is also called a linear order.
Example 3: The less-than-or-equal-to relation on the set of integers I is a total order.
The strictly-less-than and proper-subset relations are not partial order because they are not reflexive. They are examples of some relation called quasi order.
Definition(quasi order): A binary relation R on a set A is a quasi order if and only if it is
(1) irreflexive, and
(2) transitive.
A quasi order is necessarily antisymmetric as one can easily verify.
Caution Like many other definitions there is another fairly widely used definition of quasi order in the literature. According to that definition a quasi order is a relation that is reflexive and transitive. That is something quite different from "quasi order" we have defined here.
Example 4: The less-than relation on the set of integers I is a quasi order.
Example 5: The proper subset relation on the power set of a set, say {1, 2}, is also a quasi order.
The concept of least/greatest number in a set of integers can be generalized for a general poset. We start with the concepts of minimal/maximal elements.
Definition(minimal/maximal element): Let<A, ≾>be a poset, where ≾ represents an arbitrary partial order. Then an element b ∈A is a minimal element of A if there is no element a ∈A that satisfies a ≾b. Similarly an element b ∈A is a maximal element of A if there is no element a ∈A that satisfies b ≾a.
Example 6: The set of {{1}, {2}, {1, 2}} with ⊆ has two minimal elements {1} and {2}. Note that {1}, and {2} are not related to each other in ⊆. Hence we can not say which is "smaller than" which, that is, they are not comparable.
Definition(least/greatest element): Let<A, ≾>be a poset. Then an element b∈A is the least element of A if for every element a ∈A, b ≾a.
Note that the least element of a poset is unique if one exists because of the antisymmetry of ≾.
Example 7: The poset of the set of natural numbers with the less-than-or-equal-to relation has the least element 0.
Example 8: The poset of the powerset of {1, 2} with ⊆ has the least element ∅.
Definition(well order): A total order R on a set A is a well order if every non-empty subset of A has the least element.
Example 9: The poset of the set of natural numbers with the less-than-or-equal-to relation is a well order, because every set of natural numbers has the least element.
Notification Switch
Would you like to follow the 'Discrete structures' conversation and receive update notifications?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|