📂Set Theory

부분순서 집합

Definition ¹

1. A relation $\le$ on a set $A$ is called a partial order if it is reflexive, transitive, and antisymmetric, and $(A,\le)$ is referred to as a partially ordered set. In other words, that $A$ is a partially ordered set means that for all elements $a,b,c \in A$, the following holds: $$\begin{align*} a \le a & \text{ (reflexivity) } \\ a \le b \land b \le c \implies a \le c & \text{ (transitivity) } \\ a \le b \land b \le a \implies a = b & \text{ (antisymmetry) } \end{align*}$$
2. Given a partially ordered set $(A, \le)$, if for all $a,b \in A$ either $a \le b$ or $b \le a$ holds, then $\le$ is called a total order on $A$, and $(A,\le)$ is called a totally ordered set.

Explanation

A partial order (set) can also be translated as a quasi-order (set). The notation $\preceq$ is also used for partial orders.

In the definition, $\le$ is merely a symbol and does not necessarily need to be an inequality comparing sizes. While inequalities or subset relations can be partial orders, the converse is not true. For example, in the alphabet, ‘a’ follows ‘b’, and simply using symbols, it can be represented as $a \le b$, without issue. In computer science, ‘a’ corresponds to ASCII code $0000001_{(2)}$ and ‘b’ to ASCII code $00000010_{(2)}$, and the order between characters can also be represented by the binary relations of these ASCII codes.

In fact, a totally ordered set is something that anyone with an elementary education might naturally think of, and it might be more difficult to immediately think of a non-totally ordered set. A good example of a totally ordered set is the set of natural numbers $\mathbb{N}$, and this is similarly true for the set of integers $\mathbb{Z}$, the set of rationals $\mathbb{Q}$, and the set of real numbers $\mathbb{R}$. However, when we reach the set of complex numbers $\mathbb{C}$, there is no natural order that is immediately defined.

Defining a partial order before defining a total order is mathematically much more natural. Consider the following five sets, $$\begin{align*} A &= \left\{ 1 \right\} \\ B &= \left\{ 1,2 \right\} \\ C &= \left\{ 1,3 \right\} \\ D &= \left\{ 1,2,3 \right\}\\ E &= \left\{ 1,2,4 \right\} \end{align*}$$ and think about the subset relation of these sets to confirm the following relationships: $$A \subset B \subset D \\ A \subset B \subset E \\ A \subset C \subset D$$ Visually, one can confirm this complex structure at a glance.

Or, consider another example with the following six sets: $$\begin{align*} A^{\prime} &= \left\{ 1 \right\} \\ B^{\prime} &= \left\{ 1,2 \right\} \\ C^{\prime} &= \left\{ 1,3 \right\} \\ D^{\prime} &= \left\{ 1,2,4 \right\}\\ E^{\prime} &= \left\{ 5 \right\}\\ F^{\prime} &= \left\{ 2, 5 \right\} \end{align*}$$ $$A^{\prime} \subset B^{\prime} \subset D^{\prime} \\ A^{\prime} \subset C^{\prime} \\ E^{\prime} \subset F^{\prime}$$ The visual representation is as follows:

In truth, such nonlinear forms are natural relationships that can often be found in our daily lives. Upon reflection, a relationship where everything is entirely linearly related might actually seem unusual. Even the set of natural numbers $\mathbb{N}$, according to von Neumann’s construction, is somewhat removed from the expression ‘intuitive’. Therefore, it might be more convenient to refer to a total order simply as a relationship where a partial order is defined linearly over the entire set.