Unit 2 - Notes

MTH265 8 min read

Unit 2: Ordered Sets and Lattices

1. Introduction

In discrete mathematics, relations are used to describe associations between elements of sets. Among the most important types of relations are those that formalize the concept of "ordering" elements, such as comparing numbers by size, sets by inclusion, or tasks by prerequisites. This unit explores the mathematical structures that arise from these ordering relations, progressing from basic partially ordered sets to highly structured systems known as lattices.

2. Ordered Sets (Partially Ordered Sets / Posets)

An ordered set, or more formally a Partially Ordered Set (Poset), is a set combined with a specific binary relation that dictates the arrangement of the elements.

A relation $\le$ on a set $S$ is called a partial order if it satisfies three properties for all $a, b, c \in S$ :

Reflexivity: $a \le a$ (Every element is related to itself).
Antisymmetry: If $a \le b$ and $b \le a$ , then $a = b$ (Two distinct elements cannot precede each other).
Transitivity: If $a \le b$ and $b \le c$ , then $a \le c$ (Order is passed down a chain).

A poset is denoted by the pair $(S, \le)$ . The word "partially" indicates that not every pair of elements needs to be comparable. If neither $a \le b$ nor $b \le a$ , then $a$ and $b$ are incomparable (denoted $a \parallel b$ ).

Examples of Posets:

$(\mathbb{Z}, \le)$ : The integers under the standard "less than or equal to" relation. (This is actually a total order, a specific type of partial order).
$(\mathcal{P}(A), \subseteq)$ : The power set of $A$ under set inclusion. E.g., $\{1\} \subseteq \{1, 2\}$ , but $\{1\}$ and $\{2\}$ are incomparable.
$(\mathbb{N}^+, |)$ : Positive integers under the "divides" relation ( $a | b$ means $a$ divides $b$ without a remainder).

3. Hasse Diagrams of Partially Ordered Sets

A Hasse Diagram is a graphical representation of a finite poset that eliminates redundant information, making the order structure easy to visualize.

Rules for Constructing a Hasse Diagram:

Represent elements as vertices (dots).
Draw upwards: If $x < y$ (meaning $x \le y$ and $x \neq y$ ), place the vertex for $y$ higher than the vertex for $x$ .
Remove self-loops: Because all partial orders are reflexive ( $x \le x$ ), loops at every vertex are assumed and omitted.
Remove transitive edges: If $x < y$ and $y < z$ , the edge from $x$ to $z$ is omitted because it is implied by transitivity.
Draw lines (edges): Connect $x$ and $y$ with a line if $y$ covers $x$ . ( $y$ covers $x$ if $x < y$ and there is no element $z$ such that $x < z < y$ ).

Example:
For the poset $(D_{12}, |)$ , where $D_{12} = \{1, 2, 3, 4, 6, 12\}$ (the divisors of 12):

1 is at the bottom (it divides everything).
2 and 3 cover 1.
4 covers 2; 6 covers 2 and 3.
12 covers 4 and 6.

4. Consistent Enumeration (Topological Sorting)

A consistent enumeration (also known as a topological sort) of a finite poset $(S, \le)$ is a way of assigning a unique integer to each element of the set such that the assignment respects the partial order.

Definition: A consistent enumeration is a bijective function $f: S \rightarrow \{1, 2, \dots, |S|\}$ such that if $x < y$ in $S$ , then $f(x) < f(y)$ in standard integer ordering.
Significance: It proves that every partial order can be embedded into a total order (a sequence). This is crucial in scheduling tasks where prerequisites exist (e.g., compiling software dependencies or university course prerequisites).
Algorithm:
1. Find a minimal element in the Hasse diagram (an element with no predecessors).
2. Assign it the next available integer (starting from 1).
3. Remove this element and its edges from the diagram.
4. Repeat until all elements are enumerated.

5. Supremum and Infimum

In a poset $(S, \le)$ , we often look at subsets $A \subseteq S$ to find bounds. Let $A$ be a subset of $S$ .

Upper Bound: An element $u \in S$ is an upper bound of $A$ if $x \le u$ for all $x \in A$ .
Lower Bound: An element $l \in S$ is a lower bound of $A$ if $l \le x$ for all $x \in A$ .

Supremum (Least Upper Bound / LUB / Join):
An element $s \in S$ is the supremum of $A$ , denoted $\sup(A)$ or $x \vee y$ for a two-element set, if:

$s$ is an upper bound of $A$ .
For any other upper bound $u$ of $A$ , $s \le u$ .

Infimum (Greatest Lower Bound / GLB / Meet):
An element $i \in S$ is the infimum of $A$ , denoted $\inf(A)$ or $x \wedge y$ for a two-element set, if:

$i$ is a lower bound of $A$ .
For any other lower bound $l$ of $A$ , $l \le i$ .

