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

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: