# Help with elementary question involving a partially ordered set.

Let N with divisibility be a partially ordered set.

Show that any 2 element subset of N has a greatest lower bound and a least upper bound.

I seem to keep going in circles, but I have the idea that if we let $m=ab\in N$ then $a\mid m$ and $b\mid m$, but this only guarantees we have an upper bound.

Any help is appreciated.

HINT: You want the least common multiple and its mate, the greatest ... what?

• greatest common divisor, of course – Julius Jackson Sep 7 '13 at 6:40
• @Julius: That’s right; you shouldn’t have too much trouble verifying that those are the numbers that you want. – Brian M. Scott Sep 7 '13 at 6:41
• thanks, will go back to the drawing board. – Julius Jackson Sep 7 '13 at 6:45
• @Julius: You’re welcome. – Brian M. Scott Sep 7 '13 at 6:50

You probably got stuck because the statement looks like it might be nearly a tautology. It tempts you into hoping that it can be proven just by understanding the abstract properties of divisibility. For example, it's clearly true that $a$ and $b$ both divide $ab$. However, it turns out that that isn't enough!

As Brian has pointed out, you can call upon the least common multiple and greatest common divisor or $a$ and $b$. In fact, you almost have to do so! The existence of the lcm and gcd is a nontrivial property of the natural numbers $\mathbb N$. There are other number systems in which divisibility is meaningful but lcms and gcds don't always exist. For an example, see https://en.wikipedia.org/wiki/Greatest_common_divisor#The_gcd_in_commutative_rings.

So the statement isn't just about divisibility, and it's not just about partially ordered sets. It's an interesting property of $\mathbb N$. Therefore, no matter how clever one is, there is no hope of proving the statement without saying something about $\mathbb N$!

(For your purposes, it's probably enough to say "gcds and lcms exist in $\mathbb N$" without proof. I just wanted to point out why the problem is harder than it appears.)

• Definitely clear as to what you believe happened, I am in my first ever Topology course as an undergraduate so there's learning to do. I will add the fact that lcm's and gcd's exist in $\N$ in my written proof, thank you. – Julius Jackson Sep 7 '13 at 7:34