Welcome to our community

Be a part of something great, join today!

Natural numbers form a poset under $ \le$

Jul 22, 2012
35
Problem: let $\mathbb{N} = \left\{0, ~ 1, ...\right\}$ be the set of natural numbers. Prove that $(\mathbb{N},~\le)$ is a poset under the ordinary order.

Solution: let $x \in\mathbb{N}$, then $x \le x$ as of course $x = x$. If also $y \in\mathbb{N}$, then $x \le y$ and $y \le x$ implies $x = y$. Lastly, $x \le y$ and $y \le z$ implies $x \le z$. Therefore $(\mathbb{N}, ~ \le)$ is a poset under the ordinary order.

Is the above valid? I feel like I'm basically stating what I was asked to prove!
 

Fantini

"Read Euler, read Euler." - Laplace
MHB Math Helper
Feb 29, 2012
342
I think your conscience could be eased if you try to justify using euclidean division: if $x \leq x$ then we have that $x = qx+r$ with unique $q,r$. This is true if and only if $q=1$ and $r=0$.

If $x \leq y$ and $y \leq x$ then we have $x = q_1 y + r_1$ and $y = q_2 x + r_2$. It follows that $y = q_2 (q_1 y + r_1) + r_2 = qy + r$, which by previous arguments leads to $q=1$ and $r=0$, but then $r=r_2 + q_2 r_1 = 0$ and $q=q_2 q_1 = 1$, concluding that $q_1 = q_2 = 1$ and $r_1 = r_2 = 0$.

I believe the last one can be done in a similar way. I hope this helps. (Nod)
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
if $x \leq x$ then we have that $x = qx+r$ with unique $q,r$. This is true if and only if $q=1$ and $r=0$.
And what does this prove?
 

Fantini

"Read Euler, read Euler." - Laplace
MHB Math Helper
Feb 29, 2012
342
It seemed a more confident way to prove the assertions, but I confess it does seem tautological.
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
By saying "If x <= x", you assume x <= x instead of proving it. And in any case x = x and x <= x <-> x = x \/ x < x are axioms or easily derivable statements in most systems, so proving x <= x using Euclidean division is definitely more complicated than necessary. Proving antisymmetry using Euclidean division may make sense, though the first thing that comes to my mind is to express <= through < and = and use transitivity an irreflexivity of < .

As an answer to the original question, this statement is definitely trivial and I think the suggested "argument" is fine. Unless one has to prove this using specific axioms in a specific formalism, there is not much more here than to look at it and say, "Yes, this is trivial."
 

Deveno

Well-known member
MHB Math Scholar
Feb 15, 2012
1,967
i think the crucial thing here is that:

x ≤ y

is actually:

(x = y) v (x < y).

so if you wanted to get nit-picky about it, you'd have to consider the various cases.

for example, suppose x ≤ y, and y ≤ z.

if x = y, then x ≤ z.

if x < y, and y = z, then x < z (= y), so x ≤ z.

else, if x < y < z, then x < z, so x ≤ z.

******
of course, perhaps you are meant to delve deeper:

what do we MEAN when we say: x < y, for 2 natural numbers x and y?.

we mean that y is "bigger" than x. that is, we are asserting there is a natural number k ≠ 0, with x+k = y.

so x < y, and y < z means:

there is k ≠ 0 with y = x+k, and m ≠ 0 with z = y+m.

thus z = y+m = (x+k)+m = x+(k+m).

now, to be thorough, we should verify k+m ≠ 0.

since m ≠ 0, m = s(t), for some natural number t (by definition of successor).

thus k+m = k+s(t) = s(k+t), by definition of addition on the natural numbers.

since 0 is not the successor of any natural number, k+m ≠ 0.

*******************

more generally, given any TOTAL order < on a set S, (S,≤) is a poset. in some sense these posets are "trivial": their hasse diagrams are linear. in other words, not very interesting (but not unimportant).

*******************

with questions concerning the natural numbers, it's perhaps a good question for your instructor: "what properties of $\Bbb N$ can we take as 'obvious'?"