Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
partial_order [2008/04/29 22:29] vkuncak |
partial_order [2008/04/30 10:00] vkuncak |
||
---|---|---|---|
Line 21: | Line 21: | ||
**Example:** Let $U = \{ 1,2,3\}$ and let $A = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{2,3\} \}$. Then $(A, \le)$ is a partial order. We can draw it as a Hasse diagram. | **Example:** Let $U = \{ 1,2,3\}$ and let $A = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{2,3\} \}$. Then $(A, \le)$ is a partial order. We can draw it as a Hasse diagram. | ||
+ | |||
+ | ===== Hasse diagram ===== | ||
+ | |||
+ | [[wk>Hasse diagram]] presents the relation as a directed graph in a plane, such that | ||
+ | * the direction of edge is given by which nodes is drawn above | ||
+ | * transitive and reflexive edges are not represented (they can be derived) | ||
===== Extreme Elements in Partial Orders ===== | ===== Extreme Elements in Partial Orders ===== | ||
Line 31: | Line 37: | ||
* **greatest element** of $S$ if $a \in S$ and for all $a' \in S$ we have $a' \le a$ | * **greatest element** of $S$ if $a \in S$ and for all $a' \in S$ we have $a' \le a$ | ||
* **least element** of $S$ if $a \in S$ and for all $a' \in S$ we have $a \le a'$ | * **least element** of $S$ if $a \in S$ and for all $a' \in S$ we have $a \le a'$ | ||
- | * **least upper bound** (lub, supremum, $\sqcup$) of $S$ if $a$ is the least element in the set of all upper bounds of $S$ | + | * **least upper bound** (lub, supremum, meet, $\sqcup$) of $S$ if $a$ is the least element in the set of all upper bounds of $S$ |
- | * **greatest lower bound** (glb, infimum, $\sqcap$) of $S$ if $a$ is the least element in the set of all upper bounds of $S$ | + | * **greatest lower bound** (glb, infimum, join, $\sqcap$) of $S$ if $a$ is the least element in the set of all upper bounds of $S$ |
Taking $S=A$ we obtain minimal, maximal, greatest, least elements for the entire partial order. | Taking $S=A$ we obtain minimal, maximal, greatest, least elements for the entire partial order. |