Lexicographical Order

"Lexicographical order" is just a formal name for an idea we use every day: looking up a word in a dictionary. We instinctively understand that 'apple' comes before 'apply' because we compare them letter by letter. This fundamental principle brings order to our contacts, files, and libraries. But what happens when we take this simple, everyday concept and apply it to more abstract domains? What if we organize not words, but points on a plane, or infinite sets of mathematical objects? This is where the familiar becomes fascinatingly strange.

This article delves into the profound consequences of this simple ordering rule, showing how it bridges the gap between intuitive organization and complex mathematical theory. We will uncover how "dictionary order" can be used to construct a bizarre new type of geometry and serve as a powerful tool in modern computation.

First, we will explore the ​​Principles and Mechanisms​​ of lexicographical order, defining it formally and using it to build the "ordered square"—a topological space with bizarre properties that challenge our geometric intuition. Then, in ​​Applications and Interdisciplinary Connections​​, we will see how this principle becomes a workhorse in computer science, powering everything from search algorithms to data compression, and we will also examine its critical limitations.

Imagine you are organizing a library. Not by subject, not by author, but purely by the title of the books, as if you were creating a giant dictionary. "Aardvark's Adventures" comes before "Apple Pie," which comes before "Banana." This simple, intuitive process you use every time you look up a word is the heart of what mathematicians call ​​lexicographical order​​. It’s a way of extending the order we know for letters of the alphabet to entire words, and as we shall see, to a vast universe of other mathematical objects.

Let's play a little game. Suppose we have a set of numbers: $\{1, 2, 10, 11, 20\}$. How would you arrange them using dictionary order? It's not about their value as numbers, but their "shape" as strings of characters.

• "1" comes before "10" and "11" because "1" is a prefix of both longer strings.
• "10" comes before "11" because they match on the first character ('1'), but the second character '0' comes before '1'.
• Now for the surprise: "11" comes before "2"! Why? Because when we compare "11" and "2", we look at the very first character. Since '1' comes before '2' in our character list, "11" is "smaller."
• Following this logic, the complete ordering is: $1 \prec 10 \prec 11 \prec 2 \prec 20$.

This simple example reveals the first key principle: lexicographical order can behave very differently from the usual numerical order we are accustomed to. Yet, it possesses a crucial property: it is a ​​total order​​. For any two distinct items, we can always definitively say which one comes first. There are no ambiguities. This property allows us to arrange not just numbers as strings, but pairs of numbers, coordinates in a plane, or even tasks in a computer program. For instance, in a task scheduling system where tasks are indexed by pairs of natural numbers $(m, n)$, the lexicographical rule—find the task with the smallest $m$, and if there's a tie, pick the one with the smallest $n$—provides a clear, unambiguous way to prioritize every single task. This turns out to be a ​​well-ordering​​ on $\mathbb{N} \times \mathbb{N}$, meaning any collection of tasks always has a "first" one to be processed, which is a profoundly useful guarantee in computer science and logic.

Now, here is where things get truly interesting. Physicists and mathematicians have learned that a rule for ordering things can be used to define a notion of "space" and "nearness"—a ​​topology​​. The basic idea is wonderfully simple: an "open set," the fundamental building block of a topology, can be thought of as an "open interval." For the real number line, an open interval $(a, b)$ is just all the numbers strictly between $a$ and $b$.

What happens if we apply this idea to the lexicographical order on a plane, like the unit square $[0,1] \times [0,1]$? We get the ​​lexicographic order topology​​, a space often called the "ordered square." It is a plane, but it doesn't behave at all like the flat, familiar Euclidean plane we learn about in school.

Let's compare. In the standard ​​product topology​​ on the plane, the basic open sets are "open rectangles" $(a,b) \times (c,d)$. A neighborhood of a point is like a little box drawn around it. If you're at a point, you can move a tiny bit in any direction—left, right, up, or down—and still be inside your neighborhood.

Not so in the lexicographically ordered plane! Let's examine a neighborhood of a point, say $p = (1/2, 1)$, which sits at the very top of the vertical line at $x=1/2$. A basic open neighborhood of $p$ is an "interval" $(a, b)$ where $a \prec p \prec b$.

