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$$


$$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.

Thank you for your help


$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.

At least that is the common meaning of total. Then again, you are free to use whichever notation you want.

The rest of your argument is correct.

  • $\begingroup$ Sorry, that's what I meant! I'm italian and mathematical terms can get lost in translation sometimes. "Partial ordering" is the opposite of strict ordering right? Because in italian that's called "large ordering", which makes sense but I don't know if that's the english term as well. $\endgroup$ – Paul Sep 19 '16 at 11:33
  • $\begingroup$ A partial ordering is one where there are elements which cannot be compared. $\endgroup$ – Jsevillamol Sep 19 '16 at 11:36
  • $\begingroup$ Ok, got it. I'll edit the question to make my intentions clear $\endgroup$ – Paul Sep 19 '16 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.