Preordered Set

The idea of "order" is one of the most intuitive tools we use to structure our world, from numbers on a line to events in a timeline. This is typically governed by strict rules like transitivity (if A≤B and B≤C, then A≤C). However, standard ordering falls short when we encounter items that are different yet equivalent in some crucial way, such as two distinct computer programs with the same capabilities. Forcing them to be identical would mean losing important information. This knowledge gap highlights the need for a more flexible framework.

This article delves into the preordered set, a powerful mathematical structure that gracefully handles such equivalences. By relaxing one simple rule—antisymmetry—it opens up a richer way to describe relationships in logic, topology, and analysis. We will first explore the fundamental principles and mechanisms of preorders, understanding how they allow for "ties" and how the added property of "directedness" creates a machine for describing approximation and convergence. Following this, we will journey through its diverse applications, revealing how this single concept provides a new lens to view convergence in topology, underpins the true meaning of the integral in calculus, and forms the very architecture of models for knowledge and logic.

So, we have this idea of an "order." It's one of the most fundamental concepts we use to make sense of the world. We order numbers on a line, events in time, and preferences for pizza toppings. The rules of this game usually seem straightforward. If $A$ is no bigger than $B$, and $B$ is no bigger than $C$, then surely $A$ is no bigger than $C$. This is ​​transitivity​​, and it's the bedrock of logic. And of course, anything is as big as itself—that’s ​​reflexivity​​.

But what happens when the lines of comparison get a little blurry? What if we have two things, say, two chess programs, Alpha and Beta, where Alpha can see every move Beta can see, and Beta can see every move Alpha can see? In some sense, they are "equally powerful." A strict ordering, like the one we use for numbers, would force us to say Alpha and Beta are the same program. But they aren't! They might have different code, run on different hardware, or have been developed by different teams. This is where the simple idea of an order blossoms into something more subtle and powerful: the ​​preorder​​.

A ​​preorder​​ is simply a relation that is reflexive and transitive. It doesn't demand the one extra property that partial orders do—antisymmetry. Antisymmetry is the rule that says if $x \le y$ and $y \le x$, then you must have $x = y$. By dropping this requirement, we open the door to a richer description of reality. We allow for "ties" or "equivalences" between distinct objects.

Let’s imagine a tiny universe with just two elements, $\{a, b\}$. How many fundamentally different ways can we relate them with a preorder? After accounting for the fact that it doesn't matter which we call '$a$' and which we call '$b$', we find there are just three non-isomorphic structures.

1. ​​The Discrete World:​​ Nothing is related except to itself. $a$ and $b$ are incomparable. Think of apples and oranges.
2. ​​The Chain:​​ One element is "less than" the other. A one-way street, like $a \le b$.
3. ​​The Equivalence:​​ Each is "less than or equal to" the other. A two-way street, $a \le b$ and $b \le a$. They are different, but equivalent under our ordering.

This last case is the soul of the preorder. It tells us that we can group things into "clumps" of equivalent items. Within each clump, everything is mutually related. Then, we can describe how these clumps are ordered with respect to each other. In fact, any preorder on a set can be thought of as defining a collection of equivalence classes, and then placing a true partial order on those classes. This act of "collapsing" equivalent items into a single conceptual unit is not just a mathematical trick; it's a profound insight with surprising applications.

Let's step into the world of logic and knowledge. Imagine a scientist trying to solve a problem. At any moment, she is in a certain "state of knowledge." As she performs experiments or makes deductions, she moves to new states, which contain all the old information plus something new. We can model this journey as a collection of "worlds" or "states," with an accessibility relation telling us which worlds we can get to from our current one. This relation, let's call it $\le$, is naturally a preorder.

It's reflexive ($w \le w$) because a state is accessible from itself (no new information is gained). It's transitive ($w \le v$ and $v \le u$ implies $w \le u$) because if you can get from state $w$ to $v$, and from $v$ to $u$, you've effectively found a path from $w$ to $u$.

