Can someone read my parts (a) to (d)? I think they're good - however, I'm really stuck on part (e) and would love some help.
Definition: 2 sets X and Y have the same cardinality (card(X)=card(Y)) if there exists a bijection f: X --> Y.
Let $m,n\ge1$ be integers. The point of this problem is to prove that if the sets $\{1,\ldots,m\}$ and $\{1,\ldots,n\}$ have the same cardinality, then $m=n$. For brevity, denote $\{1,\ldots,n\}$ by $[n]$. Show each of the following.
(a) If $f:[m]\rightarrow \{1\}$ is a bijection, then $m=1$.
Proof: Suppose $f:[m]\rightarrow \{1\}$ is a bijection, and suppose (for the sake of contradiction) that $m \neq 1$. Then $m \geq 2$. However, since $f(1),\cdots,f(m)$ all must map to 1, $f: \{1, \cdots, m\} \rightarrow \{1\}$ cannot be injective. This is a contradiction, and so $m=1$.
(b) Fix $k\in[n]$. Define a bijection $g:[n]\rightarrow[n]$ such that $g(k)=n$ and $g(n)=k$.
Proof: Choose an arbitrary $k \in [n]$. We construct a bijection as follows:
g(x)=\begin{cases}
x&x \neq k \text{ and } x \neq n\\
n&x= k\\
k&x=n
\end{cases}
We know that $g$ is bijective if and only if there exists a mapping $f:Y\rightarrow X$ such that $gf=i_Y \text{ and } fg=i_X$. Let $f=g$. We see that for $x \neq k \text{ and } x \neq n$, $g(g(x))=x$; for $x = k$, $g(g(k))=g(n)=k$; and for $x=n$, $g(g(n))=g(k)=n$. Thus, $g$ is bijective.
(c) If $f:[m]\rightarrow[n]$ is a bijection, then there exists another bijection $f':[m]\rightarrow [n]$ so that $f'(m)=n$.
Suppose $f:[m]\rightarrow[n]$ is a bijection. By part (b), we can define a bijection $g: [n] \mapsto [n]$ such that $g(n)=f(m) \text{ and } g((f(m))=n$. Then, the composite map $g \circ f: [m] \mapsto [n]$ is a bijection such that $g(f(m))=n$.
(d) If $f:[m]\rightarrow[n]$ is a bijection and $f(m)=n$, then the restriction of $f$ to $[m-1]$ defines a bijection $[m-1]\rightarrow[n-1]$.
Suppose $f:[m]\rightarrow[n]$ is a bijection, and $f(m)=n$. By restricting the domain of $f$ to $[m-1]$, we also restrict the codomain to $[n-1]$, since $f(m)=n$. Let $f':[m-1] \mapsto [n-1]$ be the restriction of $f$ to $[m-1]$. To see injectivity, suppose $f'(x_1)=f'(x_2)$. Since $f'(x_1)=f(x_1)$ and $f'(x_2)=f(x_2)$, $f(x_1)=f(x_2)$, and since $f$ is injective, $x_1=x_2$. To see surjectivity, choose an arbitrary $y \in [n-1]$. We know $y \in [n]$ and due to the surjectivity of $f$, we know there exists an $x \in [m]$ such that $f(x)=y$. Since $y \neq n \text{ and } x \neq m$ (since $f(m)=n)$, there exists an $x \in [m-1]$ such that $f'(x)=y$, and so $f'$ is surjective. Thus, $f'$ is bijective.
(e) Use induction on $n$ (and the above) to prove that $\text{card}([m])=\text{card}([n])$ implies $m=n$.
Proof: Let $P(n)$ be "$\text{card}([m])=\text{card}([n])$ implies $m=n$."
To see $P(1)$, suppose $\text{card}([m])=\text{card}([1])$. Then, there exists a bijective function $ f:[m]\rightarrow \{1\}$. By part (a), $m=1=n$.
To see $P(n+1)$ assuming $P(n)$, suppose $card([m])=card([n+1])$. Then, there exists a bijective function $f:[m]\rightarrow [n+1]$. By part (c), there exists another bijective function $f': [m] \mapsto [n+1]$ such that $f'(m)=n+1$.
Although I know I should just follow my nose, utilizing parts (a) to (d), I'm really stuck, and honestly confused about the value of m: if we assume p(n), then card(m)=card(n) implies m = n, but then we're trying to show if card(m)=card(n+1), then m = n+1, so what is m?
EDIT: To see $P(n+1)$ assuming $P(n)$, suppose $card([m])=card([n+1])$. Then, there exists a bijective function $f:[m]\rightarrow [n+1]$. By part (c), there exists another bijective function $g: [m] \mapsto [n+1]$ such that $f'(m)=n+1$; and by part (d), there exists a bijective function $g': [m-1] \mapsto [n]$. By $P(n)$, since $card([m-1])=card([n]), \text{ then } m-1=n \Rightarrow m = n +1$ (as long as $m-1 \geq 1$). Thus, $\forall n \geq 1, card([m])=card([n])$ implies $m=n$.
