\documentclass[%
version=last,%
a5paper,
10pt,%
headings=small,%
bibliography=totoc,%
index=totoc,%
twoside,%
reqno,%
cleardoublepage=empty,%
%open=any,%
%parskip=half,%
%draft=false,%
draft=true,%
%DIV=classic,%
DIV=11,%
headinclude=true,%
pagesize]%{scrreprt}
{scrartcl}

%\usepackage[notref,notcite]{showkeys}
%\renewcommand{\theequation}{\fnsymbol{equation}}

\usepackage[headsepline]{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\ohead{\pagemark}
\ihead{\headmark}

\hyphenation{Dede-kind}
\usepackage{hfoldsty,relsize}
\usepackage[neverdecrease]{paralist}
%\newenvironment{myenum}{\begin{compactenum}}{\end{compactenum}}
%\newenvironment{myitem}{\begin{compactitem}}{\end{compactitem}}
%\newenvironment{mydesc}{\begin{compactdesc}}{\end{compactdesc}}
\newenvironment{myenum}{\begin{enumerate}}{\end{enumerate}}
\newenvironment{myitem}{\begin{itemize}}{\end{itemize}}
\newenvironment{mydesc}{\begin{description}}{\end{description}}

\usepackage{url,pstricks}


\renewenvironment{quote}{\begin{list}{}
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}}
\item\relax}
{\end{list}}

\usepackage[polutonikogreek,english]{babel}

%\usepackage{cmbright} % documentation of gfsneohellenic suggests this
\usepackage{gfsneohellenic} % From the Greek Font Society
\usepackage{gfsporson} % From the Greek Font Society