• To get a point $a$ just before $p$, we could pick a point on the same vertical line but slightly lower, like $a = (1/2, 1-\epsilon)$.
• To get a point $b$ just after $p$, we must move to a larger first coordinate, for instance, $b = (1/2+\epsilon, 0)$.

What does the interval $(a, b)$ actually look like? It contains all points $(x,y)$ such that $(1/2, 1-\epsilon) \prec (x,y) \prec (1/2+\epsilon, 0)$. This works out to be:

1. The small vertical segment above $a$: $\{1/2\} \times (1-\epsilon, 1]$.
2. All the points in the vertical strips between $x=1/2$ and $x=1/2+\epsilon$: $(1/2, 1/2+\epsilon) \times [0,1]$.

Think about what this means. A neighborhood of $(1/2, 1)$ isn't a tidy little box. It's a small piece of the vertical line at $x=1/2$, plus a whole collection of complete vertical lines to its immediate right! This structure is fundamentally different. In fact, any vertical line segment, like $\{x_0\} \times (c,d)$, is itself an open set in this topology. It can be written as the "interval" between $(x_0, c)$ and $(x_0, d)$. In the standard product topology, a vertical line segment is certainly not open; you can't draw a little open box around any of its points that stays within the line. This is the crucial distinction: the lexicographic topology has more open sets than the product topology, making it a ​​finer​​ topology.

This idea extends to other sets too. On $\mathbb{Z} \times \mathbb{R}$, an "open interval" from, say, $(0, 1)$ to $(2, -1)$ consists of the top part of the line at $x=0$, the entire line at $x=1$, and the bottom part of the line at $x=2$. The space is like a series of vertical threads, and open sets can span across them in this very particular, directional way.

This peculiar structure of open sets leads to some mind-bending consequences that challenge our intuition about space.

A Space That's Connected, But You Can't Walk Across

Let's return to the ordered square, $[0,1] \times [0,1]$. Is it ​​connected​​? In topology, this means you can't break it into two separate, non-empty open pieces. The ordered square is indeed connected. It forms a "linear continuum"; there are no gaps in the order, much like the real number line. You can't slice it cleanly into two open parts.

But is it ​​path-connected​​? Can you draw a continuous path, like a pencil line, from any point to any other point? Let's try to draw a path from a point on the left side, say $(0.2, 0.5)$, to a point on the right, say $(0.8, 0.5)$. Our intuition screams "yes," just draw a straight line! But that intuition is from the standard topology.

In the lexicographic topology, the answer is a resounding ​​no​​. No continuous path can connect two points with different x-coordinates. The argument is as beautiful as it is profound. A continuous path would form a compact and connected set. Because the space is ordered, this means the path must contain the entire lexicographical "interval" between its start and end points. This interval, however, contains a vertical open segment $\{x\} \times (0,1)$ for every single real number $x$ between the start and end x-coordinates. That's an uncountable collection of disjoint, non-empty open sets. But a continuous image of the nice, simple interval $[0,1]$ (our path's domain) cannot contain such a thing. It's a fundamental mismatch of "topological size." It's as if to get from one vertical line to another, you'd have to jump over an uncountably infinite number of open chasms simultaneously, which no continuous path can do. The space is one whole piece, but its internal structure forbids movement across its vertical fibers.

Uncountably Many Rooms, Not Enough Guests

This theme of uncountably many vertical slices appears again when we ask if the space is ​​separable​​. A space is separable if it has a countable "skeleton" of points that is dense, meaning it gets arbitrarily close to every point in the space. The familiar plane $\mathbb{R}^2$ is separable; the set of points with rational coordinates, $\mathbb{Q} \times \mathbb{Q}$, is a countable dense skeleton.

