Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
I suggest you also say what your ideas are. – MJD Dec 16 '12 at 16:47
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
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.