Finite Sets Induction

Question

Every finite set of natural numbers has a maximum. Hint: Induct on the number of elements. A set with n + 1 elements is a set of n elements union a set of 1 element. What is the P(n) statement and how does the induction step work?

Answer 1

P(n) = every set of $n$ elements has a maximum element. And if $P(k)$ is true. And $M$ be a set of $k+1$ elements and $x \in M$ then $M -\{x\}$ is a set of $k$ elements so it has a max. Can you figure out how to prove $M = (M - \{x\}) \cup \{x\}$ has a max?

Hint: What is $\max(\max (M-\{x\}), x)$? What happens if $x \le \max (M-\{x\})$? Can you show that $M$ has a max? If so what is it? What happens if $x > \max (M-\{x\})$? Can you show that $M$ has a max? Is so what is it?

Are there any other possibilities?

Base Step:

$P(1)$ if $M$ is a set with one element it has a maximum. Proof: If $M = {n}$ has one element than $n$ is maximal. ($n \ge x$ for all $x \in M$ as $n$ is the only $x \in M$ and $n \ge n$.)

Hypothese for $n = k$ an immediate consecuences:

Assume $P(k)$. Assume $M$ has $k + 1$ elements. Let $x \in M$. Then $M - \{x\}$ has $k$ elements. So a $M - \{x\}$ has a maximal element. Call it $m$.

Induction step:

$x \ne m$ as $m \in M - \{x\}$ and $x\not \in M - \{x\}$. So either $x < m$ which would mean $m \ge x$ and $m \ge y$ for all $y \in M - \{x\}$ so $m \ge y$ for all $y \in( M - \{x\}) \cup \{x\} = M$. So $M$ has a maximal element.

.

But if $x > m$ then $x\ge y$ for all $y \in M - \{x\}$ and $x \ge x$ so $x \ge y$ for all $y \in( M - \{x\}) \cup \{x\} = M$. So $M$ has a maximal element.