in Set Theory & Algebra retagged by
3,457 views
18 votes
18 votes

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?

  1. $N^{*}$ is uncountable.
  2. $\leq_{p}$ is a total order.
  3. Every non-empty subset of $N^{*}$ has a least upper bound.
  4. Every non-empty subset of $N^{*}$ has a greatest lower bound.
  5. Every non-empty finite subset of $N^{*}$ has a least upper bound.
in Set Theory & Algebra retagged by
3.5k views

2 Comments

@Arjun Sir, 

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

0
0

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 

0
0

4 Answers

15 votes
15 votes
Best answer
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.
edited by
by

4 Comments

@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
1
1
@Mk Utkarsh thank you bro for your comment.
0
0
@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?
0
0
0 votes
0 votes
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
by

2 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
0
0

@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.

2
2
0 votes
0 votes

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

edited by
0 votes
0 votes

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