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/28 16:14] vkuncak |
partial_order [2008/04/30 15:21] vkuncak |
||
|---|---|---|---|
| Line 12: | Line 12: | ||
| Given a partial ordering relation $\le$, the corresponding **strict ordering relation** $x < y$ is defined by $x \le y \land x \neq y$ and can be viewed as a shorthand for this conjunction. | Given a partial ordering relation $\le$, the corresponding **strict ordering relation** $x < y$ is defined by $x \le y \land x \neq y$ and can be viewed as a shorthand for this conjunction. | ||
| - | We can view partial order $(A,r)$ as a first-order interpretation $I=(A,\alpha)$ of language ${\cal L}={\le\}$ where $\alpha({\le\})=r$. | + | We can view partial order $(A,r)$ as a first-order interpretation $I=(A,\alpha)$ of language ${\cal L}=\{\le\}$ where $\alpha({\le})=r$. |
| ===== Example Partial Orders ===== | ===== Example Partial Orders ===== | ||
| 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 ===== | ||
| Given a partial order $(A,\le)$ and a set $S \subseteq A$, we call an element $a \in A$ | Given a partial order $(A,\le)$ and a set $S \subseteq A$, we call an element $a \in A$ | ||
| - | * **upper bound** of $S$ if for all $a' \in S$ we have $a \le a'$ | + | * **upper bound** of $S$ if for all $a' \in S$ we have $a' \le a$ |
| * **lower bound** of $S$ if for all $a' \in S$ we have $a \le a'$ | * **lower bound** of $S$ if for all $a' \in S$ we have $a \le a'$ | ||
| * **minimal element** of $S$ if $a \in S$ and there is no element $a' \in S$ such that $a' < a$ | * **minimal element** of $S$ if $a \in S$ and there is no element $a' \in S$ such that $a' < a$ | ||
| * **maximal element** of $S$ if $a \in S$ and there is no element $a' \in S$ such that $a < a'$ | * **maximal element** of $S$ if $a \in S$ and there is no element $a' \in S$ such that $a < a'$ | ||
| - | * **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. | ||
| Line 38: | Line 44: | ||
| Duality minimal/maximal, least/greatest, supremum/infimum | Duality minimal/maximal, least/greatest, supremum/infimum | ||
| - | Note | + | Notes |
| * minimal element need not exist: $(0,1)$ interval of rationals | * minimal element need not exist: $(0,1)$ interval of rationals | ||
| * there may be multiple minimal elements: $\{\{a\},\{b\},\{a,b\}\}$ | * there may be multiple minimal elements: $\{\{a\},\{b\},\{a,b\}\}$ | ||
| Line 45: | Line 51: | ||
| * least element is always glb and minimal | * least element is always glb and minimal | ||
| * if glb belongs to the set, then it is always least and minimal | * if glb belongs to the set, then it is always least and minimal | ||
| + | * for relation $\subseteq$ on sets, $glb$ is intersection, $lub$ is union (not all families of sets are closed under $\cap$, $\cup$) | ||
| ===== Monotonic functions ===== | ===== Monotonic functions ===== | ||