calendar_todayarticle
4410 words
access_time
30 min
replay Modified
Table of Contents
Ways to Count
Ordinal: Arranging things sequentially or making lists
Cardinal: Responding to the question “how many?”
Counting
The establishment of a one-to-one correspondence between objects and a set of numerals
Make steps from a numeral to the successive numeral
For a successor to be defined:
Definition 01.1(Successor Properties).
a. Every object has a unique successor
b. Different objects have different successors
c. There is an object that is not the successor of any object (the “first” object)
The Abstract Number System
A set of objects $\mathbb{N}$ in which there is a successor operation $*$ satisfying the successor properties
Each number system must be a realization of this system
Definition 01.2(Complete Matching).
Identify the “first” elements of both sets, then their successors with each other, then identify the successors of any pair that is already identified. This is a complete matching of the two sets.
Definition 01.3(Extended Successor Property).
A subset of $\mathbb{N}$ is all of $\mathbb{N}$ if it includes the initial element and the successor of each element of $\mathbb{N}$.
Peano Axioms
Axiom(Peano Axiom 1).
Every $n \in \mathbb{N}$ has a unique successor $n^{*} \in \mathbb{N}$.
Axiom(Peano Axiom 2).
$n \ne m \implies n^{*} \ne m^{*}$
Axiom(Peano Axiom 3).
There exists an element (denoted 1), in $\mathbb{N}$ such that $1 \ne n^{*} \ \forall \ n \in \mathbb{N}$.
Axiom(Peano Axiom 4 (Induction Axiom)).
If $S \subset \mathbb{N}$ satisfies
$1 \in S \quad \text{(One-Case)}$
and
$n \in S \Rightarrow n^{*} \in S \quad \text{(Inductive Step)},$
then $S = \mathbb{N}$.
Addition
Definition 01.4(Addition).
$$
\begin{align}
m + 1 &= m^{*}, \\
m + n^{*} &= (m + n)^{*}
\end{align}
$$
Since RHS = LHS, the Inductive Step is complete, and so is the proof.
This shows commutativity holds for the first part of the definition of multiplication. 1 is a neutral element under multiplication since $1 \cdot m = m \cdot 1 = m \ \forall \ m \in \mathbb{N}$
$$\begin{align}
m \cdot (n + 1) &= m \cdot n^* \\
&= m \cdot n + m
\end{align}$$
Since RHS = LHS, the One-Case is complete.
Inductive Step $(k = k^*)$:
$$m \cdot (n + k^*) = m \cdot n + m \cdot k^*$$
RHS:
$$m \cdot n + m \cdot k^*$$
LHS:
$$\begin{align}
m \cdot (n + k^*) &= m \cdot (n+k)^* \\
&= m \cdot (n + k) + m \\
&= m \cdot n + m \cdot k + m \\
&= m \cdot n + m \cdot k^* \\
\end{align}$$
Since RHS = LHS, the Inductive Step is complete and so is the proof.
Proof of Right Distributive Law.(Exercise 11[Pedrick, A First Course in Analysis, p. 23])
One-Case $(m = 1)$:
$$(n + k) \cdot 1 = n \cdot 1 + k \cdot 1$$
RHS:
$$n \cdot 1 + k \cdot 1 = n + k$$
LHS:
$$(n + k) \cdot 1 = n + k$$
Since RHS = LHS, the One-Case is complete.
Inductive Step $(m = m^*)$:
$$(n + k) \cdot m^* = n \cdot m^* + k \cdot m^*$$
RHS:
$$\begin{align}
n \cdot m^* + k \cdot m^* &= n \cdot m + n + k \cdot m + k \\
&= n \cdot m + k \cdot m + n + k
\end{align}$$
LHS:
$$\begin{align}
(n + k) \cdot m^* &= (n + k) \cdot m + (n + k) \\
&= n \cdot m + k \cdot m + n + k
\end{align}$$
Since the RHS = LHS, the Inductive Step is complete, and so is the proof.
$$\begin{align}
n^* \cdot m &= (n + 1) \cdot m \\
&= n \cdot m + 1 \cdot m \\
&= n \cdot m + m
\end{align}$$
LHS:
$$\begin{align}
m \cdot n^* &= m \cdot n + m \\
&= n \cdot m + m
\end{align}$$
Since RHS = LHS, the Inductive Step is complete and so is the proof.
Ordering
$\mathbb{N}$ is naturally ordered
$m < n \implies \exists k \in \mathbb{N} : m + k = n$
Theorem 01.13(Transitive Law).
$l < m \land m < n \Rightarrow l < n$
Theorem 01.14(Trichotomy Property).
$m = n \lor m < n \lor n < m \ \forall \ (m, n) \in \mathbb{N}$
Proof of Trichotomy Property.(EXERCISE 13[Pedrick, A First Course in Analysis, p. 24])
The Peano Axioms imply that $\mathbb{N}$ can be decomposed into three distinct sets:
$\{m \in \mathbb{N}: m < n\}$
$\{n\}$
$\{m \in \mathbb{N}: n < m\}$
Fix $n \in \mathbb{N}$. Define $T = \{ m \in \mathbb{N} : m = n \lor m < n \lor n < m \}$.
One-Case: $1 \in T$
If $n = 1$, then $1 = n$.
If $n \ne 1$, then $1 < n$.
So $1 \in T$.
Inductive Step: Assume $m \in T$. Then one of the following holds:
If $m = n$, then $m^* = n^*$, so $n < m^*$, hence $m^* \in T$.
If $m < n$, then $\exists k \in \mathbb{N}$ such that $m + k = n$.
Then $m^* + k = (m + 1) + k = m + (1 + k) = m + k + 1 = n + 1 = n^*$, so $m^* < n^*$, hence $m^* < n \lor m^* = n \lor n < m^*$, thus $m^* \in T$.
If $n < m$, then $\exists k \in \mathbb{N}$ such that $n + k = m$. Then $n + k + 1 = m^*$, so $n < m^*$, hence $m^* \in T$.
By induction, $T = \mathbb{N}$. Therefore, $m = n \lor m < n \lor n < m$ for all $m, n \in \mathbb{N}$.
Proof of Addition preserves order.(EXERCISE 14[Pedrick, A First Course in Analysis, p. 24])
$m < n \implies \exists \ b \in \mathbb{N}: n = m + b$
$k \in \mathbb{N} \implies m + k = n - b + k$
$n - b + k$ is trivially less than $n + k$, so the proof is complete.
Proof of Multiplication preserves order.(EXERCISE 14[Pedrick, A First Course in Analysis, p. 24])
$m < n \implies \exists \ b \in \mathbb{N}: n = m + b$
$k \in \mathbb{N} \implies m \cdot k = (n - b) \cdot k$
$(n-b) \cdot k$ is trivially less than $n \cdot k$, so the proof is complete.
Remark on Induction
Authors use ellipse or etc. when writing proofs, an implicit use of induction
We can create a “careful” definition that uses induction for these omitted details
Factorial example[Pedrick, A First Course in Analysis, p. 24]
Exponentiation
Definition 01.17(Exponentiation).
(EXERCISE 15[Pedrick, A First Course in Analysis, p. 24])
$$\begin{align}
m ^ 1 &= m \\
m^{n^*} &=m^n \cdot m
\end{align}$$
Theorem 01.18(Exponent Addition Law).
$$m^n \cdot m^k = m^{n + k}$$
Theorem 01.19(Exponent Distributive Law).
$$(m \cdot n)^k = m^k \cdot n^k$$
Theorem 01.20(Exponent Multiplication Law).
$$\left(m^n\right)^k = m^{n \cdot k}$$
Proof of Exponent Addition Law.(EXERCISE 16[Pedrick, A First Course in Analysis, p. 24])
One-Case $(k = 1)$:
Since RHS = LHS, the Inductive Step is complete and so is the proof.
Miscellaneous Proofs with Induction
Proof.(EXERCISE 17[Pedrick, A First Course in Analysis, p. 26])
One-Case $(n = 1)$:
$$(1 + x)^1 \ge 1 + 1 \cdot x$$
RHS:
$$1 + 1 \cdot x = 1 + x$$
LHS:
$$(1 + x)^1 = 1 + x$$
Since RHS = LHS, $\ge$ can be refined to =, and the One-Case holds. This also implies all choices of $x$ work when $n=1$.
Inductive Step $(n = n^*)$:
$$(1 + x)^{n^*} \ge 1 + n^* \cdot x$$
RHS:
$$1 + n^* \cdot x = 1 + n \cdot x + x$$
LHS:
$$\begin{align}
(1 + x)^{n^*} &= (1+x)^n(1+x) \\
&\ge (1+ n \cdot x)(1+x) \\
&= 1 + n \cdot x + x + n \cdot x^2
\end{align}$$
Since LHS contains an extra $n \cdot x^2$ than the RHS, which is guaranteed to be positive for $x \ge -1$, the Inductive Step is complete and so is the proof. The inequality does not hold for $x < -1$ because $(1 + x)$ would be negative, reversing the inequality.
Proof.EXERCISE 18[Pedrick, A First Course in Analysis, p. 26]
One-Case $(n=1)$:
Since RHS = LHS, the Inductive Step is complete. However, the One-Case fails for any arbitrary $n$. This is why the One-Case should never be overlooked in an inductive proof.
Exercise 01.23.
(EXERCISE 22[Pedrick, A First Course in Analysis, p. 26])
One-Case $(n = 1)$:
$S \subset \mathbb{N}$ is all of $\mathbb{N}$ if $1 \in S$ and $\{1, 2, \dots , k\} \subset S$ implies $k+1 \in S$
This is a type of induction that uses all numbers up to and including $n$ to imply $n^*$ rather than just $n$
Proposition 01.28.
Every nonempty set of natural numbers has a first member.
Proof[Pedrick, A First Course in Analysis, p. 27]
Sequence
A sequence of a set $S$ maps $n \in \mathbb{N}$ to $x \in S$
They are infinite by definition and repetition of values in $S$ is allowed
The $n$th value of the sequence is denoted $x_n$
The sequence itself is indicated by writing its typical value in brackets (e.g. $\{1/n\}$ or $\{x_n\}$)
Exercise 01.29.
(EXERCISE 28[Pedrick, A First Course in Analysis, p. 28])
Part I:
One-Case $(n = 1)$:
$$a ^ 1 - b ^ 1 = k_{1}(a - b)$$
This is trivially true with $k_{1} =1 \in \mathbb{N}$
Inductive Step $(n = n^*)$:
Since RHS = LHS, the Inductive Step is complete, and so is the proof.
More on Sequences
The value set of a sequence is the set of all points of $x_n$ (the range)
If the value set has one point, $x_n$ is a constant sequence
$x_n$ may be restricted to an infinite subset of $\mathbb{N}$ to create a subsequence
“Infinite” means the sequence extends beyond $m$ for any $m \in \mathbb{N}$
Definition 01.30.
Every infinite subset, $\mathbf{K}$, of $\mathbb{N}$ is injective over $\mathbb{N}$, starting with $n_1 =$ the first element of $\mathbf{K}$. The notation is $\{x_{n_k}\}$, where $n_k$ is the first unmatched integer.
Proof.(EXERCISE 29[Pedrick, A First Course in Analysis, p. 29])
Consider any finite list of prime numbers $p_1, p_2, \ldots, p_n$. It will be shown that there exists at least one additional prime number not included in this list.
Let $P$ be the product of all the prime numbers in the list:
$$
P = p_1 p_2 \cdots p_n.
$$
Let $q = P + 1$. Then $q$ is either prime or not:
If $q$ is prime, then there is at least one more prime that is not in the list, namely, $q$ itself.
If $q$ is not prime, then some prime factor $p$ divides $q$. If this factor $p$ were in our list, then it would also divide $P$ (since $P$ is the product of every number in the list). If $p$ divides both $P$ and $q$, then $p$ must also divide the difference of the two numbers:
$$
q - P = (P + 1) - P = 1.
$$
Since no prime number divides 1, $p$ cannot be in the list. This means that at least one more prime number exists that is not in the list.
Extending $\mathbb{N}$ to $\mathbb{Z}$
Given $m, n \in \mathbb{N}$, solve $m + x = n$
There is no such $x \in \mathbb{N}$ when $n \le m$
$\mathbb{N} \cup \{0\}$
Adjoining 0 to $\mathbb{N}$ gives us the solution for the equations $n + x = n$, for any $n$ in this new set of numbers.
$\forall \ n \in \mathbb{N} \cup 0$:
$0 + n = n + 0 = n$
$0 \cdot n = n \cdot 0 = 0$
$0 < n$
Creating $\mathbb{Z}$
We create a “negative $k$” that solves $m + x = n$ when $n < m$
This results in $\mathbb{Z} = \{-k: k \in \mathbb{N}\} \cup \{0\} \cup \mathbb{N}$ for which the solution is denoted $n-m$
$\forall \ z \in \mathbb{Z}$, the solution $x$ of $z + x = 0$ is the additive inverse of $z$
Exercise 01.31.
(EXERCISE 30[Pedrick, A First Course in Analysis, p. 30])
Using the definition of additive inverse:
Therefore, $(-k) \cdot l = -(k \cdot l)$
Exercise 01.32.
(EXERCISE 31[Pedrick, A First Course in Analysis, p. 30])
Definition 01.33(Cancellation Law for Addition).
$$m + k = n + k \implies m = n$$
Proof.(EXERCISE 32[Pedrick, A First Course in Analysis, p. 30])
Definition 01.34(Cancellation Law for Multiplication).
$$m \cdot k = n \cdot k \implies m = n; k \ne 0$$
Proof.(EXERCISE 33[Pedrick, A First Course in Analysis, p. 30])
Definition 01.35(Inequality Reversing).
$$m < n \implies -m > -n$$
Proof.(EXERCISE 34[Pedrick, A First Course in Analysis, p. 30])
Binomial
Definition 01.36(Binomial Coefficients).
Define $0! = 1$ and
$${n\choose k} = \frac{n!}{k!(n-k)!}$$
Proposition 01.37(Addition of Binomial Coefficients).