Now consider the space $\mathbb{R} \times \mathbb{Q}$ with the lexicographic topology. For each real number $x$, the vertical line segment $\{x\} \times (q_1, q_2)$ is an open set. This gives us an uncountable family of disjoint open sets—one for each real number $x$. Now, imagine you have a countable set of points, $D$, that you hope is dense. Since $D$ is countable, the set of x-coordinates of its points is also countable. This means there must be some real number $x_0$ that is not an x-coordinate for any point in $D$. But then the open set $\{x_0\} \times (q_1, q_2)$ contains no points from $D$ at all! So $D$ cannot be dense. The space has uncountably many disjoint "open rooms," and any countable collection of "guests" is bound to leave most of them empty. The space is not separable.

From the simple act of ordering words in a a dictionary, we have journeyed into a strange and wonderful world. We have constructed a space that feels like a plane but is built of vertical threads, a space that is a single connected whole but which you cannot traverse, a space filled with so many open rooms that no countable set can ever visit them all. Lexicographical order, it turns out, is not just a tool for organization; it is a key that unlocks a gallery of some of topology's most beautiful and counter-intuitive treasures.

"Lexicographical order" is just a fancy name for what we do when we look up a word in a dictionary. We understand that 'apple' comes before 'apply' because, after the common prefix 'appl', the next letter 'e' comes before 'y' in the alphabet. Simple enough. We use this principle to organize our contacts, our computer files, and our libraries. It's a fundamental, almost invisible, tool for bringing order to the chaos of information.

But what happens when we take this simple, everyday idea and apply it to more exotic domains? What if we try to organize not words, but points on a geometric plane? Or the infinite set of all possible mathematical polynomials? The journey into these questions reveals that this humble ordering principle is a thread that weaves through the very fabric of mathematics and computer science, sometimes creating beautiful and familiar patterns, and other times, giving rise to wonderfully strange and counter-intuitive new worlds.

Let's imagine the unit square, the set of all points $(x, y)$ where both coordinates are between 0 and 1, written as $[0,1] \times [0,1]$. We are used to thinking about this space with our familiar Euclidean notion of distance. But let's throw that away and install a new set of rules based on dictionary order. We will say that a point $(x_1, y_1)$ comes "before" a point $(x_2, y_2)$ if $x_1 x_2$, or, if they have the same first coordinate ($x_1 = x_2$), if $y_1 y_2$.

You can think of the square as an infinitely thick book. The $x$-coordinate tells you the page number, and the $y$-coordinate tells you your position on that page. To get from a point on page 0.3 to a point on page 0.4, you must first traverse the entirety of the rest of page 0.3, no matter how "close" the $y$-coordinates might seem.

This simple change has profound consequences for our geometric intuition. Consider the projection maps that take a point $(x,y)$ and return either its $x$ or $y$ coordinate. Projecting onto the $x$-axis, defined by the map $\pi_1(x, y) = x$, feels natural. Points that are close in our new lexicographic sense cannot have wildly different $x$-coordinates (unless one is at the very end of a "page" and the other is at the beginning of the next), so this projection is continuous. But what about projecting onto the $y$-axis, $\pi_2(x, y) = y$? Here, our intuition breaks down completely. Take the points $(0.5, 0.9)$ and $(0.500001, 0.1)$. The second point has a much smaller $y$-value, but it comes after the first in the lexicographic order because its "page number"—its $x$-coordinate—is slightly larger. These two points can be arbitrarily "far apart" in the lexicographic topology, even if their $y$-values are nearly identical. The result is that the projection onto the $y$-axis is not continuous; it tears the space apart in a way our Euclidean minds find jarring.

The weirdness doesn't stop there. What about a simple line, say, the main diagonal where $y=x$? In a standard drawing, it's the very definition of a single, connected object. But in the lexicographic square, it shatters. Consider a point on the diagonal, like $(0.5, 0.5)$. We can create an "open neighborhood" around it that consists only of points with the same $x$-coordinate, for example, all points $(0.5, y)$ where $y$ is between $0.49$ and $0.51$. This neighborhood, a tiny vertical sliver of the square, contains no other point from the diagonal! This means every point on the diagonal is isolated from every other. The connected line has been pulverized into a discrete dust of points. The same fate befalls other familiar curves, like a parabola; they become ghostly skeletons with no "interior" substance whatsoever, because no piece of the curve is thick enough to contain one of these vertically-oriented open sets.

