Question

Consider the set N* of finite sequences of natural numbers with a denoting that sequence a is a prefix of sequence b. Then, which of the following is true?

(a) Every non-empty subset of has a greatest lower bound

(b) It is uncountable

(c) Every non-empty finite subset of has a least upper bound

(d) Every non-empty subset of has a least upper bound

I got this question during an interview for a job.

My doubt is from Relations in division Relations of Discrete Mathematics

Answer 1

The correct option is (a) Every non-empty subset of has a greatest lower bound

To explain I would say: Consider any sequence like “45, 8, 7, 2” – it can have many (infinite) least upper bounds like “45, 8, 7, 2, 5”, “45, 8, 7, 2, 1” and so on but it can have only 1 greatest lower bound – “45, 8, 7” because we are using the prefix relation. So, every non-empty subset has a greatest lower bound.