## 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 be nonempty.

Existence: We will prove this result using total induction.

For the base case, note that if , then has a least element- namely , since for all .

Now let be fixed and suppose that for all with , if , then has a least element. Now suppose . If is a least element of , we’re done. If not, then there exists a positive integer with . But note that , hence has a least element.

Thus, for all , if then has a least element. Since is nonempty by hypothesis, then, it has a least element.

Uniqueness: Suppose has two least elements, and . Then by the definition of least element we have and . Since is a partial order on , we have . Thus the least element of is unique.

### Like this:

Like Loading...

*Related*

or leave a trackback:

Trackback URL.