1
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.