Is there a sequence of strings where there is always an element between any two other elements?

Question

Can I define a way of sorting strings such that for any two strings X and Z, I can find another one Y such that X < Y < Z ?

This is clearly not the case for alphanumeric sorting: there is no string between "4a" and "4a0".

But it's not obvious to me whether there might be a sequence definition that takes advantage of the fact that strings can be infinitely long, where you could always find a string between two others.

I haven't been able to do so, but I lack the formal understanding to be able to decide whether this is fundamentally not possible.

Answer 1

Yes, just construct a bijection between the set of strings and and the set of rational numbers. Then pull back the order on $\mathbb Q$ on the strings.

You probably don't need a bijection on $\mathbb Q$, you just need a function $f: S \to \mathbb R$ which has dense image.

For example think about each character being a number starting at 0. Thus, any strong becomes $a_1.. a_n$ where each $a_i \in \{ 0, 1, 2, ..,35 \}$.

Now define $f(a_1.. a_n)=2^{a_1}3^{-a_2}5^{a_3} ... p_n^{(-1)^{n+1}a_n}$ where $p_n$ is the $n$ th prime number.

Define $a_1.. a_n < b_1...b_k$ if and only if $f(a_1..a_n) < f(b_1...b_k)$.

Answer 2

To address this question we first need to have a precise definition of what a "string" is.

The usual formalization is that we have an "alphabet" containing some finite number of symbols. The "alphabet" is not necessarily just letters of a language; for example, you could have an alphabet of $36$ symbols ($26$ letters and $10$ numeric digits) or an alphabet of $1000$ symbols. A "string" is a sequence of these symbols, possibly with repetition. A "string" can be as long as we want, so given any string there is always a longer one. We could include strings of infinite length in our model, but (at least for now) let's consider only strings of finite length.

Now observe that if you take the alphabet consisting of the ten decimal digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9, make strings over this alphabet, and then write a decimal point before the first symbol of each of these strings, we have all the terminating decimal fractions in the interval $[0,1).$

Now, if this set were strictly ordered by numeric value, we'd be almost done. Unfortunately, these terminating decimal fractions include many that end with one or more zeros, and these are numerically equal to decimals with fewer digits.

So for any terminating decimal with trailing zeros, count the number of trailing zeros and write that number before the decimal point. For example, in this way the string "123000" corresponds to the number $3.123.$ Use this as a rule to define a mapping $f$ from strings over the decimal digits to rational numbers. Every string over this alphabet is mapped to a unique number (different from any other string). Now if $X$ and $Y$ are any two strings over this alphabet, say that $X < Y$ if $f(X) < f(Y).$

Now observe that any decimal number $x$ with a finite number of digits is equal to $f(X)$ for some string $X$ of decimal digits; specifically, $X$ consists of all the digits of $x$ after the decimal point (excluding any trailing zeros), followed by $\lfloor x \rfloor$ zeros.

Between any two terminating decimal numbers there is another terminating decimal number. Therefore, for any strings $X$ and $Z$ such that $X < Z,$ there is a terminating decimal number $y$ such that $f(X) < y < f(Z).$ Construct the string $Y$ such that $f(Y) = y,$ and we have $X < Y < Z.$

Any other alphabet can be handled in a similar way. For an alphabet of $N$ symbols, give each symbol a unique value in the range $0$ to $N-1,$ and define the ordering of strings as we did for the ten decimal digits, but using a base-$N$ representation instead of base $10$ if $N \neq 10.$

There are some slight complications if we allow infinitely long strings.

By the way, what if we don't explicitly stipulate that our alphabet has a finite number of symbols? Finite alphabets are the norm for theory-of-computing exercises (or at least they were when I studied that field), and this makes sense if we imagine that each symbol must be written in a fixed number of bits of memory in a computer, such as $8$-bit ANSI strings. But there are encodings that allow different "characters" to be encoded in different numbers of bits; for example, Unicode has several $8$-bit characters, then a larger number of $16$-bit characters, and $24$-bit characters as well. We could define an "infinitely-extended Unicode" encoding that repeated this pattern to simply increase the size of the next group of characters by $8$ bits, indefinitely. And we could then define the order of the characters of this alphabet so that there is always an $8n+8$-bit character that comes lexically before any character of $8n$ or fewer bits. Using such an alphabet, there would be a string that comes lexically between "4a" and "4a0", and other strings that come lexically between any two other strings we might choose as counterexamples.

