0 0

By admin 数学代写 2022年2月22日

Definition 2.7.1 A set is well ordered if every nonempty subset $S$, contains a smallest element $z$ having the property that $z \leq x$ for all $x \in S$.
Axiom 2.7.2 Any set of integers larger than a given number is well ordened.
In particular, the natural numbers defined as $\mathbb{N} \equiv{1,2, \cdots}$ is well ordered.
The above axiom implies the principle of mathematical induction.
Theorem $2.7 .3$ (Mathematical indwction) A set $S \subseteq \mathbb{Z}$, having the property that $a \in S$ and $n+1 \in S$ whenever $n \in S$ contains all integers $x \in \mathbb{Z}$ such that $x \geq a$.
Proof: Let $T \equiv([a, \infty) \cap \mathbb{Z}) \backslash S$. Thus $T$ consists of all integers larger than or equal to $a$ which are not in $S$. The theorem will be proved if $T=\emptyset .$ If $T \neq \emptyset$ then by the well ordering principle, there would have to exist a smallest element of $T$, denoted as $b$. It must be the case that $b>a$ since by definition, $a \notin T$. Then the integer, $b-1 \geq a$ and $b-1 \notin S$ because if $b-1 \in S$, then $b-1+1=b \in S$ by the assumed property of $S$. Therefore, $b-1 \in([a, \infty) \cap \mathbb{Z}) \backslash S=T$ which contradicts the choice of $b$ as the smallest element of $T$. ( $b-1$ is smaller.) Since a contradiction is obtained by assuming $T \neq \emptyset$, it must be the case that $T=\emptyset$ and this says that everything in $[a, \infty) \cap \mathbb{Z}$ is also in $S$.
Mathematical induction is a very useful device for proving theorems about the integers.
Example 2.7.4 Prove by induction that $\sum_{k-1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}$.
By inspection, if $n=1$ then the formuls is true. The sum yields 1 and so does the formula on the right. Suppose this formuls is valid for some $n \geq 1$ where $n$ is an integer. Then
$$
\sum_{k=1}^{n+1} k^{2}=\sum_{k=1}^{n} k^{2}+(n+1)^{2}=\frac{n(n+1)(2 n+1)}{6}+(n+1)^{2}
$$
The step going from the first to the second equality is based on the assumption that the formula is true for $n$. This is called the induction hypothesis. Now simplify the expression in the second line,
$$
\frac{n(n+1)(2 n+1)}{6}+(n+1)^{2} .
$$This equals $(n+1)\left(\frac{n(2 n+1)}{6}+(n+1)\right)$ and
$$
\frac{n(2 n+1)}{6}+(n+1)=\frac{6(n+1)+2 n^{2}+n}{6}=\frac{(n+2)(2 n+3)}{6}
$$
Therefore,
$$
\sum_{k=1}^{n+1} k^{2}=\frac{(n+1)(n+2)(2 n+3)}{6}=\frac{(n+1)((n+1)+1)(2(n+1)+1)}{6}
$$
showing the formula holds for $n+1$ whenever it holds for $n$. This proves the formula by mathematical induction.
Example $2.7 .5$ Show that for all $n \in \mathbb{N}, \frac{1}{2} \cdot \frac{3}{4} \ldots \frac{2 n-1}{2 n}<\frac{1}{\sqrt{2 n+1}}$. If $n=1$ this reduces to the statement that $\frac{1}{2}<\frac{1}{\sqrt{3}}$ which is obviously true. Suppose then that the inequality holds for $n$. Then $$ \frac{1}{2} \cdot \frac{3}{4} \cdots \frac{2 n-1}{2 n} \cdot \frac{2 n+1}{2 n+2}<\frac{1}{\sqrt{2 n+1}} \frac{2 n+1}{2 n+2}=\frac{\sqrt{2 n+1}}{2 n+2} $$ The theorem will be proved if this last expression is less than $\frac{1}{\sqrt{2 n+3}}$. This happens if and only if $$ \left(\frac{1}{\sqrt{2 n+3}}\right)^{2}=\frac{1}{2 n+3}>\frac{2 n+1}{(2 n+2)^{2}}
$$
which occurs if and only if $(2 n+2)^{2}>(2 n+3)(2 n+1)$ and this is clearly true which may be seen from expanding both sides. This proves the inequality.
Lets review the process just used. If $S$ is the set of integers at least as large as 1 for which the formula holds, the first step was to show $1 \in S$ and then that whenever $n \in S$, it follows $n+1 \in S$. Therefore, by the principle of mathematical induction, $S$ contains $[1, \infty) \cap \mathbb{Z}$, all positive integers. In doing an inductive proof of this sort, the set, $S$ is normally not mentioned. One just verifies the steps above. First show the thing is true for some $a \in \mathbb{Z}$ and then verify that whenever it is true for $m$ it follows it is also true for $m+1$. When this has been done, the theorem has been proved for all $m \geq a$.

定义 2.7.1 如果每个非空子集 $S$ 包含一个最小元素 $z$，则一个集合是良序的，该元素具有 $z \leq x$ for all $x \in S$ 的性质。公理 2.7.2 任何大于给定数的整数集都是有序的。特别是，定义为 $\mathbb{N} \equiv\{1,2, \cdots\}$ 的自然数是有序的。上述公理隐含了数学归纳法的原理。定理 $2.7 .3$ (数学推理) 一个集合 $S \subseteq \mathbb{Z}$，具有 $a \in S$ 和 $n+1 \in S$ 的性质，只要 $n \in S$ 包含所有整数 $x \in \mathbb{Z}$ 使得 $x \geq a$. 证明：设$T \equiv([a, \infty) \cap \mathbb{Z}) \backslash S$。因此，$T$ 包含所有大于或等于 $a$ 且不在 $S$ 中的整数。如果$T=\emptyset .$ 将证明该定理如果$T\neq \emptyset$ 则根据井序原理，必须存在$T$ 的最小元素，记为$b$。它必须是 $b>a$，因为根据定义，$a \notin T$。然后是整数，$b-1 \geq a$ 和 $b-1 \notin S$ 因为如果 $b-1 \in S$，那么 $b-1+1=b \in S$ 由假定的属性美元。因此，$b-1 \in([a, \infty) \cap \mathbb{Z}) \backslash S=T$ 与选择 $b$ 作为 $T$ 的最小元素相矛盾。（$b-1$ 更小。）由于假设 $T \neq \emptyset$ 得到矛盾，因此必须满足 $T=\emptyset$ 并且这表示 $[a, \infty) 中的所有内容\cap \mathbb{Z}$ 也是 $S$。数学归纳法是证明整数定理的一种非常有用的工具。例 2.7.4 通过归纳证明 $\sum_{k-1}^{n} k^{2}=\frac{n(n+1)(2 n+1)}{6}$。通过检查，如果 $n=1$ 则公式为真。总和产生 1，右边的公式也是如此。假设这个公式对某些 $n \geq 1$ 有效，其中 $n$ 是一个整数。然后 $$ \sum_{k=1}^{n+1} k^{2}=\sum_{k=1}^{n} k^{2}+(n+1)^{2}=\frac{n (n+1)(2 n+1)}{6}+(n+1)^{2} $$ 从第一个等式到第二个等式的步骤是基于公式对 $n$ 成立的假设。这称为归纳假设。现在简化第二行的表达式， $$ \frac{n(n+1)(2 n+1)}{6}+(n+1)^{2} 。 $$