note-math

Natural number $ℕ$ addition

$𝑎$ is counting $𝑎$ times $1$ , $𝑎 + 𝑏$ is counting $𝑎$ times first, then counting $𝑏$ times

Associative law: $(𝑎 + 𝑏) + 𝑐 = 𝑎 + (𝑏 + 𝑐)$
Commutative law: $𝑎 + 𝑏 = 𝑏 + 𝑎$

Proof The intuition in the real world is that for counting $+ 1$ , no matter how the counting task is manually divided into several subtasks, the result will not be affected, and the total decomposition methods are limited. The associative and commutative laws of addition are just special cases. Just as we recognize natural numbers by counting, we can always recognize the commutative and associative laws by counting. Everything reduces to the case of complete additive decomposition, with only the commutative and associative laws of a large number of $1$ s.

It seems difficult for computers to express this intuition, but it seems that all finite results must be correct. Similar to what is done in #link(<natural-number>)[], in order for computers to express this property, which holds for all natural numbers, using finite characters, memory, and finite time (and potentially infinite time), it needs to be defined as a true proposition.

The usual "proof" is to use the smallest assumption, the associative law of $1$ , $(𝑎 + 𝑏) + 1 = 𝑎 + (𝑏 + 1)$ or the definition of addition $(𝑎 + 1) + 𝑏 = (𝑎 + 𝑏) + 1$ , and then deduce other

Natural number $ℕ$ multiplication

$𝑎 \cdot 𝑏$ is counting $𝑎$ times of counting $𝑏$ times

It also satisfies the commutative and associative laws. The intuition in the real world is "two-dimensional and three-dimensional rectangles". For counting $+ 1$ , no matter how it is decomposed into subtasks of product decomposition, it will not affect the result. Therefore, the commutative and associative laws of multiplication are just special cases of complete multiplication decomposition i.e. prime factorization, and the total number of decompositions is limited

Distributive law of natural number operations

$(𝑎 + 𝑏) \cdot 𝑐 = 𝑎 \cdot 𝑐 + 𝑏 \cdot 𝑐$

The intuition is to decompose the side length of a two-dimensional rectangle into sum

Integer $ℤ$

The number axis has two directions

Rational number $ℚ$

$𝑛$ equal division operation, the inverse of multiplication $\frac{1}{𝑛}$

Do not confuse it with the division and remainder of $ℕ, ℤ$ , which is a successive subtraction of a number $𝑎$ by another number $𝑏$ , rather than equal division

Real number $ℝ$

One intuition of real numbers is length

Given the intuitiveness of real numbers, we can assume that it exists and use many axioms to define real numbers i.e. assume a true proposition. But you can also "recover" real numbers from rational numbers

Examples of irrational numbers

Algebraic integer $algebraic-integer ≔ {𝑥 \in ℝ : (𝑥^{𝑛} + 𝑎_{𝑛 - 1} 𝑥^{𝑛 - 1} + \dots + 𝑎_{0} = 0) \land (𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑛 - 1} \in ℤ)}$

The "integer" in algebraic integer is because $algebraic-integer \cap ℚ = ℤ$

Proof (p.43 of ref-8)

Take $𝑝, 𝑞 \in ℤ$ and make them relatively prime. Substitute $𝑥 = \frac{𝑝}{𝑞}$ into the equation, multiply by $𝑞^{𝑛}$

\begin{matrix} 𝑝^{𝑛} + 𝑎_{𝑛 - 1} 𝑞 𝑝^{𝑛 - 1} + \dots + 𝑎_{0} 𝑞^{𝑛} = 0 \\ 𝑝^{𝑛} = - 𝑞 (𝑎_{𝑛 - 1} 𝑝^{𝑛 - 1} + \dots + 𝑎_{0} 𝑞^{𝑛 - 1}) \end{matrix}

The right side is divisible by $𝑞$ . But $𝑝, 𝑞$ are relatively prime, so $𝑞 = \pm 1$ or $𝑝 = \pm 1$ .

$𝑝 \neq \pm 1 ⟹ 𝑞 = \pm 1$

$𝑝 = \pm 1 ⟹ \pm 1 = 𝑝^{𝑛} = 𝑞 \cdot some-integer ⟹ 𝑞 = \pm 1$

