Mathematical induction, Well-ordering principle
Mathematical Induction. Let $A \subseteq \mathbb{N}$. If $A$ satisfies
(1) $1 \in A$,
(2) If $n \in A$ then $n+l \in A$.
Then $A=\mathbb{N}$.
Well-Ordering Principle. Let $A \subseteq \mathbb{N}, A \neq \varnothing$.
Then there exists the minimum of $A$
Proposition. Mathematical Induction (M.I.) and Well-Ordering Principle (W.O) are equivalent.
Proof. 1) W.O $\Rightarrow$ M.I.
Suppose M.I is false. i.e., let $A \subseteq \mathbb{N}$ satisfying (1) and (2), but $\frac{A \neq \mathbb{N}}{(*)}$.
By $(*), \quad N-A \neq \varnothing$ which is a proper subset of $\mathbb{N}$.
Apply W.O. Then there exists the minimum $m_{0} \in$$\mathbb{N – A}$.
But, $1 \in A$, which implies $2 \in A$.
$\ldots \Rightarrow m_{0} \in A . \Rightarrow m_{0} \in A$ and $m_{0} \notin A $ which is a contradiction.
Thus $A=\mathbb{N}$.
2) M.I. $\Rightarrow$ W.O.
Let $A$ be non-empty subset of $\mathbb{N}$.
Suppose w.o is false for A i.e., there is no minimum of $A$.
Define $B:=\{k \in \mathbb{N} \mid K \leq n$, for any $n \in A\}$.
Since $ 1\notin A, 1\in B .(\Rightarrow B \neq \varnothing)$
Let $m \in B$, then $m \notin A$.
Thus $m+1 \in B$ (For any $n \in A, m<n \leadsto m+1 \leq n$).
By M.I., $B=\mathbb{N} \Rightarrow A=\varnothing$ which is a contradiction.
Archimedean property (A.P)
Let $x,y \in R$ with $x >0 $. Then there exists $n \in \mathbb{N}$ such that $n*x>y$.
Remark.
(1) Take $x=\varepsilon>0, y=1$
Then by A.P, there exists $n \in \mathbb{N}$ such that $n-\varepsilon>1$.
Equivalently, $\frac{1}{n}<\varepsilon$.
(2) Let $E \subseteq \mathbb{R}$ be a non-empty, bounded above.
$\Rightarrow$ there exists $\operatorname{sap} E=\beta \in \mathbb{R}$.
$\Leftrightarrow$ For each $\varepsilon>0$, there exists $x_{\varepsilon} \in E$ such that
$\beta-\varepsilon<x_{\varepsilon} \leq \beta$.
In particular, for each $n \in \mathbb{N}\left(\varepsilon=\frac{1}{n}\right)$, there exists $x_{n} \in E$ such that
$\beta-\frac{1}{n}<x_{n} \leq \beta$ : (**).
In fact, the converse also holds. Indeed, suppose (**) holds
Let $\varepsilon>0$ be fixed. Then A.P, there exists $n \in \mathbb{N}$ such that $\frac{1}{n}<\varepsilon$ (by (1))
$\Leftrightarrow-\frac{1}{n}>-\varepsilon \Leftrightarrow \beta-\frac{1}{n}>\beta-\varepsilon$
Thus for each $\varepsilon>0$, there exists $n \in \mathbb{N}$ such that, for corresponding $x_{n} \in E$ satisfying
$\beta-\varepsilon<\beta-\frac{1}{n}<x_{n} \leq \beta$.
Consequently, we have a seq $\left(x_{n}\right)_{n=1}^{\infty}$ such that $\lim _{n \rightarrow \infty} x_{n}=\beta$
Note. 위의 논지는 $\beta$를 handling 하는 과정을 $\beta$로 수렴하는 수열로 환원하여 다룰 수 있고, 이 과정에서 uncountable한 $\epsilon>0$의 선택지를 countable한 $n\in \mathbb{N}$으로 다룰 수 있음을 시사한다.
Proof of Archimedean Property.
If $y \leq 0$, take $n=1 (n \cdot x>y)$.
So, suppose $y>0$( $x>0$ is already fixed).
Claim: there exists $n \in \mathbb{N}$ st $n \cdot x>y$.
Suppose not, i.e, for each $n \in \mathbb{N}, n x \leq y$
Define $E:=\left\{ nx : n \in \mathbb{N} \right\}$.
Then $\phi \neq E \subseteq \mathbb{R}, E$ is bounded above by $y$
Thus there exists sup $E \in \mathbb{R}$.
Since $x>0, \beta-x<\beta$, $\beta-x$ is not an upper bound of $E$.
So there exists $n \in \mathbb{N}$ s.t $\beta-x < n\cdot x \leq \beta$.
$\Rightarrow \beta<(n+1) x, n+1 \in \mathbb{N} \Rightarrow(n+1) x \in E$ : contradiction.
since $B$ is an upper bound.
Density of $\mathbb{Q}$ (유리수의 조밀성)
For any $x, y \in \mathbb{R}$, with $x<y$, there exists $r \in Q$ set $x<r<y$
Proof. (3) Cases for $x<y$
It suffices to show (2)
since $x<y, y-x>0$
with 1, there exists $n \in \mathbb{N}$ such that $n \cdot(y-x)>1$ by A.P $\Leftrightarrow n x+1<n y$.
(Purpose $x<\frac{m}{n}<y$).
Define $A:=\{k \in \mathbb{N} \mid n x<k\} \neq \varnothing$.
$$
\Rightarrow \phi \neq A \subseteq \mathbb{N}
$$
By W.O, there exists the smallest element $m_{0} \in A$.
i.e., $n x<m_{0}$ but $n x \geq m_{0}-1$.
So, $m_{0}-1 \leqslant n x<m_{0}$.
$$
\begin{gathered}
\Rightarrow n x<m_{0} \leq n x+1 \stackrel{A \cdot P}{<} n \cdot y \\
\Rightarrow n x<m_{0}<n y \\
\Leftrightarrow x<\frac{m_{0}}{n}<y.
\end{gathered}
$$