Dictionary Order and Lexicographic Intervals

Ordering Points by Their Coordinates

On the real plane, a point is an ordered pair, but the usual coordinate-by-coordinate comparison does not give a total order: for example, neither \((1,4)\) nor \((2,3)\) is smaller in both coordinates. The dictionary order compares first coordinates first and uses second coordinates only when the first coordinates agree. Its order topology has intervals whose shapes depend on whether their endpoints lie on the same vertical line.

Throughout, \(\mathbb{R}\) has its standard topology, but the topology on \(\mathbb{R}^2\) in this tutorial is the order topology for the dictionary order, not a topology specified by the usual coordinate geometry.

Because the first coordinates are totally ordered, this comparison places any two distinct points in exactly one order: if their first coordinates differ, the smaller first coordinate determines the smaller point; if they agree, compare their second coordinates. In particular, a point with first coordinate \(a\) is below every point with first coordinate \(c\) whenever \(a<c\), regardless of the second coordinates.

There are no first or last points in this order. Given \((a,b)\), the points \((a,b-1)\) and \((a,b+1)\) lie below and above it, respectively. Thus the open intervals form a basis for the order topology; no endpoint rays are needed to supply neighborhoods.

Intervals with Equal or Different First Coordinates

Proof. First suppose \(a=c\). Since \(p<_{\mathrm{lex}}q\), we have \(b<d\). A point \((x,y)\) strictly between \(p\) and \(q\) cannot have \(x<a\), because it would be below \(p\), or \(x>a\), because it would be above \(q\). It must have \(x=a\), and then the two strict comparisons are exactly \(b<y<d\). This proves the first formula in both directions.

Now suppose \(a<c\). If \(a<x<c\), then \(p<_{\mathrm{lex}}(x,y)<_{\mathrm{lex}}q\) for every real \(y\): the first comparison follows from \(a<x\), and the second from \(x<c\). If \(x=a\), the point is above \(p\) exactly when \(y>b\), and it is automatically below \(q\) because \(a<c\). If \(x=c\), it is below \(q\) exactly when \(y<d\), and it is automatically above \(p\). For \(x<a\) the point lies below \(p\), and for \(x>c\) it lies above \(q\). These cases exhaust all first coordinates, giving precisely the stated union. \(\square\)

The formulas show why endpoints with different first coordinates produce a wider interval: every point on every intermediate vertical line is included. At the endpoint lines, only the appropriate upward or downward part is included. If the first coordinates agree, the interval stays on that one vertical line.

Including endpoints gives the corresponding closed-interval descriptions. For \(a=c\), \([p,q]=\{a\}\times[b,d]\). For \(a<c\), \([p,q]=(\{a\}\times[b,\infty))\cup((a,c)\times\mathbb{R})\cup(\{c\}\times(-\infty,d])\). The closed interval consists of the open interval together with its two endpoints, which gives these formulas. Half-open intervals are obtained by including just the endpoint indicated by the bracket: for example, when \(a<c\), \([p,q)= (\{a\}\times[b,\infty))\cup((a,c)\times\mathbb{R})\cup(\{c\}\times(-\infty,d))\).

Basic Neighborhoods in the Lexicographic Plane

Proof. Let \(U\) be an open neighborhood of \(x\). By the interval basis for the order topology, there are \(r=(r_1,r_2)\) and \(s=(s_1,s_2)\) with \(r<_{\mathrm{lex}}x<_{\mathrm{lex}}s\) and \(x\in(r,s)\subseteq U\). We choose \(\varepsilon>0\) so that every \((a,t)\) with \(b-\varepsilon<t<b+\varepsilon\) remains above \(r\) and below \(s\).

If \(r_1<a\), every point with first coordinate \(a\) is above \(r\), so the lower comparison imposes no restriction on \(\varepsilon\). If \(r_1=a\), then \(r_2<b\); it suffices to require \(\varepsilon\le (b-r_2)/2\), which is positive. Similarly, if \(s_1>a\), every point with first coordinate \(a\) is below \(s\); if \(s_1=a\), then \(b<s_2\), and it suffices to require \(\varepsilon\le (s_2-b)/2\). Choose \(\varepsilon\) to be the minimum of \(1\) and whichever positive bounds apply. Then \(r<_{\mathrm{lex}}(a,t)<_{\mathrm{lex}}s\) whenever \(b-\varepsilon<t<b+\varepsilon\). The vertical interval is contained in \((r,s)\), hence in \(U\). \(\square\)

Conversely, each such vertical interval is itself open: it is the order interval \(((a,b-\varepsilon),(a,b+\varepsilon))\). The theorem therefore says that these vertical intervals give a local base: every neighborhood contains one of them. This statement describes a useful way to find small neighborhoods without having to work with arbitrary endpoints.

A Common Mistake

Pitfall: When the first coordinates differ, it is incorrect to require the second coordinate to lie between the endpoint second coordinates. For the interval from \((1,2)\) to \((4,-1)\), such a rule would reject \((2,-100)\), since \(-100\) is not between \(-1\) and \(2\). But the calculation \(1<2<4\) puts \((2,-100)\) in the middle part of the lexicographic interval, so it belongs. The second coordinate matters only on the endpoint vertical lines; at intermediate first coordinates, every second coordinate is allowed.

A reliable membership calculation is to compare points in order: first compare first coordinates; compare second coordinates only when the first coordinates tie. The same rule then determines which pieces of an interval are included and which boundary comparisons are strict.