2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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

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.)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Julius Jackson Sep 7 '13 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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