Induction based proof.

Question

Let S be an ordered set. Let $A \subset S$ be a nonempty finite subset. Prove that $A$ is bounded, that inf A exists and is in $A$, and that $\sup (A)$ exists and is in $A$. Hint: Use induction. (A finite set is a set from which, for some $n \in \mathbb{N}$, there is an injective map to the set {$1, 2, \cdots , n$}

I started with induction on cardinality on set $|A|$. But I am stuck right here in the beginning.

What would the base case be? – Benjamin Sep 09 '14 at 18:33 — Benjamin, Sep 09 '14 at 18:33
When there is one element, infA=supA – Gregory Eritsyan Sep 09 '14 at 20:03 — Gregory Eritsyan, Sep 09 '14 at 20:03

score 1 · Accepted Answer · answered Sep 09 '14 at 18:41

If $A$ has one member, it's obvious that it's bounded, and

$$\text{inf } A = \text{sup } A \in A.$$

Assuming the statements hold for an $n$-member subset, add another member.

The new member exists, since it's a member of $S$.

Since $A$ is bounded, the addition of one member does not change this (a finite set plus one member is still a finite set). (Call the new set $A'$, and the new element $m$.)

This new member $m$ is either greater than $\text{sup } A$ (which exists), or it is less than $\text{sup } A$. If it is greater, $\text{sup } A' = m$. Otherwise, $\text{sup } A' = \text{sup } A.$

Also, this new member $m$ is either less than $\text{inf } A$ (which exists), or it is greater than $\text{inf } A$. If it is less, $\text{inf } A' = m$. Otherwise, $\text{inf } A' = \text{inf } A.$

I think that covers everything?

Induction based proof.

1 Answers1