But why not a partial order? Why isn't it antisymmetric? Suppose the scientist is in state $w$. She could perform experiment A to reach state $v_A$, or she could run a computer simulation B to reach state $v_B$. It's entirely possible that both paths lead to the exact same set of conclusions and predictive power. In our model, this means $v_A \le v_B$ (everything known in $v_A$ is known in $v_B$) and $v_B \le v_A$ (everything known in $v_B$ is known in $v_A$). Yet, $v_A$ and $v_B$ are distinct historical paths! They are not the same state. A partial order would force us to call them identical, losing this crucial information about the process of discovery.

A preorder lets us have our cake and eat it too. It preserves the distinction between informationally equivalent but distinct states. And here is the beauty of it: when we want to ask what is logically and universally true in this system, it turns out that all these equivalent worlds are indistinguishable. We can, for the purpose of logic, "collapse" them into a single super-world. The set of all valid formulas remains the same whether we use the full preorder model or the collapsed partial order model. Antisymmetry isn't necessary for the logic to work; it's a simplification we can make without losing logical power.

Now we add one more ingredient, a property that transforms a preorder into a machine for describing approximation and convergence. A preordered set is called a ​​directed set​​ if for any two elements, $a$ and $b$, there is always a third element $c$ that is "greater than or equal to" both. We say $c$ is an upper bound for $a$ and $b$. This simple property is a guarantee: no matter where you are, no matter which two points you pick, there's always a path forward that unifies them.

Think of a sequence of numbers getting closer and closer to a limit. The natural numbers $(\mathbb{N}, \le)$ are a simple directed set: for any $n_1$ and $n_2$, their maximum, $\max(n_1, n_2)$, is an upper bound. A net, which is a generalization of a sequence, is a function from an abstract directed set. This allows us to talk about convergence in much stranger spaces. Let's see it in action.

• ​​Exploring a Network:​​ Imagine you're mapping an infinite, sprawling cave system, starting from the entrance, $v_0$. Your maps are finite, connected pieces of the cave that include the entrance. The set of all possible such maps forms a directed set under the inclusion relation ($\subseteq$). Why? Take any two maps, $H_1$ and $H_2$. Their union, $H_1 \cup H_2$, is also a finite map containing the entrance, and it contains both of the original maps. There is always a way to create a more comprehensive map that incorporates any two previous explorations. This directedness captures the very essence of systematic exploration.

• ​​Zooming In on a Point:​​ How do we mathematically define "getting arbitrarily close" to a point $c$ in some space? We use its ​​neighborhoods​​—the open sets containing it. The collection of all neighborhoods of $c$, $\mathcal{N}(c)$, forms a directed set, but with a twist: the order is reverse inclusion, $\supseteq$. For any two neighborhoods $U_1$ and $U_2$, their intersection $U_1 \cap U_2$ is also a neighborhood of $c$. This intersection is contained in both original sets, i.e., $U_1 \supseteq U_1 \cap U_2$ and $U_2 \supseteq U_1 \cap U_2$. In the reverse-inclusion order, this means the intersection $U_1 \cap U_2$ is an upper bound for both $U_1$ and $U_2$. This guarantees we can always find a neighborhood that is "tighter" than any two given ones, allowing us to squeeze down onto the point $c$. This is the engine of calculus and topology.

• ​​Building Better Approximations:​​ Consider the set of all continuous functions on the interval $[0,1]$, denoted $C([0,1])$. We can order them pointwise: $f \le g$ if $f(x) \le g(x)$ for all $x$. Is this a directed set? Yes! For any two functions, $f_1$ and $f_2$, we can define their pointwise maximum, $h(x) = \max(f_1(x), f_2(x))$. This new function $h$ is also continuous, and by its very construction, $f_1 \le h$ and $f_2 \le h$. This ability to always find an "envelope" function is crucial in many areas of analysis and approximation theory.

To truly appreciate the directedness property, it's illuminating to see where it fails. What does a non-directed set look like? It looks like a place with irreparable forks in the road.

Consider the non-zero integers, $\mathbb{Z} \setminus \{0\}$. Let's define a relation where $a \preceq b$ means $b$ is a positive integer multiple of $a$. This is a perfectly good preorder. Is it directed? Let's check. Take $a=2$ and $b=3$. Can we find an upper bound? Yes, their least common multiple, $c=6$, works. $6 = 3 \times 2$ and $6 = 2 \times 3$. But now, let's try a different pair: $a=1$ and $b=-1$. An upper bound $c$ would need to be a positive multiple of $1$, so $c$ must be positive. It would also need to be a positive multiple of $-1$, so $c$ must be negative. A number cannot be both positive and negative. There is no upper bound. The set is not directed. From the pair $(1, -1)$, the paths irreconcilably split.

Furthermore, directionality is not a symmetric concept. Just because a set is directed in one "direction" doesn't mean it is directed in the opposite one. Let's look at the set of all non-empty open intervals $(a,b)$ on the real line, ordered by set inclusion $\subseteq$. This set is directed. Given any two intervals, their union is contained within some larger interval, which serves as an upper bound. Now, what about the reverse order, $\supseteq$? For this to be directed, we'd need to be able to find a common lower bound for any pair of intervals. That is, for any two intervals, we need to find a third non-empty interval that is contained within both. Can we always do this? No. Consider the intervals $(0,1)$ and $(2,3)$. Their intersection is the empty set. There is no non-empty interval contained in both. So, while you can always go "up" (find a bigger interval), you can't always go "down" (find a common smaller one).

The concept of a preordered set, especially a directed one, is a beautiful piece of mental machinery. It gives us a language to describe order in a flexible way, to model processes of discovery, and to build the rigorous foundations for the idea of "approaching" a limit. It reveals a hidden unity, tying together logic, topology, analysis, and computer science through the simple, powerful idea of a guided path forward.

Now that we have acquainted ourselves with the formal rules of the game for preordered sets, we can embark on the most exciting part of our journey: seeing them in action. You might be tempted to think of preorders as a niche curiosity, a piece of abstract scaffolding for mathematicians. But nothing could be further from the truth. The simple, elegant idea of a set of points with a sense of direction—a reflexive and transitive relation—is one of the great unifying concepts in science. It is the language we use to describe processes that move forward, approximations that grow more precise, and knowledge that accumulates over time. Let’s explore a few of these remarkable appearances.

In our first encounter with mathematics, we learn about sequences. A list of numbers, $x_1, x_2, x_3, \dots$, "converges" to a limit $L$ if the terms get closer and closer to $L$ as we go further down the list. The "direction" is simple: the natural numbers $\mathbb{N}$ with their usual order "less than or equal to," $(\mathbb{N}, \le)$. This is a perfectly good preordered set, but it is deceptively simple. What if the path to a limit wasn't a single, straight line?

This is where topology provides a stunning generalization using ​​nets​​. A net is just like a sequence, but instead of marching along the integers, it can navigate any ​​directed set​​—a special kind of preordered set where any two points have a common "successor." This allows us to define convergence in a far more general and powerful way. A net converges to a point $x$ if, no matter how small a neighborhood you draw around $x$, the net will eventually enter that neighborhood and stay there forever.

Consider the sequence $x_n = \frac{(-1)^n}{n}$. It clearly converges to 0 in the standard way. But we can view the function $n \mapsto x_n$ as a net on a different directed set: the natural numbers ordered by divisibility, $(\mathbb{N}, |)$. Here, "moving forward" from an integer $d_0$ means moving to its multiples ($2d_0, 3d_0, \dots$). Does the net still converge to 0? Yes! If we want the terms to be smaller than some tiny $\varepsilon$, we can just pick a starting point $d_0 > 1/\varepsilon$. Any multiple of $d_0$ will be even larger, making its reciprocal even smaller. So, the net still converges to 0. The concept of convergence is robust enough to handle this strange new "direction."

This generalization is not just a clever trick; it’s the key that unlocks the deepest properties of topological spaces. Sequences are not powerful enough to describe the structure of all spaces, but nets are. Two of the most fundamental properties of a space are whether its points are cleanly separated (​​Hausdorff​​) and whether it is "self-contained" without any missing boundary points (​​compactness​​). Both can be expressed with breathtaking elegance using nets.

