\documentclass[12pt]{article}

\usepackage[margin=1in]{geometry}
\setlength{\parskip}{0.5\baselineskip}

\usepackage{amsmath,amsfonts}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage[usenames,dvipsnames]{xcolor}

\definecolor{light-gray}{gray}{0.75}
\definecolor{orange}{rgb}{1,0.5,0}


%\usepackage[color,notref,notcite]{showkeys}
%\definecolor{refkey}{gray}{0.5}
%\definecolor{labelkey}{gray}{0.5}

% \usepackage{refcheck}

% time and date
\begingroup
\count0=\time \divide\count0by60 % Hour
\count2=\count0 \multiply\count2by-60 \advance\count2by\time%Minute
\def\2#1{\ifnum#1<10 0\fi\the#1}
\xdef\isodayandtime%
{\the\year-\2\month-\2\day\space\2{\count0}:\2{\count2}}
\xdef\now{\space\2{\count0}:\2{\count2}}
\endgroup


\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem*{definition*}{Definition}
\newtheorem{problem}[definition]{Problem}
\newtheorem{example}[definition]{Example}
\newtheorem{exercise}[definition]{Exercise}
\newtheorem{remark}[definition]{Remark}
\newtheorem{principle}[definition]{Principle}
\newtheorem{project}[definition]{Project}
\newtheorem{axiom}{Axiom}
\newtheorem{statement}{Statement}


\theoremstyle{plain}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{proposition}[definition]{Proposition}
\newtheorem{corollary}[definition]{Corollary}

\numberwithin{equation}{section}


\newcommand{\nA}{\mathbb A}
\newcommand{\nB}{\mathbb B}
\newcommand{\nC}{\mathbb C}
\newcommand{\nD}{\mathbb D}
\newcommand{\nE}{\mathbb E}
\newcommand{\nF}{\mathbb F}
\newcommand{\nG}{\mathbb G}
\newcommand{\nH}{\mathbb H}
\newcommand{\nI}{\mathbb I}
\newcommand{\nJ}{\mathbb J}
\newcommand{\nK}{\mathbb K}
\newcommand{\nL}{\mathbb L}
\newcommand{\nM}{\mathbb M}
\newcommand{\nN}{\mathbb N}
\newcommand{\nO}{\mathbb O}
\newcommand{\nP}{\mathbb P}
\newcommand{\nQ}{\mathbb Q}
\newcommand{\nR}{\mathbb R}
\newcommand{\nS}{\mathbb S}
\newcommand{\nT}{\mathbb T}
\newcommand{\nZ}{\mathbb Z}

\newcommand{\cA}{{\mathcal A}}
\newcommand{\cB}{{\mathcal B}}
\newcommand{\cC}{{\mathcal C}}
\newcommand{\cD}{{\mathcal D}}
\newcommand{\cE}{{\mathcal E}}
\newcommand{\cF}{{\mathcal F}}
\newcommand{\cG}{{\mathcal G}}
\newcommand{\cH}{{\mathcal H}}
\newcommand{\cI}{{\mathcal I}}
\newcommand{\cK}{{\mathcal K}}
\newcommand{\cL}{{\mathcal L}}
\newcommand{\cM}{{\mathcal M}}
\newcommand{\cN}{{\mathcal N}}
\newcommand{\cO}{{\mathcal O}}
\newcommand{\cP}{{\mathcal P}}
\newcommand{\cQ}{{\mathcal Q}}
\newcommand{\cR}{{\mathcal R}}
\newcommand{\cS}{{\mathcal S}}
\newcommand{\cT}{{\mathcal T}}
\newcommand{\cU}{{\mathcal U}}
\newcommand{\cV}{{\mathcal V}}
\newcommand{\cW}{{\mathcal W}}
\newcommand{\cX}{{\mathcal X}}
\newcommand{\cY}{{\mathcal Y}}
\newcommand{\cZ}{{\mathcal Z}}


\newcommand{\lt}{<}
\newcommand{\gt}{>}


\begin{document}


\title{Basic properties of the Integers}

