+1 vote
177 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 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.

Consider any sequence like "43,9,8,2" - it can have many (infinite) least upper bounds like "43,9,8,2,5", "43,9,8,2,1" ... but can have only 1 greatest lower bound - "43,9,8" because we are using prefix relation. So, option D is true.
selected
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 ?