Hasse Diagram and Lattices: Introduction

Definition

A partially ordered set (poset) is a set $P$ together with a relation $\le$ such that for all $a, b, c \in P$:

Reflexive

• $a \le a$

Antisymmetric

• if $a \le b$ and $b \le a$, then $a = b$

Transitive

• if $a \le b$ and $b \le c$, then $a \le c$

A Hasse diagram is a graphical representation of a finite poset in which:

• elements are drawn as points,
• larger elements are placed higher than smaller ones,
• edges are drawn only for covering relations,
• reflexive and transitive edges are omitted.

An element $b$ covers an element $a$ if $a < b$ and there is no element $c$ such that $a < c < b$.

A lattice is a poset in which every pair of elements $a, b$ has:

• a greatest lower bound (also called meet, denoted $a \wedge b$),
• a least upper bound (also called join, denoted $a \vee b$).

So, a lattice is a poset where both meet and join exist for every pair of elements.

Example of a lattice under divisibility:

For the set $\{1,2,3,6\}$ with divisibility $(\mid)$:

• $1$ divides every element,
• $6$ is divisible by every element,
• the meet of $2$ and $3$ is $1$,
• the join of $2$ and $3$ is $6$.

---

Main Content

1. Posets and Order Relations

• A poset is a set with a relation that organizes elements in a meaningful order, but unlike total order, not every pair must be comparable.
• Common examples include divisibility on integers, inclusion on sets, and dependency relations in tasks or courses.

A key idea in posets is comparability. Two elements $a$ and $b$ are comparable if either $a \le b$ or $b \le a$. If neither holds, they are incomparable. This is what makes posets more general than ordinary number ordering.

Example: Divisibility Poset

Consider the set $\{1,2,3,6\}$ with the relation “divides”:

• $1 \mid 2$, $1 \mid 3$, $1 \mid 6$
• $2 \mid 6$, $3 \mid 6$
• $2$ and $3$ are incomparable

This structure is a poset because:

• every number divides itself,
• if $a$ divides $b$ and $b$ divides $a$, then $a=b$,
• divisibility is transitive.

Why Posets Matter

• They generalize order in situations where full ranking is impossible or unnecessary.
• They provide the foundation for Hasse diagrams.
• They are the starting point for lattice theory.

---

2. Hasse Diagram

• A Hasse diagram is a neat and efficient way to draw a finite poset.
• It shows only the essential order relations, making the structure easier to interpret than a full relation graph.

In a Hasse diagram:

• higher placement means “greater” in the order,
• lines are drawn only when one element covers another,
• arrows are usually omitted because upward direction already indicates order,
• transitive edges are not drawn, since they can be inferred.

Example: Hasse Diagram for $\{1,2,3,6\}$ under divisibility

    6
   / \
  2   3
   \ /
    1

This diagram shows:

• $1$ is below $2$ and $3$,
• $2$ and $3$ are below $6$,
• $2$ and $3$ are incomparable,
• the missing lines $1\to 6$ are not drawn because they are implied by transitivity.

How to Read a Hasse Diagram

• Elements at the bottom are smaller.
• Elements at the top are larger.
• If there is a path going upward from $a$ to $b$, then $a \le b$.
• If there is no upward path between two elements, they may be incomparable.

Important Features

Minimal element

• an element with nothing below it.

Maximal element

• an element with nothing above it.

Least element

• one element below all others.

Greatest element

• one element above all others.

Not every poset has a least or greatest element, but many examples do.

---

3. Lattices, Meet and Join

• A lattice is a poset in which every pair of elements has both a meet and a join.
• Meet and join capture the ideas of “common lower part” and “common upper part.”

Meet $(a \wedge b)$

The meet of $a$ and $b$ is their greatest lower bound:

• it is below both $a$ and $b$,
• and is the largest such lower bound.

Join $(a \vee b)$

The join of $a$ and $b$ is their least upper bound:

• it is above both $a$ and $b$,
• and is the smallest such upper bound.

Example 1: Divisibility Lattice

In $\{1,2,3,6\}$ under divisibility:

• $2 \wedge 3 = 1$
• $2 \vee 3 = 6$
• $1 \wedge 6 = 1$
• $1 \vee 6 = 6$

Here, meet corresponds to gcd and join corresponds to lcm.

Example 2: Power Set Lattice

For the power set of $\{a,b\}$, ordered by inclusion:

$$\emptyset, \{a\}, \{b\}, \{a,b\}$$

• meet is intersection,
• join is union.

For example:

• $\{a\} \wedge \{b\} = \emptyset$
• $\{a\} \vee \{b\} = \{a,b\}$

Importance of Lattices

• They provide a strong algebraic structure for ordered systems.
• They unify many mathematical ideas under one framework.
• They are widely used in logic, algebra, and combinatorics.

---

Working / Process

1. Identify the set and relation

• Start with the given set of elements.
• Determine the ordering relation, such as divisibility or inclusion.
• Verify that the relation is reflexive, antisymmetric, and transitive to confirm that it is a poset.

2. Construct the Hasse diagram

• Arrange elements so that smaller ones are lower and larger ones are higher.
• Remove reflexive and transitive connections.
• Draw only covering relations.
• Check which elements are comparable and which are not.

3. Test whether the poset is a lattice

• Take each pair of elements and find their lower bounds and upper bounds.
• Determine whether a greatest lower bound and least upper bound exist for every pair.
• If every pair has both, the poset is a lattice.
• Use the diagram to visually support the computation of meet and join.

Example workflow for $\{1,2,3,6\}$ under divisibility:

• Step 1: Relation is “divides.”
• Step 2: Hasse diagram shows $1$ at bottom, $6$ at top, $2$ and $3$ in between.
• Step 3: Every pair has meet and join, so it is a lattice.

---

Advantages / Applications

Simplifies order relations

• Hasse diagrams compress a large amount of ordering information into a clean visual form, making posets easier to analyze.

Helps identify key structural properties

• They make it easy to see minimal/maximal elements, chains, antichains, and comparability.

Broad mathematical and practical applications

• Lattices and posets are used in set theory, algebra, logic, database theory, scheduling, decision-making, and combinatorics.

Some important applications include:

Number theory

• divisibility lattices, gcd and lcm structures

Set theory

• power set lattices under union and intersection

Computer science

• data hierarchy, type systems, dependency ordering, Boolean algebra

Logic

• proposition lattices and Boolean lattices

Scheduling

• prerequisite graphs and task precedence

Combinatorics

• counting ordered structures and understanding hierarchical arrangements

---

Summary

• Hasse diagrams give a clean visual form of a poset.
• Lattices are posets where every pair has a meet and a join.
• These ideas help study order, hierarchy, and structure in mathematics and applications.
• Important terms to remember
• poset
• comparable / incomparable
• Hasse diagram
• cover relation
• minimal and maximal element
• least and greatest element
• meet
• join
• lattice