number-theory.tex

\chapter{Number theory}

\begin{definition}[Natural numbers]
    Natural numbers is the set of all positive integers.
    The symbol \N{} is used to denote them.
    The set can be expressed as
    \begin{equation}
        \N = \{1,2,3,4,5,... \}
    \end{equation}
    The number is zero is not part of the natural numbers.
    All positive integers including zero is denoted by \Nzero{} and can be expressed as
    \begin{equation}
        \Nzero = \N \cup \{0\} = \{0, 1,2,3,4,5,... \}
    \end{equation}
\end{definition}

\begin{definition}[Natural numbers via Peano axioms]
    The successor of a given number $n$ is denoted as $S(n)$.
    \begin{enumerate}
        \item 1 is the first natural number
        \item $n \in \N \implies S(n) \ne 0$
        \item $\forall n \in \N \implies S(n) \in \N$
        \item $\forall n,m \in \N: S(n) = S(m) \implies n=m$
        \item $\forall X: 1 \in X \land \forall n \in X \land S(n) \in X \implies \N \subseteq X$
    \end{enumerate}
    Please note: The natural numbers do not include zero here. 
    It might be defined different elsewhere.
\end{definition}

\begin{corollary}
    When the natural numbers defined Peano axioms are extended by 0,
    it is $S(0)=1$.
\end{corollary}

\begin{definition}[Addition in \Nzero]
    Addition in \Nzero{} can be defined as:
    \begin{equation}
        \forall n,m \in \Nzero: n+0:=n \quad \land \quad n + S(m) := S(n + m)
    \end{equation}
\end{definition}

\begin{corollary}
    It can easily be seen, that the successor can be derived from addition:
    \begin{equation}
        S(n+0) = n + S(0)  \quad \Leftrightarrow \quad S(n) = n + 1
    \end{equation}
\end{corollary}

\begin{theorem}[The naturual numbers are closed under addition]
    \begin{equation}
        \forall n,m \in \Nzero: n + m \in \Nzero
    \end{equation}
\end{theorem}
\begin{proof}
    Proof is given by mathematical induction.
    Let $a,n \in \Nzero$:

    \emph{Base case:} For n = 1 that's clearly true.
    \begin{equation}
        a + n = a + 1 = a + S(0) \in \Nzero \quad \text{(see Peano axioms)}
    \end{equation}

    \emph{Induction requirement}: The equation is valid for n: $a + n \in \Nzero$.
    
    \emph{Induction step:} 
    \begin{equation}
        a + S(n) = a + (n + 1) = (a + n) + 1 = (a + n) + S(0) \in \Nzero
    \end{equation}
\end{proof}

\begin{definition}[Multiplication in \Nzero]
    Multiplication in \Nzero{} can be defined as:
    \begin{equation}
        \forall n,m \in \Nzero: n \cdot 0:=0 \quad \land \quad n \cdot S(m) := n + (n \cdot m)
    \end{equation}
\end{definition}

\begin{corollary}
    It can easily be seen, that the successor of zero is the multiplicative identity:
    \begin{equation}
        \forall n \in \Nzero: n \cdot S(0) = n + (n \cdot 0) = n
    \end{equation}
\end{corollary}

\begin{theorem}[The naturual numbers are closed under multiplication]
    \begin{equation}
        \forall n,m \in \Nzero: n \cdot m \in \Nzero
    \end{equation}
\end{theorem}
\begin{proof}
    Proof is given by mathematical induction.
    Let $a,n \in \Nzero$:

    \emph{Base case:} For n = 1 that's clearly true.
    \begin{equation}
        a \cdot n = a \cdot 1 = a \in \Nzero
    \end{equation}

    \emph{Induction requirement}: The equation is valid for n: $a \cdot n \in \Nzero$.
    
    \emph{Induction step:} 
    \begin{equation}
        a \cdot S(n) = a \cdot (n + 1) = a + (a \cdot n)
    \end{equation}
    Since natural numbers are closed under addition and 
    $a \cdot n \in \Nzero \implies a + (a \cdot n) \in \Nzero$
\end{proof}

\begin{definition}[Negative integers]
    Negative integers are defined as the additive inverse of natural numbers.
    The minus sign is used to denote the additive inverse of a given natural number,
    \begin{equation}
        \forall a \in \N: \exists -a: a + (-a) = 0
    \end{equation}
    The symbol \Nminus{} is used to denote them.
    \begin{equation}
        \Nminus = \{-1, -2, -3, -4, ... \}
    \end{equation}
