Partially ordered sets, or posets, are the building blocks of order theory. They help us understand relationships between elements in a set, like how numbers compare or how sets fit inside each other. Posets have special rules that make them work, like reflexivity and transitivity.

In this part of our study, we'll look at different types of posets and their cool features. We'll see how some posets have special elements that are bigger or smaller than others, and how we can draw pictures to show how elements relate. It's all about finding patterns in how things are ordered!

Partially Ordered Sets

Definition and Fundamental Concepts

• Partially ordered set (poset) consists of a set P and a binary relation ≤ satisfying specific order axioms
• Binary relation ≤ must meet three key properties for a valid partial order
  • Reflexivity ensures every element relates to itself
  • Antisymmetry prevents distinct elements from being mutually comparable in both directions
  • Transitivity maintains consistency of the order relation across multiple elements
• Hasse diagrams provide graphical representations of posets
  • Vertices represent elements
  • Edges show order relations between comparable elements
• Maximal elements have no greater elements within the given order
• Minimal elements have no lesser elements within the given order

Bounds and Extrema

• Upper bounds exceed or equal all elements in a subset
• Lower bounds fall below or equal all elements in a subset
• Least upper bound (supremum) represents the smallest upper bound
• Greatest lower bound (infimum) represents the largest lower bound
• Supremum and infimum concepts crucial for understanding poset structure
• Not all subsets in a poset necessarily have suprema or infima

Properties of Posets

Reflexivity

• Reflexive property requires a ≤ a for every element a in poset P
• Ensures each element relates to itself
• Represented mathematically as $\forall a \in P, a \leq a$
• Examples include:
  • Natural numbers under standard ≤ relation (5 ≤ 5)
  • Set inclusion relation (A ⊆ A for any set A)

Antisymmetry

• Antisymmetric property states if a ≤ b and b ≤ a, then a = b for elements a and b in poset P
• Prevents distinct elements from being mutually comparable in both directions
• Expressed mathematically as $\forall a, b \in P, (a \leq b \land b \leq a) \implies a = b$
• Examples include:
  • Integer division relation (if a | b and b | a, then a = ±b)
  • Subset relation (if A ⊆ B and B ⊆ A, then A = B)

Transitivity

• Transitive property requires if a ≤ b and b ≤ c, then a ≤ c for elements a, b, c in poset P
• Maintains consistency of order relation across multiple elements
• Represented mathematically as $\forall a, b, c \in P, (a \leq b \land b \leq c) \implies a \leq c$
• Examples include:
  • Real numbers under ≤ relation (if 2 ≤ 3 and 3 ≤ 4, then 2 ≤ 4)
  • Ancestral relation in family trees (if A is an ancestor of B and B is an ancestor of C, then A is an ancestor of C)

Proving Poset Properties

• Direct logical arguments often used to prove reflexivity, antisymmetry, and transitivity
• Counterexamples help identify violations of these properties
• Formal proofs establish validity of given partial orders
• Recognizing property violations crucial for identifying invalid partial orders
• Practice constructing proofs strengthens understanding of poset fundamentals

Comparability in Posets

Comparable and Incomparable Elements

• Elements a and b in poset P are comparable if a ≤ b or b ≤ a
• Elements are incomparable if neither a ≤ b nor b ≤ a holds
• Comparability relation in posets not necessarily transitive
• Techniques for determining comparability:
  • Analyzing Hasse diagrams
  • Applying properties of partial order relation
• Examples:
  • In the poset of subsets of {1, 2, 3} under ⊆, {1} and {2, 3} are incomparable
  • In the poset of natural numbers under divisibility, 2 and 3 are incomparable, but 2 and 4 are comparable

Chains and Antichains

• Chain represents a subset where every pair of elements is comparable
• Antichain consists of a subset where no two distinct elements are comparable
• Poset width defined as size of largest antichain
• Poset height measured by size of longest chain
• Dilworth's theorem connects poset width to minimum number of chains covering all elements
• Examples:
  • In the divisibility poset of {1, 2, 3, 4, 6, 12}, {1, 2, 3, 4, 6, 12} forms a chain
  • In the subset poset of {a, b, c}, {{a}, {b}, {c}} forms an antichain

Special Types of Posets

Total Orders and Well-Orders

• Total order (linear order) represents a partial order where every pair of elements is comparable
• Examples of total orders:
  • Natural numbers under standard ≤ relation
  • Alphabetical ordering of words in a dictionary
• Well-order constitutes a total order where every non-empty subset has a least element
• Natural numbers under usual order form a well-order
• Integers under standard order do not form a well-order (no least element in set of negative integers)
• Well-ordering principle fundamental in mathematical induction and recursion theory

Lattices and Complete Lattices

• Lattices represent posets where every pair of elements has unique supremum (join) and infimum (meet)
• Applications of lattices span algebra and computer science
• Complete lattices ensure every subset (including empty set) has supremum and infimum
• Examples of lattices:
  • Power set of a set ordered by inclusion
  • Divisors of a positive integer ordered by divisibility
• Boolean algebra forms an important class of lattices used in logic and circuit design

Advanced Poset Concepts

• Product order on Cartesian products allows construction of complex posets from simpler ones
• Zorn's lemma, equivalent to Axiom of Choice, proves existence of maximal elements in certain posets
• Applications of Zorn's lemma:
  • Proving existence of bases in vector spaces
  • Demonstrating existence of maximal ideals in rings
• Understanding these advanced concepts crucial for deeper exploration of order theory and its applications