Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider the poset ($\mathbb{Z}^+ - \{1\}, |)$.

What is the least upper bound and greatest lower bound of $\{6,10,14,15\}$?

I don't see how the set in the question applies to the poset. What operations am I supposed to be performing on these numbers to determine what the GLB or LUB is?

EDIT: The answer says there is no GLB and that the LUB = 2*3*5*7 = 210. Why is this so?

share|improve this question

3 Answers 3

up vote 5 down vote accepted

You’ve been given the order relation: it’s $\mid$, divisibility. Because it may be difficult to think order relation when you see $\mid$, let me use $\preceq$ instead: I’ll write $m\preceq n$ if and only if $m\mid n$. Thus, for instance, $3\preceq12$, but $3\not\preceq 5$. You’re asked for the least upper bound and greatest lower bound of the set $\{6,10,14,15\}$. The least upper bound, if it exists, is an integer $n\in\Bbb Z^+\setminus\{1\}$ such that:

  1. $6\preceq n$, $10\preceq n$, $14\preceq n$, and $15\preceq n$; and
  2. if $m\in\Bbb Z^+\setminus\{1\}$ and $6\preceq m$, $10\preceq m$, $14\preceq m$, and $15\preceq m$, then $n\preceq m$.

The first condition makes $n$ an upper bound for $\{6,10,14,15\}$; the second makes it the least upper bound.

Remember that $\preceq$ is really just divides, so the first condition really just requires that $n$ be a multiple of each of the numbers $6,10,14$, and $15$; in other words, it must be a common multiple of the elements of the set $\{6,10,14,15\}$. The second condition says that if $m$ is any common multiple of these four numbers, then $n\mid m$; in other words, $n$ is not just a common multiple of them, but the least common multiple.

You should now be able both to find $n$. With that as an example, you should be able to figure out what a lower bound has to be in terms of divisibility, and then what the greatest lower bound must be. Be careful, though: remember that $1$ is not in the partial order.

share|improve this answer
    
There seems to be a weird MathJax bug which makes me see "$3\preceq12$, but $3\preceq5$", even though you mean (and typed) a "not" in the second one. Let me try again in this comment, to test how it appears: $3\not\preceq5$. (I still don't see the not.) –  ShreevatsaR Nov 14 '12 at 10:53
    
@ShreevatsaR: I see it in your comment. (On the other hand, Firefox is currently not displaying embedded images for me.) –  Brian M. Scott Nov 14 '12 at 10:54
    
I also see what @ShreevatsaR sees. Thanks for the thoughtful response, Brian. Do you mind just elaborating a little more on the $\preceq$ notation? I've seen it used quite often, but I don't really have a great intuitive sense of what it means. –  user1038665 Nov 14 '12 at 10:58
    
I've also seen it as $\prec$. Is there a difference? –  user1038665 Nov 14 '12 at 10:59
    
@user1038665: It’s just a common symbol for a partial order relation. The difference between $\prec$ and $\preceq$ is entirely analogous to the difference between $<$ and $\le$: $x\preceq y$ allows the possibility that $x=y$ as well as the possibility that $x\prec y$ in the strict sense. (Be careful, though: I have occasionally seen $\prec$ used in the non-strict sense, just as $\subset$ is sometimes used to mean $\subseteq$.) –  Brian M. Scott Nov 14 '12 at 11:02

In the poset $(\mathbb Z^+ \setminus\{1\}, \mid)$ a lower bound is a common divisor and an upper bound is a common multiple. So you have to find the greatest common divisor and the least common multiple (if such exist in $\mathbb Z^+\setminus\{1\}$) of your given numbers.

share|improve this answer
    
So the GLB is the smallest number that divides all of 6, 10, 14, 15? And the LUB is the smallest number that is a multiple of 6, 10, 14, 15? –  user1038665 Nov 14 '12 at 10:40
    
@user1038665 Yes. –  martini Nov 14 '12 at 10:44
    
@user1038665: The GLB is the largest (greatest) number that divides all of 6, 10, 14, 15. –  ShreevatsaR Nov 14 '12 at 10:55

Well, since the ordering relation is $|$ (divides), then, you can rephrase the "least upper bound" question as "what number, is divisible by 6, 10, 14, and 15, and such that no divisor of it is itself divisble by 6, 10, 14, and 15". Now, "is divisible by x" is the same as "is a multiple of x", so we see that we want a multiple of 6, 10, 14, and 15 that is not itself a multiple of such a multiple. A candidate is the least common multiple (or lcm) of 6, 10, 14, and 15. This will be divisible by all of those, and furthermore, we can prove it is the desired least upper bound since it is not divisible by another such multiple, since such a multiple would have to be a smaller one, but it's the least one (note that if $n | m$, then $n \le m$. Since $n \ne m$ in this case, $n < m$). We have $\mathrm{lcm}(6, 10, 14, 15) = 210$, so 210 is the least upper bound.

Now, for the greatest lower bound. We can rephrase this as "what number is a divisor of 6, 10, 14, and 15, and such that it is not itself a divisor of such a divisor". A natural candidate is then the greatest common divisor (or gcd) of 6, 10, 14, and 15. This will be a divisor of all of those. To prove this is the desired number, we merely note that if it was a divisor of another such divisor, then there would be a larger common divisor, but it's the greatest one. We have $\gcd(6, 10, 14, 15) = 1$. BUT!!! $1$ is not in the set! So, there is NO greatest lower bound. There are in fact no lower bounds at all, since there are no common divisors except $1$!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.