GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
199 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.
asked in Set Theory & Algebra by Veteran (29k points)   | 199 views

2 Answers

+2 votes

Answer -> E)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.
 
 
 

 

answered by Veteran (41.2k points)  
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$?
0 votes
Ans will be (c)W is not partial order
answered by Veteran (51.7k points)  
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'.

Related questions

Top Users Feb 2017
  1. Arjun

    5166 Points

  2. Bikram

    4204 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2298 Points

  6. Debashish Deka

    2234 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    1998 Points

  9. mcjoshi

    1626 Points

  10. sh!va

    1552 Points

Monthly Topper: Rs. 500 gift card

20,815 questions
25,974 answers
59,606 comments
22,025 users