The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+8 votes

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 (47.9k points) | 360 views

I understood how it is a partial order. But I did not understand why it is a well order? According to the definition given in the question, a partial order ≪ is called a well order if it has no infinite descending chains.

But if we pick random word like ab, it has infinite descendants like aa, aaa, aaaaaa, .....

How is this a well order?


the minimal element is {a}

u cannot go below that

it stops there it isnt infinite

3 Answers

+6 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 ->

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 (49.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$?

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

0 votes
Ans will be (c)W is not partial order
answered by Veteran (82.7k points)
Because W={aa,,ba,bb,,,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

0 votes
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 by Loyal (4.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,210 questions
40,894 answers
39,793 users