TIFR CSE 2014 | Part B | Question: 15

Question

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 true?

• A. $N^{*}$ is uncountable.
• B. $\leq_{p}$ is a total order.
• C. Every non-empty subset of $N^{*}$ has a least upper bound.
• D. Every non-empty subset of $N^{*}$ has a greatest lower bound.
• E. Every non-empty finite subset of $N^{*}$ has a least upper bound.

Comments

@Arjun Sir, 

had it been R* given would not change the answer , as it would not affect the bounds , is it correct ?

---

Detailed Video Solution of Option A, with Proof: https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=5886s 

Understand $N^*$ & learn the Proof of $N^*$ being countable. 

---

Countability Complete Course, with Proofs, Variations & All type of questions covered: https://youtube.com/playlist?list=PLIPZ2_p3RNHgXosiQv-gL1PvJkcHokW1p&feature=shared 

Answer 1

Consider two sequences $\langle 43,9 \rangle$ and $\langle 52, 2\rangle$. These two are not comparable as there is no common prefix and also there can be no sequence which can be higher than these in the prefix relation - so no upper bound for these. So, options B, C and E are ruled out. Option D is correct as for any two sequences their common prefix acts as the greatest lower bound, and in case there is nothing common, empty sequence will act as the greatest lower bound.

So, option D is true.

Comments

Consider two sequences : { (2,3,4)  (4,5,6) } .. What would be lower bound for this ??

Is this would be Empty sequence ()..

---

As N (Natural No. set is Infinite)

Now,  Number of finite Subsets of  N are Countable ?

---

1) The set N^* won't be uncountable but countably infinite.

2)Not total order because we can find any two sequences which are not-comparable like sequence 234 and sequence 67 have no prefix common so not comparable sequences.

3)It's not necessary that any subset of N^*  will have a LUB like N^*={1,2,3} have no LUB

4) Yes! GLB would always be there. as sir answered.

5)same as option 3).

---

The statement should be true for all cases.

For (2,3,2) (1,5,6) subset there is no comon prefix.Morever it is not even a lattice.

---

@Rupendra Choudhary How could you say that N* is countably infinite and not uncountable? I did not understand it.

Can you please elaborate?

---

https://www.nayuki.io/page/countable-sets-and-kleene-star

---

@Arjun Sir can you please verify my answer ?

N* looks like

{},                                     length 0 string 

1,2,3,4,5,....................... length 1 string 

11,12,13,14,15,16....      length 2 string 

21,22,23,24,25,26....      length 2 string 

.

.

111, 112,113,                 length 3 string.

                                      length infinite  String 

Now take any  subset of N* (subset may be finite or infinite ) lets say  {1 ,2,3}

Now there is no string whose prefixes are 1 as well as 2 as well as 3. Hence no LUB.

But there is string which is suffixes of all three i.e. {}  Hence GLB exist

Hence for Every non-empty subset of N* , {} will be always be lower bound for all elements of that subset. 

Hence LUB always exist.

---

@mehul vaidya ji. i did not understand this "Now take any  subset of N* (subset may be finite or infinite ) lets say  {1 ,2,3} Now there is no string whose prefixes are 1 as well as 2 as well as 3. Hence no LUB."  Please explain.

---

@Arjun sir,

I have a basic doubt. To prove that the relation is not a total order, you have taken two sequences as <43,9> <52,2>.

But in question its given that it is a set of sequences of N, so that set would have numbers like {1,2,3...11,12,13...21,22...} Now for proving not a total order we should check 2 seq like 1 and 2 there is no common prefix between 1 and 2, so they r not comparable. This is how I have interpreted this question so I am having doubt how <43,9> is being compared with <52,2> . please correct me where I am wrong.

Thank you.

---

Sequence doesn't mean every integer should be present. Moreover it is given that sequence is finite.

---

@Arjun sir, Thanks for replying.

So it means that the set is having sequences of natural nos, like first seq Y= <123, 34> 2nd seq X= <12>, Z= <12,54> and so on, each such sequence is of finite length. Now X is related to Y because prefix of X is prefix of an element of Y.. isn't it?. Can Z also be related to Y?

And why can't there be any other seq which can be higher than <43,9> , <52,5> in prefix relation? A seq like <43,9,52,5> is not possible?

Thanks

---

@Mk Utkarsh thank you bro for your comment.

---

@Arjun Sir,

{1,2} is also non empty subset of N* however it does not have any GLB and LUB so isn't c,d,e options false. Moreover it is also a total order?

Answer 2

consider any sequence like 4,6,3,5,8....$$   4,6,3,5,36,2.... $$  4,6,3,5,69,12..... it can have many infinte least upper bound but it contain greatest lower bound 4,6,3,5 because it using prefix relation

Comments

HI @avadh can you please tell me that this question is from which topic?

I am not even able to understand what this question is asking to do.

could please suggest names of topics or concepts which I can study in order to understand and answer this question?

Thankyou

---

@jaco 

1. Set Theory.

2. Relation

3. Partial Order Set followed by Total Order Set.

4. Prefix Property

5. Least Upper Bound / Greatest Lower Bound you can just read over Google, No need to go much deeper.

Answer 3

There's no reason why we can't club the given set in one-to-one correspondence with Natural Numbers, so $N^*$ is countable.

---

Not every two elements of this set need to be comparable.

Take these two random sequences <17,900,2> and <4, 11> Neither is a prefix of the other, so we have two incomparable elements. Hence, not TOSET.

---

Say we only have three sequences: <4,35> <750,66> <1>

No upper bound for any of these, because no sequence exists such that all of the given sequences are a prefix to it.

Now extend this to infinite number of sequences. If one sequence starts with 27 other starts with 82, you can extend them infinitely; but they both together can't serve as the prefix to any sequence. So, no upper bound.

---

Take any number. What is a guaranteed prefix to that number? $\epsilon$ is.

So, the least case, ie, $\epsilon$ or empty sequence exists, which would be a lower bound to every element.

Option D

Answer 4

Prefix Property:

Let's consider the set N* of finite sequences of natural numbers. Here are a few sequences:

x = (1, 2) y = (1, 2, 3) z = (2, 3)

The prefix property is a relation between sequences. In this example, x is a prefix of y because x appears at the beginning of y. We can denote this as x <p y. However, x is not a prefix of z, and z is not a prefix of y.

The set N* consists of finite sequences of natural numbers. Each element in N* is a sequence of natural numbers, which could be of varying lengths. For example, the set N* could include sequences like (1), (2, 3), (4, 5, 6), and so on.

In the context provided, x <p y denotes that sequence x is a prefix of sequence y. A prefix of a sequence is a subsequence that occurs at the beginning of the original sequence. For instance, if x = (1, 2) and y = (1, 2, 3, 4), then x is a prefix of y, denoted by x <p y.

Here are a few examples to better understand the concept:

1. If x = (1) and y = (1, 3, 4), then x <p y because x is a prefix of y.
2. If x = (2, 3) and y = (2, 3, 5, 6), then x <p y because x is a prefix of y.
3. If x = (4, 5) and y = (1, 4, 5), then x is NOT a prefix of y, and x <p y does not hold.
   
   We Can create the Partial Order lattice where we can find the every subset of the of GLB (meet) but may not find the every subset of  LUB.