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

Related questions

Top Users Jan 2017
  1. Debashish Deka

    8608 Points

  2. sudsho

    5398 Points

  3. Habibkhan

    4718 Points

  4. Bikram

    4522 Points

  5. Vijay Thakur

    4468 Points

  6. saurabh rai

    4222 Points

  7. Arjun

    4122 Points

  8. santhoshdevulapally

    3742 Points

  9. Sushant Gokhale

    3576 Points

  10. GateSet

    3394 Points

Monthly Topper: Rs. 500 gift card

19,177 questions
24,073 answers
52,975 comments
20,310 users