Algebra Solutions: 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$

Algebra Solutions

Every nonempty set of positive integers has a unique least element

No comments:

Post a Comment