1

I'm trying to proof if the following Relations R ⊆ M×M total order or partially order are.

  1. $M = \{1,2,3\} , R = \{(x,y) : x|y\}$

  2. $M = {\bf Z} , R = \{(x,y) : x\vert y\}$

  3. $M = {\bf N}, R = \{(x,y): y ≤ x\}$

  4. $M = {\bf Z} × {\bf Z}, R = \{((x1,x2),(y1,y2)):x1 ≤ y1 ∧ x2 ≤ y2\}$.

Well i know exactly how to determine if the relation total order or partially order

Total order is reflexiv, transitiv, antisymmetric and total/linear.

Partially total order is reflexiv, transitiv and antisymetric.

I have some ideas for these relations but to be honest i have no idea about how to proof it.

Well if a relation would given for example like this :

M = {1,2,3} , R = {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}

I could say that this is a total order, i see exactly the all binary couples in the relation. But the exercises above confuse me , because i don't see the set(or binary couples). There are just some conditons. For exampe in 1) it says a divides b. But how can i proof using this condition if this relation is reflexiv, antisymmetric and so on. This is my problem !!!

Thanks in adavance for your help!

Tiro
  • 49
  • 1
    I suggest you also say what your ideas are. – MJD Dec 16 '12 at 16:47
  • 2
    You need to do some work. For example, 1) can be trivially answered by just making a 3x3 table. The answer for 1) can be used to answer 2). – copper.hat Dec 16 '12 at 16:48
  • i hope i explained better now, and what do you mean btw 3*3 table ? – Tiro Dec 16 '12 at 16:58
  • 1
    3x3 table for the first one looks like this: ${(x,y) \in M\times M : x | y} = {(1,1), (1,2), (1,3), (2,2), (3,3)}$, that is, $$ \left[\begin{array}{ccc} 1&1&1\0&1&0\0&0&1\end{array}\right]. $$ Try doing it yourself for the rest of the exercise. – dtldarek Dec 16 '12 at 17:48
  • @dtldarek :Thank you my friend, i think i just understand what should i do. For example for 3) i thought:

    {(x,y) ∈ M × M : y ≤ x } = {(1,1),(1,0),(2,2),(2,0),(2,1),(3,3),(3,0),(3,1),(3,2),....}

    So it's reflexiv, antisymmetric,transitiv and total. That means it is total order. I hope it's true.

     – Tiro Dec 16 '12 at 18:32
  • @Tiro Yeah, that's the basic idea. But you should be careful, in the set you have written, you missed $(0,0)$, and even such a triffle (if it was true) would cause the relation not being a total order. – dtldarek Dec 16 '12 at 18:37

0 Answers0