数学归纳法是一种数学证明方法，通常被用于证明某个给定命题在整个自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，Peano公理告诉我们数学归纳法本质上是正整数公理的一部分。作为数学分析（实分析）的开端，学习正整数和实数的构造是第一步。下面是一些典型的Math 115A 第一次assignment可能会出现的典型题目。
Use mathematical induction to show that $n^{3}+5 n$ is divisible by 6 for all $n \in \mathbb{N}$
$$
(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)$
$$
\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.
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).
$$
\{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.
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.
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.
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.
$$
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).
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.
$$
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).
$$
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.
real analysis代写， math 115A代写，实分析代写， 数学分析代写请认准UpriviateTA. UpriviateTA为您的留学生涯保驾护航。
更多内容请参阅另外一份Galois代写.
[…] 更多内容请参阅另外一份Math115代写. […]
[…] 更多内容请参阅另外一份Math115代写. […]
[…] 更多内容请参阅另外一份Math115代写. […]
[…] 更多内容请参阅另外一份Math115代写. […]
[…] 更多内容请参阅另外一份Math115代写. […]
[…] 更多内容请参阅另外一份Math115代写. […]