\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}%
{%
\relscale{0.9}%
\textneohellenic{#1}}}%  Greek text


\usepackage{amsmath}
\newcommand{\lto}{\rightarrow}
\newcommand{\liff}{\leftrightarrow}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\setminus}{\smallsetminus}
\newcommand{\included}{\subseteq}
\newcommand{\pincluded}{\subset}
\newcommand{\size}[1]{\lvert#1\rvert}
\DeclareMathOperator{\gcm}{gcm}

\newcommand{\axiom}[1]{Axiom %
\ref{#1}\marginpar[\hfill\small Axiom \ref{#1}]{\small Axiom \ref{#1}}}
%\ref{#1}\marginpar[\hfill\ref{#1}]{\ref{#1}}}

\newcommand{\ax}[1]{%
\ref{#1}\marginpar[\hfill\small Axiom \ref{#1}]{\small Axiom \ref{#1}}}
%\ref{#1}\marginpar[\hfill\ref{#1}]{\ref{#1}}}

\newcommand{\axplain}[1]{%
\marginpar[\hfill\small Axiom \ref{#1}]{\small Axiom \ref{#1}}}
%\marginpar[\hfill\ref{#1}]{\ref{#1}}}

%\usepackage{stmaryrd} % for \varolessthan

\usepackage{amssymb}
\newcommand{\N}{\mathbb N}
\newcommand{\Q}{\mathbb Q}
\newcommand{\Qp}{\Q^{+}}
\newcommand{\R}{\mathbb R}


\usepackage{amsthm,bm,upgreek,mathrsfs}


\usepackage[all]{xy}
\newcommand{\Forall}[1]{\forall#1\;}
\newcommand{\Exists}[1]{\exists#1\;}

%\swapnumbers
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{document}

\title{Commutativity of Multiplication in\\Euclid's Arithmetic}
\author{David Pierce}
\date{Draft of May 5, 2015}
\publishers{Mathematics Department\\
Mimar Sinan Fine Arts University\\
Istanbul\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}

\maketitle
\tableofcontents
\section{Introduction}

In Euclid's \emph{Elements} \cite{Euclid-Heiberg-II,MR17:814b},
the arithmetical books---Books \textsc{vii, viii,} and \textsc{ix}---%
rely on no explicit postulates.
Nonetheless, I contend that,
on the basis of some plausible assumptions about numbers,
Propositions 1, 2, 4, 5, 6, 12, and 15 of Book \textsc{vii}
provide us with a valid nontrivial proof 
that multiplication of numbers is commutative.
The proof relies
on a theory of \emph{proportion,}
developed by means of
the so-called Euclidean Algorithm.

The commutativity of multiplication of numbers 
might be taken as a plausible assumption itself,
if numbers are thought of as rows of dots,
as in Figure \ref{fig:dots}.
\begin{figure}[ht]
\psset{unit=5mm}
\mbox{}\hfill
  \begin{pspicture}(2,3.2)
    \psdots(0,0)(1,0)(2,0)(0,1)(1,1)(2,1)(0,2)(1,2)(2,2)(0,3)(1,3)(2,3)
  \end{pspicture}
\hfill
  \begin{pspicture}(0,-0.5)(3,2)
    \psdots(0,0)(1,0)(2,0)(3,0)(0,1)(1,1)(2,1)(3,1)(0,2)(1,2)(2,2)(3,2)
  \end{pspicture}
\hfill\mbox{}
  \caption%[Mult.\ of points]
{Multiplication of rows of dots}\label{fig:dots}
  
\end{figure}
However, if numbers are thought of as bounded straight lines,
as in Euclid's diagrams and as in Figure \ref{fig:lines},
\begin{figure}[ht]
\psset{unit=5mm}
  \centering
  \begin{pspicture}(12,1.2)
    \psline(0,0)(12,0)
    \psline(0,1)(12,1)
\psdots(0,1)(3,1)(6,1)(9,1)(12,1)
\psdots[dotstyle=|](1,1)(2,1)(4,1)(5,1)(7,1)(8,1)(10,1)(11,1)
\psdots(0,0)(4,0)(8,0)(12,0)
\psdots[dotstyle=|](1,0)(2,0)(3,0)(5,0)(6,0)(7,0)(9,0)(10,0)(11,0)
  \end{pspicture}
  \caption%[Mult.\ of lines]
{Multiplication of bounded straight lines}\label{fig:lines}
  
\end{figure}
then the commutativity of multiplication is not obvious.

I make a more detailed analysis of Euclid's arithmetic elsewhere
\cite{Pierce-Eu-nth}.
Here I try to cast Euclid's proof of the commutativity of multiplication 
in modern terms, 
without giving a full account of why (or to what extent)
the result really \emph{is} Euclid's proof.
In one sense, the modern proof cannot be Euclid's proof,
since the modern proof is written out symbolically.

In \S\ref{sect:ax} below,
I give a list of axioms that I think Euclid uses implicitly.
There are some redundancies, as worked out in \S\ref{sect:mod};
but I have seen no reason to think that Euclid recognized these redundancies.
Some axioms allow us to prove results that Euclid may have taken as axiomatic;
see \S\ref{sect:proof}.

Thus the list of axioms is not entirely obvious.
I have tried to be explicit about the use 
or at least the \emph{first} use of an axiom in a given proof.
Axioms are thus named both in the main text, and in the margin.
This technique allowed me to make 
corrections and improvements to the list of axioms.
This work of correcting and improving may turn out not to have been finished.

\section{Outline of Euclid's Argument}

Multiplication is defined by
\begin{equation*}
  a\cdot b=\underbrace{a+\dots+a}_b.
\end{equation*}
If the Euclidean algorithm has the same steps for $a$ and $b$
that it does for $c$ and $d$,
this means
\begin{equation*}
  a:b::c:d.
\end{equation*}
Then in particular
\begin{equation}\label{eqn:1abba}
  1:a::b:b\cdot a.
\end{equation}
Also
\begin{equation}\label{eqn:a+c}
  a:b::c:d\implies a:b::a+c:b+d.
\end{equation}
Therefore, in particular, since $1:a::1:a$, also
\begin{equation}\label{eqn:gen}
  1:a::\underbrace{1+\dots+1}_b:\underbrace{a+\dots+a}_b,
\end{equation}
that is,
\begin{equation*}
  1:a::b:a\cdot b,
\end{equation*}
and consequently, because of \eqref{eqn:1abba},
\begin{equation*}
b\cdot a=a\cdot b.
\end{equation*}

A different proof in this style seems possible.
The proof of \eqref{eqn:a+c} uses the distribution axiom
\begin{equation*}
  (a+b)\cdot c=a\cdot c+b\cdot c,
\end{equation*}
for which Euclid gives intuitive justification.
The way he generalizes \eqref{eqn:a+c} to get \eqref{eqn:gen},
he might generalize the distribution axiom to get
\begin{equation*}
  (\underbrace{a+\dots+a}_b)\cdot c=\underbrace{a\cdot c+\dots+a\cdot c}_b,
\end{equation*}
that is,
\begin{equation*}
  (a\cdot b)\cdot c=(a\cdot c)\cdot b.
\end{equation*}
Letting $a$ be unity yields commutativity of multiplication.
This second proof may seem simpler; 
but then we are using symbolism that Euclid does not.
At this stage,
he may prefer to avoid talking about products of three (or more) factors.


\section{Euclid's Arithmetical Structure}

In his arithmetical books,
Euclid can be seen as working in a structure
\begin{equation*}
(\N,1,+,\times,<).
\end{equation*}
Here $1$ is \textbf{unity,} or the \textbf{unit,} 
in the sense of Definition 1 of Book \textsc{vii} of the \emph{Elements.}
(However, this definition itself 
may be a later addition to the \emph{Elements}; 
see \cite[\S3.1, p.\ 54]{Pierce-Eu-nth}.)
Then elements of $\N$ are \textbf{numbers,}
that is, multitudes of units in the sense of Definition 2.
Thus, for Euclid, there are many units.
They are all equal to one another, however:
this is noted explicitly in the proof of Proposition \textsc{vii}.15.
For Euclid, equality is not identity:
for example, in an isosceles triangle, by definition
two sides (and not just their ``lengths'') are equal.
Today we do treat equality as identity:
this should not cause us any problem in the present work.

The binary operation $+$ of \textbf{addition} is undefined,
though it has been used in the \emph{Elements} since the beginning:
at the head of Book \textsc i,
Common Notion 2 is,
\begin{quote}\centering
If equals be added to equals, the wholes are equal.
\end{quote}
We can read the expression $a+b$ in the conventional way,
as $a$ \textbf{plus} $b$, meaning $a$ with the addition of $b$.
For Euclid, this will be the same as $b+a$;
it is the \textbf{sum} of $a$ and $b$, or $b$ and $a$.
In Proposition \textsc i.35,
two parallelograms on the same base and in the same parallels
are equal to one another,
because one of the parallelograms can be cut up into pieces
that can be \emph{added} back together in a different way 
to form the other parallelogram.

The binary operation $\times$ of \textbf{multiplication} is defined,
after a fashion: Definition \textsc{vii}.15 reads
(in my translation),
\begin{quote}
  A number is said to \textbf{multiply} a number when,
however many units are in it,
so many times is the multiplicand composed,
and some number comes to be.
\end{quote}
As usual, when in use between two numbers, 
our symbol $\times$ will become a dot.
Suppose then
\begin{equation*}
a\cdot b=c.
\end{equation*}
Let us understand this to mean that
when $a$ is the multiplicand,
and $b$ the multiplier, then $c$ is produced.
We may write the equation also as
\begin{equation*}
  \underbrace{a+\dots+a}_b=c,
\end{equation*}
meaning $c$ is the sum of $b$ copies of $a$.
In Euclid's terminology, $a$ \textbf{measures} $a\cdot b$.
Measuring is an undefined notion in the text of the \emph{Elements} 
as we have it;
but by Definitions \textsc{vii}.3 and 5, there are two more ways to express it:
\begin{myitem}
  \item
$a$ is \textbf{part} of $a\cdot b$,
\item
$a\cdot b$ is a \textbf{multiple} of $a$.  
\end{myitem}
We might also say 
\begin{myitem}
  \item
$b$ \textbf{divides} $a\cdot b$ (into parts, each of which is equal to $a$),
\item
$a\cdot b$ is $b$ \textbf{times} $a$ (or $a$, $b$ times).
\item
$a\cdot b$ is the \textbf{product} of $a$ when multiplied by $b$.
\end{myitem}
The main point is that multiplication is initially presented 
in an asymmetrical way.
I have chosen to write $b$ times $a$ as $a\cdot b$, rather than $b\cdot a$,
because the former is the way that 
\emph{ordinal} multiplication is conventionally written today.

In Euclid, the status of unity as a number is ambiguous.
For example, by Definition \textsc{vii}.11,
\begin{quote}\centering
  A \textbf{prime number} is [a number] measured only by unity;
\end{quote}
and yet in the proof of Proposition \textsc{vii}.2,
it is noted that a number measures itself.
We may refer to the elements of $\N$ other than $1$ as \textbf{proper} numbers.

The binary relation $<$ is of course the (undefined) notion of 
being \textbf{less than.}
There is the converse relation $>$ of being \textbf{greater than,}
which may be more common in the \emph{Elements}:
Common Notion 5 (in Heath's numbering) is
\begin{quote}\centering
The whole is greater than the part,
\end{quote}
although the geometric sense of ``part'' meant here
is not the more precise arithmetical sense given above.
 
I propose now that, for Euclid, the structure
$(\N,1,+,\times,<)$ is tacitly understood 
to be isomorphic to some structure
\begin{equation*}
(\alpha\setminus1,1,+,\times,\in),
\end{equation*}
where in the latter structure, 
$1=\{0\}$, and
$+$ and $\times$ are \emph{ordinal} operations,
and $\alpha$ is a nonzero ordinal that is closed under these operations.
In particular, $\alpha=\upomega^{\upomega^{\beta}}$ 
for some ordinal $\beta$, as will be shown below.
Then Euclid makes additional assumptions ensuring that
$\beta=0$, so $\alpha=\upomega$,
and, in particular, multiplication must be commutative.

\section{Euclid's Implicit Axioms}\label{sect:ax}

Presumably Euclid is not actually thinking in terms of our ordinals.
But his work suggests that he understands the following axioms to be true
in the structure $(\N,1,+,\times,<)$:
\begin{myenum}
\item\label{ax:lo}
The less-than relation is a linear ordering.
  \item\label{ax:wo}
Every non-empty subset has a least element.
\item\label{ax:1}
$1$ is the least element of the whole set: $1\leq a$.
\item\label{ax:+ass}
Addition is associative: $a+(b+c)=(a+b)+c$.
\item\label{ax:<nat}
Addition makes greater: $a+b>a$.
\item\label{ax:+sol}
Being greater is achieved by addition: if $b>a$, 
then the equation
\begin{equation*}
  b=a+x
\end{equation*}
is soluble.
\item\label{ax:dist}
To multiply by a sum is to add the multiples:
%$a\cdot(b+c)=a\cdot b+a\cdot c$.
%That is, multiplication distributes over addition from the left:
\begin{equation*}
c\cdot(a+b)=c\cdot a+c\cdot b.
\end{equation*}
\item\label{ax:x1}
Multiplication by unity is identical:
$x\cdot1=x$.
\item\label{ax:.sol}
Division with remainder is always possible:
if $b\geq a$, then either the equation
\begin{equation*}
  b=a\cdot x
\end{equation*}
is soluble, or else the system
\begin{equation*}
  b=a\cdot x+y\And a>x
\end{equation*}
is soluble.
\item\label{ax:.ass}
Multiplication is associative: $c\cdot(b\cdot a)=(c\cdot b)\cdot a$.
\item\label{ax:.inc}
Multiplication by a proper number makes greater:
\begin{equation*}
  b>1\implies a\cdot b>a.
\end{equation*}
%if $b>1$, then $a\cdot b>a$.
\item\label{ax:1x}
The multiple of unity by a number is the number:
$1\cdot x=x$.
\item\label{ax:rdist}
A multiple of a sum is the sum of the multiples:
\begin{equation*}
  (a+b)\cdot c=a\cdot c+b\cdot c.
\end{equation*}
%$\times$ distributes over $+$ from the right.
\item\label{ax:+comm}
Addition is commutative: $b+a=a+b$.
\end{myenum}
All of these axioms but number \ref{ax:wo} belong to first-order logic.
Most of the axioms would seem to be ``obvious'' properties of numbers.
Axiom \ax{ax:rdist} is a modern interpretation
of Euclid's Proposition \textsc{vii}.5;
this proposition then should be understood as an 
``intuitive'' argument for why the axiom is true.
Axiom \ax{ax:.sol} is used implicitly in the Euclidean Algorithm.
We shall see below how the other axioms arise in Euclid's work.

\section{Modern Analysis of the Axioms}\label{sect:mod}

Meanwhile, let us note that
the first twelve axioms are indeed true in 
$(\upomega^{\upomega^{\beta}}\setminus1,1,+,\times,\in)$ as suggested above
(see for example \cite[Ch.\ IV]{MR1924429}).
It is a straightforward exercise to show that the converse is true as well:

\begin{theorem}\label{thm:1}
  If a structure $(A,1,\oplus,\otimes,<)$ satisfies the first nine axioms above,
then it is isomorphic to some structure $(\alpha\setminus1,1,+,\times,\in)$,
where $\alpha=\upomega^{\upomega^{\beta}}$ for some ordinal $\beta$, 
and $+$ and $\times$ are the ordinal operations.
\end{theorem}

\begin{proof}
Since $(A,<)$ is a well-ordered set by Axioms \ax{ax:lo} and \ax{ax:wo},
we may assume from the start that it is a nonempty ordinal with $0$ removed,
and $<$ is $\in$.
Showing that $\oplus$ and $\otimes$ are then the ordinal operations
means showing the following, 
for all $\alpha$ and $\beta$ in $A$:
\begin{myenum}
  \item
$1$ is the least element of $A$.
\item
$\alpha\oplus1$ is the successor $\alpha'$ of $\alpha$ with respect to $<$.
\item
$\alpha\oplus\beta'=(\alpha\oplus\beta)'$.
\item
If $\beta$ is a limit ordinal, 
then $\alpha\oplus\beta=\sup_{\xi<\beta}(\alpha\oplus\beta)$.
\item
$\alpha\otimes1=\alpha$.
\item
$\alpha\otimes\beta'=(\alpha\otimes\beta)\oplus\alpha$.
\item
If $\beta$ is a limit,
then $\alpha\otimes\beta=\sup_{\xi<\beta}(\alpha\otimes\xi)$.
\end{myenum}
An important part of the argument will be showing that the operations
$\xi\mapsto\alpha\oplus\xi$ and $\xi\mapsto\alpha\otimes\xi$ 
are strictly increasing.
Details are as follows.
\begin{asparaenum}
  \item
Minimality of $1$ is \axiom{ax:1}.

\item
Suppose $\alpha<\beta$ in $A$.
By \axiom{ax:+sol}, for some $\gamma$ in $A$,
\begin{equation*}
  \alpha\oplus\gamma=\beta,
\end{equation*}
and therefore, by Axioms \ax{ax:<nat} and \ax{ax:+ass},
for all $\delta$ in $A$,
\begin{equation*}
  \delta\oplus\alpha<(\delta\oplus\alpha)\oplus\gamma
=\delta\oplus(\alpha\oplus\gamma)=\delta\oplus\beta.
\end{equation*}
Thus the operation
\begin{equation*}
\xi\mapsto\delta\oplus\xi
\end{equation*}
on $A$ is strictly increasing.
If also $\beta<\alpha\oplus1$, 
this means $\alpha\oplus\gamma<\alpha\oplus1$,
so $\gamma<1$, which is absurd.
Thus $\alpha\oplus1$ is the successor, $\alpha'$, of $\alpha$.

\item
%By \axiom{ax:+ass},
$\alpha\oplus\beta'=\alpha\oplus(\beta\oplus1)
=(\alpha\oplus\beta)\oplus1
=(\alpha\oplus\beta)'$.

\item
Now suppose $\beta$ is a limit ordinal in $A$.
Then $\alpha\oplus\beta$ is an upper bound of 
$\{\alpha\oplus\xi\colon\xi<\beta\}$.
%Using \axiom{ax:wo}, 
Let $\gamma$ be the least upper bound.
Then for some $\delta$ in $A$, $\alpha\oplus\delta=\gamma$.
We must have $\delta\leq\beta$.
If $\delta<\beta$, then $\delta'<\beta$, 
so $\alpha\oplus\delta'\leq\gamma=\alpha\oplus\delta<\alpha\oplus\delta'$,
%but also $\alpha\oplus\delta'>\alpha\oplus\delta=\gamma$, 
which is absurd.
Therefore $\delta=\beta$.
Thus
\begin{equation*}
  \alpha\oplus\beta=\sup_{\xi<\beta}(\alpha\oplus\xi).
\end{equation*}
Therefore $\oplus$ is indeed the usual ordinal addition, $+$.

\item
$\alpha\otimes1=\alpha$ by \axiom{ax:x1}.
\item
By \axiom{ax:dist},
$\alpha\otimes\beta'=\alpha\otimes(\beta+1)=\alpha\otimes\beta+\alpha\otimes1
=\alpha\otimes\beta+\alpha$.

\item
Also, the operation
\begin{equation*}
\xi\mapsto\delta\otimes\xi
\end{equation*}
is strictly increasing: 
for if again $\alpha<\beta$ in $A$,
so that $\alpha+\gamma=\beta$ for some $\gamma$, then
\begin{equation*}
  \delta\otimes\alpha<\delta\otimes\alpha+\delta\otimes\gamma
=\delta\otimes(\alpha+\gamma)=\delta\otimes\beta.
\end{equation*}
Now suppose again $\beta$ is a limit ordinal in $A$,
so $\alpha\otimes\beta$ is an upper bound of 
$\{\alpha\otimes\xi\colon\xi<\beta\}$.
Let $\gamma$ be the least upper bound.
By \axiom{ax:.sol},
for some $\delta$ and $\theta$, we have either
$\alpha\otimes\delta=\gamma$ or $\alpha\otimes\delta+\theta=\gamma$,
where $\theta<\alpha$.
As before, $\delta$ must be $\beta$, and there is no $\theta$, that is,
\begin{equation*}
  \alpha\otimes\beta=\sup_{\xi<\beta}(\alpha\otimes\beta).
\end{equation*}
Thus $\otimes$ is ordinal multiplication, $\times$.
\end{asparaenum}

Finally, the ordinal $A\cup1$ has a Cantor normal form
\begin{equation*}
\upomega^{\alpha_0}\cdot b_0+\dots+\upomega^{\alpha_n}\cdot b_n, 
\end{equation*}
where
$\alpha_0>\dots>\alpha_n$ and $\{b_0,\dots,b_n\}\included\upomega\setminus1$.
If $n>0$, then $A$ contains $\upomega^{\alpha_0}\cdot b_0$,
but not its double,
 $\upomega^{\alpha_0}\cdot b_0+\upomega^{\alpha_0}\cdot b_0$ or
 $\upomega^{\alpha_0}\cdot(b_0\cdot2)$:
this is absurd,
since $A$ is closed under addition.  Thus $n=0$,
and we may write $A\cup1=\upomega^{\alpha}\cdot b$.
If $b>1$, then $b=c'$ for some $c$ in $\upomega\setminus1$,
and $A$ contains $\upomega^{\alpha}\cdot c$, but not its double,
which again is absurd.  Thus $b=1$, and $A\cup1=\upomega^{\alpha}$.
Since $A$ is closed under multiplication,
$\alpha$ must be closed under addition,
so as before, $\alpha$ must be $\upomega^{\beta}$ for some $\beta$.
\end{proof}

\begin{corollary}
  The first nine axioms entail the next three.
\end{corollary}

\begin{corollary}
  With the first nine axioms,
either of Axioms \ax{ax:rdist} and \ax{ax:+comm}
entails
\begin{equation*}
(\upomega\setminus1,+,\times,\in)\cong  (\N,1,+,\times,<),
\end{equation*}
and therefore $\times$ on $\N$ is commutative.
\end{corollary}

\begin{proof}
In the statement of Theorem \ref{thm:1},
if $\beta>0$, so $\alpha>\upomega$, then $\alpha$ contains $\upomega+1$;
but
\begin{gather*}
  (\upomega+1)\cdot\upomega
=\upomega\cdot\upomega<\upomega\cdot\upomega+1\cdot\upomega,\\
1+\upomega=\upomega<\upomega+1.\qedhere
\end{gather*}
\end{proof}

Of course Euclid's argument does not proceed as above.
Meanwhile, there is a more economical approach:

\begin{theorem}\label{thm:ind}
The first six axioms, along with Axiom \ref{ax:+comm},
entail
\begin{equation*}
(\upomega\setminus1,1,{}',\in)\cong  (\N,1,x\mapsto x+1,<).
\end{equation*}
\end{theorem}

\begin{proof}
Without the use of any axioms about $\N$ at all,
there is a unique homomorphism from $(\upomega\setminus1,1,{}')$ 
to $(\N,1,x\mapsto x+1)$.
Showing that it is an isomorphism is equivalent to establishing
the so-called Peano Axioms:
\begin{myenum}
  \item
$(\N,1,x\mapsto x+1)$ allows proof by induction.
\item
The operation $x\mapsto x+1$ on $\N$ is not surjective.
\item
The operation $x\mapsto x+1$ on $\N$ is injective.
\end{myenum}
(See for example \cite[Thm 2]{Pierce-IR}.)

\begin{asparaenum}
  \item
In $\N$, if $a\neq1$, then $a>1$ by \axiom{ax:1},
so $a=1+b$ for some $b$ by \axiom{ax:+sol},
and then $a=b+1$ by \axiom{ax:+comm}, 
so $b<a$ by \axiom{ax:<nat}.
Therefore $(\N,1,x\mapsto x+1)$ allows proof by induction
by the standard argument:
if $B\included\N$, and $1\in B$,
and $a+1\in B$ whenever $a\in B$,
then the complement $\N\setminus B$ can contain no least element,
so by \axiom{ax:wo} it is empty.

\item
Since $1\leq a<a+1$,
the operation $x\mapsto x+1$ on $\N$ is not surjective.

\item
Using also \axiom{ax:+ass} as in the proof of Theorem \ref{thm:1},
if $a<b$, then we have $a+1=1+a<1+b=b+1$,
and so by \axiom{ax:lo}, 
the operation $x\mapsto x+1$ on $\N$ is injective.
\end{asparaenum}

Finally, since the ordering of $\N$ is determined by the addition
according to the rule
\begin{equation}\label{eqn:<}
  a<b\iff\Exists xa+x=b,
\end{equation}
and a similar rule holds for $\upomega\setminus1$,
we have the desired isomorphism.
\end{proof}

Assuming only that the structure $(\N,1,x\mapsto x+1)$ 
allows proof by induction,
Landau shows implicitly in \emph{Foundations of Analysis} \cite{MR12:397m}
that there are unique operations $+$ and $\times$ on $\N$ such that
\begin{equation*}
  x+(y+1)=(x+y)+1
\end{equation*}
and
\begin{align}\label{eqn:.ind}
x\cdot1&=x,&x\cdot(y+1)&=x\cdot y+x.
\end{align}
By induction too,
these operations respect the remaining of the axioms above 
that govern the operations alone and $1$.
In the same way, multiplication is commutative.
Under the additional assumption
that $x\mapsto x+1$ is injective, but not surjective,
one shows that the relation $<$ defined by \eqref{eqn:<}
satisfies the remaining axioms.

\section{Euclid's Argument}\label{sect:proof}

We now look at Euclid's argument for the commutativity of multiplication.

We can understand \axiom{ax:1x} to mean
\begin{equation*}
  b=\underbrace{1+\dots+1}_b.
\end{equation*}
We can understand expressions like $1+\dots+1$,
and more generally $a+\dots+a$, as being justified by
\axiom{ax:+ass}.
But we can also understand the latter expression to mean simply
\begin{equation*}
  (\cdots((a+a)+a)+\cdots+a).
\end{equation*}

We might take the following as being obvious for numbers,
as Euclid seems to; but we \emph{can} prove it
using axioms already enumerated:

\begin{lemma}\label{lem:uni}
  In $\N$,
%by Axioms \ax{ax:+sol}, \ax{ax:wo}, \ax{ax:<nat}, and \ax{ax:+ass},
if $a>b$, then the equation
\begin{equation*}
  a=b+x
\end{equation*}
has a \emph{unique} solution.
\end{lemma}

\begin{proof}
  There is a solution by \axiom{ax:+sol}.
Any two solutions are comparable, by \axiom{ax:lo}.
But then there cannot be two solutions,
since $x\mapsto b+x$ is strictly increasing,
as in the proof of Theorem \ref{thm:1},
which uses also Axioms \ax{ax:<nat} and \ax{ax:+ass}.
\end{proof}

The unique solution in the theorem is the \textbf{difference} of $a$ from $b$,
denoted by
\begin{equation*}
  a-b.
\end{equation*}

\begin{lemma}\label{lem:sub}
  In $\N$,
if $a>b$, then
  \begin{equation*}
    c\cdot(a-b)=c\cdot a-c\cdot b.
  \end{equation*}
\end{lemma}

\begin{proof}
We have, by Axiom \ref{ax:dist}, 
\begin{gather*}
  b+(c-b)=a,\\
c\cdot\bigl(b+(c-b)\bigr)=c\cdot a,\\
c\cdot b+c\cdot(a-b)=c\cdot a,\\
c\cdot(a-b)=c\cdot a-c\cdot b.\qedhere
\end{gather*}
\end{proof}\marginpar{\hfill\small Axiom \ref{ax:dist}}

The \textbf{Euclidean Algorithm}
is given in \textbf{Propositions 1 and 2} of Book \textsc{vii}.
We combine these propositions into one:

\begin{theorem}\label{thm:alg}
If $a_1>a_2$, there are sequences
\begin{align*}
&(b_1,b_2,\dots,b_n),&&(a_1,a_2,\dots,a_{n+1})
\end{align*}
given by
\begin{gather*}
  a_1=a_2\cdot b_1+a_3\And a_2>a_3,\\
  a_2=a_3\cdot b_2+a_4\And a_3>a_4,\\
\makebox[3cm]{\dotfill},\\
a_k=a_{k+1}\cdot b_k+a_{k+2}\And a_{k+1}>a_{k+2},\\
\makebox[3cm]{\dotfill},\\
a_n=a_{n+1}\cdot b_n.
\end{gather*}
Thus
\begin{equation*}
  a_1>a_2>\dots>a_n>a_{n+1}.
\end{equation*}
Then,
%by Axioms \ax{ax:.ass}, \ax{ax:x1}, and \ax{ax:dist},
$a_{n+1}$ is a common measure of $a_1$ and $a_2$,
and $a_{n+1}$ is measured by every common measure of $a_1$ and $a_2$.
Moreover,
%By Axioms \ax{ax:1} and \ax{ax:.inc}, 
$a_{n+1}$ is greater than every other common measure of $a_1$ and $a_2$.
\end{theorem}

\begin{proof}
By \axiom{ax:.sol},
from $a_k$ and $a_{k+1}$,
we can obtain $b_k$ and perhaps $a_{k+2}$.
By \axiom{ax:wo}, for some $n$, there is no $a_{n+2}$.
We can now compute
\begin{align*}
    a_{n-1}
&=a_n\cdot b_{n-1}+a_{n+1}&&\\
&=(a_{n+1}\cdot b_n)\cdot b_{n-1}+a_{n+1}&&\\
&=a_{n+1}\cdot(b_n\cdot b_{n-1})+a_{n+1}&&\text{[Axiom \ref{ax:.ass}]}\\
&=a_{n+1}\cdot(b_n\cdot b_{n-1})+a_{n+1}\cdot1&&\text{[Axiom \ref{ax:x1}]}\\
&=a_{n+1}\cdot(b_n\cdot b_{n-1}+1).&&\text{[Axiom \ref{ax:dist}]}
\end{align*}%
\axplain{ax:.ass}%
\axplain{ax:x1}%
\axplain{ax:dist}
Continuing in this way, we obtain
$a_{n+1}$ as a common measure of $a_1$ and $a_2$.
Similarly, every common measure of $a_1$ and $a_2$
measures $a_3$, and $a_4$, and so on up to $a_{n+1}$.
Since in general $1\leq b$ by \axiom{ax:1}, we have
\begin{equation*}
  a\leq a\cdot b
\end{equation*}
by \axiom{ax:.inc}.
In particular, if $a$ measures $c$, then $a\leq c$.
\end{proof}

Thus $a_{n+1}$ as in the theorem is the \textbf{greatest common measure} 
of $a_1$ and $a_2$.
We may write
\begin{equation*}
  a_{n+1}=\gcm(a_1,a_2).
\end{equation*}
Two numbers are \textbf{prime to one another,}
as in Definition 12, if their only (and therefore their greatest)
common measure is unity.

As noted earlier, \textbf{Proposition 5} of Book \textsc{vii} 
is our \axiom{ax:rdist}.
Meanwhile, though \emph{proportion} is mentioned in Definition 4,
the real meaning is suggested by \textbf{Proposition 4:}
four numbers $a$, $b$, $c$, and $d$ are \textbf{proportional,}
and we shall write this as
\begin{equation}\label{eqn:abcd}
  a:b::c:d,
\end{equation}
just in case, for some $e$ and $f$,
\begin{equation}\label{eqn:ef}
\begin{aligned}
  a&=\gcm(a,b)\cdot e,&c&=\gcm(c,d)\cdot e,\\
b&=\gcm(a,b)\cdot f,&d&=\gcm(c,d)\cdot f.
\end{aligned}
\end{equation}

Euclid seems not to make the following two lemmas explicit.
Lemma \ref{lem:.canc}, like Lemma \ref{lem:uni},
might be considered as axiomatic.
Lemma \ref{lem:prop}
might be taken as an obvious consequence of the axioms,
although writing out a proof in modern fashion is tedious.

\begin{lemma}\label{lem:.canc}
%  By Axioms \ax{ax:wo}, \ax{ax:+sol}, ve \ax{ax:dist},
If $a\cdot b=a\cdot c$, then $b=c$.
\end{lemma}

\begin{proof}
  If $b\neq c$, then we may assume $b<c$, by \axiom{ax:lo}.
But then $a\cdot b<a\cdot c$,
since $x\mapsto a\cdot x$ is strictly increasing,
as in the proof of Theorem \ref{thm:1},
which uses Axioms \ax{ax:+sol}, \ax{ax:<nat}, and \ax{ax:dist}.
\end{proof}

\begin{lemma}\label{lem:prop}
%By Axioms \ax{ax:.ass}, \ax{ax:1}, and \ax{ax:.inc},
Under the conditions \eqref{eqn:ef}, 
$e$ and $f$ must be prime to one another.
Conversely, if this is so, and
\begin{equation}\label{eqn:gh}
  \begin{aligned}
  a&=g\cdot e,&c&=h\cdot e,\\
b&=g\cdot f,&d&=h\cdot f
\end{aligned}
\end{equation}
for some $g$ and $h$, then \eqref{eqn:abcd} holds.
\end{lemma}

\begin{proof}
Given \eqref{eqn:ef} and \axiom{ax:.ass},
we find that $\gcm(a,b)\cdot\gcm(e,f)$ is a common measure of $a$ and $b$.
Then
\begin{equation*}
  \gcm(a,b)\cdot\gcm(e,f)\leq\gcm(a,b)
\end{equation*}
by Theorem \ref{thm:alg};
but if $\gcm(e,f)>1$, then
\begin{equation*}
  \gcm(a,b)\cdot\gcm(e,f)>\gcm(a,b)
\end{equation*}
by \axiom{ax:.inc};
therefore $\gcm(e,f)=1$ by Axioms \ax{ax:lo} and \ax{ax:1}.

Conversely, if \eqref{eqn:gh} holds,
then $g$ is a common measure of $a$ and $b$,
so for some $k$, 
\begin{equation*}
  g\cdot k=\gcm(a,b).
\end{equation*}
But for some $e'$ and $f'$,
\begin{gather*}
g\cdot e=  a=\gcm(a,b)\cdot e'=(g\cdot k)\cdot e'=g\cdot(k\cdot e'),\\
g\cdot f=  b=\gcm(a,b)\cdot f'=(g\cdot k)\cdot f'=g\cdot(k\cdot f')
\end{gather*}
by \axiom{ax:.ass}, so
\begin{align*}
  e&=k\cdot e',&f&=k\cdot f'
\end{align*}
by Lemma \ref{lem:.canc},
and so $k$ is a common divisor of $e$ and $f$.
Suppose these are prime to one another.
then $g=\gcm(a,b)$ by \axiom{ax:x1}, and likewise $h=\gcm(c,d)$.
We thus obtain \eqref{eqn:ef}, and therefore \eqref{eqn:abcd}.
\end{proof}

I suppose it is just possible that Euclid overlooked 
the need to prove the last lemma.
It seems to me more likely that he would reason as follows.
If $e$ and $f$ are prime to one another,
this means applying the Euclidean Algorithm to them yields unity.
But if we replace unity with $g$,
obtaining $a$ and $b$ as in \eqref{eqn:ef},
then the same steps of the algorithm will obviously yield $g$.

In any case, the lemma yields the following,
which is \textbf{Proposition 12} of Book \textsc{vii}:

\begin{theorem}\label{thm:+}
%By \axiom{ax:rdist}, 
If $a:b::c:d$, then
\begin{equation*}
a:b::a+c:b+d.
%  x:y::z:w\lto x:y::x+z:y+w.
\end{equation*}
\end{theorem}

\begin{proof}
Suppose \eqref{eqn:abcd} holds,
so that \eqref{eqn:ef} holds.
By \axiom{ax:rdist},
\begin{gather*}
    a+c=\bigl(\gcm(a,b)+\gcm(c,d)\bigr)\cdot e,\\
b+d=\bigl(\gcm(a,b)+\gcm(c,d)\bigr)\cdot f,
\end{gather*}
and therefore $a:b::a+c:b+d$ by Lemma \ref{lem:prop}.
\end{proof}

Euclid's \textbf{Proposition 15}
is that if 
$b$ measures $a$ as many times as unity measures $c$, 
then $c$ measures $a$ as many times as unity measures $b$.
Since $c=1\cdot c$ by \axiom{ax:1x},
the conclusion is
\begin{equation*}
  b\cdot c=a\implies c\cdot b=a,
\end{equation*}
or simply the following theorem, which is Euclid's Proposition 16.

\begin{theorem}
  In $\N$, multiplication is commutative:
  \begin{equation*}
    a\cdot b=b\cdot a.
  \end{equation*}
\end{theorem}

\begin{proof}
By Theorem \ref{thm:alg},
\begin{equation*}
  \gcm(a,a\cdot b)=a.
\end{equation*}
Since again $1\cdot b=b$ by \axiom{ax:1x},
so that $\gcm(1,b)=1$,
 we now have
\begin{equation}\label{eqn:1b}
  1:b::a:a\cdot b.
\end{equation}
Since
\begin{align*}
  a&=\underbrace{1+\dots+1}_a,&
b\cdot a&=\underbrace{b+\dots+b}_a,
\end{align*}
repeated application of Theorem \ref{thm:+} yields
\begin{equation}\label{eqn:ba}
  1:b::a:b\cdot a.
\end{equation}
Comparison with \eqref{eqn:1b} yields the desired conclusion.
Such, approximately, is Euclid's argument.
Strictly, the comparison of two proportions is not needed, 
but by definition of proportion, and \axiom{ax:x1}, \eqref{eqn:ba} yields
\begin{gather*}
  a=\gcm(a,b\cdot a)\cdot1=\gcm(a,b\cdot a),\\
b\cdot a=\gcm(a,b\cdot a)\cdot b=a\cdot b.
\end{gather*}
The possibility of applying Theorem \ref{thm:+} 
repeatedly to obtain \eqref{eqn:ba}
might be taken as an implicit rule of inference.
Today we can justify \eqref{eqn:ba} by induction.
First, by \axiom{ax:1x},
\begin{equation*}
  1:b::1:1\cdot b.
\end{equation*}
Assuming $1:b::c:c\cdot b$, we have
\begin{equation*}
  1:b::c+1:c\cdot b+b;
\end{equation*}
and $c\cdot b+b=c\cdot b+1\cdot b=(c+1)\cdot b$ 
by Axioms \ax{ax:1x} and \ax{ax:rdist}.
In the proof of Theorem \ref{thm:ind},
we used Axioms \ax{ax:1}, \ax{ax:+sol}, \ax{ax:+comm}, \ax{ax:<nat},
and \ax{ax:wo} 
to justify proof by induction.
\end{proof}

%\bibliographystyle{plain}
%\bibliography{../references}

\begin{thebibliography}{1}

\bibitem{Euclid-Heiberg-II}
Euclid.
\newblock {\em Euclidis Elementa}, volume~II of {\em Euclidis Opera Omnia}.
\newblock Teubner, Leipzig, 1884.
\newblock Edited with Latin interpretation by I. L. Heiberg. Books V--IX.

\bibitem{MR17:814b}
Euclid.
\newblock {\em The Thirteen Books of {E}uclid's {E}lements}.
\newblock Dover Publications, New York, 1956.
\newblock Translated from the text of {H}eiberg with introduction and
  commentary by Thomas L. Heath. In three volumes. Republication of the second
  edition of 1925. First edition 1908.

\bibitem{MR12:397m}
Edmund Landau.
\newblock {\em Foundations of Analysis. {T}he Arithmetic of Whole, Rational,
  Irrational and Complex Numbers}.
\newblock Chelsea Publishing Company, New York, N.Y., third edition, 1966.
\newblock Translated by F. Steinhardt; first edition 1951; first German
  publication, 1929.

\bibitem{MR1924429}
Azriel Levy.
\newblock {\em Basic set theory}.
\newblock Dover Publications Inc., Mineola, NY, 2002.
\newblock Reprint of the 1979 original [Springer, Berlin].

\bibitem{Pierce-IR}
David Pierce.
\newblock Induction and recursion.
\newblock {\em The De Morgan Journal}, 2(1):99--125, 2012.
\newblock
  \url{http://education.lms.ac.uk/2012/04/david-pierce-induction-and-recursion/}.

\bibitem{Pierce-Eu-nth}
David Pierce.
\newblock On the foundations of arithmetic in {E}uclid.
\newblock \url{http://mat.msgsu.edu.tr/~dpierce/Euclid/}, April 2015.
\newblock 98 pp., size A5.

\end{thebibliography}


\end{document}