数学归纳法是一种数学证明方法，通常被用于证明某个给定命题在整个自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，Peano公理告诉我们数学归纳法本质上是正整数公理的一部分。作为数学分析（实分析）的开端，学习正整数和实数的构造是第一步。下面是一些典型的Math 115A 第一次assignment可能会出现的典型题目。

Problem 1. [
Use mathematical induction to show that $n^{3}+5 n$ is divisible by 6 for all $n \in \mathbb{N}$

Proof . When $n=1$ we have $n^{3}+5 n=6$ which is obviously divisible by $6 .$ Now suppose the assertion is true for $n,$ then
$$
(n+1)^{3}+5(n+1)=n^{3}+3 n^{2}+3 n+1+5 n+5=n^{3}+5 n+3 n(n+1)+6
$$
By inductive hypothesis, it remains to prove that $3 n(n+1)$ is divisible by $6 .$ But this is easy as there must be an even number between two consecutive natural numbers, so 2 divides $n(n+1),$ which implies 6 divides $3 n(n+1)$

Problem 2. Show that there is no $x \in \mathbb{Q}$ so that $x^{2}=6$.

Proof . Suppose for a contradiction that there is $p, q \in \mathbb{N}$ such that $x=p / q$ in lowest terms (that is, the greatest common divisor of $p$ and $q$ is 1 ). Then
$$
\frac{p^{2}}{q^{2}}=6 \Longrightarrow p^{2}=6 q^{2}
$$
This means $p$ has to be even. Writing $p=2 p_{0}$ and inserting it in the above equation yields
$$
4 p_{0}^{2}=6 q^{2} \Longrightarrow 2 p_{0}^{2}=3 q^{2}
$$
This means $q$ has to be even as well, contradicting the fact that $x$ is expressed in lowest terms.

Problem 3. For a given number $n \in \mathbb{N}$ with $n>1,$ use the well ordering principle of $\mathbb{N}$ to show that $n$ has at least one prime factor. (Hint: Consider $F_{n}$ the set of factors of $n$ which are greater than 1 ).

Proof . As the hint suggests, let $F_{n}$ be the set of factors of $n$ which is greater than $1 .$ Note $F_{n}$ is not empty since $n \in F_{n} .$ By well-ordering principle there is a least element, say $p,$ in $F_{n} .$ We claim that $p$ is a prime. Indeed, suppose that $p$ is not a prime, then we can write $p=p_{0} q_{0}$ where $p_{0}, q_{0}>1$ are factors of $p$. It follows that $p_{0}<p$ and $p_{0} \in F_{n}$, a contradiction to our choice of $p$.

Problem 4.

For any set $A$, let $2^{A}=\left\{f: f: A \rightarrow \mathbb{N}_{2}\right\}$. Show that $2^{A}$ is in bijection with $P(A),$ the power set of $A$. Here, $\mathbb{N}_{N}=\{1,2, \ldots, N\} \subset \mathbb{N}$. (Hint: Construct natural maps between the two sets).

Proof . Consider the map $F: 2^{A} \rightarrow P(A)$ constructed in the following way: given $f \in 2^{A}, F$ sends $f$ to the set
$$
\{a \in A \mid f(a)=2\}
$$
That is, the subset of $A$ whose element are those mapped to 1 by $f . F$ is an injection: given two distict maps $f$ and $g$ there is $a_{0} \in A$ such that $f\left(a_{0}\right) \neq g\left(a_{0}\right) .$ Say $f\left(a_{0}\right)=2$ and $g\left(a_{0}\right)=1,$ then $a_{0} \in F(f)$ but $a_{0} \neq F(g),$ so $F(f) \neq F(g) . F$ is also a surjection: given any $A_{0} \subset A$ we let $f_{0} \in 2^{A}$ be defined as
$$
f_{0}(a)=\left\{\begin{array}{ll}
2 & a \in A_{0} \\
1 & a \notin A_{0}
\end{array}\right.
$$
One easily checks that $F\left(f_{0}\right)=A_{0} .$ So $F$ is the desired bijection.

Problem 5.

Show that every subset of $\mathbb{N}$ is either finite or countable (Hint: Use the well ordering property of $\mathbb{N}$ ). Conclude that every subset of a countable set is finite or countable.

Proof .

Let $A$ be a subset of $\mathbb{N}$ that is not finite. By the well-ordering principle there is a least element of $A,$ say $a_{1} .$ Since $A$ is not finite, so is $A \backslash\left\{a_{1}\right\}$ and there is another least element of $A \backslash\left\{a_{1}\right\},$ say $a_{2}$ Continuing this way, we can define a map $f: \mathbb{N} \rightarrow A$ inductively by assigning $f(1)=a_{1},$ and, having defined $f(1), \ldots, f(n), f(n+1)=a_{n+1},$ the least element of the (infinite) set $A \backslash\{f(1), \ldots, f(n)\},$ for $n \geq 1$. One easily checks that $f$ is a bijection and so $A$ is countable.

In general given any countable set $B,$ let $g: B \rightarrow \mathbb{N}$ be a bijection. A subset of $B_{0} \subset B$ is in bijection with $g\left(B_{0}\right),$ which is finite or countable by the above paragraph.

Problem 6.

Let $A_{n}$ be collection of countable sets, where $n \in \mathbb{N}$. Show that
$A=\bigcup_{n \in \mathbb{N}} A_{n}=\left\{x: \exists n \in \mathbb{N}\right.$ so that $\left.x \in A_{n}\right\}$
is countable.

Proof . Let $f_{n}: \mathbb{N} \rightarrow A_{n}$ be the corresponding bijections. Let
$$
G=\left\{2^{n} 3^{m} \mid n, m \in \mathbb{N}\right\}
$$
$G$ is evidently countable as a subset of $\mathbb{N}$ by Problem $5 .$ Now define $f: G \rightarrow A$ by
$$
f\left(2^{n} 3^{m}\right)=f_{n}(m)
$$
One checks easily that $f$ is indeed a surjection, so $A$ is at most countable. Finally note that $A_{1}$ is countable and $A_{1} \subset A,$ so $A$ is countable (that is, $A$ cannot be finite).

Problem 7.

a) Show that if both $A$ and $B$ are countable, then so is $A \times B$.
b) Show that $\mathbb{Q}$, the set of rational numbers, is countable.
Problem #8. Determine whether, $P_{\text {finite }}(\mathbb{N})$ the set of all finite subsets of $\mathbb{N},$ is countable.

