Trying to prove every nonempty finite set of Z has a smallest element by induction

Question

I found this question on a past paper while preparing for my mid-term exam

Prove by mathematical induction that every nonempty finite set of Z has a smallest element

I previously answered a question similar to this where instead of set Z it was set N. Here is my solution to that version of the question:

Every nonempty subset of N has a smallest element.

Let S be a nonempty subset of N.

Base case: If 1∈S, then the proof is done since 1 is the smallest natural number.

Inductive hypothesis: If S contains an integer k such that 1≤k≤n, then it must be that S contains a smallest element.

Inductive step: It remains to be shown that if S contains an integer k≤n+1, then S has a smallest element.

Suppose S contains an element 1≤k≤n+1. If S does not contain an element 1≤l≤n then that element k is n+1 and it is the smallest element of S because S contains it and nothing less than it.

If S does contain an element 1≤l≤n then it meets the criteria of the inductive hypothesis and therefore has the smallest element.

Either way, any set S with an element 1≤k≤n+1 has the smallest element. This concludes the induction step.

I am unsure how to adjust this to answer the question above. Any help would be highly appreciated

Answer 1

You can use the exact same proof and preface it with the fact that a finite set in $\mathbb{Z}$ with cardinal n is isomorphic to the subset $[1..n]\in \mathbb{N}$. (isomorphic sets are such that there is a bijection between)

Note that this can also be extended to show that $\forall a\in\mathbb{Z}$: the subset $\mathbb{Z}_{\geq a}$ has a smallest element. Indeed it is isomorphic to the natural numbers under $f(x) = x+|a|$

Answer 2

I assume by $Z$ you mean the set of natural numbers.

Suppose $S$ is a non-empty subset of $Z$ and there is no smallest element in $S$

i.e. no $k\in Z$ is the smallest element of $S$.

Then there exists a set $T$

$T=\{1,2,...,k\}$

$(k+1)\notin S\implies (k+1) \in T$.

Thus by the induction principle: $T=Z$, in contradiction to the assumption that $S\neq\emptyset$.

Thanks for the comment: So $S=\{a_1,...,a_n\}$ is a nonempty finite set of the integers.

Thus it is isomorphic to $\{1,...,n\}$.

I.e. there exists a bijection: $a_i\sigma=i,\;i\in\{1,...,n\}$.

Where i am using left notation for functions.