3

So for the division relation (or divides relation, depending on how one says it), I have to show the following:

a. Prove that | is a partial order on the set of Natural Numbers.

b. Prove that | has no maximum element.

c. Prove that | has a minimum element.

d. Consider the relation | on the set ℕ \ {1}. Prove that there are infinitely many minimal elements that are not minimums.

For a, I can prove everything on it except for antisymmetry. For reflexive, I have shown that it a divides itself, and for transitivity, I have shown that for all a,b, and c in the set of Natural numbers, then if a|b, and b|c, then we need only apply properties of division to show that c is a multiple of b which is a multiple of a, and therefore, a divides c.

For part b, could I prove there is no maximum by proving that the set of all natural numbers is infinite, therefore there cannot be a maximum in the relation?

For part c, I am a little lost on how to prove such a thing because if it is the set of all natural numbers, which would start at 1, wouldn't 1 be the minimum element?

The same question I have for c goes for part d.

Any help would be appreciated. Thank you kindly.

JCMcRae
  • 843

1 Answers1

1

Antisymmetry for (a): Suppose $a|b$ and $b|a.$ Then there are positive integers $s,t$ such that both $as=b$ and $bt=a.$ Substitution then gives $ast=a,$ so that $st=1.$ But since $s,t \ge 1$ this implies $s=t=1$ which then gives $a=b.$

For part (b) all you need to note is that, if $m$ is assumed to be maximal, it should be that every positive integer $x$ is a divisor of $m,$ i.e $x|m$ for all positive $x.$ But this cannot be true for example if $x=2m,$ since then there is $k$ for which $(2m)k=m,$ giving $2k=1$ which is not possible for a positive integer $k.$

In part (c) you are correct in that $1$ is a divisor of every positive integer $x$ since one only needs some $k$ with $1 \cdot k=x,$ and taking $k=x$ works.

For part (d) one is throwing $1$ out of the positive integers, and then you can show that any prime $p$ is a minimal element, in the sense that no other element divides it (in the set of naturals other than $1$). However none of these primes $p$ is a minimum because there are other positive non-1 integers which any specific prime $p$ does not divide.

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • ,I sort of understand what you are saying for c and d, but could you perhaps explain it a little further? As in, for c, how does k = x show that there are no minimums, and for d, how you came to the conclusion that none of the primes p are minimum.

    Sorry if it seems trivial, but I just want to make sure I understand every aspect of the problem.

     – JCMcRae Nov 10 '14 at 08:36
  • As I read it, part c is to show that $|$ does have a minimum element, not that there are no minimums. $1$ is the minimum because it divides every natural number $x$ since $1\cdot x=x.$ For part d, of $p$ is a prime then its only divisors in the naturals are $1$ and $p$, so if working in (naturals except 1) then $p$ has its only divisor as $p$ itself. – coffeemath Nov 10 '14 at 09:33
  • Okay, that explains it a lot. Thanks! – JCMcRae Nov 10 '14 at 16:22
  • 1
    I had misread my own question haha! – JCMcRae Nov 10 '14 at 16:45