Note: The supremum and infimum of a subset, if they exist, are unique due to the antisymmetry property.

6. Isomorphic (Similar) Ordered Sets

Two posets $(S_1, \le_1)$ and $(S_2, \le_2)$ are order-isomorphic if they share the exact same structural properties, merely differing by the names of their elements.

Definition: An order isomorphism is a bijective function $f: S_1 \rightarrow S_2$ such that for any $x, y \in S_1$ :
$x \le_1 y \iff f(x) \le_2 f(y)$
Properties: If two posets are isomorphic, their Hasse diagrams can be drawn to look identical. Isomorphisms preserve all order-theoretic properties, such as maximal/minimal elements, bounds, supremums, and infimums.

7. Well-Ordered Sets

A poset $(S, \le)$ is a well-ordered set if every non-empty subset of $S$ has a least (minimum) element.

Key Implications:

Total Order: Every well-ordered set is totally ordered (a chain). For any $x, y \in S$ , the subset $\{x, y\}$ must have a least element, meaning either $x \le y$ or $y \le x$ .
No Infinite Descending Chains: A well-ordered set cannot contain an infinite strictly decreasing sequence ( $x_1 > x_2 > x_3 > \dots$ ).
Mathematical Induction: The principle of mathematical induction is fundamentally based on the fact that the set of natural numbers $\mathbb{N}$ is well-ordered.

Example: $(\mathbb{N}, \le)$ is well-ordered.
Non-Example: $(\mathbb{Z}, \le)$ is not well-ordered because the subset of negative integers has no least element.

8. Lattices and Bounded Lattices

Lattices

A lattice is a poset $(L, \le)$ in which every pair of elements $\{a, b\}$ has both a unique supremum (Join, $a \vee b$ ) and a unique infimum (Meet, $a \wedge b$ ).

Lattices can also be defined algebraically. An algebraic structure $(L, \vee, \wedge)$ is a lattice if it satisfies the following axioms for all $a, b, c \in L$ :

Commutative: $a \vee b = b \vee a$ and $a \wedge b = b \wedge a$
Associative: $a \vee (b \vee c) = (a \vee b) \vee c$ and $a \wedge (b \wedge c) = (a \wedge b) \wedge c$
Absorption: $a \vee (a \wedge b) = a$ and $a \wedge (a \vee b) = a$
Idempotent: $a \vee a = a$ and $a \wedge a = a$

Bounded Lattices

A lattice $L$ is bounded if it has a greatest element (universal upper bound) and a least element (universal lower bound).

The greatest element is usually denoted by $1$ (or $I$ ). For all $x \in L$ , $x \le 1$ .
The least element is usually denoted by $0$ (or $O$ ). For all $x \in L$ , $0 \le x$ .
In a bounded lattice: $a \vee 1 = 1$ , $a \wedge 1 = a$ , $a \vee 0 = a$ , and $a \wedge 0 = 0$ .
Note: Every finite lattice is bounded.

9. Distributive Lattices

A lattice $(L, \vee, \wedge)$ is called a distributive lattice if the operations of join and meet distribute over each other. For all $a, b, c \in L$ :

$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$
$a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$

(Note: In a lattice, if one of these distributive laws holds, the other necessarily holds as well).

Examples:

Any chain (totally ordered set) is a distributive lattice.
The power set $\mathcal{P}(S)$ under union ( $\cup$ ) and intersection ( $\cap$ ) is a distributive lattice.

Non-Examples (Birkhoff's Theorem):
A lattice is distributive if and only if it does not contain a sublattice isomorphic to:

$M_3$ (The Diamond Lattice): Five elements where three elements are incomparable to each other, all sharing the same upper and lower bound.
$N_5$ (The Pentagon Lattice): Five elements forming a pentagon shape in the Hasse diagram.

10. Complements and Complemented Lattices

Complements

Let $(L, \vee, \wedge, 0, 1)$ be a bounded lattice. An element $a' \in L$ is called a complement of an element $a \in L$ if it satisfies two conditions:

$a \vee a' = 1$ (Their join is the universal upper bound)
$a \wedge a' = 0$ (Their meet is the universal lower bound)

Important Property: In a distributive bounded lattice, if an element has a complement, that complement is unique.

Complemented Lattices

A bounded lattice $L$ is called a complemented lattice if every element in $L$ has at least one complement.

Connection to Boolean Algebra:
A lattice that is both distributive and complemented is called a Boolean Algebra (or Boolean Lattice).

Example: The power set lattice $(\mathcal{P}(S), \cup, \cap, \emptyset, S)$ is a complemented distributive lattice (Boolean Algebra). The complement of any subset $A$ is its set-theoretic complement $S \setminus A$ .
Non-Example: In the divisor lattice $(D_{12}, |)$ , the element 2 does not have a complement, so $D_{12}$ is not a complemented lattice.

Unit 1

Unit 3