A space is Hausdorff if and only if every convergent net has a unique limit. In other words, in a well-behaved space, a path can't lead to two different destinations at once.

A space is compact if and only if every net within it has a "cluster point"—a point that it revisits infinitely often. This means no path can wander off forever and "fall off the edge" of the space. For example, the sequence $x_n = 1 - \frac{1}{n+1}$ in the open interval $(0, 1)$ gets closer and closer to 1, but 1 is not in the space. The net has no cluster point inside $(0, 1)$, which demonstrates that the space is not compact. The local behavior of a directed path reveals the global character of the space itself.

The power of preorders also appears in a place you might not expect: the heart of calculus. We all learn that the definite integral $\int_a^b f(x) dx$ is the area under a curve, calculated by slicing the area into thin rectangles and summing their areas. We usually imagine making the rectangles narrower and narrower by taking $n$ equal slices and letting $n \to \infty$.

But what if the slices aren't equal? What if we refine our measurement in a more complicated way? The truly robust definition of the Riemann integral relies on a preorder. Consider the set $\mathcal{P}$ of all possible partitions of the interval $[a, b]$. We can define a preorder on this set by ​​refinement​​: we say a partition $P_2$ is "at least as fine as" $P_1$, written $P_1 \le P_2$, if $P_2$ contains all the points of $P_1$ and possibly more. This set of all partitions, ordered by refinement, is a directed set.

The Riemann integral is the limit of the net of Riemann sums over this directed set. This means that for the integral to exist, the sum must converge to the same value no matter which path of successive refinements you take. Whether you make all your rectangles a little thinner, or just refine a few of them in a certain area, you are always "moving forward" in the directed set, and you will always approach the same limit. This preorder structure is what guarantees that the integral represents a single, well-defined "true value" of the area.

Perhaps the most profound application of preorders is in mathematical logic, where they provide the very scaffolding for models of knowledge and reasoning. In classical logic, a proposition is either true or false, once and for all. But in ​​intuitionistic logic​​, which is a logic of construction and verification, truth is something that is established over time. A proposition is "true" at a certain stage if we have constructed a proof for it. As we gather more information, more propositions may become true.

How can we model this growth of knowledge? With a ​​Kripke frame​​, which is nothing more than a set of "worlds" or "states of knowledge," equipped with a preorder $\le$. A relation $w_1 \le w_2$ means that the state of knowledge $w_2$ is an extension of $w_1$; we know everything we knew at $w_1$, and perhaps more.

This preorder structure dictates the very meaning of logical connectives. For a proposition to be considered true in a given state, its truth must persist. This is the ​​monotonicity property​​: if a statement $\varphi$ is true at world $w$, it must also be true at any "future" world $v$ where $w \le v$. This is enforced by requiring the set of worlds where a basic proposition is true to be an ​​up-set​​ in the preorder—if it contains a world, it must contain all worlds accessible from it.

The intuitionistic meaning of implication is particularly beautiful. The statement "$\varphi \to \psi$" is true at a world $w$ if and only if for all possible future states of knowledge $v$ (where $w \le v$), if $\varphi$ ever becomes established, then $\psi$ must also become established at that same future state. The implication is a guarantee that holds across all possible paths of future discovery, a concept made precise by the preorder.

The connection becomes even deeper. If we take a finite set of points and a preorder, the collection of all "up-sets" forms a special kind of topology known as an Alexandrov topology. Conversely, if we start with such a topology, we can define a "specialization preorder" on its points, recovering the original frame. This creates a stunning equivalence: the structure of logical models for growing knowledge is, in a very concrete sense, the same as the structure of a certain class of topological spaces. The preorder is the Rosetta Stone that translates between the two.

From the paths of convergence in topology, to the process of approximation in calculus, to the growth of knowledge in logic, the preorder provides the fundamental language of direction. It is a testament to the power of mathematics that such a simple and elegant structure can illuminate so many different corners of our intellectual world, revealing a deep and satisfying unity among them.