Discrete Math Problem - Relation

Hello,

I am needing some assistance on the problem below. Thank you for your help in advance.


Let R be a relation on the set N of natural numbers defined by

R = {(a,b) (element symbol) N x N ׀ a divides b in N }

Is R a partial order of N? Explain.

Is N with the divisibility relation given above a totally ordered set? Explain.

Quote:

---

Originally Posted by MathStudent1

R = {(a,b) (element symbol) N x N ׀ a divides b in N }

Is R a partial order of N? Explain.

---

Yes.

1)Reflexcise. Note that a|a is a true statement for any "a" in N.

2)Anti-symmettric. Note if a|b and b|a then a<= b and b<= a. Thus, a=b.

3)Transitive. Yes, if a|b and b|c then a|c. I leave that to thee to prove.

Thus, "|" is an ordering relation on this set.

Quote:

---

Is N with the divisibility relation given above a totally ordered set? Explain.

---

By definition, "total order" is that all elements are comparable, i.e. the full set is a chain.
But that is note the case,
(a,b) = (3,5) in R.
But 3|5 is not true.
Thus, it is not a totally ordered set.

Okay, thank you I have been working on the problem and understand it (I believe) except the antisymmetric part. Here is what I have, please tell me if I am right so far:

Reflexive: so, a <= a always holds.

For example, 2 <= 2
3 <= 3
...etc.

Antisymmetric: so, if a <= b and b <= a holds, then a = b

Don't see this yet? What values to choose to show? Can a and b be the same value?

Transitive: so, if a <= b and b <= c hold, then a <= c also holds.

For Example, since 2 <= 3, and
3 <= 6, then
2 <= 6

** I need to know the antisymmetric part before I can tell if it holds and therefore is a poset.

To be totally ordered every pair of elements a,b in the set is comparable (a <=b or b <= a). The set of natural numbers is not totally ordered since for example, 3 and 5 are not comparble, neither 3 <= 5 nor 5 <= 3 holds.

Thank you!

The relation is indeed antisymmetric.
If a divides and b divides a then a is b.

More formally: a|b implies b=ka; b|a implies a=jb.
So b=ka=kjb or kj=1. But that means k=j=1, b=a.

So, can I say for example, since 2 ≤ 2 and 2 ≥ 2, it must be true that 2=2? Or, I am wrong with I am choosing a and b to be 2? I am needing an example. I am still stuck. Thanks.

I am still spinning my wheels on this one. After thinking about it, I don't think I can prove it by examples like I tried above? Thanks.