## Every nonempty set of positive integers has a unique least element

Prove that every nonempty set of positive integers has a least element by induction and prove that the minimal element is unique.

Let $A \subseteq \mathbb{Z}^+$ be nonempty.

Existence: We will prove this result using total induction.

For the base case, note that if $1 \in A$, then $A$ has a least element- namely $1$, since $1 \leq k$ for all $k \in \mathbb{Z}^+$.

Now let $n$ be fixed and suppose that for all $k$ with $1 \leq k \leq n$, if $k \in A$, then $A$ has a least element. Now suppose $n+1 \in A$. If $n+1$ is a least element of $A$, we’re done. If not, then there exists a positive integer $k < n+1$ with $k \in A$. But note that $1 \leq k \leq n$, hence $A$ has a least element.

Thus, for all $n \in \mathbb{Z}^+$, if $n \in A$ then $A$ has a least element. Since $A$ is nonempty by hypothesis, then, it has a least element. $\square$

Uniqueness: Suppose $A$ has two least elements, $a$ and $b$. Then by the definition of least element we have $a \leq b$ and $b \leq a$. Since $\leq$ is a partial order on $\mathbb{Z}$, we have $a = b$. Thus the least element of $A$ is unique. $\blacksquare$

Post a comment or leave a trackback: Trackback URL.