So $𝑞 = \pm 1$ . Thus $𝑥 = \pm 𝑝 \in ℤ$

Special case ${𝑥 \in ℚ : 𝑥^{2} - 2 = 0}$ . But ${(\pm 1)}^{2} = 1$ and $| 𝑥 | \geq 2 ⟹ | 𝑥 |^{2} \geq 4$

So ${𝑥 \in ℚ : 𝑥^{2} - 2 = 0} = \emptyset$ that is $\sqrt{2}$ is not a rational number

Algebraic number $algebraic-number ≔ {𝑥 \in ℝ : (𝑎_{𝑛} 𝑥^{𝑛} + 𝑎_{𝑛 - 1} 𝑥^{𝑛 - 1} + \dots + 𝑎_{0} = 0) \land (𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑛} \in ℤ)}$

Note that $𝑎_{𝑛} = 1$ is not required, $𝑥 \in ℚ$ is not restricted, including all rational numbers $\frac{𝑝}{𝑞}$ , some irrational numbers e.g. $\sqrt{2}$

Algebraic number $algebraic-number$ is a countable set, real number $ℝ$ is an uncountable set

Transcendental number $transcendental-number ≔ ℝ ∖ algebraic-number \neq \emptyset$ . $𝑒, 𝜋$ are transcendental numbers

Decimal, binary vs nested interval vs segmentation

Decimal (nested interval) seems very intuitive

However, decimal cannot natively handle $𝑒 = \sum_{𝑛 = 0}^{\infty} \frac{1}{𝑛!}$

Many different $ℕ$ nested intervals have the same limit, e.g. $[0, \frac{1}{𝑛}]$ vs $[- \frac{1}{𝑛}, 0]$ , need limit-distance-vanish system quotient. let $distance (𝐴) = \sup_{𝑥, 𝑥^{'} \in 𝐴} | 𝑥 - 𝑥^{'} |$

let $𝐴_{0} \supset 𝐴_{1} \dots, 𝐵_{0} \supset 𝐵_{1} \dots$ and $lim_{𝑛 \to \infty} distance (𝐴_{𝑛}), distance (𝐵_{𝑛}) = 0$ , limit-distance-vanish relation (alias Cauchy convergence)

\forall (𝜀 \in ℚ) \land (𝜀 > 0), \exists 𝑁 \in ℕ, \forall 𝑛, 𝑚 > 𝑁, distance (𝐴_{𝑛} \cup 𝐵_{𝑚}) < 𝜀

You can change the $ℕ$ rational number interval nesting to a general rational number interval whose length #link(<hom-limit>)[limit] tends to zero $\subset$ #link(<maximal-linear-order>)[linearly ordered chain] or a more general rational number interval whose length tends to zero (maximal) #link(<net>)[net]

A rational number interval is a subset $𝐴 \subset ℚ$ with property order uninterrupted

\underset{\begin{matrix} 𝑎, 𝑏 \in 𝐴 \\ 𝑎 < 𝑏 \end{matrix}}{⋀} \underset{\begin{matrix} 𝑐 \in ℚ \\ 𝑎 < 𝑐 < 𝑏 \end{matrix}}{⋀} 𝑐 \in 𝐴

From an operational simplicity perspective, Dedekind-cut should be used. "Operational simplicity" means

let $𝑥 \in ℝ$ , ${𝑥} \leftrightarrow ℝ ∖ {𝑥}$ one-to-one correspondence
$(ℝ ∖ {𝑥}) \cap ℚ = ℚ ∖ {𝑥} = ℚ_{< 𝑥} ⊔ ℚ_{> 𝑥}$
So $𝑥 \in ℝ$ and $ℚ_{< 𝑥} ⊔ ℚ_{> 𝑥}$ one-to-one correspondence

Dedekind-cut_(tag) irrational number $ℝ ∖ ℚ$

$𝑥 \in ℝ ∖ ℚ$ one-to-one corresponds to ${(𝐴, 𝐵) \in {Subset (ℚ)}^{2} : (ℚ = 𝐴 ⊔ 𝐵) \land (\forall (𝑎, 𝑏) \in (𝐴, 𝐵), 𝑎 < 𝑏)}$

$𝑥 ≔ (𝐴, 𝐵)$ . Record $(𝐴, 𝐵)$ as $(ℚ_{< 𝑥}, ℚ_{> 𝑥})$ again

Real number $ℝ ≔ ℚ ⊔ (ℝ ∖ ℚ)$

order-real_(tag) $ℝ$ order $𝑥 < 𝑦 ⟺ (ℚ_{< 𝑥} ⊊ ℚ_{< 𝑦})$

let

\begin{matrix} 𝐴 + 𝐴^{'} ≔ {𝑎 + 𝑎^{'} : (𝑎, 𝑎^{'}) \in (𝐴, 𝐴^{'})} \\ 𝐴 \cdot 𝐴^{'} ≔ {𝑎 \cdot 𝑎^{'} : (𝑎, 𝑎^{'}) \in (𝐴, 𝐴^{'})} \end{matrix}

