# Prove if these two relations are order relations

I have this assignement for my discreet math course, and I would like a opinion on my answer:

Let $a = p_1^{e_1} + p_2^{e_2} + ... + p_s^{e_s}$ and $b = q_1^{f_1} + q_2^{f_2} + ... + q_t^{f_t}$ be positive integers expressed as sum of powers of prime numbers. In $\Bbb N$ , let these two binary relations be defined:

$$aR_1b \Leftrightarrow e_1 + e_2 + ... e_s \le f_1 + f_2 + ... + f_t$$ $$aR_2b \Leftrightarrow e_1 + e_2 + ... e_s \lt f_1 + f_2 + ... + f_t$$

Which of these relations is an order relation?

What I came up with:

For $R_1$ to be a large ordering it needs to be reflexive, antisymmetrical and transtive.

Reflexivity: $aRa$ so $e_1 + e_2 + ... e_s \le e_1 + e_2 + ... + e_s$ must be true. And it is, the sum of the exponents is $\le$ to itself, so $R_1$ is reflexive.

Antisymmetry: If $aRb$ and $bRa$, then $a=b$.

$$aRb \Leftrightarrow e_1 + e_2 + ... e_s \le f_1 + f_2 + ... + f_s$$ $$bRa \Leftrightarrow f_1 + f_2 + ... + f_s \le e_1 + e_2 + ... e_s$$

This can happen, and it implies that the values of the two sums are equal. But the fact that the sums are equal, does not imply that $a=b$, because it doesn't take into consideration the bases of the powers. We could have $A=5^3+7^2$ and $B=3^2+2^3$ and they would have the same sum for the exponents, but A and B themselves would be different numbers. So $aRb$ and $bRa$ can both happen even if $a\neq b$, so the relation is not antisymmetric.

Transitivity: This is straightforward. If $$e_1 + e_2 + ... e_s \le f_1 + f_2 + ... + f_s$$

and

$$f_1 + f_2 + ... + f_s \le g_1 + g_2 + ... g_h$$

of course

$$e_1 + e_2 + ... e_s \le g_1 + g_2 + ... + g_h$$

So the relation is transitive.

$R_1$ is not a large ordering because it's not antisymmetric.

To prove that it is a strict ordering we need to prove that $R_1$ is irreflexive and transitive. We already know that it is transitive, and we also know that it is reflexive, so $R_1$ can't be irreflexive, thus it is not an order relation.

For $R_2$ :

Reflexivity: $R$ can't be reflexive because the sum of the exponents of $a$ can't be lesser than itself.

Antisymmetry: We already know that if $$e_1 + e_2 + ... e_s \lt f_1 + f_2 + ... + f_s$$ is true, the opposite can't be. So if $aRb$ we can never have $bRa$, be $a=b$ or not. So the relation is antisymmetric.

Transitivity: Same as $R_1$ but with $\lt$ instead of $\le$.

Since the relation is not reflexive, it is not a large ordering.

Is the relation irreflexive? It is because $\forall x \in S : a\lnot Ra$, the reason being the counter-proof of reflexivity. So $R_2$ is a strict ordering relation.

$R_2$ is a strict ordering, not a total ordering. A total ordering is one such that for every $a,b$ we have either $a\le b$ or $b \le a$.
This is not satisfied in $R_2$ because of the irreflexivity.