edited by
7,009 views
20 20 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.

5 Answers

Best answer
9 9 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 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.

edited by
0 0 votes
Ans will be (c)W is not partial order
0 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
0 0 votes
For W to be a well order

It has to be a connix relation on a total order

a connex relation forces your element to have atleast one lower bound for all elements belonging to A

Hence D is correct

iT is a partial order but not a well order
Answer:
Position:
Show:

Related questions

14 14 votes
4 answers 4 answers
2.4k
2.4k views
Misbah Ghaya asked Nov 8, 2015
2,362 views
Consider a function $T_{k, n}: \left\{0, 1\right\}^{n}\rightarrow \left\{0, 1\right\}$ which returns $1$ if at least $k$ of its $n$ inputs are $1$. Formally, $T_{k, n}(x)...
19 19 votes
3 answers 3 answers
4.2k
4.2k views
Misbah Ghaya asked Nov 4, 2015
4,247 views
Three candidates, Amar, Birendra and Chanchal stand for the local election. Opinion polls are conducted and show that fraction $a$ of the voters prefer Amar to Birendra, ...
18 18 votes
5 answers 5 answers
9.4k
9.4k views
Misbah Ghaya asked Nov 20, 2015
9,352 views
Consider the ordering relation $x\mid y \subseteq N \times N$ over natural numbers $N$ such that $x \mid y$ if there exists $z \in N$ such that $x ∙ z = y$. A set is call...
19 19 votes
4 answers 4 answers
5.8k
5.8k views
Misbah Ghaya asked Nov 20, 2015
5,760 views
Consider the set $N^{*}$ of finite sequences of natural numbers with $x \leq_{p}y$ denoting that sequence $x$ is a prefix of sequence $y$. Then, which of the following is...