2.1 Axioms
To prove results about integers we need a starting point. What are the integers? What properties do they have?
We must have some properties of the integers that we accept without requiring a proof. Without such a starting point, we would need to prove each property in terms of some previous result which in turn would require proof in terms of other results – and we would be stuck in an infinite descent.
These properties, which we accept without proof are referred to as axioms. We may think of these are defining what we mean by the set of integers.
In Chapter 3, we shall learn more of Euclid, who’s most important contribution to mathematics, whilst also being famous for many other things, was the formulation of the axiomatic method.
In all of his writings he carefully sets out his assumptions and his rules for reasoning and then develops mathematical theory relying only on those rules or axioms.
We denote the set of integers by \(\mathbb{Z}\). This comes from the German word Zahlen, meaning numbers.
The integers satisfy the following axioms:
- [Operations (Op)] The integers are equipped with two binary operations1, addition and multiplication. These operations are denoted by the symbols \(+, \cdot\) respectively.
- [Identity (Id)] \(\mathbb Z\) contains two special elements, denoted \(0\) and \(1\), with \(0\neq 1\) such that for any integer \(m\), \(m+0=0+m=m\) and \(m\cdot 1=1\cdot m=m\).
- [Negation (Neg)] For every integer \(m\), there exists an integer denoted \(-m\) such that \(m+(-m)=(-m)+m=0\).
We write \(a-b\) as a shorthand for \(a+(-b)\). - [Commutative (Comm)] Addition and multiplication are commutative, i.e. \(m+n=n+m\) and \(m\cdot n=n\cdot m\) for all \(m,n\in \mathbb{Z}\)
- [Associative (As)] Addition and multiplication are associative, i.e. \((m+n)+p=m+(n+p)\) and \(m\cdot (n\cdot p)=(m\cdot n)\cdot p\) for all \(m,n,p\in \mathbb{Z}\)
- [Distributive (Dist)] Multiplication distributes over addition, i.e, \(m\cdot (n+p)=m\cdot n + m\cdot p\) for all \(m,n,p\in \mathbb{Z}\).
- [Zero divisors (ZD)] If \(m\cdot n=0\) then \(m=0\) or \(n=0\).
As well as the algebraic structure the integers have an ordering, by size, which interacts with the algebra. The axioms for this ordering are as follows:
- [Order relation (Ord)] \(\mathbb Z\) is equipped with a relation \(\leq\) called “less than or equal to”.
- [Reflexive (Ref)] Every integer \(m\) satisfies \(m\leq m\).
- [Antisymmetric (ASy)] Given two integers \(m,n\), if \(m\leq n\) and \(n\leq m\) then \(m=n\).
- [Transitive (Tr)] If \(m,n,p\) are integers with \(m\leq n\) and \(n\leq p\) then \(m\leq p\).
- [Comparability (Comp)] Given any two integers \(m,n\) either \(m\leq n\) or \(n\leq m\).
- [Shift (Sh)] If \(m,n,p\) are integers with \(m\le n\), then \(m+p\le n+p\)
- [Scale (Sc) ] If \(m,n,p\) are integers with \(m\leq n\) and \(0\le p\) then \(m\cdot p\le n\cdot p\).
- [Well ordering (WO)] The well ordering principle – any non-empty subset of non-negative2 integers has a unique least element.
We say that \(n\) is the least element of a set \(S\) if
- \(n\in S\) and
- \(\forall m \in S\) if \(m\leq n\) then \(m=n\).
The second condition is really telling us that no \(m\in S\) is strictly less than \(n\).
We accept these axioms as being true without requiring any justification of them. We will however justify almost ALL other results in this course.
We can also introduce the symbols \(\geq\), \(<\) and \(>\) defined as:
- \(m\geq n\) is defined to be \(n\leq m\)
- \(m<n\) is defined to be \(m\leq n\) and \(m\neq n\)
- \(m>n\) is defined to be \(n\leq m\) and \(m\neq n\)
Note that if \(m<n\) is false then \(m\leq n\) is false or \(m\neq n\) is false. If \(m\leq n\) is false then by (Comp) we have \(n\leq m\). If \(m\neq n\) is false then (by double \(\lnot\)) \(m=n\) is true so \(n\leq m\) by (Ref). Hence not \(m < n\) implies \(n\leq m\).
Conversely suppose \(n\leq m\) is true. The predicate \(m\leq n\) is either true or false. If it is true then \(m=n\) by (Ref) so \(m<n\) is false. On the other hand if \(m\leq n\) is false then \(m<n\) is false by definition.
Hence we have proved that “not \(m<n\)” \(\iff\) “\(n\leq m\)”. Of course it also follows that “not \(n\leq m\)” \(\iff\) “\(m<n\)”. We can therefore freely use this “translation” of not \(n\leq m\) in any future proofs.
None of the axioms mention division. Indeed we don’t even have a symbol for division since this is not defined as an operation on pairs of integers.
What can we do if we want to divide integers? We can take the integer part of the quotient along with the remainder, for example \(13\) divided by \(5\) is \(2\) with remainder \(3\). We do not need the notation of division to write this, instead we can write \[13 = 2\cdot 5 + 3.\] The fact that we can always “divide” (be a non-zero integer) to get a quotient and remainder is a result called the Remainder Theorem which we will prove at the end of this chapter.
Show that if \(x\) is a non-zero integer, then the sequence \[ x, 2x, 3x, \ldots \] contains no repetition.
The example is asking us to show that if \(a\) and \(b\) are distinct positive integers then \(ax\ne bx\). (In fact we won’t use positivity here as this is not required.)
The strategy is to use a proof by contradiction. Supposing that \(ax=bx\) we would like to rearrange this as \((a-b)x=0\) and then use (ZD) to deduce that either \(a=b\) or \(x=0\) both of which are assumed to be false (\(x\) is non-zero and \(a,b\) are distinct.)
How do we rearrange \(ax=bx\) to get \((a-b)x=0\)? We would like to subtract \(bx\) from both sides, or more precisely add \(-(bx)\) to both sides. However this yields the left-hand side as \((ax)+-(bx)\) which – as written – does not have a common term of \(x\) to pull out using (Dist).
To fix this we should add \((-b)x\) to both sides3. This will leave us with \(bx+(-b)x=(b+-b)x=0\cdot x\) on the right-hand side, and this is zero.
But wait, how do we know that \(0\cdot x=0\)? We need to prove this first. Note: (ZD) tells us that if \(m\cdot n=0\) then \(m=0\) or \(n=0\) but we need the converse: if \(m=0\) or \(n=0\) then \(m\cdot n=0\).
4 For all integers \(n\) \[0\cdot n = n \cdot 0 = 0.\]
Proof. We will focus on showing that \(0\cdot n=0\) since we can use (Comm) to show that \(n\cdot 0=0\cdot n\).
When we look at the axioms we see that there is only one axiom (Id) which allows us to write something which is a product as an expression which does not involve a product. We will therefore need to use this axiom: \[1\cdot n = n\] The idea is now to subtract \(n\) from both sides. We then need to show that \(1\cdot n+(-n)\) is the same as \(0\cdot n\) for which the trick is to write \(1\cdot n\) as \((0+1)\cdot n\) and use distributivity: \[ \begin{array}{rll} 0\;\;\; =&n+(-n)&\textit{(Neg)}\\ =&(1\cdot n)+(-n)&\textit{(Id)}\\ =&((0+1)\cdot n)+(-n)&\textit{(Id)}\\ =&((0\cdot n)+(1\cdot n))+(-n)&\textit{(Dist)}\\ =&(0\cdot n)+((1\cdot n)+(-n))&\textit{(As)}\\ =&(0\cdot n)+(n+(-n))&\textit{(Id)}\\ =&(0\cdot n)+0&\textit{(Neg)}\\ =&0\cdot n&\textit{(Id)}\\ \end{array} \]
We can now return to the solution to Example 2.2.
Solution. Our premise is that \(x\neq 0\) and we also suppose, by way of contradiction, that \(ax=bx\).
Then adding \((-b)x\) to both sides we deduce that \[ax+(-b)x = bx +(- b)x.\]Now the right hand side of this equation is equal to \((b+(-b))x\) by (Dist) which equals \(0\cdot x\) by (Neg). By Lemma 2.3 we know that \(0\cdot x=0\).
Hence \[ax+(-b)x = bx +(- b)x=0.\]Now rearranging the left-hand side \(ax+(-b)x\), by axiom (Dist) becomes \((a+(-b))x\), so we have shown that \((a+(-b))x=0\).
From axiom (ZD), we can now deduce that either \(a+(-b)=0\) or \(x=0\). By our original assumption, \(x\ne0\) and so we conclude that \(a+(-b)=0\). We can now add \(b\) to both sides of this equation to deduce \[(a+(-b))+b=0+b=b\] by (Id). Now by (As) the left-hand side is \(a+((-b)+b)\) and applying (Neg) we have \[a+0=a+((-b)+b) = b\] Consequently we deduce that \(a = b\) by axiom (Id).
This is the contradiction that we are seeking as \(a,b\) were assumed to be distinct and so we conclude that the terms in the sequence are all distinct.
When when we have an equation like \(a+(-b)=0\) we often wish to add \(b\) (to get \(a=b\)). To save going through the axioms every time, let’s write a Lemma we can come back to.
For all integers \(m,n\) \[(m+(-n))+n=m\] and \[(m+n)+(-n)=m\]
Proof. We have \((m+(-n))+n=m=m+((-n)+n)\) by (As).
Now \((-n)+n=0\) by (Neg) so \((m+(-n))+n=m=m+0\).
This equals \(m\) by (Id).
The second statement is proved in exactly the same way!
A binary operation on a set (here the integers \(\mathbb Z\)) means a function taking two elements from the set at input and returning one as output, for example \(+\;:\;(m,n)\mapsto m+n\).↩︎
An integer \(n\) is defined to be non-negative if \(0\leq n\).↩︎
Of course it is true that \(-(bx)=(-b)x\) but we would need to prove this first.↩︎
A Lemma is a little theorem which will be used to prove other results.↩︎