algebra.tex

\chapter{Algebra}

\begin{definition}[Groupoid]
    A groupoid is a pair consisting of a set $S$ and a binary operation $\cdot$.
    The binary operation is defined:
    \begin{equation}
        \cdot: S \times S \rightarrow S \quad \forall a,b \in S: a \cdot b \in S
    \end{equation}
\end{definition}

\begin{definition}[Semigroup]
    A semigroup is a groupoid with a set $S$ and a binary operation $\cdot$.
    Its elements follow the law of associativity.
    It has the following properties:
    \begin{enumerate}
        \item The binary operation is defined:
            \begin{equation}
                \cdot: S \times S \rightarrow S \quad \forall a,b \in S: a \cdot b \in S
            \end{equation}
        \item Associative:
            \begin{equation}
                \forall a,b,c \in S: a \cdot (b \cdot c) = (a \cdot b) \cdot c
            \end{equation} 
    \end{enumerate}
\end{definition}

\begin{definition}[Monoid]
    A monoid is a triple $(S, \cdot, e)$ consisting of a set $S$, a binary operation $\cdot$ and 
    a neutral element $e \in S$.
    It is also a groupoid and has the following properties:
    \begin{enumerate}
        \item The binary operation is defined:
            \begin{equation}
                \cdot: S \times S \rightarrow S \quad \forall a,b \in S: a \cdot b \in S
            \end{equation}
        \item Associative:
            \begin{equation}
                \forall a,b,c \in S: a \cdot (b \cdot c) = (a \cdot b) \cdot c
            \end{equation} 
        \item The neutral element $e \in S$:
            \begin{equation}
                \forall a \in S: a \cdot e = e \cdot a = a
            \end{equation}
    \end{enumerate}
\end{definition}

\begin{definition}[Group]
    A group is a monoid with triple $(S, \cdot, e)$ consisting of a set $S$, 
    a binary operation $\cdot$ and a neutral element $e \in S$.
    For each element there is an ``inverse''.
    A group has the following properties:
    \begin{enumerate}
        \item The binary operation is defined:
            \begin{equation}
                \cdot: S \times S \rightarrow S \quad \forall a,b \in S: a \cdot b \in S
            \end{equation}
        \item Associative:
            \begin{equation}
                \forall a,b,c \in S: a \cdot (b \cdot c) = (a \cdot b) \cdot c
            \end{equation} 
        \item The neutral element $e \in S$:
            \begin{equation}
                \forall a \in S: a \cdot e = e \cdot a = a
            \end{equation}
        \item The inverse element:
            \begin{equation}
                \forall a \in S: \exists a': a \cdot a' = e
            \end{equation}
        \item If a group also commutative, it is called an Abelian group:
        \begin{equation}
            \forall a,b \in S: a \cdot b = b \cdot a
        \end{equation}
    \end{enumerate}
\end{definition}

\begin{definition}[Ring]
    A ring $(R,+,\cdot )$ consists of a set $R$ and two binary operations $+$ and $\cdot$.
    It has the following properties:
    \begin{enumerate}
        \item $(R,+)$ is an Abelian group.
        \item $(R,\cdot)$ is a semigroup.
        \item Distributive:
            \begin{equation}
                \forall a,b,c \in S: a \cdot (b + c) = a \cdot b + a \cdot c
            \end{equation}
    \end{enumerate}
    The operator $\cdot$ is usually omitted, e.g. $a (b + c) = ab + ac$.
\end{definition}

\begin{definition}[Field]
    A field consists of a set $F$ and two binary operations $+$ and $\cdot$.
    It has the following properties:
    \begin{enumerate}
        \item $(F,+)$ is an Abelian group. Element ``0'' is the neutral element.
        \item $(F\setminus\{0\},\cdot)$ is an Abelian group. Element ``1'' is the neutral element.
        \item Distributive:
            \begin{equation}
                \forall a,b,c \in F: a \cdot (b + c) = a \cdot b + a \cdot c
            \end{equation}
    \end{enumerate}
    The operator $\cdot$ is usually omitted, e.g. $a (b + c) = ab + ac$.
\end{definition}

\begin{lemma}
    Let $F$ be a field, then the following equations are valid:
    \begin{enumerate}
        \item $\forall a \in F: 0 \cdot a = 0$
        \item $\forall a,b \in F: -((-a) \cdot b) = -(a \cdot (-b)) = a \cdot b$
        \item $\forall a,b \in F: (-a) \cdot (-b) = a \cdot b$
    \end{enumerate}
\end{lemma}
\begin{proof}
    \begin{enumerate}
        \item $\forall a \in F: 0 \cdot a = 0$
        \begin{align}
                                  & 0 \cdot a = (0 + 0) \cdot a = 0 \cdot a + 0 \cdot a \nonumber \\
            \Leftrightarrow \quad & 0 \cdot a = 0 \cdot a + 0 \cdot a \nonumber \\
            \Leftrightarrow \quad & 0 \cdot a + 0 \cdot a = 0 \cdot a  \quad | - 0 \cdot a \nonumber \\
            \Leftrightarrow \quad & 0 \cdot a = 0 
        \end{align}
        \item $\forall a,b \in F: -((-a) \cdot b) = -(a \cdot (-b)) = a \cdot b$
        \begin{align}
            & a \cdot b + (-a) \cdot b = (a + (-a)) \cdot b = (0 + 0) \cdot b = 0 \nonumber \\
            \Leftrightarrow \quad & -((-a) \cdot b) = a \cdot b
        \end{align}
        \item $\forall a,b \in F: (-a) \cdot (-b) = a \cdot b$
        \begin{align}
            & (-a) \cdot b + (-a) \cdot (-b) = (-a) \cdot (b + (-b)) = (-a) \cdot (0 + 0) = 0 \nonumber \\
            \Leftrightarrow \quad & -((-a) \cdot b) = (-a) \cdot (-b) = a \cdot b
        \end{align}
    \end{enumerate}