But infinite strings and infinite alphabets are a digression. Finite strings over finite alphabets are interesting enough for the purpose of this question.

Answer 3

Yes - very easily too. For simplicity, assume we only have the letters $0$ and $1$ (but any number of letters will work just fine - it'll just be a different base system). We could interpret any string as a number, in base $2$ between $0$ and $1$ - like, the string "0110" becomes the number $.0110_2=\frac{3}{8}$. However, we have an issue with trailing zeros, since the strings "011" and "0110" and "01100" would all be considered equal. To remedy this, we can divide strings into various distinct classes, based on how many zeros they have and, if strings belong to different classes, we use the following rule:

• If string $A$ has more trailing zeros than string $B$, let $A>B$. (e.g. "0100" > "10" since the first has two trailing zeros. Similarly, "0100" > "010" - which avoids the fact that $.0100_2=.010_2$)

Then, we need to define the order within each class. Naively, we would just compare binary representations, with a decimal point at the start. However, this would mean that $1$ is the greatest binary representation obtainable in each class, and $0$ is the least (as pointed out in a comment) - which is a problem, since then our order has adjacent elements (e.g. the $1$ of a given class and the $0$ of the next greater class). Thus, we consider that a string $A$ should be associated with the the bit string in binary, with the decimal place before the first $0$ - so "11001" becomes $11.001_2$, for instance. Then, if $A$ has a greater associated number than $B$, we say $A>B$. There can be no maximum element in each class, since $A$ is always less than $A$ with a "1" prepended.

Then, we can easily construct a string between any $A$ and $B$. In particular, suppose $A>B$ and $A$ has more trailing zeros. Then $B$ with a "1" prepended is greater than $B$ and less than $A$. If they have equally many trailing zeros, we just choose some binary number (with integer part $2^{k}-1$ for some $k$ - numbers like $10_2$ aren't representable) between them and write it with equally many trailing zeros.

Answer 4

For finite strings, the lexicographic order will do if you tinker with it a bit so that one (or more) of the letters of the alphabet sorts before the empty string.

In more detail, say you have a two-letter alphabet $\Sigma=\{+,-\}$. Given two different strings $X,Y\in\Sigma^{<\omega}$, where without loss of generality $Y$ is not an initial substring of $X$ (otherwise we can swap them): if $a$ is the first letter of $Y$ following the largest common initial substring of $X$ and $Y$, put $X<Y$ if $a=+$, and $X>Y$ if $a=-$.

This gives a dense linear order: given $X<Z$, we have $X<X+<Z$ or $X<Z-<Z$.

In the case of a general alphabet $\Sigma$ with a fixed order $\prec$ on the letters $a\in\Sigma$, split the alphabet in two disjoint nonempty sets $\Sigma=\Sigma^-\cup\Sigma^+$ so that $\Sigma^+$ is closed upwards in $\prec$, and put \begin{align*} XaY&<XbZ&&\text{if }a\prec b,\\ X&<XaY&&\text{if }a\in\Sigma^+,\\ XaY&<X&&\text{if }a\in\Sigma^- \end{align*} for all strings $X,Y,Z$ and letters $a,b$. Note that the only difference from the standard lexicographic order is in the third clause.

Another way to view it is that you consider finite strings as extended on the right-hand side to infinite strings using a special symbol $\epsilon\notin\Sigma$, and you order them according to the lexicographic order of the infinite extensions, with respect to some ordering $\prec$ of $\Sigma\cup\{\epsilon\}$. If you make $\epsilon$ smaller than all actual letters $a\in\Sigma$, you get the usual lexicographic order on finite strings, whereas if there are $a,b\in\Sigma$ such that $a\prec\epsilon\prec b$, you get a dense order.