📂Set Theory

Partially Ordered Set

Definitions ¹

1. A relation $\le$ in a set $A$ that is reflexive, transitive, and antisymmetric is called a Partial Order, and $(A,\le)$ is referred to as a partially ordered set. Saying that $A$ is a partially ordered set means that it satisfies the following for all elements $a,b \in A$. $$ a \le b \land b \le a \implies a = b $$
2. Given a partially ordered set $(A, \le)$, for all $a,b \in A$, if $a \le b$ or $b \le a$, then $\le$ is called a Total Order in $A$, and $(A,\le)$ is called a Totally Ordered Set.

Explanation

In the definition, $\le$ is just a symbol and does not necessarily have to be an inequality sign comparing sizes. Of course, inequalities or inclusion relations can be partial orders, but the converse is not true. For example, in the alphabet, following ‘a’ is ‘b’, and it doesn’t matter if it is represented as $a \le b$ using just symbols. In fact, in computer science, ‘a’ corresponds to ASCII code $0000001_{(2)}$, and ‘b’ corresponds to ASCII code $00000010_{(2)}$, and the order between characters can also be represented by the binary relations of their sizes.

In fact, totally ordered sets might be something that anyone with compulsory education could easily recall, whereas it may not come as readily to mind what constitutes sets that are not. A good example of a totally ordered set is the set of natural numbers $\mathbb{N}$, and this applies to the sets of integers $\mathbb{Z}$, rational numbers $\mathbb{Q}$, and real numbers $\mathbb{R}$ as well. However, once you reach complex numbers $\mathbb{C}$, there is not a naturally defined order.

Defining partial orders before total orders is mathematically much more natural for that reason. Consider the following five sets, which naturally have partial orders. $$ 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\} $$ Thinking of the inclusion relationship of sets, $$ A \subset B \subset D \\ A \subset B \subset E \\ A \subset C \subset D $$ Visually, this complex shape can be understood at a glance. These non-linear forms represent natural relationships that are common enough to be found in our everyday lives. Upon reflection, a purely linearly stacking relationship might seem more unusual. Even the set of natural numbers $\mathbb{N}$, according to Von Neumann’s construction, is not exactly ‘intuitive’. Thus, it might be easier to understand total orders as simply when a partial order is linearly defined across an entire set.