1.2 Properties of partial orders and their representations

Partial orders have special elements and relationships that define their structure. Upper and lower bounds, maximal and minimal elements, and greatest and least elements all play crucial roles in understanding how elements relate within a poset.

Posets can be visually represented using Hasse diagrams, which show covering relations between elements. The concept of dual posets allows us to reverse order relations, while isomorphisms help identify structurally equivalent posets with different elements.

Bounds and Extrema

Upper and Lower Bounds

Top images from around the web for Upper and Lower Bounds

• 

  calculus - Upper and Lower Integral Bounds on Infinite Sum - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Boolean algebra (structure) - Wikipedia View original

  Is this image relevant?

• 

  calculus - Upper and Lower Integral Bounds on Infinite Sum - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Boolean algebra (structure) - Wikipedia View original

  Is this image relevant?

1 of 2

Top images from around the web for Upper and Lower Bounds

• 

  calculus - Upper and Lower Integral Bounds on Infinite Sum - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Boolean algebra (structure) - Wikipedia View original

  Is this image relevant?

• 

  calculus - Upper and Lower Integral Bounds on Infinite Sum - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Boolean algebra (structure) - Wikipedia View original

  Is this image relevant?

1 of 2

• Upper bound of a subset $S$ of a poset $P$ is an element $u \in P$ such that $s \leq u$ for all $s \in S$
• Lower bound of a subset $S$ of a poset $P$ is an element $l \in P$ such that $l \leq s$ for all $s \in S$
• A subset may have multiple upper or lower bounds
• Example: In the poset of natural numbers ordered by divisibility, the set $\{2, 3\}$ has upper bounds 6 and 12 (among others)
• Example: In the same poset, the set $\{6, 10, 15\}$ has lower bounds 1 and 3 (among others)

Maximal, Minimal, Greatest, and Least Elements

• Maximal element of a poset $P$ is an element $m \in P$ such that there is no $x \in P$ with $m < x$
  • A poset can have multiple maximal elements
• Minimal element of a poset $P$ is an element $n \in P$ such that there is no $x \in P$ with $x < n$
  • A poset can have multiple minimal elements
• Greatest element of a poset $P$ is an element $g \in P$ such that $x \leq g$ for all $x \in P$
  • A poset can have at most one greatest element
• Least element of a poset $P$ is an element $l \in P$ such that $l \leq x$ for all $x \in P$
  • A poset can have at most one least element
• Example: In the poset of subsets of $\{1, 2, 3\}$ ordered by inclusion, $\{1, 2\}$ and $\{1, 3\}$ are maximal elements, while $\{1, 2, 3\}$ is the greatest element
• Example: In the same poset, $\{1\}$, $\{2\}$, and $\{3\}$ are minimal elements, while $\emptyset$ is the least element

Poset Structure

Covering Relation and Hasse Diagrams

• Covering relation in a poset $P$: $y$ covers $x$ (denoted $x \prec y$) if $x < y$ and there is no $z \in P$ such that $x < z < y$
• Hasse diagram is a graphical representation of a poset using its covering relations
  • Elements are represented by vertices
  • If $y$ covers $x$, there is an edge drawn from $x$ up to $y$
  • Provides a concise visual summary of the poset structure
• Example: In the divisibility poset of $\{1, 2, 3, 6\}$, the covering relations are $1 \prec 2$, $1 \prec 3$, $2 \prec 6$, and $3 \prec 6$
• The Hasse diagram of this poset would have 1 at the bottom, 2 and 3 above it, and 6 at the top

Dual Posets and Isomorphisms

• Dual of a poset $P = (X, \leq)$ is the poset $P^d = (X, \geq)$ where the order relation is reversed
  • If $x \leq y$ in $P$, then $y \geq x$ in $P^d$
• Isomorphism between posets $P = (X, \leq_P)$ and $Q = (Y, \leq_Q)$ is a bijection $f: X \to Y$ such that for all $x_1, x_2 \in X$, $x_1 \leq_P x_2$ if and only if $f(x_1) \leq_Q f(x_2)$
  • Isomorphic posets have the same structure, just with possibly different elements
• Example: The poset $(\{1, 2, 3, 6\}, |)$ (divisibility) and the poset $(\{\{1\}, \{1, 2\}, \{1, 3\}, \{1, 2, 3\}\}, \subseteq)$ (subset inclusion) are isomorphic
• The dual of the divisibility poset $(\{1, 2, 3, 6\}, |)$ is the poset $(\{1, 2, 3, 6\}, \geq)$, where $6 \geq 3$, $6 \geq 2$, $3 \geq 1$, and $2 \geq 1$