in Set Theory & Algebra edited by
3,028 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.
in Set Theory & Algebra edited by
3.0k views

4 Comments

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

This is Not a descending sequence.. This is ascending sequence. And for this Subset we have least element $aa$..So, This sequence can't be used as a counter example for showing that it is not well ordered set.

3
3

it stops there right...so it isnt infinite

It indeed is Infinite. But Not descending infinite.  

1
1
Indeed a nice exolexplana dee. But anyone if doesn't get something , even a little.. i highly recommend to go for K.H Rosen (P-619)
0
0

5 Answers

8 votes
8 votes
Best answer

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

4 Comments

the least element would be a, wouldn't it? 

Least element is describes w.r.t. some Set. Assuming you're taking whole set $A,$ then Yes, $a$ will be the least element of "this" set (Unless you allow Epsilon in the set $A$)

2
2
Yes, for the whole set A, 'a' would be the minimal element. And if we take minimal element of S, it should be 'aaa......b' (finite times a followed by b since it is a finite sequence), right? In this case it would be well ordered, wouldn't it?
0
0
edited by
@Dee Sir

How it is Reflexive ?  ‘a’ can never be related to ‘a’

Moreover, I think lexicographical here means {a,b,c,…….z,aa,ab,ac,…...zz,aaa,aab,….zzz...}

then option E would be the answer
0
0
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.

4 Comments

Isn't the sequence ‘‘z"≫‘‘yz"≫‘‘yyz"≫‘‘yyyz"⋯‘⋯ a sequence such that xi+1≪xi and xi+1≠xi?

Yes. Indeed it is. You are right. The Correct Answer will be Option D, Not E. And The Sequence you gave is one of the Counter example to show that the given structure is not Well ordered.

1
1

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

Infinite. 

1
1

Akash Kanase I think after "aa" we can get "aaa","aaaa" and so on before getting "ab" in the dictionary order.

0
0
0 votes
0 votes
Ans will be (c)W is not partial order

8 Comments

why?
0
0
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
0
0
The order is "dictionary" and it is specified in question. So, ab << ba.
0
0
edited by
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
0
0
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.
1
1
yes it is woset because it is toset and lowest element is fixed - 'a'.
1
1

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

0
0

yes it is woset because it is toset and lowest element is fixed - 'a'.

No. It is not Woset. Check my answer. And Just because there is Least element for the Whole set doesn't mean that it is a Woset. It will be a Woset only if For All the Non-empty subsets there be a least element. 

4
4
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

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