GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
218 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.
asked in Set Theory & Algebra by Veteran (29.2k points)   | 218 views

1 Answer

+3 votes
Best answer
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.
answered by Veteran (283k points)  
selected by
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 ?
Answer:

Related questions



Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arjun

    1472 Points

  10. Arunav Khare

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,063 answers
63,297 comments
24,169 users