The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+5 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.
asked in Set Theory & Algebra by Veteran (42.7k points) | 319 views

1 Answer

+5 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 (326k 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

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

29,017 questions
36,844 answers
34,722 users