edited by
3,056 views
17 votes
17 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.
edited by

5 Answers

Best answer
8 votes
8 votes

Answer = D. 

The set $A$ of all words (finite sequence of letters $a−z$), denoted by $W$, in dictionary order.

$W$ is a Poset as it is Reflexive, Antisymmetric and transitive. $W$ is even a Total Ordered structure as Every Two elements of Set $A$ are comparable.

Let's catch the bigger fish here i.e. Well-order. : 

A set S together with partial order ≪ is called a well order if it has no infinite descending chains, i.e. there is no infinite sequence x1,x2,..... of elements from S such that xi+1≪ xi  and xi+1≠xi  for all i.

We know a different definition of Well-ordered set which is "A well-ordered set is a structure of the form $(S, ≤)$ such that $≤$ is a partial order on $S$ and Every nonempty subset of S has a $≤-smallest \,\, element$...We will call this definition as Definition 1 of Well Order.  If $(S, ≤)$ is a well-ordered set, we may express this by saying that the relation $≤$ well-orders $S$. (NOTE that We need not say that $S$ first should be a Total ordered set to be a Well Ordered set Because  the first and second condition of the definition  together itself imply that $(S, \leq)$) is a Total ordered structure)

Now, there is an Equivalent definition to the above definition of Well-Ordered set which is "A total ordered structure is well-ordered if and only if it does not contain infinite descending chains; that is, a linearly ordered set $(S, ≤)$ is a well-ordered set if and only if there does not exist a sequence $a_0, a_1, a_2, . . .$ of elements of $S$ such that $a_0 > a_1 > a_2 > . . . .$ ..We will call it as Definition 2 of well order.

We can prove that Definition 1 and Definition 2 are Equivalent (Proof is given below, after the answer to the asked question).

Since now that we know both the definitions are equivalent. We can use the Definition 1 to check for Well-ordering. 

Now consider the following Subset of the given set $A$ :

$S$ = $\left \{ a^nb\,\,|\,\,n \geq 0 \right \}$.. this Subset has No least element. Hence, The given Structure $(A, dictionary \,\,order)$ is NOT Well-Ordered Structure. 


Proving that Definition 1 and Definition 2 are Equivalent :

Prove that a structure is well-ordered if and only if it does not contain infinite descending chains; that is, prove that a linearly ordered set (S, ≤) is a well-ordered set if and only if there does not exist a sequence a0, a1, a2, . . . of elements of S such that a0 > a1 > a2 > . . . .

(Only if Part)   If $a_0 > a_1 > a_2$, . . . is an infinite descending sequence in $S$, then the set {${ a0, a1, a2, . . . }$} does not have a minimum element, so $S$ is not well-ordered. 

(If part)   Suppose that S is not well-ordered, and fix a nonempty $A ⊆ S$ that does not have a minimum element. Fix $a_0 ∈ A$. Since $a_0$ is not a minimum element of $A$, there exists $a_1 ∈ A$. such that $a_0 > a_1$. Since $a_1$ is not a minimum element of $A$, there exists $a_2 ∈ A$ such that $a_1 > a_2$. Continuing this construction inductively, we find an infinite descending chain in $A$.

selected by
8 votes
8 votes

Answer: E. well order

Minimal Element is $a.$ It is less than all the elements.

  1. False, after $aa,$ we can have $ab.$ Then $aba,abb,abc,\ldots$ Not limited to $24$
  2. False. after $aa,$ we can have $ab,aba,abc,\ldots$ In fact $ab(a-z)^*.$ Not limited to $2^{24}.$
  3. False. Why not partial order? Dictionary order is partial order as it is Reflexive, Antisymmetric & Transitive.  Even definition in wikipedia says it is.
  4. False. Dictionary order is well order.

Definition of lexicographical ordering:

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.

0 votes
0 votes
Ans will be (c)W is not partial order
0 votes
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
Answer:

Related questions