Ordered Set

Definition

An ordered set is a set equipped with an order relation that arranges its elements in a specified way.

Most commonly, in the context of unit topics like posets and lattices, an ordered set means a partially ordered set (poset).

A partially ordered set is a pair $(A, \le)$ , where:

$A$ is a set
$\le$ is a relation on $A$ satisfying:
Reflexive: $a \le a$ for every $a \in 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$

If every pair of elements is comparable, the ordered set is called a totally ordered set or linearly ordered set. That means for any $a, b \in A$ , either $a \le b$ or $b \le a$ .

Examples of ordered sets:

$(\mathbb{N}, \le)$ , natural numbers with usual order
$(\mathcal{P}(S), \subseteq)$ , power set ordered by inclusion
$(\{1,2,3,6\}, \mid)$ , divisors of 6 ordered by divisibility

Main Content

1. Types of Ordered Sets

Totally ordered set (linear order)

: Every pair of elements can be compared. Example: $1 \le 3 \le 5$ . Here, any two numbers have a definite order.

Partially ordered set (poset)

: Not every pair must be comparable. Example: the set $\{1,2,3,6\}$ under divisibility. Here, 2 and 3 are incomparable because neither divides the other.

A clearer comparison:

Structure	Comparability	Example
Total order	Every pair comparable	$(\mathbb{Z}, \le)$
Partial order	Some pairs may be incomparable	$(\mathcal{P}(S), \subseteq)$

Important observations:

In a total order, the elements form a complete sequence.
In a partial order, the structure may branch, showing hierarchy rather than a single line.
Ordered sets are often represented using Hasse diagrams to visualize partial orders.

Example of a poset: Let $A = \{1,2,3,6\}$ with divisibility.

$1 \mid 2$ , $1 \mid 3$ , $1 \mid 6$
$2 \mid 6$ , $3 \mid 6$
But $2$ and $3$ are not comparable

This makes it a partial order, not a total order.

2. Comparability, Minimal and Maximal Elements

Comparable elements

: Two elements $a$ and $b$ are comparable if either $a \le b$ or $b \le a$ .

Minimal element

: An element that has no smaller element below it in the ordered set.

Maximal element

: An element that has no larger element above it in the ordered set.

These are different from the smallest or largest element:

A least element is less than or equal to every element in the set.
A greatest element is greater than or equal to every element in the set.
A minimal element need not be least.
A maximal element need not be greatest.

Example: Consider the poset $(\{1,2,3,6\}, \mid)$ .

$1$ is the least element
$6$ is the greatest element
$2$ and $3$ are both minimal above 1 in certain substructures, but in the whole set they are not minimal because 1 divides them
$2$ and $3$ are maximal only if we consider a smaller subset such as $\{1,2,3\}$ under divisibility, where neither divides the other and neither has a larger element in that subset

Another example: Set $S = \{ \{1\}, \{2\}, \{1,2\} \}$ ordered by inclusion.

$\{1\}$ and $\{2\}$ are minimal elements
$\{1,2\}$ is maximal and also greatest
There is no least element among $\{1\}$ and $\{2\}$ because neither is contained in the other

This concept is important in identifying the “edge” elements of an ordered structure.

3. Hasse Diagram Representation

A Hasse diagram is a graphical way to represent a finite poset.
It shows only the essential order relations, leaving out reflexive and transitive edges.

Rules for drawing a Hasse diagram:

Place smaller elements lower and larger elements higher.
Draw an edge only when one element covers another directly.
Do not draw arrows; upward direction indicates increasing order.
Do not include self-loops or redundant transitive connections.

Example: Poset $(\{1,2,3,6\}, \mid)$

Interpretation:

$1$ is below $2$ , $3$ , and $6$
$2$ and $3$ are below $6$
No line is drawn from $1$ directly to $6$ because that relation is implied through transitivity

Why Hasse diagrams matter:

They make partial orders easier to understand visually.
They show chains, branches, minimal and maximal elements.
They are used in analyzing lattices and combinatorial structures.

Another example using subsets of $\{a,b\}$ ordered by inclusion:

   {a,b}
   /   \
 {a}   {b}
   \   /
     ∅

This represents the power set ordered by inclusion.

Working / Process

1. Identify the set and the relation

Determine what objects are being compared.
Decide the relation used to order them, such as $\le$ , $\subseteq$ , or divisibility.

2. Check whether it is a partial or total order

Verify reflexivity, antisymmetry, and transitivity.
Check whether every pair is comparable to decide if it is total.

3. Analyze the structure

Find comparable and incomparable elements.
Identify minimal, maximal, least, and greatest elements.
Draw a Hasse diagram if the set is finite.

Advantages / Applications

Organizes mathematical objects systematically

: Ordered sets help classify elements by hierarchy, size, inclusion, or divisibility.

Useful in computer science and algorithms

: They appear in scheduling, dependency resolution, task ordering, and topological sorting.

Foundation for advanced topics

: Ordered sets lead naturally to Hasse diagrams, lattices, Boolean algebra, and combinatorial analysis.

Summary

Ordered sets arrange elements according to a relation
Partial orders and total orders are the two main forms
Hasse diagrams help visualize finite ordered sets
Important terms to remember: ordered set, partial order, total order, comparable elements, minimal element, maximal element, Hasse diagram, divisibility, inclusion