I want to show that $\mathrel{R_1}$ and $\mathrel{R_2}$ are a partial order on $\mathbb N$, how would I do this?

Question

Let $\mathrel{R_1}$ and $\mathrel{R_2}$ be relations on $\mathbb N$ defined by

$x\mathrel{R_1}y$ if and only if $y = a + x$ for some $a \in\mathbb N_0$.

$x\mathrel{R_2}y$ if and only if $y = xa$ for some $a \in\mathbb N$

For all $x; y\in\mathbb N.$

Also $\mathbb N_0$ denotes all integers $x\ge 0$, while $\mathbb N$ denotes all integers $x\ge 1$.

I want to show how $\mathrel{R_1}$ is a partial order on $\mathbb N$, and I want to show how $\mathrel{R_2}$ is a partial order on $\mathbb N$. I am confused on how I would exactly show the steps, if someone could explain that would be great.

Answer 1

Recall that to show a relation $R$ is a partial order, you need to verify that the following properties hold for all elements in the set $A$ on which the order is defined:

1. $R$ is reflexive: for all $a \in A$, $a R a$.

2. $R$ is antisymmetric: for all $a, b \in A,\;$ if $aRb$ and $bR a$, then it must be the case that $a = b$.

3. $R$ is transitive: for all $a, b, c \in A, \;$ if $aRb$ and $bR c$, then $a R c$.

---

I'll model how you can approach relation $R_1$, which I'll just denote here by $R$. Then you can use the same approach to prove $R_2$ is a partial order on $\mathbb N$. For relation $R_1 = R$, note that $a \in \mathbb N_0$ means that $a$ is some non-negative integer.

This is mostly an exercise in applying the definitions of these properties given the relation $$R: \{(x, y)\mid y = x + a \;\text{for some non-negative integer}\;a\}$$ where $x\,R\,y$ means $x, y \in \mathbb N, (a, b) \in R$.

1. $R$ is reflexive ?:
   
   Is it true that for all $x \in \mathbb N,$ there exists an integer $a \geq 0\,$ such that $x = x + a?$ Hint: let $\,a = 0.$

2. $R$ is antisymmetric ?:
   
   Is it true that for all $x, y \in \mathbb N$, if we know $x R y$ (that is, if there exists an integer $a_1 \geq 0$ such that $y = x + a_1$) and we also know that $y R x$, so that there is some integer $a_2 \geq 0$ such that $x = y + a_2\;$ then it has to be the case that $x = y$?
   
   I'll start you out: Assume $x R y$ and $y R x$. So there exist non-negative integers $a_1, a_2$ such that $y = x + a_1\;$ and $\;x = y + a_2$. Now, try to determine whether it must follow then that $x=y$.

3. $R$ is transitive?:
   
   Is it true that for all $x, y, z\in \mathbb N$, if we know $x R y\;$ and know that $\;y R z,\;$ then it is also true that $x R z\;?$ Try to write our what this means in terms of your given relation.

Once you've answered the questions above in the affirmative, you will have shown that $R = R_1$ is reflexive, antisymmetric, and transitive, and so you will have proven that $R_1$ is a partial order.