add-real_(tag) $ℝ$ addition. let $𝑥, 𝑦 \in ℝ$

\begin{matrix} 𝑥 + 𝑦 & ≔ & (ℚ_{< 𝑥} + ℚ_{< 𝑦}, ℚ_{> 𝑥} + ℚ_{> 𝑦}) & expect (ℚ_{< 𝑥 + 𝑦}, ℚ_{> 𝑥 + 𝑦}) \\ - 𝑥 & ≔ & (- ℚ_{> 𝑥}, - ℚ_{< 𝑥}) & expect (ℚ_{< - 𝑥}, ℚ_{> - 𝑥}) \end{matrix}

Because of the existence of $< 0$ , multiplication does not preserve order. But the multiplication of $ℚ_{> 0}, ℝ_{> 0}$ preserves order. First deal with the case of $> 0$ , and then use reflection $- 𝑥$ to get the case of $< 0$

multiply-real_(tag) $ℝ$ multiplication. let $𝑥, 𝑦 > 0$

\begin{matrix} 𝑥 \cdot 𝑦 & ≔ & (ℚ_{(0, 𝑥)} \cdot ℚ_{(0, 𝑦)}, ℚ_{(𝑥, \infty)} \cdot ℚ_{(𝑦, \infty)}) & expect (ℚ_{(0, 𝑥 𝑦)}, ℚ_{(𝑥 𝑦, \infty)}) \\ \frac{1}{𝑥} & ≔ & (\frac{1}{ℚ_{(𝑥, \infty)}}, \frac{1}{ℚ_{(0, 𝑥)}}) & expect (ℚ_{(0, \frac{1}{𝑥})}, ℚ_{(\frac{1}{𝑥}, \infty)}) \end{matrix}

$ℤ, ℚ, ℝ$ 's $+, \cdot$ all have associativity, commutativity, and distributivity

$ℝ$ completeness completeness-real_(tag)

exact-bound_(tag) Least-upper-bound property

let $𝐴 \subset ℝ$ have an upper bound

$\exists 𝑥 \in ℝ, ⋃_{𝑎 \in 𝐴} ℚ_{< 𝑎} = ℚ_{< 𝑥}$

Supremum $\sup 𝐴 ≔ 𝑥$

$\forall 𝑎 \in 𝐴, 𝑎 \leq \sup 𝐴$
$\forall 𝜀 > 0, \exists 𝑎 \in 𝐴, \sup 𝐴 - 𝜀 < 𝑎 \leq \sup 𝐴$

monotone-convergence_(tag) monotone bound #link(<limit-sequence-real>)[convergence] Proof use exact-bound

nested-closed-interval-theorem_(tag) Nested interval theorem

Whether it is

ℕ

nested intervals or

\subset

linearly ordered chain nested intervals, linear order means the monotonicity of interval endpoints, use supremum

𝑎_{1}

and infimum

𝑎_{0}

for the endpoints with

𝑎_{0} \leq 𝑎_{1}

to get the intersection of nested closed intervals is a closed interval

[𝑎_{0}, 𝑎_{1}] \neq \emptyset

[𝑎_{0}, 𝑎_{1}]

can be understood as the minimal element of

\subset

linear order chain nested closed sets

closed-interval-net-theorem_(tag) Closed interval #link(<net>)[net] $B$ intersection is non-empty $⋂ B \neq \emptyset$

Proof

Supplement the net $B$ with all finite intersections

