GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
219 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 (30k points)   | 219 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.5k 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 (54.8k 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 Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1408 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1148 Points

  8. Debashish Deka

    1112 Points

  9. srestha

    932 Points

  10. Arjun

    930 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    392 Points


23,361 questions
30,068 answers
67,376 comments
28,385 users