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.

real analysis代写， math 115A代写，实分析代写， 数学分析代写请认准UpriviateTA. UpriviateTA为您的留学生涯保驾护航。

real analysis代写analysis 2, analysis 3请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。

# 概率论代考

## 复变函数代写

#### Real Analysis代写| Topology of the Real Number Line代写|R上的拓扑代写 代写 代写 | 数学代写数学答疑数学辅导 · 2021年2月20日 at 下午12:33

[…] 更多内容请参阅另外一份Math115代写. […]

#### 实分析代写| Topology of the Real Number Line代写|实轴的拓扑代写 代写 代写 | 数学代写数学答疑数学辅导 · 2021年2月20日 at 下午1:26

[…] 更多内容请参阅另外一份Math115代写. […]

#### 实分析代写| Topology of the Real Number Line代写|实轴的拓扑代写|Math115A代写 代写 代写 | 数学代写数学答疑数学辅导 · 2021年2月20日 at 下午6:36

[…] 更多内容请参阅另外一份Math115代写. […]

#### 实分析代写| 极限的定义代写|limit代写|Math115A代写|番外篇 代写 代写 | 数学代写数学答疑数学辅导 · 2021年2月20日 at 下午6:52

[…] 更多内容请参阅另外一份Math115代写. […]

#### 实分析代写| 极限的定义代写|limit代写|Math115A代写 代写 代写 | 数学代写数学答疑数学辅导 · 2021年2月20日 at 下午7:06

[…] 更多内容请参阅另外一份Math115代写. […]

#### STATS 101A|Note1 代写 代写 | 数学代写数学答疑数学辅导 · 2021年2月23日 at 上午9:30

[…] 更多内容请参阅另外一份Math115代写. […]