unclear why subset of a lexicographic ordered set of strings is said NOT to have a least element.

Question

I am watching an excellent series on Discrete Mathematical Structures from IIT

At the 47:33 mark of the video the instructor constructs a set of strings as

S = {a^nb | n >= 0 }

That is.. any number of a's followed by a 'b'.

The instructor gives a subset of all the possible generated strings:

aab
ab
b

Then the instructor says there is no least element in the above set. But it seems clear to me (given the definitions that I reproduced in 'Background', below) that 'aab' is the lexicographically least element. It comes before 'ab' and 'b'.

Am I missing something here ?

Note - I understand why the set as a whole is not well ordered. There are subsets like the set of all strings of S longer than 10 characters which have no least element (since a's can repeat forever). However for the subset given above, I think a least element is clearly there. (But I've been known to be wrong in the past.. so I suspect I've misunderstood).

Background

Earlier in the video, the following definitions are stated:

Let $\langle A, \le \rangle$ be a poset and $B$ be a subset of $A$. Then an element $b$ of $B$ is a least element of $B$ if for every element $b'$ (where $b'$ is an element of $B$) : $b \le b'$.

A binary relation $R$ on $A$ is well ordered if $R$ is a linear order and every non-empty subset of $A$ has a least element.

Thanks in advance for your help

• chris

Answer 1

It seems that the instructor was explaining that the entire set does not have a least element. You are correct in saying that the subset above has a least element: aab. But because we can always construct an element smaller than that in the set (it's not in the subset though), the entire infinite set does not have a least element.

Answer 2

This set must refer to $S$, not to the subset of 3 that he just gave. Any finite linearly ordered set has a minimum, as the instructor probably well knows.

So the set of strings over the alphabet $\{a,b\}$ is not a well-order, because there is a subset of those strings, namely $S$, that has no least element.

He just gave a few examples of strings that are in $S$, to give more of an idea of it, I think.