Proof . Let $f_{B}: \mathbb{N} \rightarrow B$ be a bijection, then
$$
A \times B=\bigcup_{n \in \mathbb{N}} A \times\left\{f_{B}(n)\right\}
$$
which is countable by Problem 6 (applied to $A_{n}=A \times\left\{f_{B}(n)\right\}$ which is countable). To see $\mathbb{Q}$ is countable, let $f: \mathbb{Z} \times \mathbb{N} \backslash\{0\} \rightarrow \mathbb{Q}$ be given by $f(p, q)=p / q . f$ is a surjection so
$$
|\mathbb{Q}| \leq|\mathbb{Z} \times \mathbb{N} \backslash\{0\}|
$$
the right hand side of which is countable by part a).

Problem 8. Determine whether, $P_{\text {finite }}(\mathbb{N})$ the set of all finite subsets of $\mathbb{N},$ is countable.

Proof . We claim that $P_{\text {finite }}(\mathbb{N})$ is countable. Denote by $P_{n}(\mathbb{N})$ the subsets of $\mathbb{N}$ of exactly $n$ elements, then
$$
P_{\text {finite }}(\mathbb{N})=\bigcup_{n \in \mathbb{N}} P_{n}(\mathbb{N})
$$
By Problem $6,$ it remains to show that each $P_{n}(\mathbb{N})$ is countable. To see this, denote by $P_{n}\left(\mathbb{N}_{m}\right)$ the subsets of $\mathbb{N}_{m}=\{1, \ldots, m\}$ of exactly $n$ elements (so when $n>m, P_{n}\left(\mathbb{N}_{m}\right)=\emptyset$ ). Then we can write
$$
P_{n}(\mathbb{N})=\bigcup_{m \in \mathbb{N}} P_{n}\left(\mathbb{N}_{m}\right)
$$
which is countable by Problem $6,$ since this time every set on the right hand side is finite.