Let A be a totally ordered alphabet. Let L the lexicographic ordering on A*

Question

Let A be a totally ordered alphabet. Let L the lexicographic ordering on A*, and S the standard ordering on A*

A / L is well-founded and S is well-founded

B/ L is not well-founded and S is well-founded

C/ L is well-founded and S is not well-founded

D/ L is not well-founded and S is not well-founded

Is B the correct answer? If it is, can anyone please explain why?

Thank You

a binary relation, R, is well-founded (or wellfounded) on a class X if and only if every non-empty subset S ⊆ X has a minimal element. This is the one I copied online. — pkim, Feb 27 '17 at 00:07
Could you create a situation that a subset of L can not have a minimal element? — Q the Platypus, Feb 27 '17 at 00:08
this is one of exam questions that I had, and it was unclear to me as well ( — pkim, Feb 27 '17 at 00:45

score 2 · Answer 1 · answered Feb 27 '17 at 00:33

It is unclear what you mean by standard order as opposed to lexicograpical order. I would have assumed the standard order on an alphabet was the lex-order. Presumably your standard order checks if one word is a prefix of another. That means standard order on the Latin alphabet works like sad $<$ saddle $<$ saddlebag $<$ saddlebags.

It's easy to see this is well-ordered because a descending chain has to decrease word length each step. So all descending chains are finite.

To see the lex-order is not well-founded consider the following infinite descending chain: $AC > ABC > ABBC > ABBBC > \ldots$. The set of all elements $AB \ldots B C$ has no minimal element.

Standard order is also called numerical order. Shorter strings sort before longer strings "0 < 00 < 01 < 10 < 11 < 000" — Q the Platypus, Feb 27 '17 at 01:15

Let A be a totally ordered alphabet. Let L the lexicographic ordering on A*

1 Answers1