Question

Show that the set of strings of lowercase English letters with lexigraphic order is neither well-founded nor dense.

Short answer

Hence, the set of strings of lowercase English letters with lexigraphic order is neither well-founded nor dense is proved.

Step-by-step solution

Given data

The set is a stings of lowercase English letters.

Concept used of poset

A relation\(R\)is a poset if and only if,\((x,x)\)is in\({\rm{R}}\)for all x (reflexivity)

\((x,y)\)and\((y,x)\)in R implies\(x = y\)(anti-symmetry),\((x,y)\)and\((y,z)\)in R implies\((x,z)\)is in\({\rm{R}}\)(transitivity).

Prove for dense set of strings

A poset\((R, < )\) is well founded if there is no infinite decreasing sequence of elements in the poset, that is elements \({x_1},{x_2}, \ldots \ldots \ldots ..,{x_n}\) such that \( \prec {x_n} \prec \ldots .{x_2} \prec {x_1}\). A poset\((R, \prec )\) is dense if for all \(x \in R\) and \(y \in R\) with \(x \prec y\) there is an element \(z \in R\) such that \(x < z < y\).Let us consider on some strings of lowercase English letters with lexicographic ordering.Suppose the chain is like this \(, < ccccd \prec cccd \prec ccd \prec cd\) .This chain of lowercase English letters is in lexicographic ordering, it is finite and decreasing, so the poset is not well founded. Neither it is dense because there are no strings between \(c\) and c c. Hence, the set of strings of lowercase English letters with lexigraphic order is neither well-founded nor dense is proved.