Take a #link(<maximal-linear-order>)[maximal linearly ordered chain] $C$ . By the nested interval theorem, its intersection is a non-empty closed interval $⋂ C \neq \emptyset$

By the linear order maximality of $C$ , intuitively, the closed interval $⋂ C$ will be smaller than all closed intervals of $B$ , so $⋂ C \subset ⋂ B$

$\forall 𝐵 \in B$ , we prove $⋂ C \subset 𝐵$

Define the closed interval linear ordered chain $C_{𝐵} = {𝐵 \cap 𝐶 \in B : 𝐶 \in C}$ . $𝐵 \cap 𝐶 \subset 𝐵$ . We prove $⋂ C_{𝐵} = ⋂ C$

Proof by contradiction. Assume $⋂ C_{𝐵} ⊊ ⋂ C$ . Then the small/large endpoint of $⋂ C_{𝐵}$ is larger/smaller than the small/large endpoint of $⋂ C$

The $\subset$ linear ordered chain satisfies $⋂_{𝐴 \supset 𝐴_{0}} 𝐴 = 𝐴_{0}$

If the closed interval $⋂ C_{𝐵} \notin B$ , then use the $ℝ$ exact bound principle for the endpoints

\begin{matrix} \exists 𝐵 \cap 𝐶_{0} \in C_{𝐵} \\ 𝐵 \cap 𝐶_{0} \in B \\ 𝐵 \cap 𝐶_{0} = ⋂_{𝐵 \cap 𝐶 \supset 𝐵 \cap 𝐶_{0}} 𝐵 \cap 𝐶 ⊊ ⋂ C \end{matrix}

There exists $𝐵 \cap 𝐶_{0} \in B$ that belongs to $⋂ C$ , which contradicts that $⋂ C$ is a $\subset$ maximal linear ordered chain

If the closed interval $⋂ C_{𝐵} \in B$ , the same contradiction applies

let $𝑎_{𝑛} : ℕ \to ℝ$

def $ℕ \to ℝ$ sequence $𝑘 ⇝ \sup_{𝑘 \geq 𝑛} {𝑎_{𝑘}}$ monotone decreasing, $𝑘 ⇝ \inf_{𝑘 \geq 𝑛} {𝑎_{𝑘}}$ monotone increasing

limsup_(tag) Upper limit

\underset{𝑛 \to \infty}{lim sup} {𝑎_{𝑛}} ≔ lim_{𝑛 \to \infty} \sup_{𝑘 \geq 𝑛} {𝑎_{𝑘}} = \inf_{𝑛 \in ℕ} \sup_{𝑘 \geq 𝑛} {𝑎_{𝑘}}

liminf_(tag) Lower limit

\underset{𝑛 \to \infty}{lim inf} {𝑎_{𝑛}} ≔ lim_{𝑛 \to \infty} \inf_{𝑛 \geq 𝑘} {𝑎_{𝑘}} = \sup_{𝑛 \in ℕ} \inf_{𝑛 \geq 𝑘} {𝑎_{𝑘}}

Example

$𝑎_{𝑘} = 1 + \frac{1}{𝑘}$
$\begin{matrix} \sup_{𝑛 \in ℕ} {𝑎_{𝑛}} & = & 2 \\ \sup_{𝑛 \geq 𝑘} {𝑎_{𝑘}} & = & 1 + \frac{1}{𝑘} \\ lim_{𝑛 \to \infty} \sup_{𝑛 \geq 𝑘} {𝑎_{𝑘}} & = & 1 \end{matrix}$
$𝑎_{𝑘} = 1 + {(- 1)}^{𝑘}$
$\underset{𝑛 \to \infty}{lim sup} {𝑎_{𝑛}} = 2$

For the $ℕ$ sequence, define $distance {𝑎_{𝑛}, 𝑎_{𝑛 + 1}, \dots} ≔ \sup_{𝑚, 𝑚^{'} \geq 𝑛} | 𝑎_{𝑚} - 𝑎_{𝑚^{'}} |$

