Ordered Set

Definition

An ordered set is a set equipped with an order relation that tells how its elements are arranged relative to one another.

Most commonly in this unit, an ordered set means a partially ordered set (poset):

A pair $(P, \le)$ is called a partially ordered set if:

1. $\le$ is reflexive: $a \le a$ for every $a \in P$
2. $\le$ is antisymmetric: if $a \le b$ and $b \le a$, then $a = b$
3. $\le$ is transitive: if $a \le b$ and $b \le c$, then $a \le c$

Here, $\le$ is not necessarily the usual numerical less-than-or-equal relation; it is any relation that satisfies these three properties.

Example

Let $P = \{1, 2, 3, 6\}$ with the relation “divides” $|$. Then:

• $1 \mid 2$, $1 \mid 3$, $1 \mid 6$
• $2 \mid 6$, $3 \mid 6$
• $2 \nmid 3$ and $3 \nmid 2$

This forms an ordered set because divisibility is reflexive, antisymmetric, and transitive.

---

Main Content

1. Partial Order and Poset

• A partial order is a relation in which not every pair of elements must be comparable.
• In an ordered set, some elements may be related while others may not be. This is what makes it partial rather than total.

Key idea

For elements $a$ and $b$:

• If $a \le b$, then $a$ is “before” or “below” $b$ in the order.
• If neither $a \le b$ nor $b \le a$, then the two elements are incomparable.

Example of incomparable elements

Consider the set of subsets of $\{a, b\}$ ordered by inclusion $\subseteq$:

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

Here, $\{a\}$ and $\{b\}$ are incomparable because neither is a subset of the other.

Common examples of ordered sets

• Natural numbers with $\le$
• Integers with $\le$
• Sets ordered by inclusion $\subseteq$
• Positive integers ordered by divisibility
• Tasks ordered by precedence in scheduling problems

Important properties

Reflexive

• : every element relates to itself

Antisymmetric

• : no two different elements can dominate each other in both directions

Transitive

• : order can be chained consistently

---

2. Comparable and Incomparable Elements

• Two elements in an ordered set are comparable if one is related to the other.
• If neither element is related to the other, they are incomparable.

Why this matters

In a total order, every pair is comparable. In a partial order, some pairs may not be comparable, which gives the structure more flexibility.

Example

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

• $1$ and $2$ are comparable because $1 \mid 2$
• $2$ and $3$ are incomparable because $2 \nmid 3$ and $3 \nmid 2$
• $2$ and $6$ are comparable because $2 \mid 6$

Interpretation

Comparable elements can be placed in a definite order, while incomparable elements represent branches or independent choices.

Real-life meaning

• In project planning, some tasks must be done before others, but some tasks can be done independently.
• In computer science, dependency graphs often form posets because some components depend on others, but unrelated components are incomparable.

---

3. Chains, Antichains, and Hasse Diagrams

• A chain is a subset of an ordered set in which every pair of elements is comparable.
• An antichain is a subset in which no two distinct elements are comparable.
• A Hasse diagram is a simplified graphical representation of a poset.

Chain

A chain behaves like a linearly ordered sequence.

Example: $$1 < 2 < 3 < 4$$

This is a chain because every pair can be compared.

Antichain

An antichain contains elements that are mutually incomparable.

Example in subsets of $\{a,b\}$: $$\{a\},\ \{b\}$$ These form an antichain.

Hasse diagram

A Hasse diagram shows the order relation without drawing:

• self-loops
• repeated transitive edges
• arrows, usually

Instead, elements are placed so that larger elements appear above smaller ones, and lines connect only covering relations.

Example Hasse diagram for divisibility on $\{1,2,3,6\}$

    6
   / \
  2   3
   \ /
    1

Interpretation:

• $1$ divides $2$ and $3$
• $2$ and $3$ divide $6$
• The diagram avoids drawing the direct edge $1 \to 6$ because it is implied by transitivity

Cover relation

An element $b$ covers $a$ if:

• $a < b$
• there is no element $c$ such that $a < c < b$

This concept is essential in drawing Hasse diagrams.

---

Working / Process

1. Identify the set

• First, specify the collection of elements you want to study.
• Example: $\{1,2,3,6\}$, subsets of a set, tasks in a project, or numbers in a sequence.

2. Choose or verify the relation

• Determine the relation that will define the order.
• Check whether it is reflexive, antisymmetric, and transitive.
• If all three properties hold, the structure is a poset.

3. Analyze the structure

• Find comparable and incomparable elements.
• Determine chains, antichains, maximal and minimal elements if needed.
• Construct a Hasse diagram by drawing only covering relations.
• Use the structure to solve problems in ordering, dependency, or hierarchy.

---

Advantages / Applications

• Ordered sets provide a clear way to study hierarchy, dependency, and arrangement in mathematics and applied fields.
• They are essential in constructing and understanding Hasse diagrams, which make complex order relations easy to visualize.
• They are widely used in combinatorics, lattice theory, scheduling, data organization, and computer science problems such as dependency resolution and topological ordering.

---

Summary

• Ordered sets organize elements using a relation that describes precedence or hierarchy.
• A poset is an ordered set with reflexive, antisymmetric, and transitive relation.
• Hasse diagrams give a compact visual form of ordered sets.

Important terms to remember

• ordered set, partial order, poset, comparable, incomparable, chain, antichain, Hasse diagram, cover relation, maximal element, minimal element