retagged by
3,473 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.
retagged by

4 Answers

Best answer
15 votes
15 votes
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
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
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.
Answer:

Related questions