Lest you think this topology is pure chaos, it does have a discernible structure. It's an uncountable number of vertical lines, copies of the interval $[0,1]$, stacked side-by-side. Within each vertical line, where the $x$-coordinate is fixed, the topology behaves just like the normal topology on a line segment. Limit points behave as you'd expect within their vertical fiber. If we simplify the space to a discrete set of such lines, say by taking integers for the first coordinate (giving the space $\mathbb{Z} \times \mathbb{R}$), the structure becomes even clearer. The space becomes a collection of disjoint real lines, each one being an open set. This kind of space is actually quite well-behaved; it's a "topological sum" of familiar pieces and is even metrizable, meaning we can define a consistent notion of distance on it. This framework is so powerful it even allows us to analyze the properties of bizarre sets like the product of a Cantor set and a two-point space, revealing them to be compact but, unsurprisingly, utterly disconnected.

Let's leave the mind-bending world of topology and see how this ordering principle becomes a workhorse in the more concrete realm of computer science. Here, lexicographical order isn't used to redefine space, but to systematically navigate it.

One of the most fundamental strategies in logic and computer science is the exhaustive search. If you want to find a counterexample to a claim, or the solution to a puzzle, the most straightforward (if brutish) way is to list every single possibility in a fixed order and check them one by one until you find what you're looking for. Lexicographical order is the perfect tool for this. It gives us a canonical way to "count through" sets of strings or sequences. This principle is so fundamental that it appears in the deepest results of theoretical computer science, such as proofs about the limits of computation. When trying to determine if two complex systems are equivalent, a key theoretical approach involves searching for the lexicographically smallest string that is produced by one system but not the other. This ordered search provides a constructive path through an otherwise impossibly vast search space.

This isn't just a theoretical curiosity. It's at the heart of very practical technology. Have you ever used a program like [bzip2](/sciencepedia/feynman/keyword/bzip2) to compress a file? You've used an algorithm that relies critically on lexicographical ordering. The Burrows-Wheeler Transform (BWT) is a clever preprocessing step that makes text highly compressible by grouping similar characters together. How does it do this? It takes your input text, creates every possible cyclic shift of it, and then—you guessed it—sorts these shifts lexicographically. The final output of the transform is simply the last character of each string in this sorted list. This scrambling and sorting might seem random, but it has the remarkable property of clustering identical characters, which is exactly what subsequent compression stages need to work efficiently. A simple dictionary sort is a key step in a sophisticated data compression algorithm.

Given its power to organize, one might be tempted to think that lexicographical order can solve all our ordering problems. Specifically, we might ask: does this order guarantee that any collection of items will have a "smallest" or "first" element? A set with this property is called "well-ordered," and it's an incredibly useful property to have (the natural numbers $\mathbb{N} = \{0, 1, 2, \dots\}$ are the classic example).

Let's test this. Consider the set of all polynomials with integer coefficients, like $5x^3 - 2x + 1$. We can define a lexicographical order on them, for instance, by comparing the coefficients of the highest power where they differ. This gives us a perfectly valid total ordering. But is it a well-ordering? Let's look at a very simple subset of these polynomials: the constant polynomials that are negative integers, $S = \{-1, -2, -3, \dots\}$. Is there a "least" element in this set? No. For any element $-n$ you pick, the element $-(n+1)$ is also in the set and is smaller. The set has no bottom. Therefore, this lexicographically ordered set of polynomials is not well-ordered. This teaches us a crucial lesson: the properties of a lexicographically ordered set depend critically on the properties of the underlying "alphabet" it is built from. Because the integers $\mathbb{Z}$ are not well-ordered from below, this property does not magically appear when we use them as coefficients in polynomials.

From organizing a dictionary to revealing the bizarre geometry of the lexicographic square, from powering data compression to probing the limits of computation, this one simple idea—arranging things as if they were words—demonstrates a remarkable versatility. It is a fundamental tool for imposing structure, a concept at the heart of all mathematics. It shows us that by taking a familiar idea and pushing it into unfamiliar territory, we can generate new insights, uncover hidden connections, and sometimes, create worlds that delightfully defy our everyday intuition.