1 The Integers
1.1 The Well-Ordering Principle and Induction
Our general goal is the generalization of common algebraic structures; we will try to
capture their essence by determining axioms which are responsible for their properties.
We start with the set of integers Z, considered along with the two operations of ad-
dition (+) and multiplication (·). We will spend some time trying to understand how
Z is put together with respect to these two operations, and we will identify several key
properties. We will then take a selection of those properties, the so-called ring axioms,
and eventually aim at studying all structures that are defined by requiring a set R along
with two operations (which will be called + and · even if they may have nothing to do
with the conventional + and ·) to satisfy the ring axioms. These structures will be called
rings: from this perspective, Z is a particular example of a ring. Other examples you are
(hopefully) familiar with are Q (‘rational’ numbers), R (‘real’ numbers), C (‘complex’
numbers); but many more exist, and most of them have nothing to do with numbers. We
will study ‘all’ of them at once in the sense that we will determine several features that
every such structure (as opposed to specific examples like Z or Q) must have. We will
(implicitly) define a category of rings by specifying certain types of functions (which
we will call ‘homomorphisms’) between rings.
In any case, we begin with Z. We will start by recalling several known facts about Z,
from a perspective that will perhaps be a little more modern and rigorous than what may
be seen in high-school math or Calculus. Everything we will see should sound familiar,
but the viewpoint may seem unusual at first—the goal will be to single out the key
facts that are responsible for ‘the way Z works’. These facts will be useful in studying
other examples, particularly coming from ‘modular arithmetic’, and the study of these
examples will guide us in choosing the axioms that we will use in order to define what
a ring is.
We do not really start with a blank slate: I will assume familiarity with the basic,
elementary-school properties of addition and multiplication between integers. I will also
assume familiarity with the notion of ‘ordering’ in Z: if a and b are integers, we write
a ≤ b to mean that a is ‘less than or equal to’ b, in the ordinary sense. This ordering
behaves in predictable ways with respect to the operations: for example, if a ≤ b and
c ≥ 0, then ac ≤ bc; and similar statements you already know.
We can take these basic properties for granted, but it is helpful to introduce some
terminology. We will begin by focusing on the fact that ‘division’ behaves rather pe-
,4 The Integers
culiarly in Z. For example, we can divide 18 by 3, getting a quotient of 6, which is an
element of Z. We can also divide 1 by 2, but the quotient is not an element of Z: there
is no integer c such that 1 = 2c. We need some terminology to be able to deal with this
distinction.
definition 1.1 Let a, b ∈ Z. We say that ‘b divides a’, or ‘b is a divisor of a’, or ‘a is
a multiple of b’, and write b | a, if there is an integer c such that a = bc.
Thus, 3 ‘divides’ 18 since 18 = 3 · 6 and 6 is an integer; while 2 does not divide 1,
because 1 = 2 · 21 but 12 is not an integer. The divisors of 12 are ±1, ±2, ±3, ±4, ±6, and
±12. Every integer divides 0, since 0 = b · c for some integer c; as it happens, c = 0
works. On the other hand, the only integer that 0 divides is 0 itself.
With this understood, we can already record a useful (if completely elementary) fact.
lemma 1.2 If b | a and a 0, then |b| ≤ |a|.
Proof Indeed, by definition of divisibility we have a = bc for some integer c; in par-
ticular, both b and c are nonzero since a 0. Since c ∈ Z and c 0, we have |c| ≥ 1.
And then
|a| = |b| · |c| ≥ |b| · 1 = |b|
as claimed.
‘Divisibility’ defines an order relation on the set of nonnegative integers (Exercise 1.2).
What Lemma 1.2 says is that, to some extent, this ‘new’ order relation is compatible
with the ordinary one ≤.
What if b does not divide a? We can still divide b into a (at least if b 0), but we have
to pay a price: we get a remainder as we do so. Even if this fact is familiar to you, we
will look into why it works the way it does, since it is something special about Z—we
have no need for this complication when we divide rational numbers, for example. So
there must be some special property of Z which is responsible for this fact.
This property is in fact a property of the ordering ≤ we reviewed a moment ago.
It will be responsible for several subtle features of Z; in fact, besides the basic high-
school properties of addition and multiplication, it is essentially the one property of Z
that makes it work the way it does. So we focus on it for a moment, before returning to
the issue of divisibility.
As recalled above, Z comes endowed with an order relation ≤. In fact, this is what
we call a ‘total ordering’. By this terminology we mean that given any two integers a
and b, one of three things must be true: a < b, or a = b, or a > b. The same can be
said of other sets of numbers, such as the set of rational numbers Q and the set of real
numbers R; but there is something about the ordering relation on Z that makes it very
special. Terminology: Z≥0 stands for the set of nonnegative integers:
Z≥0 = {a ∈ Z | a ≥ 0} = {0, 1, 2, 3, . . . } .
, 1.1 The Well-Ordering Principle and Induction 5
(Similarly Z>0 stands for the set of positive integers, Q≤0 is the set of nonpositive ratio-
nal numbers, and so on.) Another name for Z≥0 is N, the set of ‘natural numbers’. The
fact we need has everything to do with Z≥0 .
fact (Well-ordering principle) Every nonempty set of nonnegative integers contains a
least element.
We can summarize this fact by saying that Z≥0 is ‘well-ordered’ by the relation ≤. A
‘well-ordering’ on a set S is simply an order relation such that every nonempty subset
of S has a minimum.
The well-ordering principle should sound reasonable if not outright obvious: if we
have many bags of potatoes, there will be one (or more) bags with the least number
of potatoes. But whether this is obvious or not is a matter of perspective—if we were
to attempt to define Z rigorously, the well-ordering principle for nonnegative integers
would be one of the axioms we would explicitly adopt; there is (to my knowledge) no
direct way to derive it from more basic properties of the set of integers.
Also note that ≤ is not a well-ordering on the set Q≥0 of nonnegative rationals, or on
the set R≥0 of nonnegative reals. For example, the set of positive rationals is a nonempty
subset of Q≥0 , but it does not have a ‘least’ element. (If q > 0 were such an element, then
q
2 would be even smaller and still rational and positive, giving a contradiction.) So the
well-ordering principle is really a rather special feature of Z≥0 . We will derive several
key properties of Z from it, granting (as we already did above) simple facts about how
the ordering ≤ behaves with respect to the operations +, · on Z.
Even before we see the well-ordering principle in action in ‘algebra’ proper, it is
useful to observe that it already plays a role in a specific logical tool with which you
are already familiar: the process of induction depends on it. Every proof by induction
can be converted into an argument appealing to the well-ordering principle. (In fact, my
preference is often to do so.) Why?
As you likely know, induction works as follows. We want to prove a certain prop-
erty P(n) for all integers n ≥ 0. Suppose we manage to prove that
(i) P(0) holds: the property is true for n = 0; and
(ii) the implication P(n) =⇒ P(n + 1) holds for all n ≥ 0.
Then induction tells us that indeed, our property P(n) holds for all n ≥ 0. This smacks of
magic, particularly the first few times you see it in action, but it is in a sense ‘intuitively
clear’: the ‘seed’ P(0) holds because you have proved it by hand in (i); and then P(1)
holds since P(0) holds and you have proved in (ii) that P(0) =⇒ P(1); and then P(2)
holds since P(1) holds and you have proved that P(1) =⇒ P(2); and then P(3) holds
since P(2) holds and you have proved that P(2) =⇒ P(3); and so on forever.
The problem with this argument is that ‘so on forever’ is not mathematics. There is
an alternative argument which is rigorous, once you grant the truth of the well-ordering
principle. Here it is.
1.1 The Well-Ordering Principle and Induction
Our general goal is the generalization of common algebraic structures; we will try to
capture their essence by determining axioms which are responsible for their properties.
We start with the set of integers Z, considered along with the two operations of ad-
dition (+) and multiplication (·). We will spend some time trying to understand how
Z is put together with respect to these two operations, and we will identify several key
properties. We will then take a selection of those properties, the so-called ring axioms,
and eventually aim at studying all structures that are defined by requiring a set R along
with two operations (which will be called + and · even if they may have nothing to do
with the conventional + and ·) to satisfy the ring axioms. These structures will be called
rings: from this perspective, Z is a particular example of a ring. Other examples you are
(hopefully) familiar with are Q (‘rational’ numbers), R (‘real’ numbers), C (‘complex’
numbers); but many more exist, and most of them have nothing to do with numbers. We
will study ‘all’ of them at once in the sense that we will determine several features that
every such structure (as opposed to specific examples like Z or Q) must have. We will
(implicitly) define a category of rings by specifying certain types of functions (which
we will call ‘homomorphisms’) between rings.
In any case, we begin with Z. We will start by recalling several known facts about Z,
from a perspective that will perhaps be a little more modern and rigorous than what may
be seen in high-school math or Calculus. Everything we will see should sound familiar,
but the viewpoint may seem unusual at first—the goal will be to single out the key
facts that are responsible for ‘the way Z works’. These facts will be useful in studying
other examples, particularly coming from ‘modular arithmetic’, and the study of these
examples will guide us in choosing the axioms that we will use in order to define what
a ring is.
We do not really start with a blank slate: I will assume familiarity with the basic,
elementary-school properties of addition and multiplication between integers. I will also
assume familiarity with the notion of ‘ordering’ in Z: if a and b are integers, we write
a ≤ b to mean that a is ‘less than or equal to’ b, in the ordinary sense. This ordering
behaves in predictable ways with respect to the operations: for example, if a ≤ b and
c ≥ 0, then ac ≤ bc; and similar statements you already know.
We can take these basic properties for granted, but it is helpful to introduce some
terminology. We will begin by focusing on the fact that ‘division’ behaves rather pe-
,4 The Integers
culiarly in Z. For example, we can divide 18 by 3, getting a quotient of 6, which is an
element of Z. We can also divide 1 by 2, but the quotient is not an element of Z: there
is no integer c such that 1 = 2c. We need some terminology to be able to deal with this
distinction.
definition 1.1 Let a, b ∈ Z. We say that ‘b divides a’, or ‘b is a divisor of a’, or ‘a is
a multiple of b’, and write b | a, if there is an integer c such that a = bc.
Thus, 3 ‘divides’ 18 since 18 = 3 · 6 and 6 is an integer; while 2 does not divide 1,
because 1 = 2 · 21 but 12 is not an integer. The divisors of 12 are ±1, ±2, ±3, ±4, ±6, and
±12. Every integer divides 0, since 0 = b · c for some integer c; as it happens, c = 0
works. On the other hand, the only integer that 0 divides is 0 itself.
With this understood, we can already record a useful (if completely elementary) fact.
lemma 1.2 If b | a and a 0, then |b| ≤ |a|.
Proof Indeed, by definition of divisibility we have a = bc for some integer c; in par-
ticular, both b and c are nonzero since a 0. Since c ∈ Z and c 0, we have |c| ≥ 1.
And then
|a| = |b| · |c| ≥ |b| · 1 = |b|
as claimed.
‘Divisibility’ defines an order relation on the set of nonnegative integers (Exercise 1.2).
What Lemma 1.2 says is that, to some extent, this ‘new’ order relation is compatible
with the ordinary one ≤.
What if b does not divide a? We can still divide b into a (at least if b 0), but we have
to pay a price: we get a remainder as we do so. Even if this fact is familiar to you, we
will look into why it works the way it does, since it is something special about Z—we
have no need for this complication when we divide rational numbers, for example. So
there must be some special property of Z which is responsible for this fact.
This property is in fact a property of the ordering ≤ we reviewed a moment ago.
It will be responsible for several subtle features of Z; in fact, besides the basic high-
school properties of addition and multiplication, it is essentially the one property of Z
that makes it work the way it does. So we focus on it for a moment, before returning to
the issue of divisibility.
As recalled above, Z comes endowed with an order relation ≤. In fact, this is what
we call a ‘total ordering’. By this terminology we mean that given any two integers a
and b, one of three things must be true: a < b, or a = b, or a > b. The same can be
said of other sets of numbers, such as the set of rational numbers Q and the set of real
numbers R; but there is something about the ordering relation on Z that makes it very
special. Terminology: Z≥0 stands for the set of nonnegative integers:
Z≥0 = {a ∈ Z | a ≥ 0} = {0, 1, 2, 3, . . . } .
, 1.1 The Well-Ordering Principle and Induction 5
(Similarly Z>0 stands for the set of positive integers, Q≤0 is the set of nonpositive ratio-
nal numbers, and so on.) Another name for Z≥0 is N, the set of ‘natural numbers’. The
fact we need has everything to do with Z≥0 .
fact (Well-ordering principle) Every nonempty set of nonnegative integers contains a
least element.
We can summarize this fact by saying that Z≥0 is ‘well-ordered’ by the relation ≤. A
‘well-ordering’ on a set S is simply an order relation such that every nonempty subset
of S has a minimum.
The well-ordering principle should sound reasonable if not outright obvious: if we
have many bags of potatoes, there will be one (or more) bags with the least number
of potatoes. But whether this is obvious or not is a matter of perspective—if we were
to attempt to define Z rigorously, the well-ordering principle for nonnegative integers
would be one of the axioms we would explicitly adopt; there is (to my knowledge) no
direct way to derive it from more basic properties of the set of integers.
Also note that ≤ is not a well-ordering on the set Q≥0 of nonnegative rationals, or on
the set R≥0 of nonnegative reals. For example, the set of positive rationals is a nonempty
subset of Q≥0 , but it does not have a ‘least’ element. (If q > 0 were such an element, then
q
2 would be even smaller and still rational and positive, giving a contradiction.) So the
well-ordering principle is really a rather special feature of Z≥0 . We will derive several
key properties of Z from it, granting (as we already did above) simple facts about how
the ordering ≤ behaves with respect to the operations +, · on Z.
Even before we see the well-ordering principle in action in ‘algebra’ proper, it is
useful to observe that it already plays a role in a specific logical tool with which you
are already familiar: the process of induction depends on it. Every proof by induction
can be converted into an argument appealing to the well-ordering principle. (In fact, my
preference is often to do so.) Why?
As you likely know, induction works as follows. We want to prove a certain prop-
erty P(n) for all integers n ≥ 0. Suppose we manage to prove that
(i) P(0) holds: the property is true for n = 0; and
(ii) the implication P(n) =⇒ P(n + 1) holds for all n ≥ 0.
Then induction tells us that indeed, our property P(n) holds for all n ≥ 0. This smacks of
magic, particularly the first few times you see it in action, but it is in a sense ‘intuitively
clear’: the ‘seed’ P(0) holds because you have proved it by hand in (i); and then P(1)
holds since P(0) holds and you have proved in (ii) that P(0) =⇒ P(1); and then P(2)
holds since P(1) holds and you have proved that P(1) =⇒ P(2); and then P(3) holds
since P(2) holds and you have proved that P(2) =⇒ P(3); and so on forever.
The problem with this argument is that ‘so on forever’ is not mathematics. There is
an alternative argument which is rigorous, once you grant the truth of the well-ordering
principle. Here it is.
