0

"Define a relation on the set N of natural numbers by declaring that for all x, y ∈ N, $x \propto y \iff $(x = y) or (4x ≤ y). Let S = {2, 4, 6, 8, 10, 12} be a subset of $\mathbb{N}$ .

(i) Find all maximal and minimal elements of S with respect to $\propto$ (ii) Find the set of upper bounds of S in $\mathbb{N}$ with respect to $\propto$. Is there the least upper bound of S in $\mathbb{N}$? Explain your answer."

For part (i), I found that the set of maximal elements was {10, 12, 4, 6, 8} and the set of minimal elements were {2, 4, 6}

However I'm unsure what to do for part (ii). I can't figure out the difference between an upper bound and a maximal element, and the part of the question which says "of S in $\mathbb{N}$" confuses me.

maths123
  • 541

2 Answers2

1

A maximal element of $S$ must be a member of $S$. An upper bound need not be, but it has to be comparable to all members of $S$. $10$ is maximal in $S$ because it is not $\propto$ any member of $S$. It is not an upper bound as $12 \not \propto 10$. Neither is $12$ an upper bound as $10 \not \propto 12$ The "in $\Bbb N$" part just means you should consider all the naturals as potential upper bounds. $1,000$ is an upper bound for $S$ because $\forall x \in S (4x\le 1,000)$, which implies $\forall x \in S (x \propto 1,000)$

Ross Millikan
  • 374,822
  • Ok great, that makes sense :) So would I just say that the set of upper bounds is {48, 49, 50...} and there is no least upper bound (because for example $48 \not \propto 49$). But how would I actually prove there is no least upper bound? – maths123 Jun 16 '16 at 04:24
  • Your comment to @maths123 is not correct. ${1,4}$ has a least upper bound $4$ in $\mathbb{N}$, because every other upper bound is at least $16$. – user21820 Jun 16 '16 at 05:08
0

Let me divide it into two bits: (1) what are the upper bounds of $S$ and (2) is there a least one?

First part: $u$ is an upper bound of $S$ if $s \propto u$ for all $s$ in $S$. Given $s$, the expression $s \propto u$ means that $u$ lies in $\{s, 4s, 4s+1, 4s+2, \ldots\}$. Call this set $U(s)$. For instance, $2 \propto u$ means that $u$ lies in $U(2) = \{2, 8, 9, 10, \ldots\}$.

So the set of upper bounds of $S$ is the intersection of the sets $U(2), U(4), \ldots, U(12)$, which turns out to be the set $\{48, 49, 50, \ldots\}$, the integers greater than or equal to $4 \times 12$.

On to the second part: does $\{48, 49, 50, \ldots\}$ have a least element?

A helpful insight here is that for each $n$ in $\mathbb{N}$, the claim $n \propto n+1$ is false.

So none of the upper bounds is a least upper bound: pick any candidate $n$ in $\{48, 49, 50, \ldots\}$. If this were a least upper bound $n$, it would have to satisfy $n \propto u$ for all other upper bounds. But $n+1$ is another upper bound and we just saw that $n \propto n+1$ is false. Conclude: $S$ has no least upper bound!

Mark
  • 482