Induction Proof: If $B \subseteq A$, then $|B| \leq |A|$.

Question

Prove by induction that if $A$ is a finite set and $B$ is a subset of $A$, then $|B|≤ |A|$.

I can prove the base case with $n=0$ easily, but am stuck as to how to proceed from there.

Answer 1

Suppose, via the inductive hypothesis, that if $|A| = k$ and $B \subseteq A$, then $|B| \leq |A|$.

We want to show that if $|A| = k+1$ and $B \subseteq A$, then $|B| \leq |A|$.

Choose any element $x \in B$ (so $x$ also belongs to $A$). The cardinality of the set $A \setminus \{x\}$ is $k$ and $B \setminus \{x\}$ is a subset of $A \setminus \{x\}$, so we conclude $|B \setminus \{x\}| \leq |A \setminus \{x\}|$ by the inductive hypothesis. Now, \begin{align*} |B| &= |B \setminus \{x\}| + 1\\ &\leq |A \setminus \{x\}| + 1\\ &= |A|. \end{align*}