Define a relation $\propto$ on the natural numbers $\mathbb{N}$ by declaring that for $x, y \in \mathbb{N}$, $x \propto y \iff (x=y)$ or $(3x \leq y)$

a) Show that $\propto$ is a partial order on $\mathbb{N}$

b) Determine whether or not the subset $\{2, 6, 8\}$ of $\mathbb{N}$ is totally ordered with respect to $\propto$. Explain your answer.

c) Determine whether or not the poset $(\mathbb{N}, \propto)$ has a least element.

For part a), I showed that it was reflexive, transitive and antisymetric.

For part b) I determined that the subset was NOT totally ordered because 6 $\not \propto 8$ and $8 \not \propto 6$

I'm unsure about part c). My guess is that there is no least element because $1 \not \propto 2$ so $1$ cannot be the least element. However $\forall n \in \mathbb{N}$ with $n>1$, $n \not \propto 1$, so there is no number $n \not = 1$ which is the least element.

But I'm sure I'm phrasing this really badly...

  • $\begingroup$ If I understand the definitions correctly, $0$ is a least element, since $3\cdot 0\le n$ for every $n\in\mathbb N$. $\endgroup$ – hmakholm left over Monica Jun 19 '16 at 1:59
  • 1
    $\begingroup$ Ah yes that would be true - but my lectures told me that for this particular course we are not counting zero as a part of the natural numbers (apparently 0 $\in \mathbb{N}$ under some definitions but not others) $\endgroup$ – maths123 Jun 19 '16 at 2:08

You have the right idea.

Suppose $n \ne 1$ is a least element under $\propto $. Since you assume $\Bbb N = \Bbb Z^+$, then $n \ge 2$. Then $n \propto 1$ in particular. However, $n \ne 1$, and since $n \ge 2$, then $3n \ge 6$; thus $3n \not \le 1$ and $n \not \propto 1$

So the only remaining candidate is $n=1$. However, $1 \not \propto 2$ because $3 \cdot 1 \not =3\le 2$.

Thus, all possible candidates have been removed, and $\propto $ has no least element in $\Bbb N$. (Though if you were to include zero, then $0$ would be the least element, since $0 \cdot x = 0 \le y$ for all $y \in \Bbb N$.)

Mostly just posting this to get this out of the unanswered queue. Posting as Community Wiki in particular since I have nothing further to add.


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.