"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$ – Henning Makholm Jun 19 '16 at 1:59
  • $\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

Your Answer

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

Browse other questions tagged or ask your own question.