0
$\begingroup$

The question: Consider the poset that consists of the lexicographic ordering over the finite non-empty strings over the usual alphabet — a ≺ b ≺ c ≺ · · · ≺ z.

Please could explain if it is well-founded, or why it isn't. I am really confused to what makes a poset well-founded.

Any help would be much appreciated.

$\endgroup$
5

1 Answer 1

2
$\begingroup$

I'll first discuss well-foundedness, as that is where you say the confusion lies. Then I'll define what I would call lexicographical order before I will give a hint for your question.

Since your question does not explicitly define the order, I conclude with a related order that is also sometimes called lexicographical. If it is irrelevant to your question, it might still serve as a good exercise.

Well-foundedness

A poset $(P,\leq)$ is well-founded if any nonempty subset $A\subseteq P$ has a minimal element with respect to $\leq$.

That is, for any nonempty subset $A$, there is some element $a\in A$ such that for any $b\in A$ with $b\leq a$ we have that $b=a$.

For example, the natural numbers $\Bbb N=\{0,1,2,3,\dots\}$ are well-founded with their usual ordering, since for any nonempty set of natural numbers $A$ we can find the least natural number $a$ that is in $A$: simply take some arbitrary $n\in A$, then the only candidates for the least natural number are in the finite set $\{0,1,\dots,n\}$, so after checking them all, you will have found the minimal element.

On the other hand, the integers $\Bbb Z=\{\dots,-2,-1,0,1,2,\dots\}$ are not well-founded, since the set $\{-1,-2,-3,\dots\}$ has no least element. Another example is the interval $[0,1]$, since the set $X=\{\frac12,\frac13,\frac14,\dots\}$ has no least element (because for any $\frac1n\in X$ we have $\frac1n>\frac1{n+1}\in X$).

These last two examples give a hint to a good strategy for showing that a set is not well-founded: try to find an infinite decreasing sequence. Since it is infinite, for any element in the sequence, it has a next element that is smaller, so none of the elements in the sequence can be minimal. In fact, this strategy works both ways: if it is impossible to find an infinite decreasing sequence, then the order is well-founded.

Lexicographical order

Now let's look at lexicographical orderings.

If $s=s_1s_2\dots s_n$ and $t=t_1t_2\dots t_m$ are two finite strings in the alphabet $\tt a\prec\tt b\prec\dots\prec\tt z$ we define $s\leq t$ if and only if one of the following holds:

  • For some $i<n,m$ we have $s_1=t_1$, $s_2=t_2$, $\dots$, $s_i=t_i$ and $s_{i+1}\prec t_{i+1}$, or
  • $n\leq m$ and $s=t_1t_2\dots t_n$.

The first bullet says that $s\leq t$ when the first $i$ letters are equal, and the letter at $i+1$ in $s$ is smaller than the letter at $i+1$ in $t$. The second bullet says that if $s$ is equal to an initial part of $t$, then $s\leq t$.

For example $\tt{alpha}\leq\tt{alphabet}$ because of the second bullet point, and $\tt{algebra}\leq\tt{alpha}$ because of the first bullet point.

[One interesting thing about lexicographical orderings, is that if the underlying alphabet is totally ordered, then the lexicographical ordering of the strings will also be total. So we see that in fact the lexicographical ordering on the example you describe is not just a partial order, it is a total order.]

Hint for your question

Now how do we show whether this lexicographical ordering is well-founded? We try to find an infinite decreasing sequence. It shouldn't be too difficult to find one, but I'll give one hint:

  • Not all of the strings in the sequence can be smaller than a given length $n$, since there are only finitely many strings of length less than $n$.

Shortlex order

There is another common way to define an order on the set of finite strings that is also sometimes called the lexicographical order, but I'll call it by its usual name, the shortlex order:

If $s=s_1s_2\dots s_n$ and $t=t_1t_2\dots t_m$ are two finite strings in the alphabet $\tt a\prec\tt b\prec\dots\prec\tt z$ we define $s\leq t$ if and only if one of the following holds:

  • $n<m$ or
  • $n=m$ and there is some $i<n$ such that $s_1=t_1$, $s_2=t_2$,$\dots$,$s_i=t_i$ and $s_{i+1}\prec t_{i+1}$, or
  • $s=t$.

In this variant the length of the string has precedence over the alphabetical ordering of the string, and if strings have the same length it coincides with the lexicographical order from above. This is different than what is used in dictionaries, but a very useful ordering, because this ordering is in fact well-founded (why?)!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .