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

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