\author{Branko \'{C}urgus}

\maketitle

\section{Axioms for the Integers}



In the axioms below we use the standard notation for logical operators: the conjunction is $\wedge$, the disjunction is $\vee$, the exclusive disjunction is  $\oplus$, the implication is $\Rightarrow$, the universal quantifier is $\forall$, the existential quantifier is $\exists$.


We also use the standard set notation: the set membership $\in$, the subset $\subseteq$, the equality $=$, the set difference $\setminus$ and the Cartesian product $\times$. For singleton sets instead of writing $\{a\} = \{b\}$ we write $a = b$.



The notation $f:A\to B$ stands for a function $f$ which is defined on a set $A$ with the values in $B$.


Axiom~\ref{aAE} below establishes the existence of the addition function defined on $\mathbb{Z}\!\times\!\mathbb{Z}$ with the values in $\mathbb{Z}$.  It is common to denote the value of $+$ at a pair $(a, b) \in  \mathbb{Z}\times \mathbb{Z}$ by $a+b$.


Axiom~\ref{aME} establishes the existence of the multiplication function defined on $\mathbb{Z}\!\times\!\mathbb{Z}$ with the values in $\mathbb{Z}$. It is  common to denote the value of this function at a pair  $(a,b) \in  \mathbb{Z}\times \mathbb{Z}$ by $a\cdot b$ which is almost always abbreviated as $ab$.

Axiom~\ref{aPE} introduces the set of positive integers.%

As a mnemonic aid I have assigned each axiom an abbreviation. Here are explanations of the abbreviations: ZE~-~integers exist,  AE~-~addition exists, AA~-~addition is associative, AC~-~addition is commutative, AZ~-~addition has zero, AO~-~ addition has opposites, ME~-~multiplication exists, MA~-~multiplication is associative, MC~-~multiplication is commutative, MO~-~multiplication has one, MZ~-~multiplication respects zero, DL~-~distributive law, PE~-~positive integers exist, PD~-~dichotomy involving positive integers, PA~-~positive integers respect addition, PM~-~positive integers respect multiplication, WO~-~the well-ordering axiom.



\newpage

\large

\setcounter{axiom}{0}

{\color{black}\hrule}

%\textcolor{blue}{\hrule}

\begin{definition*}
The set $\mathbb{Z}$ of {\em integers} satisfies the following 16 axioms.
\end{definition*}

\rule{10pt}{0pt}\begin{minipage}{0.85\textwidth}
\begin{axiom}[ZE]   \label{aZE}
$\mathbb{Z} \neq \emptyset$
\end{axiom}

\vspace*{-4pt}%
{\color{light-gray}\hrule}
\vspace*{-4pt}%

\begin{axiom}[AE]   \label{aAE}
$\exists \ \, +: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$
\end{axiom}

\begin{axiom}[AA]   \label{aAA}
$\forall a \in  \mathbb{Z} \ \ \forall b \in  \mathbb{Z} \ \ \forall  c \in  \mathbb{Z} \quad a+(b+c) = (a+b)+c$
\end{axiom}

\begin{axiom}[AC]  \label{aAC}
$\forall a \in  \mathbb{Z} \ \ \forall b \in  \mathbb{Z} \quad a+b = b+a$
\end{axiom}

\begin{axiom}[AZ]  \label{aAZ}
$\exists\, 0 \in \mathbb{Z} \ \ \forall a \in \mathbb{Z} \quad 0+a = a$
\end{axiom}

\begin{axiom}[AO]  \label{aAO}
$\forall a \in \mathbb{Z} \ \ \exists\, (-\!a) \in \mathbb{Z} \quad a + (-a) = 0$
\end{axiom}

\vspace*{-4pt}%
{\color{light-gray}\hrule}
\vspace*{-4pt}%


\begin{axiom}[ME]   \label{aME}
$\exists \ \,  \cdot : \mathbb{Z}\!\times\!\mathbb{Z} \to \mathbb{Z}$.
\end{axiom}

\begin{axiom}[MA]  \label{aMA}
$\forall a \in  \mathbb{Z} \ \ \forall b \in  \mathbb{Z} \ \forall c \in  \mathbb{Z} \quad a(bc) = (ab)c$
\end{axiom}

\begin{axiom}[MC]  \label{aMC}
$\forall a \in  \mathbb{Z} \ \ \forall b \in  \mathbb{Z} \quad ab = ba$
\end{axiom}


\begin{axiom}[MO]  \label{aMO}
$\exists\, 1 \in \mathbb{Z}\!\setminus\!\{0\}  \quad \forall a \in \mathbb{Z} \quad 1\cdot a =  a$
\end{axiom}

%\begin{axiom}[MZ]  \label{aMZ}
%$\forall a \in  \mathbb{Z} \ \ \forall\, b \in  \mathbb{Z} \quad  (ab = 0) \Rightarrow (a = 0) \vee (b = 0)$
%\end{axiom}

\vspace*{-4pt}%
{\color{light-gray}\hrule}
\vspace*{-4pt}%


\begin{axiom}[DL]  \label{aDL}
$\forall a \in  \mathbb{Z} \ \ \forall b \in  \mathbb{Z} \ \ \forall c \in  \mathbb{Z} \quad a(b+c) = ab + ac$
\end{axiom}

\vspace*{-4pt}%
{\color{light-gray}\hrule}
\vspace*{-4pt}%


\begin{axiom}[PE]  \label{aPE}
$\exists \ \mathbb P \quad \bigl(\mathbb P \subseteq \mathbb Z\!\setminus\!\{0\}\bigr) \wedge \bigl(\mathbb P \neq \emptyset\bigr)$
\end{axiom}

\begin{axiom}[PD]  \label{aPD}
$\forall a \in  \mathbb Z\!\setminus\!\{0\} \quad (a \in \mathbb P) \oplus (-a \in \mathbb P)$
\end{axiom}

\begin{axiom}[PA]  \label{aPA}
$\forall a \in \mathbb P \ \ \forall b \in  \mathbb P \quad  a+b \in \mathbb P$
\end{axiom}

\begin{axiom}[PM] \label{aPM}
$\forall\, a \in \mathbb P \ \ \forall b \in  \mathbb P \quad  ab \in \mathbb P $
\end{axiom}

\vspace*{-4pt}%
{\color{light-gray}\hrule}
\vspace*{-4pt}%


\begin{axiom}[WO] \label{aWO} \rule{10pt}{0pt}

$\bigl( S \subseteq \mathbb P \bigr) \wedge \bigl( S \neq \emptyset \bigr) \Rightarrow \bigl( \exists \, m \in S \ \  \forall\, x \in S\!\setminus\!\{m\} \quad x+(-m) \in \mathbb P \bigr)$
\end{axiom}

\end{minipage}

\hrule

\normalsize

\section{Basic algebraic properties of the integers}

In this section we list properties of the integers which involve the axioms related to the addition and the multiplication, but not the order.


\begin{proposition} \label{p-ac}
Let $a, b$ and $c$ be integers. Then $a+c = b+c$ implies $a=b$.
\end{proposition}

\begin{proof}
Let $a, b$ and $c$ be arbitrary integers. Assume $a+c = b+c$. By Axiom~AO there exists $-c \in \nZ$ such that $c+(-c) = 0$. Since $+$  is a function $a+c = b+c$ implies that $(a+c)+(-c) = (b+c)+(-c)$. By Axiom~AA $a+(c+(-c)) = b+(c+(-c))$ and, since $c+(-c) = 0$, $a+0 = b+0$. By Axiom~AZ this yields.  $a=b$.
\end{proof}

\begin{proposition} \label{p0u}
The element $0 \in \nZ$ introduced in {\rm Axiom~\!AZ} is unique.
\end{proposition}
\begin{proof}
Assume that there exist $0' \in \nZ$ such that for all $a\in\nZ$ we have $0' + a = a$. Let $c \in \nZ$. The universal instantiation yields $0' + c = c$.
The universal instantiation in Axiom~AZ yields $0 + c = c$. Thus $0'+c = 0+c$. By Proposition~\ref{p-ac} we deduce $0'=0$.
\end{proof}

\begin{proposition} \label{pou}
For every $a \in \nZ$ the equation $a+x=0$ has a unique solution.
\end{proposition}

\begin{proof}
Let $a \in \nZ$ be arbitrary. By Axiom~\!AO the equation $a+x=0$ has a solution $x=-a$, that is $a+(-a) =0$. Assume that $a+x'=0$. Consequently, $a+(-a) = a+x$. By Axiom~AC the last equality implies $(-a)+a = x + a$.  By Proposition~\ref{p-ac} we deduce $x = -a$.
\end{proof}

\begin{definition} \label{do}
Let $a \in \nZ$. The unique solution $-a$ of the equation $a+x=0$ is called the {\em opposite} of $a$. For $b \in \nZ$ we write $b-a$ instead of $b+(-a)$. \end{definition}

\begin{proposition} \label{poo}
For every $a \in \nZ$ we have $-(-a) = a$.
\end{proposition}
\begin{proof}
Let $a \in \nZ$ be arbitrary. By definition $-(-a)$ we have $(-a) + \bigl(-(-a)\bigr) = 0$. By definition of $-a$ we have $a+(-a) = 0$. By Axiom~AC we have $(-a)+a = 0$. From $(-a) + \bigl(-(-a)\bigr) = 0$ and $(-a)+a = 0$ we conclude that $(-a) + \bigl(-(-a)\bigr) = (-a)+a$. By By Proposition~\ref{p-ac} we conclude that $a = -(-a)$.
\end{proof}

\begin{proposition} \label{po0}
For every $a \in \mathbb{Z}$ we have $a = 0$ if and only if $-a=a$.
\end{proposition}
\begin{proof}
Assume that $a=0$. By Definition~\ref{do} $-0$ is the unique solution of the equation $0+x=0$. Since by Axiom~\!AZ we have $0+0=0$, we deduce $-0=0$. That is $-a=a$ holds. We prove the converse by proving its contrapositive. Assume that $a \neq 0$. Then by Axiom~PD we have that
\[
\bigl((a\in\mathbb{P})\wedge-a\not\in\mathbb{P}\bigr) \oplus \bigl((-a\in\mathbb{P}) \wedge (a\not\in\mathbb{P}) \bigr)
\]
In both cases $-a \neq a$.
\end{proof}

\begin{proposition} \label{pm0}
For every $a \in \nZ$ we have $a0 = 0a = 0$.
\end{proposition}

\begin{proof}
Let $a \in \nZ$ be arbitrary. By Axiom~\!AZ and universal instantiation we have $0+0 = 0$. Since the multiplication is a function $a(0+0) = a0$. By Axiom~\!DL $a0+a0 = a0$. By Axiom~\!ME $a0 \in \nZ$. Hence $-(a0) \in \nZ$ exists by Axiom~\!AO. Now $a0+a0 = a0$ yields $(a0+a0)-(a0) = a0-(a0)$. By Axiom~\!AA and~\!AO we obtain $a0=0$. Axiom~\!AC now yields $a0 = 0a = 0$.
\end{proof}


\begin{proposition} \label{pom}
For every $a \in \nZ$ and for every $b \in \nZ$ we have $(-a)b = a(-b) =  -(ab)$.
\end{proposition}

\begin{proof}
Let $a$ and $b$ be arbitrary integers. Then by Axiom~\!AO we have $a+(-a) = 0$. By Axioms~\!ME, we have $\bigl(a+(-a)\bigr)b = 0b$. Now, Axioms~\!MC and~\!DL and Proposition~\!\ref{pm0} yield $ab+(-a)b = 0$. By Axiom~AO we have $ab+\bigl(-(ab)\bigr) = 0$. Hence, $ab+(-a)b = ab+\bigl(-(ab)\bigr)$. By Axiom~AC $(-a)b + ab = \bigl(-(ab)\bigr) + ab$. By Proposition~\ref{p-ac} we conclude $(-a)b= \bigl(-(ab)\bigr)$. The equality $a(-b) =  -(ab)$ is proved similary.
\end{proof}

\begin{proposition} \label{pdo}
For every $a \in \nZ$ and for every $b \in \nZ$ we have $(-a)(-b) = ab$.
\end{proposition}

\begin{proof}
Let $a$ and $b$ be arbitrary integers. By Proposition~\!\ref{pom} we have $(-a)(-b) = -\bigl(a(-b)\bigr)$. Applying Proposition~\!\ref{pom} yields $a(-b) = -(ab)$. Hence $(-a)(-b) = -\bigl(-(ab)\bigr)$. Now, Proposition~\!\ref{poo} implies $-\bigl(-(ab)\bigr) = ab$, and consequently $(-a)(-b) = ab$.
\end{proof}




\section{Basic properties of the integers involving the order}

The following proposition gives in some sense a converse of Axiom~PM.

\begin{proposition} \label{psp}
For every $a\in\nZ$ and every $b\in\mathbb{P}$ we have $ab \in \mathbb{P}$ if and only if $a \in \mathbb{P}$.
\end{proposition}
\begin{proof}
Let $a\in\nZ$ and $b\in\mathbb{P}$ be arbitrary. If $a \in \mathbb{P}$, then by Axiom~PM $ab \in \mathbb{P}$. We prove the converse by proving its contrapositive. Assume that $a \not\in \mathbb{P}$. We distinguish two cases: $a = 0$ and $a\neq 0$. If $a=0$, then by Proposition~\ref{pm0} $ab=0$. Therefore, $ab\not\in \mathbb{P}$. If $a\neq 0$, then the disjunctive syllogism of $a \not\in \mathbb{P}$ and Axiom~PD yields that $-a\in\mathbb{P}$. Now, by Axiom~PM and Proposition~\ref{pom} we conclude $-(ab)\in\mathbb{P}$. Since $ab \neq 0$, Axiom~PD yields $ab \not\in \mathbb{P}$. In both cases $a \not\in \mathbb{P}\Rightarrow ab \not\in \mathbb{P}$.
 \end{proof}

In Axiom~PE we have introduced the nonempty set of nonzero integers $\mathbb{P}$. Now we will prove that this set contains a lot of integers.


\begin{proposition} \label{psp}
For every nonzero integer $a$ we have $aa \in \mathbb{P}$.
\end{proposition}

\begin{proof}
Let $a$ be an arbitrary nonzero integer. By Axiom~PD we have two possibilities for $a$: either $a\in \mathbb{P}$ or $-a\in \mathbb{P}$. We proceed with two cases.  Case~1. Assume $a\in \mathbb{P}$. By Axiom~PM we have $aa\in \mathbb{P}$. Case~2. Assume $-a\in \mathbb{P}$. By Axiom~PM we have $(-a)(-a)\in \mathbb{P}$. By Proposition~\ref{pdo} we have $(-a)(-a) = aa$. Therefore $aa\in \mathbb{P}$ in this case as well.
\end{proof}


\begin{proposition} \label{aMZ}
For all $a \in \nZ$ and all $b \in  \nZ$ we have $ab = 0$ if and only if $a = 0$ or $b = 0$.
\end{proposition}
\begin{proof}
We first prove the ``only if'' part by proving its contrapositive. Assume $a \neq 0$ and $b \neq 0$. By Axiom~PD we have $(a\in\mathbb{P})\oplus(-a\in\mathbb{P})$  and $(b\in\mathbb{P})\oplus(-b\in\mathbb{P})$. Therefore we consider four  different cases: Case~1 $a\in\mathbb{P}$ and $b\in\mathbb{P}$, Case~2 $a\in\mathbb{P}$ and $-b\in\mathbb{P}$, Case~3 $-a\in\mathbb{P}$ and $b\in\mathbb{P}$, Case~4 $-a\in\mathbb{P}$ and $-b\in\mathbb{P}$. By Axiom~PM, in Case~1 and Case~4 (using Proposition~\ref{pdo}) we have $ab \in\mathbb{P}$. By Axiom~PM and Proposition~\ref{pom}, in Case~2 and Case~3 we have $-ab \in\mathbb{P}$. The converse follows from Proposition~\ref{pm0}.
\end{proof}


\begin{definition}
For $a \in \nZ$ the product $aa$ is called the {\em square of} $a$ and it is denoted by $a^2$.
\end{definition}


\begin{corollary} \label{c-1P}
$1\in \mathbb{P}$.
\end{corollary}
\begin{proof}
By Axiom~MO we have $1\neq 0$. By Proposition~\ref{psp} we deduce $1^2\in\mathbb{P}$. By Axiom~MO $1^2 = 1$. Thus, $1\in \mathbb{P}$.
\end{proof}

\begin{corollary} \label{cor1}
For every $a \in \mathbb{P}$ we have $a + 1\in \mathbb{P}$.
\end{corollary}

\begin{proof}
Let $a \in {\mathbb P}$ be arbitrary. Since $1 \in {\mathbb P}$, Axiom~PA implies $a+1 \in {\mathbb P}$.
\end{proof}

Thus, $1 \in {\mathbb P}$, $1+1 \in {\mathbb P}$, $1+1+1 \in {\mathbb P}$, and so on. This is the motivation for the following definition

\begin{definition}
The integers in the set $\mathbb{P}$ are called {\em positive integers}. An alternative notation for positive integers is $\nZ^{+}$. An integer $a$ is said to be negative if and only if $-a \in \mathbb{P}$. The set of all negative integers is denoted by $\mathbb{Z}^{-}$.
\end{definition}

Notice the following important trichotomy for integers which follows from Axioms~PE and~PD: For each $a \in \mathbb{Z}$ \underline{exactly one} of the following three propositions is true:

\noindent\rule{5pt}{0pt} \hfill \fbox{$a$ is negative} \hfill \fbox{$a=0$} \hfill \fbox{$a$ is positive} \hfill \rule{5pt}{0pt}


\begin{definition}
For arbitrary integers $a$ and $b$ we say that $a$ is {\em smaller then} $b$ and write $a \lt b$ (or equivalently $b \gt a$) if and only if $b-a \in \mathbb{P}$.
\end{definition}

Since $1-0 = 1$ and $1 \in\mathbb{P}$ we have $0\lt 1$. The following proposition gives the basic properties of order $\lt$.


\begin{proposition} \label{p-OAx}
\begin{enumerate}
 \renewcommand*\theenumi{\Alph{enumi}}
\renewcommand*\labelenumi{\rm{(\theenumi)}}
\setlength{\itemsep}{1pt}% \itemsep0em
 \item \label{aOE}
For all $a \in  \nZ$ and for all $b \in  \nZ$ exactly one of the following three propositions is true:

\noindent\rule{5pt}{0pt} \hfill \fbox{$a \lt b$} \hfill \fbox{$a=b$} \hfill \fbox{$b \lt a$} \hfill \rule{5pt}{0pt}

\item \label{aOT}
$\forall a \in  \nZ \ \forall b \in  \nZ \ \forall c \in  \nZ \quad (a < b) \wedge (b < c)  \Rightarrow (a < c)$

\item  \label{aOA}
$\forall a \in  \nZ \ \forall b \in  \nZ \ \forall c \in  \nZ \quad (a < b)  \Leftrightarrow (a + c < b + c)$


\item \label{aOM}
$\forall a \in  \nZ \ \forall b \in  \nZ \ \forall c \in  \mathbb{P} \quad (a < b)   \Leftrightarrow (ac < bc)$
\end{enumerate}
\end{proposition}

\begin{proof}
We prove (\ref{aOE}). Let $a \in \nZ$ and $b\in \nZ$ be arbitrary. Then by Axioms~AE and~AO we have $b-a \in \nZ$. We have two exclusive cases: Case~1: $b-a = 0$ and Case~2: $b-a \in \nZ\!\setminus\!\{0\}$. In Case~1 we have $a=b$. In Case~2 we use Axiom~PD to conclude
\[
(b-a \in \mathbb{P}) \oplus ( -(b-a) \in \mathbb{P} ),
\]
that is
\[
(a \lt b) \oplus (b \lt a).
\]
This proves (\ref{aOE}). Statements (\ref{aOT}), (\ref{aOA}) and (\ref{aOM}) are proved similarly.


\end{proof}


\begin{proposition} \label{porop}
Let $a$ and $b$ be integers. Then  $a < b$ if and only if $-b < -a$.
\end{proposition}

\begin{proof}
Let $a$ and $b$ be arbitrary integers. By Proposition~\ref{poo} we have $b-a = (-a)-(-b)$. Therefore, $a < b$ if and only if $b-a \in\mathbb{P}$ if and only if
$(-a)-(-b) \in\mathbb{P}$ if and only if $-b < -a$.
\end{proof}


\begin{proposition} \label{pmn}
Let $a, b$ and $c$ be integers. Then $a < b$ and $c < 0$ imply $bc < ac$.
\end{proposition}

\begin{proof}
Let $a, b$ and $c$ be arbitrary integers. Assume $a < b$ and $c < 0$. Then by Propositions~\ref{porop} and~\ref{po0} $0 < -c$. Now, $a < b$, $0 < -c$ and Proposition~\ref{p-OAx}(\ref{aOM}) imply $a(-c) < b(-c)$. By Proposition~\ref{pom}, the last inequality can be rewritten as $-(ac) < -(bc)$. By Propositions~\ref{porop} the last inequality implies $bc < ac$.
\end{proof}


Since $0 \lt 1$, Proposition~\ref{p-OAx}(\ref{aOA}) yields $1 < 1+1$. Therefore, by Proposition~\ref{p-OAx}(\ref{aOE}), $1 \neq 1+1$. Therefore we define

\begin{definition}
$2 = 1+1$.
\end{definition}

Again by Proposition~\ref{p-OAx}(\ref{aOA}) $2 < 2+1$. Therefore we define

\begin{definition}
$3 = 2+1$, $\ 4 = 3+1$,  $\ 5 = 4+1$, $\ 6 = 5+1$, $\ 7 = 6+1$, $\ 8 = 7+1$,$\ 9 = 8+1$.
\end{definition}

By Proposition~\ref{p-OAx}(\ref{aOA}), $0 < 1 < 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9$.

\begin{exercise}
Prove $2 + 2 = 4$.
\end{exercise}

\begin{exercise}
Prove $2 \cdot 2 = 4$.
\end{exercise}


\section{The Well Ordering Axiom}

We use the common abbreviation $a \leq b$ for the proposition $(a \lt b) \oplus (a=b)$. With this abbreviation and the notation $\mathbb{P} = \nZ^+$ the Well-Ordering Axiom can be rewritten as:


\setcounter{axiom}{15}

\begin{axiom}[WO]
$\bigl( S \subseteq \mathbb Z^+ \bigr) \wedge \bigl( S \neq \emptyset \bigr) \Rightarrow \bigl( \exists \, m \in S \ \  \forall x \in S  \quad m \leq x \bigr)$
\end{axiom}


\begin{definition}
Let $S$ be a nonempty subset of $\nZ$. We say that $S$ {\em has a  minimum} if there exists $m \in S$ such that for every $x \in S$ we have $m \leq x$. Formally,
\begin{equation}
\label{eqmin}
S \ \text{has a minimum} \ \ \Leftrightarrow \ \ \exists\, m \in S  \ \ \forall\, x \in S \quad m \leq x.
\end{equation}
The integer $m \in S$ satisfying the proposition on the right-hand side of  \eqref{eqmin} is called the {\em minimum} of $S$. It is denoted by $\min S$.
\end{definition}

With this definition the Well-Ordering Axiom can be restated as
\begin{equation}
\label{eqwo}
\bigl( S \subseteq \nZ^+ \bigr) \wedge \bigl( S \neq \emptyset \bigr) \ \Rightarrow  \ S \ \text{has a minimum}
\end{equation}

Recall that the propositions  $p\wedge q \Rightarrow r$ and $p\wedge \neg r \Rightarrow \neg q$ are equivalent. Consequently, the well ordering Axiom~\!WO, as stated in \eqref{eqwo}, is equivalent to
\begin{equation}
\label{eqwo-cp}
\bigl( S \subseteq \nZ^+ \bigr) \wedge \bigl( S \ \text{does not have a minimum} \bigr)  \ \Rightarrow  \ \bigl( S = \emptyset \bigr)
\end{equation}
At this point it is useful to note the formal meaning of the phrase ``$S$ does not have a minimum''. Negating \eqref{eqmin} we get:
\[
S \ \text{does not have a minimum} \ \ \Leftrightarrow \ \  \forall x \in S  \ \ \exists\, y \in S \quad y \lt x.
\]

I will illustrate how to use \eqref{eqwo-cp} in the following proposition.
\begin{proposition} \label{pZ01}
There are no integers between $0$ and $1$.
\end{proposition}

\begin{proof}
Define the set $S$ by
\[
S = \{x \in \nZ \,|\, (0 \lt x) \wedge (x < 1) \}.
\]
Clearly $S \subset \nZ^+$. Next we will prove that $S$ does not have a minimum. Let $x \in S$ be arbitrary. Then $0 < x$ and $x < 1$. The last two inequalities and Proposition~\ref{p-OAx}(\ref{aOM}) imply $x^2 < x$. Since $x \neq 0$, Proposition~\ref{psp} implies $0< x^2$. Since $x^2 < x$ and $x < 1$, Proposition~\ref{p-OAx}(\ref{aOT}) implies $x^2 < 1$. Now we have, $x^2 \in \nZ$ and $0 < x^2$ and $x < 1$. Thus, $x^2 \in S$ and also $x^2 < x$. Hence we have proved that for every $x \in S$ there exists $y=x^2 \in S$ such that $y=x^2 < x$. That is, $S$ does not have a minimum. By \eqref{eqwo-cp}, we deduce $S = \emptyset$.
\end{proof}

The next proposition can be deduced from the previous one. However, I will give a direct proof.

\begin{proposition} \label{p-minZ}
The minimum of $\ \nZ^+$ is $1$.
\end{proposition}

\begin{proof}
Since $1 \in \nZ^+$ the set $\nZ^+$ is not empty. Since clearly $\nZ^+ \subseteq \nZ^+$, Axiom~\!WO implies that $\nZ^+$ has a minimum. Denote by $m$ the minimum of $\nZ^+$; that is, set $m = \min \nZ^+$. Recall that $m$ has the following properties:
\begin{equation}\label{eqm1}
m \in \nZ^+ \quad \text{and} \quad  \forall x \in \nZ^+ \ m \leq x.
\end{equation}
Since $1 \in \nZ^+$ we have $m \leq 1$. Since $m > 0$, Axiom~OM yields $m^2 \leq m$. Since $0 < m$ by Proposition~\ref{p-OAx}(\ref{aOM}) we deduce $0 < m^2$. Thus $m^2 \in \nZ^+$. Since $m = \min \nZ^+$ we conclude $m \leq m^2$. Since both $m^2 \leq m$ and $m \leq m^2$, we have $m = m^2$, that is $m(m-1) = 0$. Now Proposition~\ref{aMZ} implies $m = 0$ or $m-1= 0$. Since $m > 0$, disjunctive syllogism yields $m-1 = 0$. That is $m=1$ is proved. 
\end{proof}


\begin{definition}
An integer $a$ is a {\it square} if there exists an
integer $b$ such that $a = b^2$.
\end{definition}

\begin{proposition} \label{pds}
Let $s$ be an integer. If $s$ and $2s$ are both square,
then $s = 0$.
\end{proposition}
\begin{proof}
In this proof we will use the fact that an integer $x$
is even if and only if $x^2$ is even.

Consider the set
\[
S = \bigl\{s \in \nZ \,|\, \ s > 0, \ s \ \text{ and } \
2s \ \text{ are squares } \bigr\}.
\]
Clearly $S \subseteq \nZ^+$.

Next we shall prove that $S$ does not have a minimum.
Let $s \in S$ be arbitrary.  Then $s > 0$ and there
exist positive integers $j$ and $k$ such that $s = j^2$
and $2s = k^2$. Since $k^2$ is even, the integer $k$ is
even. Therefore there exist a positive integer $m$ such
that $k = 2m$. Thus, $2 s = 4 m^2$, or, equivalently $s
= 2 m^2$. Clearly, $m^2 < 2 m^2 = s$.  Since $m$ is
positive, $m^2 > 0$. Now we have that $m^2 > 0$ and both
integers $m^2$ and $2m^2 = s$ are square.  Therefore
$m^2 \in S$ and $m^2 < s$. Consequently $s$ is not a
minimum of $S$.  Since $s \in S$ was arbitrary element
in $S$, we have proved that $S$ does not have a minimum.
By Axiom~\!WO, see \eqref{eqwo-cp}, $S = \emptyset$. Thus, there are
no positive integers $s$ such that both $s$ and $2s$ are
squares. Therefore, if $s$ and $s^2$ are both square,
then $s \leq 0$. Since for each square number $s$ by Proposition~\ref{psp} we have $s \geq 0$, we conclude that $s = 0$.
\end{proof}

\begin{proposition}
If $p \in \nZ$ and $q \in \nZ^+$, then $p^2 \neq 2 q^2$.
\end{proposition}

\begin{proof}
Let $p \in \nZ$ and $q \in \nZ^+$. Proposition~\ref{pds} is equivalent to: If $s$ is a square and $s \neq 0$, then $2s$ is not a square. Applying this to $q^2$ we conclude that $2q^2$ is not a square. Since $p^2$ is a square, we conclude $p^2 \neq 2 q^2$.
\end{proof}

The preceding proposition implies that a square of a rational number cannot equal $2$. In other words, $\sqrt{2}$ is irrational.




\section{Proof of the principle of mathematical induction}

\setlength{\fboxrule}{2pt}%
 % \fboxrule 1pt
 \fboxsep 6pt

In the next theorem the universe of discourse is the set $\nZ^+$ of positive integers.

\begin{theorem}
Let $P(n)$ be a propositional function involving a positive integer $n$. Then
\fboxsep 6pt
\[
\color{green}\boxed{\color{black}P(1)\wedge \Bigl( \forall \, k \  \bigl( P(k) \Rightarrow P(k+1) \bigr) \Bigr)} \color{black} \ \Rightarrow \ \fboxsep 6pt \color{red}\boxed{\color{black}\forall n \ P(n)}
\]
\end{theorem}
\begin{proof}
Recall that the implications $p\wedge q \Rightarrow r$ and $p\wedge (\neg r) \Rightarrow (\neg q)$ are equivalent. Therefore we will prove:
\fboxsep 4pt
\begin{equation} \label{eqimp}
\color{green}\boxed{\color{black} P(1) \wedge \bigl( \exists\, j \ \neg P(j) \bigr) } \color{black}  \Rightarrow
 \fboxsep 4pt
\color{red}\boxed{\color{black}  \exists \, k \  \bigl( P(k) \wedge \neg P(k+1)  \bigr)} \color{black}.
\end{equation}

\fboxsep 4pt
Assume $\color{green}\boxed{\color{black} P(1)}$ and  $\color{green}\boxed{\color{black}\exists\, j \ \neg P(j)}$. That is, assume that there exists $j_0 \in \nZ^+$ such that $\color{green}\boxed{\color{black} \neg P(j_0)}$. Now consider the set
\[
S = \bigl\{ n \in \nZ^+ \, | \, \neg P(n)  \bigr\} = \bigl\{ n \, | \, \bigl(n \in \nZ^+\bigr) \wedge \bigl( \neg P(n)\bigr)  \bigr\}.
\]
Clearly $S \subseteq \nZ^+$ and $j_0 \in S$. Hence
\[
\color{green}\boxed{\color{black} \bigl( S \subseteq \nZ^+ \bigr) \wedge \bigl( S \neq \emptyset \bigr) }
\]
is true. This and Axiom~\!WO, via modus ponens, yield that the set $S$ has a minimum, that is,
\setlength{\fboxrule}{2pt}%
 % \fboxrule 1pt
 \fboxsep 6pt
\begin{equation} \label{eq1}
\color{green}\boxed{\color{black} \exists \, m \in S \ \  \forall\, x \in S \ \ \ m \leq x }\color{black}.
\end{equation}
Since $m \in S$ we have \fboxsep 3pt $\color{green}\boxed{\color{black} m \in \nZ^+}$ and \fboxsep 3pt $\color{green}\boxed{\color{black} \neg P(m)}$. As  $\color{green}\boxed{\color{black} P(1)}$ is true, $\color{green}\boxed{\color{black} \bigl( \neg P(m)\bigr) \wedge P(1)}$ imply $1 \neq m$. Since \fboxsep 3pt $\color{green}\boxed{\color{black}1 = \min \nZ^+}$ we have
\fboxsep 3pt $\color{green}\boxed{\color{black} 1 \lt m}$. By the definition of the order $\lt$ we have
 \fboxsep 3pt $\color{green}\boxed{\color{black} m-1 \in \nZ^+}$.

Next we rewrite the proposition \eqref{eq1}. First, we notice that the proposition
\[
\forall x \in S \quad  m \leq x
\]
is equivalent to
\[
\forall x \quad x \in S \Rightarrow  m \leq x,
\]
which is further equivalent to
\[
\forall x  \quad    x < m \Rightarrow x \not\in S.
\]
Thus \eqref{eq1} is equivalent to
\begin{equation} \label{eq2}
\color{green}\boxed{\color{black} \exists \, m \in S \ \ \forall x  \  \  \bigl( x < m \Rightarrow x\not\in S\bigr) }\color{black}.
\end{equation}

Define $k = m-1$. Then $\color{green}\boxed{\color{black}k \in \nZ^+}$. Further, since $\color{green}\boxed{\color{black}k < m}$, \eqref{eq2} implies $\color{green}\boxed{\color{black}k \not\in S}$. Since $n \in S$ is equivalent to $(n \in \nZ^+)\wedge (\neg P(n))$ we conclude that  $\color{green}\boxed{\color{black}k \not\in S}$ is equivalent to  $\color{green}\boxed{\color{black}\bigl(k \not\in \nZ^+\bigr) \vee P(k)}$. Since we know that $\color{green}\boxed{\color{black}k \in \nZ^+}$ and $\color{green}\boxed{\color{black}k \not\in S}$, by disjunctive syllogism we deduce $\color{green}\boxed{\color{black}P(k)}$ is true. Recall that $\color{green}\boxed{\color{black}k+1 = m \in S}$. Hence $\color{green}\boxed{\color{black}\neg P(k+1)}$ is true. Thus, by setting $k=m-1$, we just proved that
\fboxsep 5pt
\[
\color{green}\boxed{\color{black}
\exists \, k \  \bigl( P(k) \wedge \neg P(k+1) \bigr)
}
\]
is true. This completes the proof.
\end{proof}

\section{Even and Odd Integers}

First recall the definitions of even and odd integers. The set of all even integers we denote by $\mathbb E$ and the set of all odd integers we denote by $\mathbb O$.
For $n \in \nZ$ we define
\begin{align}
n \in \mathbb E \qquad  & \Leftrightarrow \qquad \exists k \in \nZ \ \ n = 2 k,\\  n \in \mathbb O \qquad  & \Leftrightarrow \qquad \exists k \in \nZ \ \ n = 2 k + 1.  \end{align}

\begin{proposition}
$\mathbb E \cap \mathbb O = \emptyset.$
\end{proposition}
\begin{proof}
We prove this by contradiction. Assume that $\mathbb E \cap \mathbb O$ is a nonempty set. Let $n \in \mathbb E \cap \mathbb O$. Then there exist $k, j \in \mathbb Z$ such that $n = 2 k = 2 j + 1$. Hence, there exists $m = k - j \in \nZ$ such that $1 = 2m$. Recall that we proved $0 < 1 < 2$. Substituting $1 = 2m$, we get $0 < 2m < 2$. Since $0 < 2$, Proposition~\ref{p-OAx}(\ref{aOM}) applied to $2\cdot 0 < 2m$, yields $0 < m$. Proposition~\ref{p-OAx}(\ref{aOM}) applied to $2m < 2\cdot 1$, yields $m < 1$. Thus, we have $0 < m$ and $m < 1$ and $m \in \nZ$. By Proposition~\ref{pZ01} the statement ``$0 < m$ and $m < 1$ and $m \in \nZ$'' is false. Since the assumption that $\mathbb E \cap \mathbb O \neq \emptyset$ leads to a false statement, we proved $\mathbb E \cap \mathbb O = \emptyset$.
\end{proof}

\begin{proposition}
$\mathbb E \cup \mathbb O = \nZ.$
\end{proposition}
\begin{proof}
First we prove that  $\nZ^+ \subseteq \nE \cup \nO$. In other words we prove
\[
\forall \, n \in \nZ^+  \quad (n \in \mathbb E) \vee (n \in \mathbb O)
\]

The last displayed statement can be proved by Mathematical Induction. Set $P(n)$ to be $(n \in \mathbb E) \vee (n \in \mathbb O)$.

Since $1 = 2\cdot 0 + 1$ we have $1 \in \mathbb O$. Therefore, $(1 \in \mathbb E) \vee (1 \in \mathbb O)$ is true. So, the base step $P(1)$ is true.

Next we prove the inductive step. Let $n \in \nZ^+$ be arbitrary and prove the implication $P(n) \Rightarrow P(n+1)$. Assume that $P(n)$ is true. That is, assume that $(n \in \mathbb E) \vee (n \in \mathbb O)$. Consider two cases. For Case~1, assume $n \in \mathbb E$. Clearly $n \in \nE$ implies $n+1 \in \nO$. Therefore,  $(n+1 \in \mathbb E) \vee (n+1 \in \mathbb O)$ is true.  Thus $P(n+1)$ holds in this case.  For Case~2, assume $n \in \mathbb O$. Clearly $n \in \nO$ implies $n+1 \in \nE$.  Therefore,  $(n+1 \in \mathbb E) \vee (n+1 \in \mathbb O)$ is true.  Thus $P(n+1)$ holds in this case as well. Thus, for every $n\in\nZ^+$ we proved that $P(n) \Rightarrow P(n+1)$.

By Mathematical induction, this proves that $\forall \, n \in \nZ^+$ we have $(n \in \mathbb E) \vee (n \in \mathbb O)$. In other words, $\nZ^+ \subseteq \nE \cup \nO$.

Since $0 = 2\cdot 0$, we have $0 \in \nE$. Hence, $0 \in \nE \cup \nO$.

Finally we prove that $\nZ^- \subseteq \nE\cup \nO$.  Let $n \in \nZ$ be such that $n < 0$.  Then $-n > 0$ and thus, $-n \in \nE \cup \nO$. Now consider two cases. Case 1: if $-n \in \nE$, then $-n = 2k$ for some $k \in \nZ$. Hence, $n = 2(-k)$ with $-k \in \nZ$. Consequently, $n \in \nE$. Case 2: if $-n \in \nO$, then $-n = 2j+1$ for some $j \in \nZ$. Hence, $n = 2(-j) - 1 = 2(-j-1) + 1$ with $-j-1 \in \nZ$. Consequently, $n \in \nO$. In either case, $n \in \nE \cup \nO$.

In conclusion, we have proved that for every $n \in \nZ$ we have $n \in \nE \cup \nO$. That is $\mathbb E \cup \mathbb O = \nZ$.
\end{proof}


\section{The division algorithm}

The following theorem is called the {\em division algorithm}.

\begin{proposition} \label{pda}
Let $n$ be an integer and let $d$ be a positive integer.  Then
there exist unique integers $q$ and $r$ such that
\[
n = dq + r \ \ \ \text{  and  } \ \ \ 0 \leq  r < d.
\]
\end{proposition}
\begin{proof}
Let $n \in \nZ$ and let $d \in \nZ^+$. Define the set
\[
S = \Bigl\{ k \in \nZ \, \bigl| \bigr. \,  \bigl(k \geq 0\bigr) \wedge \bigl(\exists \, j \in \nZ \quad k = n - dj\bigr) \Bigr\}.
\]
By the definition of $S$ we have $S \subset \nZ$ and $S$ is bounded below by $0$.

Next we prove that $S$ is a nonempty set. We distinguish two cases for $n$: \ $n \geq 0$ and $n < 0$. If $n \geq 0$, then $n \in S$ since $n = n - d\cdot 0 \geq 0$. Now assume that $n < 0$. Then $-n > 0$. Now $-n>0$ and  $d \geq 1$, imply $-nd \geq -n$. Adding $n$ to both sides of $-nd \geq -n$ we get $n-dn \geq n-n =0$. Since with $j = n$ $k = n - d j = n - d n \in S$ we have proved that $S\neq \emptyset$ in this case. Thus, in each case we identified an integer in $S$, so $S$ is a nonempty set.

Since $S$ is both bounded below and nonempty, Proposition~\ref{pSbbm} implies that $S$ has a minimum. Denote that minimum by $r$. The integer $r$ has the following two properties: $r \in S$ and $r \leq k$ for all $k \in S$. Since $r \in S$, we have $r \geq 0$ and there exists $q \in \nZ$ such that $r = n - dq$. Hence we proved that there exist integers $r$ and $q$ such that $n = dq+r$ and $r \geq 0$.

It remains to prove that $r < d$. Consider the integer $r-d$. As $d > 0$ we have $r-d < r$. Since $x \in S$ implies $r \leq x$, the contrapositive of the last implication yields $r-d \not\in S$. Since
\[
x \in S \qquad \Leftrightarrow \qquad  (x \geq 0) \wedge \bigl( \exists \, j \in \nZ \quad x = n - dj \bigr)
\]
$r-d \not\in S$ means
\begin{equation} \label{eqvee}
\bigl(r-d < 0 \bigr) \ \vee \ \bigl( \forall \, j \in \nZ \ \ r-d \neq n-dj\bigr).
\end{equation}
However, we know that the following is true
\[
r-d = n-dq -d = n -d(q+1).
\]
Thus
\begin{equation} \label{eqnot}
\exists \, j \in \nZ \ \ r-d = n-dj.
\end{equation}
By disjunctive syllogism, \eqref{eqvee} and \eqref{eqnot} yield $r-d < 0$. That is $r < d$.

It remains to prove the uniqueness of $r$ and $q$. Assume that $q,r,q',r'$ are integers such that
\[
(n = dq + r)\wedge(0\leq r < d) \qquad \text{and} \qquad (n = dq' + r')\wedge(0\leq r' < d).
\]
Then
\[
dq+r = dq'+r' \quad \text{and} \quad 0\leq r < d \quad \text{and} \quad -d < r' \leq 0.
\]
Simplifying the first equality and adding the last two inequalities we get \[
r-r' = d(q'-q) \qquad \text{and} \qquad -d < r-r' < d.
\]
Hence
\[
-d < d(q'-q) < d.
\]
Since $0 < d$, Proposition~\ref{p-OAx}(\ref{aOM}) implies
\[
-1 < q' - q < 1.
\]
In Proposition~\ref{pZ01} we proved that there are no integers between $0$ and $1$. Since $q'-q$ is an integer we must have $-1 < q'-q \leq 0$. Multiplying by $-1 < 0$ and using Proposition~\ref{pmn} we conclude $0 \leq  -q'+q  < 1$. Now Proposition~\ref{pZ01} yields $-q' + q =0$. That is $q = q'$. Since $r-r' = d(q'-q)$ we also conclude that $r' = r$.
\end{proof}

\begin{definition} \label{3B}
The integer $r$ in Proposition \ref{pda} is called the {\it
remainder} left by $n$ when divided by $m$.
\end{definition}

\begin{example}  \label{3C}
When divided by $5$, the integer $17$ leaves a remainders of
$2$: $ 17 = 5\cdot 3 + 2. $ When divided by $5$, the integer
$-17$ leaves a remainder of $3$: $-17 = 5(- 4) + 3.$
\end{example}


\begin{definition} \label{3D}
Let $n$ be an integer.  Let $r$ be the remainder left by $n$
when divided by $2$. Then $r=0$ or $r=1$.  We say that $n$ is {\it even} if $r = 0$ and
that $n$ is {\it odd } if $r = 1$.
\end{definition}

\begin{remark}
In Proposition~\ref{pda} we proved that for every $n \in \nZ$ and every $d \in \nZ^+$ there exist unique $q \in \nZ$ and unique $r \in \nZ$ such that
\begin{equation} \label{eq-da}
n = d q + r \qquad \text{and} \qquad 0 \leq r < d.
\end{equation}
Dividing both relations in \eqref{eq-da} by $d > 0$ we get
\[
\frac{n}{d} = q + \frac{r}{d} \qquad \text{and} \qquad 0 \leq \frac{r}{d} < 1.
\]
Therefore we have
\[
q \in \nZ \qquad \text{and} \qquad q \leq \frac{n}{d} < q + 1.
\]
The last displayed line is exactly the definition of the floor of $\dfrac{n}{d}$. Thus, in the division algorithm
\[
q = \left\lfloor \dfrac{n}{d} \right\rfloor \qquad \text{and} \qquad r = n - d \, \left\lfloor \dfrac{n}{d} \right\rfloor
\]


\end{remark}


\end{document}


