243 views

A set $S$ together with partial order $\ll$ is called a well order if it has no infinite descending chains, i.e. there is no infinite sequence $x_1, x_2,\ldots$ of elements from $S$ such that $x_{i+1} \ll x_i$ and $x_{i+1} \neq x_i$ for all $i$.

Consider the set of all words (finite sequence of letters $a - z$), denoted by $W$, in dictionary order.

1. Between $aa"$ and $az"$ there are only $24$ words.
2. Between $aa"$ and $az"$ there are only $2^{24}$ words.
3. $W$ is not a partial order.
4. $W$ is a partial order but not a well order.
5. $W$ is a well order.

Minimal Element is 'a', it is less than all elements !

a) False, after aa, we can have ab. Then aba,abb,abc.. Not limited to 24

b) False. after aa, we can have ab,aba,abc.. In fact ab(a-z)*. Not limited to 224

C)False. Why not partial order ? Dictionary order  is partial order ! It is Reflexive, Antysymmetric & Transitive.  Even defination of wikipedia says it is  !

D) False.Dictionary order is well order .

Defination of Dictionary order -> Ref -> https://en.wikipedia.org/wiki/Lexicographical_order

Given two partially ordered sets A and B, the lexicographical order on the Cartesian product A × B is defined as

(a,b) ≤ (a′,b′) if and only if a < a′ or (a = a′ and bb′).
The result is a partial order. If A and B are each totally ordered, then the result is a total order as well. The lexicographical order of two totally ordered sets is thus a linear extension of their product order.

Isn't the sequence $z" \;\gg\; yz" \;\gg\; yyz" \;\gg\; yyyz" \cdots$ a sequence such that $x_{i+1} \ll x_i$ and $x_{i+1} \neq x_i$?

Is it possible to know how many words are there from aa to az

Ans will be (c)W is not partial order
why?
Because W={aa,ab...........az,ba,bb,............bz,.............za,zb,......zz}

all are possible

if we allow {ab,ba} then it will be a symmetric relation . So partial order is not possible
The order is "dictionary" and it is specified in question. So, ab << ba.
ok then dictionary order means ba,ca,cb those are not possible right?

and well order set means chains like 1-----2----------4-------12, right?

plz ans here
why "ba", "ca" etc not possible? Any word is possible in a dictionary.

aaaaaa << ba

So, options A and B are false.

I'm not sure of well order- but answer here is well order.
yes it is woset because it is toset and lowest element is fixed - 'a'.

Is it possible to know how many words are there from aa to az

E will be the answer .

a> more than 24 words are possible

b>more than 2^24 possible bcz its dictionary order so its not limited

c> dictionary order is always partial  ,because  we can go to 'B' only after 'A' ,so its considered as  a < b

so cant be symetric .so false

d> partial is true here but  not well order is false because in dictionary always least element 'A' is there. so False

e> true  bcz it is well order
answered ago by Active (1.3k points)