For a general net, define $distance (𝐵) = \sup_{𝑎, 𝑎^{'} \in 𝐵} | 𝑎 - 𝑎^{'} |$

limit-distance-vanish-sequence_(tag) := $lim_{𝑛 \to \infty} | {𝑎_{𝑛}, 𝑎_{𝑛 + 1}, \dots} | = 0$ i.e. tail distance vanish

limit-distance-vanish-net_(tag) := $\forall 𝜀 > 0, \exists 𝐵 \in B, distance (𝐵) < 𝜀$

Cauchy-completeness-real_(tag) limit-distance-vanish sequence or net converges

Proof

Unbounded ==> $\forall 𝜀 > 0, \forall 𝑁 \in ℕ, \exists 𝑛 > 𝑁, | {𝑎_{𝑛}, 𝑎_{𝑛 + 1}, \dots} | \geq 𝜀$

==> The limit-distance-vanish sequence is bounded

==> The monotonically increasing or decreasing bounded sequences $𝑛 ⇝ \inf_{𝑚 \geq 𝑛} {𝑎_{𝑚}}, \sup_{𝑚 \geq 𝑛} {𝑎_{𝑚}}$ have limits $\underset{𝑛 \to \infty}{lim inf} {𝑎_{𝑛}} \leq \underset{𝑛 \to \infty}{lim sup} {𝑎_{𝑛}}$

limit-distance-vanish property ==> $\underset{𝑛 \to \infty}{lim inf} {𝑎_{𝑛}} = \underset{𝑛 \to \infty}{lim sup} {𝑎_{𝑛}} = 𝑎$

Thus $𝑎_{𝑛}$ converges to $𝑎$

For nets, by the closed interval net theorem, let $𝑎 \in ⋂_{𝐵 \in B} 𝐵 \neq \emptyset$ . Using limit-distance-vanish-net, we obtain that the net converges $lim_{𝐵 \in B} \sup_{𝑎_{𝐵} \in 𝐵} | 𝑎_{𝐵} - 𝑎 | = 0$

Conversely, a convergent sequence is limit-distance-vanish. by the triangle inequality $| 𝑎_{𝑚} - 𝑎_{𝑚^{'}} | \leq | 𝑎_{𝑚} - 𝑎 | + | 𝑎_{𝑚^{'}} - 𝑎 |$

Sequence $ℕ \to ℝ$ or net $B$ converges to $𝑎$ <==> limit-distance-vanish

uncountable-real_(tag) The real number is uncountable $| ℕ | < | ℝ |$

It has been proved that $| ℕ | < | Subset (ℕ) |$ . cf. #link(<cardinal-increase>)[]

recall ${0, 1}^{ℕ} ≃ (ℕ \to bool) ≃ Subset (ℕ)$

$| Subset (ℝ) | = | ℕ \to ℕ | = | ℝ |$

Proof

According to the nested interval theorem, the binary decimal point representation of real numbers: $𝑎_{0} . 𝑎_{1} 𝑎_{2} \dots$ The $𝑛$ -th digit takes $0 ⇝ 0 \cdot \frac{1}{2^{𝑛}}$ or $1 ⇝ 1 \cdot \frac{1}{2^{𝑛}}$

==> ${0, 1}^{ℕ} ≃ [0, 1]$ . Where, quotient the possible two equivalent choices in binary

$[0, 1] ≃ (- 1, 1)$ by linear map or affine map

$(- 1, 1) ≃ ℝ$ by $𝑥 ⇝ \frac{𝑥}{1 - 𝑥^{2}}$

$(ℕ \to ℕ) ≃ (0, 1]$

Proof

(𝑛_{1}, 𝑛_{2}, \dots) ⇝ \frac{1}{2^{𝑛_{1}}} + \frac{1}{2^{𝑛_{1} + 𝑛_{2}}} + \dots

It represents in binary, the first position where $1$ appears is $𝑛_{1}$ , the second position is $𝑛_{2}$ …

Compare ${0, 1}^{ℕ}$ , $\frac{1}{2^{𝑚_{1}}} + \frac{1}{2^{𝑚_{2}}} + \dots$ vs $\frac{1}{2^{𝑛_{1}}} + \frac{1}{2^{𝑛_{1} + 𝑛_{2}}} + \dots$

\begin{matrix} 𝑚_{1} & = & 𝑛_{1} \\ 𝑚_{2} & = & 𝑛_{1} + 𝑛_{2} \\ \dots \end{matrix}

Distance $𝑛_{𝑖 + 1} = 𝑚_{𝑖 + 1} - 𝑚_{𝑖}$