\end{definition}

\begin{definition}[Integers]
    Integers are the set of all positive natural integers, negative integers and the number zero.
    \begin{equation}
        \Z = \N \cup \Nminus \cup \{0 \} =  \{...,-3,-2,-1,0,1,2,3,... \}
    \end{equation}
    The symbol \Z{} is used to denote them.
\end{definition}

\begin{corollary}
    The integers \Z{} are closed under addition and multiplication.
    The proof is similar to the one shown for natural numbers by applying mathematical induction. 
\end{corollary}

\begin{definition}[Rational numbers]
    Rational numbers is the set of all fractions.
    The symbol \Q{} is used to denote them.
    A rational number $a \in \Q$ can be expressed by a fraction with 
    two integers $p,q \in \Q$.
    \begin{equation}
        a = \frac{p}{q} \quad q \ne 0
    \end{equation}
\end{definition}

\begin{lemma}
    $N \subset \Nzero \subset \Z \subset \Q$
\end{lemma}
\begin{proof}
    Since \Z{} is defined as all integers it also includes all positive integers \N{} and 
    number zero.
    The set \Q{} contains all possible fractions, so it also includes fractions with denominator $1$
    \begin{equation}
        a = \frac{p}{q} = \frac{p}{1} = p \quad p \in \Nzero, q = 1
    \end{equation}
\end{proof}

\begin{lemma}
    $\sqrt{2} \notin \Q$.
\end{lemma}
\begin{proof}
    Assume $\sqrt{2} \in \Q$:
    Then, there are two integers $p,q \in \Z$, so that fraction $\frac{p}{q}$ 
    can no longer be shortened.
    Now, every integer $a$ can be expressed by 
    \begin{equation}
        a = 2^k b \quad k \in \Nzero, b \in Z \implies a^2 = (2^k b)^2 = 2^{2k} b^2
    \end{equation}
    So, every squared integer has an even number of 2s.
    However, $2 q^2 = p^2$ implies $p^2$ has odd number of 2s which contradicts the statement 
    that every squared integer has an even number of 2s.
    \begin{equation}
        2 q^2 = p^2 \implies p^2 = 2^{2k+1} b \quad \blitz  \quad k \in \Nzero, b \in \Z
    \end{equation}
\end{proof}
\begin{corollary}
    Since $\sqrt{2} \notin \Q$, there is obviously a set of infinite numbers which are not part of 
    \Q{} and therefore, \Q{} is not complete.
\end{corollary}
\begin{proof}
    It is possible to construct similar numbers like $\sqrt{2}$ and create a contradiction to show
    that they are not part of the rational numbers.

    For example,
    \begin{equation}
        \sqrt[2]{3} = \frac{p}{q} \quad p,q \in \Q, q \ne 0 \implies 3 q^2 = p^2 \implies p^2 
    \end{equation}
    Every integer $a$ can be expressed by 
    \begin{equation}
        a = 3^k b \quad k \in \Nzero, b \in Z \implies a^2 = (3^k b)^2 = 3^{2k} b^2
    \end{equation}
    Then, the contradiction is:
    \begin{equation}
        3 q^2 = p^2 \implies p^2 = 3^{3k+1} b \quad \blitz  \quad k \in \Nzero, b \in \Z
    \end{equation}
\end{proof}

\begin{definition}[Irrational numbers]
    As one can see, the set of rational numbers do not cover all possible numbers.
    Therefore, numbers which are not in \Q{} and are called irrational numbers.
\end{definition}

\begin{definition}[Real numbers]
    Reel numbers is the set of all numbers rational and irrational numbers.
    The symbol \R{} is used to denote them.
\end{definition}

\begin{lemma}
    \begin{equation}
        a^2 \in \R \setminus \Q \implies a \in \R \setminus \Q
    \end{equation}
\end{lemma}
\begin{proof}
    Assume $a \in \Q$, then:
    \begin{equation}
        \exists p,q \in \Z: a = \frac{p}{q} \implies a^2 = \frac{p^2}{q^2}
    \end{equation}
    Since \Z{} is closed for multiplication, $p^2,q^2 \in \Z$:
    \begin{equation}
        p^2,q^2 \in \Z \implies \frac{p^2}{q^2} \in \Q \implies a^2 \in \Q \quad \blitz 
    \end{equation}
\end{proof}