Prove that if a set (in a Peano System) is bounded above then it have a greatest element

60 Views Asked by At

The question is stated as: If $\emptyset \neq A \subseteq P$ and $A$ is bounded above(that is $(\exists w)(\forall u)(u \in A \Rightarrow u \leq w)$, then $A$ has a greatest element.

Here is assumed a standard Peano System $(P,S,1)$, where $P=\mathbb{N}$, $S(x)=x+1$ and "$1$" is the natural number one.

Here is my atempt:

Let $B = \{w : (\forall u)(u \in A \Rightarrow u \leq w)\}$, thus by assumption $B$ is a nonempty subset of $P$, thus by Principle of Least Number, we have $(\exists z)(z \in B \land (\forall u)(u \in B \Rightarrow z \leq u))$.

If we take $z$, the least element of $B$ we have that $(\forall u)(u \in A \Rightarrow u \leq z)$, thus for any $u \in A$ we have $u=z \lor u < z$, first if we have some $u=z$ we have that $z$ is the greatest element of $A$ since if it is not the case, we will got that there exists other element in $e \in A$ where $z<p$ which is a contradiction because any element in $A$ are less or equal to $z$.

But if no one $u$ in $A$ is equal to $z$ as we have $(\forall u)(u \in A \Rightarrow u < z)$ we have also that $(\forall u)(u \in A \Rightarrow S(u) <=z)$. First if $S(u) < z$ we have $S(u) \in A$ and therefore $u<S(u)$, thus $u$ is no the greatest element of $A$, but if $S(u)=z$, we have that $S(u) \notin A$, and $u$ is the greatest element of $A$ since there is no element between an element and it own successor, and as $z=S(u) \in B$ there is no element bigger than $u$ which can belongs to $A$.

1

There are 1 best solutions below

0
On BEST ANSWER

Your proof is mostly right, but I would change the last paragraph of your proof as follows.

After dealing with the case that there is some $u \in A$ such that $u = z$, we assume that for all $u \in A$ we have that $u < z$, and I claim that now it suffices to show that there is $u \in A$ such that $S(u) = z$; from here onwards it would follow the second bit of your last paragraph (the one starting with "but if $S(u)=z$, we have that...") and the proof would be complete. The problem with your proof is that you assume that $S(u) = z$ without specifying that $u \in A$, and yet later you claim that $u$ is the greatest element of $A$.

Here is how you can fill-in this gap. Assume for contradiction that there is no $u \in A$ such that $S(u) = z$. Since $\varnothing \neq A$, there is $u_0 \in A$, and since $S(u_0) \leq z$ and $S(u_0) \neq z$ we have that $S(u_0) < z$, so $S(u_0) \in A$. Similarly, as $S(u_0) \in A$ we get that $S(S(u_0)) \in A$, and continuing in this way we obtain a strictly increasing sequence of elements in $A$ $$u_0 < S(u_0) < S(S(u_0)) < \dots,$$ contradicting the fact that $A$ is bounded above. Therefore our assumption is false and there is indeed $u \in A$ such that $S(u) = z$.