Prove that every subset ##B## of ##A=\{1,...,n\}## is finite

[zenterix]

Homework Statement

Prove that every subset $B$ of $A=\{1,...,n\}$ is finite.

Relevant Equations

Note that the definition of a finite set is that either a set is empty or there exists a bijection between the set and $\{1,2,...,n\}$ for some $n\in\mathbb{N}$.

I am very unsure about the proof below. I'd like to know if it is correct.

If $B$ is empty then it is finite by definition.

If $B$ is non-empty then since $B\subset\mathbb{N}$ it has a smallest element $b_1$.

If $B \backslash \{b_1\}$ is non-empty then it has a smallest element $b_2$.

If $B \backslash \{b_1, b_2\}$ is non-empty then it has a smallest element $b_3$

If we keep repeating this procedure, we will eventually reach the empty set after a maximum of $n$ steps.

The reason for this is that we obtain an element of $B$ in each step (the smallest element in that step), and if we were to obtain more than $n$ elements then $B$ would have more elements than $\{1, 2, ..., n\}$ of which $B$ is a subset.

Suppose that we reach the empty set after $m\leq n$ steps. We have $b_1, b_2, ..., b_m$ elements obtained from these steps.

Define $g:B\to\{1,...,m\}$ by

$g(b_i)=i$ for $i=1,2,...,m$

Claim: $g$ is a bijection.

Proof

Suppose $g(b_i)=g(b_j)$ for any $b_i, b_j\in B$.

Then by definition of $g$ we have $i=j$ and hence $b_i=b_j$

Thus, $g$ is injective.

Now, let $i\in\{1,...,m\}$. Then $g(b_i)=i$ and so $g$ is surjective.

Thus we have obtained a bijection between $B$ and $\{1,...,m\}$ and so $B$ is finite.

 

[PeroK]

Using induction might be simpler.

 

[pasmith]

For non-empty B it suffices to find a surjection \phi : S\to B for some finite S, since then |B| \leq |S| with equality iff \phi is a bijection.

 

[zenterix]

For non-empty B it suffices to find a surjection \phi : S\to B for some finite S, since then |B| \leq |S| with equality iff \phi is a bijection.

Doesn't finding such a finite $S$ have to go through some procedure like the one in my OP?

That is, don't we have to somehow construct $S$ and isn't that precisely the part of the proof that is the trickiest?

Instead of finding a surjection I found a bijection directly.

 

[PeroK]

Induction must be the way to go.