\end{proof}

\begin{definition}[Floor and ceiling]
    Let $x \in \R$, then choose $m,n \in \Z$ so that:
    \begin{equation}
        m \le x < m + 1 \quad \land \quad n - 1 < x \le n
    \end{equation}
    Then, floor and ceiling functions are defined as 
    $\lfloor x \rfloor = m$ and 
    $\lceil x \rceil = n$.
\end{definition}

\begin{corollary}
    Properties of floor and ceiling:
    \begin{itemize}
        \item $\lfloor \lfloor x \rfloor \rfloor = \lfloor x \rfloor$
        \item $\lceil \lceil x \rceil \rceil = \lceil x \rceil$
        \item $\lfloor x + k \rfloor = \lfloor x \rfloor + k \quad k \in \Z$
        \item $\lceil x + k \rceil = \lceil x \rceil + k \quad k \in \Z$
    \end{itemize}
\end{corollary}
\begin{proof}
    It is sufficient to proof just one function, the other is analogous.
    \begin{enumerate}
        \item $\lfloor \lfloor x \rfloor \rfloor = \lfloor x \rfloor$ \\
            Let $x \in \R$ and $\lfloor x \rfloor = m$.
            Then, let $n \in \Z$, so that $\lfloor m \rfloor = n$:
            \begin{equation}
                n \le m < n+1
            \end{equation}
            The definition of ceiling function states, that it represents the integer closest, 
            but smaller than the given argument.
            \begin{equation}
                m \in \Z \quad \land \quad n \le m \implies n=m \quad \lor \quad n=m-1
            \end{equation}
            However, $n=m-1$ is invalid:
            \begin{equation}
                n \le m < n+1 \Leftrightarrow n-1 \le m < n \quad \blitz
            \end{equation}
            So, $n=m \implies \lfloor \lfloor x \rfloor \rfloor = \lfloor x \rfloor$

        \item $\lfloor x + k \rfloor = \lfloor x \rfloor + k \quad k \in \Z$ \\
            Let $\lfloor x \rfloor = n$, then:
            \begin{align}
                                & n \le x < n+1 \nonumber \\
                \Leftrightarrow \quad & n+k \le x+k < n+k+1 \nonumber \\
                \Leftrightarrow \quad  & \lfloor x \rfloor + k \le x+k < \lfloor x \rfloor + k+1 \nonumber \\
                \Leftrightarrow \quad  & \lfloor x + k \rfloor = \lfloor x \rfloor + k
            \end{align}
    \end{enumerate}
\end{proof}

\begin{definition}[Modulo]
    Let $a \in \Z, n \in \N$:
    \begin{equation}
        a \mod n = a - \left\lfloor \frac{a}{n} \right\rfloor n
    \end{equation}
\end{definition}

\begin{corollary}
    Properties of modulo arithmetic. Let $a,b \in \Z$ and $n \in \N$
    \begin{itemize}
        \item $(a + b) \mod n = ((a \mod n) + (b \mod n)) \mod n$
        \item $(a - b) \mod n = ((a \mod n) - (b \mod n)) \mod n$
    \end{itemize}
\end{corollary}
\begin{proof}
    It is sufficient to proof just one relation, the other is analogous.
    \begin{align}
        & ((a \text{ mod } n) + (b \text{ mod } n)) \text{ mod } n \nonumber \\
            = \quad & a - \left\lfloor \frac{a}{n} \right\rfloor n + b - \left\lfloor \frac{b}{n} \right\rfloor n - 
                \left\lfloor \frac{a - \left\lfloor \frac{a}{n} \right\rfloor n + b - \left\lfloor \frac{b}{n} \right\rfloor n}{n} \right\rfloor n \nonumber \\
            = \quad & a + b - \left(\left\lfloor \frac{a}{n} \right\rfloor + \left\lfloor \frac{b}{n} \right\rfloor\right)n - 
                \left\lfloor \frac{a - \left\lfloor \frac{a}{n} \right\rfloor n + b - \left\lfloor \frac{b}{n} \right\rfloor n}{n} \right\rfloor n \nonumber \\ 
            = \quad & a + b - \left(\left\lfloor \frac{a}{n} \right\rfloor + \left\lfloor \frac{b}{n} \right\rfloor - 
                \left\lfloor \frac{a - \left\lfloor \frac{a}{n} \right\rfloor n + b - \left\lfloor \frac{b}{n} \right\rfloor n}{n} \right\rfloor\right) n \nonumber \\ 
            = \quad & a + b - \left(\left\lfloor \left\lfloor \frac{a}{n} \right\rfloor + \left\lfloor \frac{b}{n} \right\rfloor - 
                \frac{a - \left\lfloor \frac{a}{n} \right\rfloor n + b - \left\lfloor \frac{b}{n} \right\rfloor n}{n} \right\rfloor\right) n \nonumber \\
            = \quad & a + b - \left(\left\lfloor
                \frac{\left\lfloor \frac{a}{n} \right\rfloor n + \left\lfloor \frac{b}{n} \right\rfloor n + a - \left\lfloor \frac{a}{n} \right\rfloor n + b - \left\lfloor \frac{b}{n} \right\rfloor n}
                     {n} \right\rfloor\right) n \nonumber \\  
            = \quad & a + b - \left(\left\lfloor\frac{a + b}{n} \right\rfloor\right) n \nonumber \\  
            = \quad & (a + b) \mod n  
    \end{align}
\end{proof}