Posets

A partially ordered set (or poset) is a set with a particular order applied to it.
This order is called a partial order because not every element in the set may be in the order.

A partial order is a set in an arrangement with an order - wherein one element precedes the other.
It is called a partial order since not every item in the set may be connected.

A partial order on set $A$ is relation $R \subseteq A \times A$ that is:

  • reflexive (for all $a \in A$ then $(a, a) \in R$)
  • transitive (if $(a, b) \in R$ and $(b, c) \in R$ then $(a, c) \in R$)
  • antisymmetric
    • for all $x, y \in A$ if $(x, y) \in R$ and $(y, x) \in R$, then $x = y$
    • this is because the two elements must be the same, as otherwise it wouldn’t be antisymmetric
    • no symmetric edges in a graphical representation allowed, only one-way edges and loops
A partially ordered set can also be called a poset

Bounds

  • Upper bound of a subset of a poset is when you can find an element that is greater than or equal to all the elements in a subset.
  • Lower bound of a subset of a poset is when you can find an element that is less than or equal to all the elements in a subset.
  • Least upper bound of a subset of a poset is an element where the upper bound is less than every other upper bound.
  • Greatest lower bound of a subset of a poset is when an element of that lower bound is greater than every other lower bound.

Hasse Diagrams

In a Hasse Diagram:

  • For a partially ordered set $(S, \leq)$
  • Each element is represented as a vertex
  • Each element is connected with a line segment whenever
    • “y covers x”
    • This means that $y \neq x$ and $x \leq y$
  • Vertices are often placed higher than another if they have a greater value

Set $X = {1, 2, 3, 4, 6, 8, 12, 24}$


Image stolen from (libretexts)[https://math.libretexts.org/Bookshelves/Abstract_and_Geometric_Algebra/Abstract_Algebra%3A_Theory_and_Applications_%28Judson%29/19%3A_Lattices_and_Boolean_Algebras/19.01%3A_Lattices]

If we let $Y = {2, 3, 4, 6}$ be contained in the set $X$ then $Y$ has the upper bounds $12$ and $24$ with $12$ as a least upper bound. The only lower boun dis $1$, hence it must be a greatest lower bound.

Latices

A lattice is a poset, such that every pair of elements has a least upper bound and a greatest lower bound.
For example: