🔳Lattice Theory Unit 1 – Introduction to Partially Ordered Sets

What's a Partially Ordered Set?

• Consists of a set and a binary relation that indicates that some elements precede others
• The binary relation is called a partial order and typically denoted as $\leq$
• For elements $a$ and $b$ in set $P$, if $a \leq b$, we say "$a$ is related to $b$" or "$a$ precedes $b$"
• Not every pair of elements in a poset must be comparable under the partial order
  • If neither $a \leq b$ nor $b \leq a$, then $a$ and $b$ are incomparable
• Partial orders are reflexive, antisymmetric, and transitive relations
• Formally denoted as an ordered pair $(P, \leq)$ where $P$ is a set and $\leq$ is a partial order on $P$
• Generalizes the concept of total orders (linear orders) where every pair of elements is comparable

Key Concepts and Terminology

• Reflexivity: For all $a \in P$, $a \leq a$ (every element is related to itself)
• Antisymmetry: For all $a, b \in P$, if $a \leq b$ and $b \leq a$, then $a = b$ (no distinct elements precede each other)
• Transitivity: For all $a, b, c \in P$, if $a \leq b$ and $b \leq c$, then $a \leq c$ (precedence is transitive)
• Comparability: Elements $a$ and $b$ are comparable if either $a \leq b$ or $b \leq a$
• Incomparability: Elements $a$ and $b$ are incomparable if neither $a \leq b$ nor $b \leq a$
• Minimal element: An element $a \in P$ is minimal if there is no $b \in P$ such that $b \leq a$ and $b \neq a$
• Maximal element: An element $a \in P$ is maximal if there is no $b \in P$ such that $a \leq b$ and $a \neq b$

Properties of Partial Orders

• Reflexivity: Every element is related to itself ($a \leq a$ for all $a \in P$)
• Antisymmetry: No distinct elements precede each other (if $a \leq b$ and $b \leq a$, then $a = b$)
• Transitivity: Precedence is transitive (if $a \leq b$ and $b \leq c$, then $a \leq c$)
• A partial order is a preorder (reflexive and transitive) that is also antisymmetric
• Partial orders may have incomparable elements, unlike total orders where all elements are comparable
• The set of real numbers with the usual $\leq$ relation is a total order, but not all posets are total orders
• A poset can have multiple minimal or maximal elements, but at most one minimum or maximum element

Types of Elements in Posets

• Minimal element: No other element precedes it (there is no $b \in P$ such that $b \leq a$ and $b \neq a$)
• Maximal element: No other element succeeds it (there is no $b \in P$ such that $a \leq b$ and $a \neq b$)
  • A poset can have multiple minimal or maximal elements
• Minimum element: Precedes all other elements (for all $b \in P$, $a \leq b$)
• Maximum element: Succeeds all other elements (for all $b \in P$, $b \leq a$)
  • A poset can have at most one minimum or maximum element
• Lower bound of a subset $S \subseteq P$: An element $a \in P$ such that $a \leq s$ for all $s \in S$
• Upper bound of a subset $S \subseteq P$: An element $a \in P$ such that $s \leq a$ for all $s \in S$

Visualizing Posets: Hasse Diagrams

• Hasse diagrams are graphical representations of posets that capture the partial order relation
• Elements of the poset are represented as vertices (dots) in the diagram
• If $a \leq b$ and there is no element $c$ such that $a \leq c \leq b$ ($a \neq c \neq b$), then there is an edge (line) drawn from $a$ to $b$
  • This edge represents a "covers" relation, denoted as $a \prec b$ or $b \succ a$
• Edges are directed upward, so if $a \leq b$, then $a$ appears below $b$ in the diagram
• Transitive relations are not explicitly shown as edges to keep the diagram simple
• Incomparable elements are not connected by an edge and are typically drawn at the same level
• The Hasse diagram of a total order is a vertical line with elements arranged from bottom to top

Common Examples and Applications

• Divisibility relation on natural numbers: $a \leq b$ if $a$ divides $b$ (denoted as $a \mid b$)
  • Example: Positive divisors of 12 ordered by divisibility: $1 \leq 2 \leq 3 \leq 4 \leq 6 \leq 12$
• Subset relation on a collection of sets: $A \leq B$ if $A \subseteq B$
  • Example: Power set of $\{a, b\}$ ordered by inclusion: $\emptyset \leq \{a\} \leq \{a, b\}$ and $\emptyset \leq \{b\} \leq \{a, b\}$
• Subgroup relation on groups: $H \leq G$ if $H$ is a subgroup of $G$
• Implication relation on logical propositions: $p \leq q$ if $p \Rightarrow q$
• Preference relations in decision theory and social choice theory
• Scheduling tasks with prerequisites or dependencies

Relationships Between Posets

• Subposet: A poset $(Q, \leq_Q)$ is a subposet of $(P, \leq_P)$ if $Q \subseteq P$ and $\leq_Q$ is the restriction of $\leq_P$ to $Q$
• Induced subposet: A poset $(Q, \leq_Q)$ is an induced subposet of $(P, \leq_P)$ if $Q \subseteq P$ and for all $a, b \in Q$, $a \leq_Q b$ if and only if $a \leq_P b$
• Isomorphic posets: Posets $(P, \leq_P)$ and $(Q, \leq_Q)$ are isomorphic if there exists a bijection $f: P \to Q$ such that for all $a, b \in P$, $a \leq_P b$ if and only if $f(a) \leq_Q f(b)$
  • Isomorphic posets have the same structure and can be viewed as "essentially the same"
• Dual of a poset: The dual of $(P, \leq)$ is the poset $(P, \geq)$ where $a \geq b$ if and only if $b \leq a$ in the original poset
  • The Hasse diagram of the dual is obtained by flipping the original Hasse diagram upside down
• Product of posets: The product of $(P, \leq_P)$ and $(Q, \leq_Q)$ is the poset $(P \times Q, \leq)$ where $(a, b) \leq (c, d)$ if and only if $a \leq_P c$ and $b \leq_Q d$

Practice Problems and Exercises

• Determine whether a given relation on a set is a partial order by checking reflexivity, antisymmetry, and transitivity
• Draw the Hasse diagram of a given poset
• Find minimal, maximal, minimum, and maximum elements in a poset, if they exist
• Determine whether two elements in a poset are comparable or incomparable
• Find lower and upper bounds of subsets in a poset
• Prove that a given function between two posets is an order-preserving map (homomorphism) or an isomorphism
• Construct the dual of a given poset and draw its Hasse diagram
• Find induced subposets of a given poset
• Determine the product of two given posets and draw its Hasse diagram
• Solve problems involving divisibility, subset relations, or other common examples of posets