} Natural numbers cannot be defined k1.1k
There are no definitions for any of the concepts (like air, water, cat, etc.) used in natural languages. Their
genesis is at the very root of our ability as a species for language. We acquire these concepts from examples of
previous usage. And we are often corrected for wrong usage. Owing to this model of learning and rectifying,
none of the natural languages provide a definition for any of the concepts used.
A latter–day logician cannot remedy the above defect by rigorously defining all the terms of a natural language.
A reason is to be found in the use of our concepts to real world situations. More specifically, an attempted
definition for any given concept cannot anticipate all future instances of the real world for which that concept
might be used. For example, on a visit to a zoo, a child calls a tiger a cat and thus misuses a working definition
of the concept of ‘cat’ constructed in its backyard.
Thus, a final definition for any of these concepts – which will not be treated as a misuse at a later date –
will remain eternally elusive. In this sense, to a logician, each and every natural language is an unendurable
nightmare.
The situation outlined above applies to the concept of natural numbers. For the latter have arisen from the
real world activity of counting.
} The set of natural numbers N = {1, 2, 3, 4, . . .} k1.2k
Having realized that a rigorous definition of natural numbers is impossible, we introduce them as concepts for
counting objects of same kind. Suppose we have a goat. Then we say we have one goat. Bring another goat.
Together, we say that we have two goats. Likewise, we say we have one sheep or two cats depending on the
situation. We may imagine the concepts of one, two, three, four, etc. to have arisen this way.
With every supply of goats being limited, should not this process of creating newer and newer natural numbers
terminate? For example, if our village has twenty–five goats, what is the need for more than twenty–five natural
numbers? Such practical minded objectors need only wait for the labours of the next breeding season.
A more serious response is that in the subject of mathematics, one exercises the freedom one has to create
all related concepts. Such a theoretical progress occurs beyond the demands of practical necessity. And what
we do next is an illustration of this principle.
Assume that we have a theoretically endless supply of goats. Suppose we have constructed the concept of
the counting number n. Consider a collection which has one goat more than n goats. Here, we need a new
counting number which is the natural successor to n. We denote the latter by n
]
. When this procedure is
executed for various values of n, we make the definitions one
]
= two, two
]
= three, three
]
= four, etc. We
gather together all these counting numbers to form the set of natural numbers one, two, three, four,... With
ten as base, this is usually written as N = {1, 2, 3, 4, . . .}. The “. . .” is to be interpreted to mean that all
counting numbers are included.
One may record this procedure as giving a succession function f
]
: N → N via f
]
(n) = n
]
for every natural n.
This function is injective and its range is N \ {1}. Is there a conundrum wherein f
]
seems to have been used
both to build N and later to give a function on it?
Clearly, the natural numbers we have created can be used to count other objects like sheep, cattle, stars, etc.
In this way natural numbers solve the problem of counting discrete objects.
} Addition of natural numbers is commutative and associative k1.3k
Given two natural numbers m and n, we line up m goats followed by n goats, all of the same kind. We count
the ensemble together from one end to the other, and find, say, s goats, for a natural number s. By repeated
experiments, our result s is independent of whether we use goats, sheep, stars or any other objects of same
kind. Hence s is a property of the natural numbers m and n. s is said to be the sum of naturals m and n. This
procedure, named addition, defines a function f
+
: N × N → N via f
+
(m, n) = s. The latter is abbreviated as
s = m + n.
Our count of the sum above is independent of which end we start. Hence we conclude that addition is
commutative, i.e., m + n = n + m for all naturals m and n. Using similar ideas one can prove that addition is
associative. That is, given any natural numbers l, m and n, we have (l + m) + n = l + (m + n). The necessity
of proving the latter is better seen when written as f
+
(f
+
(l, m), n) = f
+
(l, f
+
(m, n)).
For any natural number n, compare the previous section’s definition n
]
with this section’s definition of adding
a 1 to n. The procedures behind the two definitions are same and hence, for all natural n, f
]
(n) = f
+
(n, 1).
Repeating this observation, one concludes that addition of a natural k to n yields the k–th repeated successor
of n. Thus, we can express f
+
using f
]
alone.
} Multiplication is commutative and associative with 1 as identity k2.1k
Given two natural numbers m and n, we line up the required number of soldiers in m rows with each row
having n soldiers. We count the ensemble together one row at a time, and find, say, p soldiers, for a natural
number p. Our result p is independent of the kind of objects we use for our experiment like soldiers, horses,
tanks, etc. Hence p is a property of the natural numbers m and n. p is said to be the product of naturals
m and n. This procedure, named multiplication, defines a function f
×
: N × N → N via f
×
(m, n) = p. The
latter is simply abbreviated as p = m × n or p = m · n, or even p = mn.
Our count of the product above is independent of whether we count one row at a time or one column at a
time. Hence, we conclude that multiplication is commutative, i.e., m · n = n · m for all naturals m and n.
Using similar ideas one can prove that multiplication is associative. That is, given any natural numbers l, m
and n, we have (l · m) · n = l · (m · n).
From our definition, it is clear that for any natural n, we have n · 1 = 1 · n = n. Since multiplying any natural
number by 1 gives the natural number identical to the given one, we say 1 is a multiplicative identity. In fact,
it is the only multiplicative identity for any given natural number, let alone all natural numbers.
That multiplication involves repeated addition is clear from our definition. Indeed, we verify that for any
naturals m and n, m × n =
n times
m + · · · + m =
m times
n + · · · + n. Based on this one can express f
×
using f
+
alone and
further using f
]
alone.
} Multiplication distributes over addition k2.2k
Given any natural numbers l, m and n, line up soldiers such that there are l rows and m + n columns. By
definition we have l(m + n) soldiers. Counting the two groups (i) l rows with m columns and (ii) l rows with
n columns separately, we should have lm + ln soldiers. Our two counts should be equal and the equality
independent of the fact that we used soldiers. Hence l(m + n) = lm + ln. This property is expressed by the
phrase multiplication distributes over addition.
} Other functions k2.3k
Repeated succession led to addition, repeated addition to multiplication and we call repeated multiplication as
circumflexion. Given two naturals m and n, the product c =
n times
m × m × · · · × m defines the circumflex function
f
⊗
: N × N → N written as f
⊗
(m, n) = m
n
. One can verify that this funciton is neither commutative nor
associative. Also, for any three naturals l, m and n one can prove that l
(m+n)
= l
m
· l
n
and (l
m
)
n
= l
(mn)
.
Two common derivatives of the circumflex function are defined as follows. Let a be an arbitrary but fixed
natural. Then the function f
e
: N → N given as f
e
(n) = a
n
for all natural n is called the exponential function
on naturals with base a. Similarly, if k is a fixed natural, the function f
p
: N → N given as f
p
(n) = n
k
for all
natural n is called the power function on naturals with exponent k.
Composing power, multiplication (by a constant) and addition functions, we get polynomial functions. Given
natural numbers a
0
, a
1
, a
2
, . . . , a
k
for some natural k, a function f : N → N of the form
f(n) = a
0
+ a
1
· n + a
2
· n
2
+ · · · + a
k
· n
k
is called a polynomial function.
Suitable composition of addition, multiplication, exponential and power functions would give us a large number
of examples of functions f : N → N. However, there are many other functions which are inexpressible as such
compositions.
} Comparing naturals k3.1k
Suppose three goatherds A, B and C own 30, 40 and 50 goats. Can we compare these goatherds in terms of
their wealth? Well, B is richer than A, C is richer than B and C is richer than A. When confronted with
how we arrived at these conclusions, we may say B has more goats than A and hence B is richer, C has more
goats than B and hence C is richer etc. We can analyse a conclusion like C has more goats than A by saying
that in creation of natural numbers 50 comes after 30 or equivalently, 30 comes before 50. Similarly, we know
that 30 comes before 40 and 50.
In contrast suppose three gamblers P , Q and R lose 30, 40 and 50 rupees. Can you compare them in terms of
luck? We would say that P is luckier than Q, Q is luckier than R and P is luckier than R. These comparisons
are exactly opposite in nature to our example above.
There is only a subtle difference in the two examples. In the first one, it is desirable to be richer which occurs
by having a greater number of goats. In the second example, it is desirable to luckier which occurs by losing
a smaller number of rupees. Thus, in many instances of usage of natural numbers, we have an opportunity
to compare associated objects like goatherds or gamblers. Unfortunately, the desirability of being associated
with similar natural numbers may or may not be consistent.
However, an abstract construct called less can be applied to natural numbers. For example, we say 30 is
lesser than 40 because 30 is created before 40, 40 is lesser than 50 because 40 is created before 50 and 30
is lesser than 50 because 30 is created before 50. These constructs provide comparisons of natural numbers.
Such comparisons are devoid of any desirability connotations unlike concepts such as rich or lucky. Moreover,
with these constructs, one merely says – the goatherd A has lesser number of goats than B, the gambler Q
has lost a lesser number of rupees than R, etc. With this we move away from value judgements of counted
objects in real–world and towards comparisons of natural numbers.
Perhaps, we compare two natural numbers m and n as follows. If m appears earlier than n in the natural
listing of naturals, one concludes m is lesser than n and vice–versa. Thus, m is lesser than n if n is an eventual
successor of m.
Applying this definition, we can say that the natural 1 is lesser than every other natural, 2 is lesser than every
natural other than 1 and 2, 3 is lesser than every natural other than 1, 2 and 3, etc. Of course, 1 is not lesser
than 1, 2 is not lesser than 1 or 2, 3 is not lesser than 1, 2 or 3, etc.
One can prove the following property of this comparison:
(Transitivity) For natural numbers l, m and n, if l < m and m < n then l < n.
Moreover, for any two naturals m and n, let us associate the comparison m < n with the ordered pair
(m, n) ∈ N. Gathering together all such pairs, we get the subset, U = {(m, n) ∈ N × N|m < n} =
{(1, 2), (1, 3), (1, 4), . . . , (2, 3), (2, 4), . . . , (3, 4), . . . , }. We formalize this association in the next section.
} Order relation k3.2k
Given a set S, a binary relation, R on S is a subset, T
R
⊂ S × S. In practice, elements of T
R
are written out
as follows: xRy if and only if (x, y) ∈ T
R
. xRy is read as x is related to y or R relates x with y. Let R be a
binary relation on S. We say R is
reflexive if xRx for every x ∈ S.
symmetric if xRy implies yRx, for any x, y ∈ S.
antisymmetric xRy and yRx implies x = y, for any x, y ∈ S.
transitive xRy and yRz implies xRz, for any x, y, z ∈ S.
an order on S if R is a transitive binary relaton on S.
a partial order on S if R is an order which is reflexive and antisymmetric.
a linear or total order on S if R is an order and at least one of the following three is true: (i) xRy (ii)
x = y (iii) yRx, for every x and y in S.
a strict order on S if R is an order and at most one of the following three is true: (i) xRy (ii) x = y (iii)
yRx, for any x and y in S.
} Comparison of naturals is a strict li near order compatible with arithmetic k4.1k
The comparison < is a binary relation on naturals as we have presented all comparisons as a subset U of
N × N. Further, < is an order, since transitivity is a property of comparison. We will prove that the
comparison order relation is strict and linear and that it is compatible with the arithmetic operations of
addition and multiplication.
Given two natural numbers m and n, exactly one of the following must be true: (i) m < n or (ii) m = n or
(iii) n < m. For a proof, consider the following
Assume the two numbers are equal, i.e., m = n = l. Then (ii) is valid. Also, by definition l is not less
than l since it is not created before itself. Hence (i) and (iii) are not true.
If the two numbers are unequal, one of them, say, m appears earlier than n in our usual listing of naturals.
Then (i) is true by definition. In our construction of naturals, f
]
is injective and hence m and n are not
equal. So (ii) is not true. (iii) cannot be true as we are assuming that m appears earlier than n.
The case of n appearing earlier in the listing of naturals is similar.
Thus, we have proved that < is a strict linear order on naturals.
The linear ordering of naturals is compatible with the arithmetic operations of addition and multiplication in
the following sense:
(a) m < n implies m + r < n + r, for any naturals m, n and r.
For a proof, line up m goats followed by k goats for a natural k to get n goats in total. Next, line up r
goats in the front. Start counting from the front – when we have counted r + m = m + r goats, we are
still left with k goats to count before we hit r + n = n + r. Thus, m + r appears earlier than n + r and
m + r < n + r by definition.
(b) m < n implies mr < nr, for any naturals m, n and r.
For a proof, line up soldiers in m columns followed by k columns for a total of n columns and r rows.
Since we see fewer soldiers in m columns and r rows when compared with n columns and r rows, we
have the result mr < nr.
} Mathematical induction k5.1k
The logician who had to concede that it is not possible to give definitions for natural numbers would have
found more than an occasional objection to our definitions of addition, multiplication, etc. and proofs of their
properties. Our ‘proof’ of commutativity of addition of naturals m and n is to line up n goats behind m goats
and count from two different ends. We believe that this exercise can be done for any m and n – whereas in
practice we can merely verify m + n = n + m in only finitely many cases, no matter how large our number
of cases. This will not allow us to conclude the truth of commutativity of addition for all naturals. Similar
objections exist for our proof of associativity of addition etc. All these objections are addessed in the next
section.
We introduce mathematical induction or simply induction with an example. Given any natural number n,
consider the statement
S(n) ≡ Equality of the sum 2{1 + 2 + 3 + · · · + n} and n(n + 1)
In the direction of proving this, critically compare the following two deceptively similar methods – one by
verification and the other by what we call induction.
Verification Method
Case 1 We prove that S(1) is true, i.e., 2(1) = 1(2) is indeed true.
Case 2 We prove that S(2) is true, i.e., 2(1 + 2)
dist.
= 2(1) + 2(2)
S(1)
= 1(2) + 2(2)
dist.
= (1 + 2)(2)
comt.
= 2(3).
Case 3 We prove S(3) is true, i.e., 2(1+2+3)
dist.
= 2(1+2)+2(3)
S(2)
= 2(3)+2(3)
dist.
= (2+2)(3)
comt.
= 3(4).
Case 4 We prove S(4) is true, i.e., 2(1+2+3+4)
dist.
= 2(1+2+3)+2(4)
S(3)
= 3(4)+2(4)
dist.
= (3+2)(4)
comt.
=
4(5) .
Any case Based on the previous cases we can write a proof for S(5), S(6), . . . is true, i.e. S(n) is true
for every natural n.
Induction Method
(a) Base We prove that S(1) is true, i.e., 2(1) = 1(1 + 1) is indeed true.
(b) Induction Step Assuming S(k) is true for a natural k, we prove that S(k + 1) is true, i.e.,
assuming 2{1 + 2 + 3 + · · · + k} = k(k + 1), consider:
2{1 + 2 + 3 + · · · + k + (k + 1)} = 2{1 + 2 + 3 + · · · + k} + 2{(k + 1)} hby distributivity
= k(k + 1) + 2(k + 1) hby assumption aboutS(k)
= (k + 2)(k + 1) hby distributivity
= (k + 1)(k + 2) hby commutativity
Thus, we have proved that S(k + 1) is true.
From (a) S(1) is true. Using the latter in (b), S(2) is true. Using this in (b) again, S(3) is true.
Continuing this way, we get that S(n) is true for every natural n.
During verification, we observed that the proofs for truth of S(k + 1) are similar for k = 1, 2 & 3. They
all seem to use only the truth of S(k) and properties like commutativity and distributivity. Their pattern is
what gave us the confidence that we can prove S(n) for any natural n. In contrast to this, in the method of
induction, the author after having observed this pattern has written down a proof of the truth of S(k + 1)
assuming the truth of S(k) for any natural k. Are these two methods equally valid proofs of associativity of
addition? Or is one method more sacrosanct than the other?
The method of verification suffers from the defect that unanticipated difficulties might arise while trying to
prove S(n) for some n for which we have not yet written down a proof. And of course, we can never write
down, individually, the proofs of truth of S(n) for every natural n. This method leaves something to be
desired.
In the method of induction, the induction step ensures that the truth of S(k + 1) = S(f
]
(k)) follows from the
truth of S(k) for every natural k. And since every natural number is, by definition, a repeated successor of 1 –
we can eventually establish truth of S(n) for every natural n. Since there shall be no difficulties – anticipated
or otherwise – induction is inviolable.
A more rigorous proof of the method of induction is unnecessary.
Indeed, about induction, neither can our reason prove its correctness nor our faith forego its inviolableness.
Instead of exposing our dilemma to the world, we issue the edict titled
Principle of mathematical induction Suppose for each natural number n, S(n) is a statement which can be
true or false. If
• S(1) is true, and
• for any natural k, assuming S(k) is true we derive S(k + 1) is true
then S(n) is true for all n.
The above principle is still valid if, in the induction step above, we can prove S(k + 1) is true assuming
S(1), S(2), . . . , S(k) is true. This is called the principle of strong induction.
} Natural counting and arithmetic systems k6.1k
In this section, we gather together the development and properties of naturals. N = {1, 2, 3, . . .} is the set of
natural numbers developed to count discrete objects. It has the following properties:
(N
1
) 1 is the distinguished element of N.
(N
2
) There is a function f
]
: N → N called the succession function such that
(N
2a
) there does not exist an m ∈ N satisfying f
]
(m) = 1,
(N
2b
) f
]
is injective and
(N
2c
) for every n ∈ N, n 6= 1, there exists a m ∈ N satisfying f
]
(m) = n, i.e., f
]
is onto N \ {1}.
(N
3
) Principle of mathematical induction is valid for N, i.e., if S ⊂ N such that
1 ∈ S and
for every n ∈ S it is true that f
]
(n) ∈ S,
then S = N.
N with the above properties is called the natural counting system. It may be noted that (N
2c
) can be derived
from (N
1
), (N
2a
), (N
2b
) and (N
3
). Apart from these properties, we have studied the operations of addition
and multiplication and a compatible linear order on N. These can be formally defined as follows.
(N
4
) The addition function f
+
: N × N → N is defined recursively below. Pick an m ∈ N. Then,
m + 1 = m
]
, and
assuming m + n has been defined, let m + (n
]
) = (m + n)
]
, for every n ∈ N.
(N
5
) The multiplication function f
×
: N × N → N is defined recursively below. Pick an m ∈ N. Then,
m · 1 = m and
assuming m · n has been defined, let m · (n
]
) = m · n + m, for every n ∈ N.
(N
6
) A relation < on N such that
for m, n ∈ N, m < n if and only if n = m + k for some k ∈ N.
It is important to realize that our new definitions of addition, multiplication and order here are consistent
with our previous experimental definitions. As an example, earlier, we had defined m < n if n is an eventual
successor of m. Intepreting repeated succession as addition, we see that this is equivalent to m + k = n for a
natural k.
These newer definitions enable a more rigorous presentation of results. Using induction one can prove that
(N
4
) and (N
5
) are well defined, that f
+
and f
×
are commutative and associative, that f
×
distributes over f
+
.
One can also prove that < is a strict linear order relation compatible with addition and multiplication.
We emphasize that the definitions in (N
4
)–(N
6
) and their associated properties are derived from (N
1
)–(N
3
).
The set N with the definitions (N
1
)–(N
6
) is called the natural arithmetic system derived from the natural
counting system. We denote the natural arithmetic system also by N.
As an example, we provide proof of associativity of f
+
to illustrate the use of induction.
Notice that the addition function has been redefined in (N
4
) as follows. For any natural number s,
(i) define s + 1 = f
]
(s) and
(ii) assuming s + k has been defined for a natural k, define s + (k
]
) = (s + k) + 1 = f
]
(s + k)
For any given s ∈ N, let W
s
:= {k|k ∈ N s.t. s + k is defined}. By (i), 1 ∈ W
s
–and– assuming k ∈ W
s
we
have by (ii) that k + 1 ∈ W
s
. By induction, W
s
= N for all natural s. Hence, f
+
is well–defined.
Given any natural number n, consider the statement
S(n) ≡ Equality of (l + m) + n and l + (m + n) for all natural numbers l and m
Associativity of addition of naturals is equivalent to proving that S(n) is true for every natural n. A proof of
this follows.
Base We prove that S(1) is true, i.e., l + (m + 1) = (l + m) + 1 for all natural l and m. But this is merely
part (ii) of the definition of addition above.
Induction Step Assuming S(k) is true for a natural k, we prove that S(k + 1) is true, i.e.,
assuming l + (m + k) = (l + m) + k, consider:
l + (m + (k + 1)) = l + ((m + k) + 1) hby (a)
= (l + (m + k)) + 1 hby defn. of f
+
in (ii)
= ((l + m) + k) + 1 hby assumption S(k) in (b)
= (l + m) + (k + 1) hby defn. of f
+
in (ii)
Thus, we have proved that S(k + 1) is true.
By induction, S(n) is true for every natural n.
Other properties of +, · and < are likewise established.
} Etymological & Logical ex positions k8.1k
Etumon and Logik are the two goddesses who preside over every mathematical discourse. A mathematical
exposition pleases Etumon if it is etymologically accurate. Such an exposition should trace the genesis of
concepts. It recognises abstractions like set, function, number, vector, group etc. not as atomic revelations
but as a result of the human mind reflecting on concrete instances. On the other hand definitions like
derivative and integral are motivated by the physical world. Providing such motivations demands a greater
level of scholarship. Such an exposition should articulate thereoms instead of merely providing a proof.
On the contrary, to please Logik – one has to be just accurate. Every such exposition starts with nominal
definitions, i.e., definitions in name alone. More unflatteringly, these are terms we cannot define. This is
followed by axioms, i.e., truths about these nominal definitions which are to be accepted without proof.
Better yet, these should be called edicts. The beginner should acquaint himself with these definitions and
edicts akin to one admitted for religious studies. To excessively wonder at this stage retards one’s progress.
As one reads more, definitions appear in their polished form, theorems are a superhuman endeavour while
their proofs have descended from the heavens. But, the certainty of our conclusions more than compensates
for the poor insight from such presentations.
In short, Etumon dreams of fidelity to meaning, whereas Logik abhors transgressive inferences. The latter
goddess if not the one more easily pleased is the one more readily feared. Consequently most, if not all,
expositions are mostly, if not wholly, logical at the expense of being even partly etymological.
In the next couple of sections, as Etumon fades into background, the spotlight shines on Logik.
} Peano counting system k8.2k
A set P is a peano counting system if it satisfies:
(P
1
) P has a distinguished element α ∈ P.
(P
2
) There is a succession function σ : P → P such that
(P
2a
) there is no x ∈ P such that σ(x) = α and
(P
2b
) σ is injective, i.e., for x, y ∈ P, if σ(x) = σ(y) then x = y
(P
3
) If S ⊂ P satisfying
• α ∈ S and
• if x ∈ S then σ(x) ∈ S
then S = P.
When we need to emphasize the underlying set, we use α
P
and σ
P
in place of α and σ respectively. These
axioms are inspired by our study of natural numbers. Indeed, N satisifies (P
1
) with α
N
= 1, satisfies (P
2
) with
σ
N
= f
]
and (P
3
) with the principle of induction. Thus, we do have N as an example of a peano counting
system.
Recall that the range of f
]
is N \ {1}. This corresponds to the property that for every y 6= α, there exists an
x ∈ P such that σ(x) = y. The latter can be proved by using (P
3
) on S = {α} ∪ {σ(x)|x ∈ P}. In fact, one
can prove similarly that P = {α} ∪ {σ
k
(α)|k ∈ N}.
(P
1
) forces P to be non–empty and requires no elaboration. One might wonder whether (P
3
) is necessary.
Indeed, taking P = N with α = 1 and σ : N → N as σ(n) = n + 2 for all natural n, the first two axioms are
satisfied, but not the third.
Remember the child who axiomatized a cat as a four legged animal with whiskers and a tail – and called a
tiger to be a cat? Likewise, we ask – are there examples other than N of peano counting systems? Consider
the set M = {2, 3, 4, . . .} with α = 2 and σ = f
]
. Restating the principle of induction with 2 instead of 1, M
satisfies all the three axioms (P
1
)–(P
3
). Based on this, one can construct other examples.
M and N appear to be not substantially different. Let us make this more precise. Firstly the function n 7→ n+1
for all natural n is a bijection from the first peano counting system to the second. The bijection allows us to
treat elements of one system to be no more than relabelling of elements of the other. We would have ended
our comparison here if a peano counting system was merely a set. Just as a translation of a sentence from
one language to another is more than a bijection between two collections of words from the two languages, so
too does a comparison of two peano counting systems demand more than a bijection. This is addressed by
the following definition: Suppose X and Y are two peano counting systems. We say X is isomorphic to Y if
there exists a function ϕ : X → Y such that
(I
1
) ϕ is bijective,
(I
2
) ϕ preserves distinguished elements, i.e., ϕ(α
X
) = α
Y
and
(I
3
) ϕ commutes with the succession functions, i.e., ϕ(σ
X
(x)) = σ
Y
(ϕ(x)) for all x ∈ X.
One can prove that any two peano counting systems are isomorphic. Indeed, by induction, ϕ is both well and
uniquely defined by properties (I
2
) and (I
3
) above. Further, one can prove that ϕ is a bijection. Since this
isomorphism is uniquely determined, we say that any two peano counting systems are canonically isomorphic.
Thus, there is no example of a peano counting system of any greater interest than our natural counting system.
} Peano arithmetic system k9.1k
Let P be a peano counting system. Let us denote the distinguished element of P by α and the succession
function of P by σ. On P we define the following.
(P
4
) Writing x + y for f
+
(x, y), define an addition function f
+
: P × P → P for every p ∈ P via
p + α = σ(p) and
having defined p + q, let p + σ(q) = σ(p + q) for every q ∈ P
One can verify that f
+
is associative and commutative.
(P
5
) Writing x × y for f
×
(x, y), define a multiplication function f
×
: P × P → P for every p ∈ P via
p × α = p and
having defined p × q, let p × σ(q) = pq + p for every q ∈ P
One can verify that f
×
is associative and commutative and that f
×
distributes over f
+
.
(P
6
) Define an order relation < on P such that
for p, q ∈ P, p < q if and only if q = p + r for some r ∈ P
One can verify that < is a strict linear order on P which is compatible with addition and multiplication,
i.e., if for p, q ∈ P it is known that p < q then p + a < q + a and p × b < q × b for any a, b ∈ P.
A peano counting system together with the definitions (P
4
)–(P
6
) is called a peano arithmetic system. We
denote this too by P. Of course, the set of natural numbers with the usual operations of addition and
multiplication along with the usual order relation is a peano arithmetic system. One can give other examples.
The canonical isomorphism between any two peano counting systems commutes with the succession functions.
Hence the isomorphism commutes with the derived arithmetic operations of addition, multiplication and the
order relation. More elaborately, let X and Y be two peano counting systems with ϕ : X → Y as the canonical
isomorphism between them. Next, extend X and Y into arithmetic systems. Then for any x, y ∈ X, one can
prove ϕ(x + y) = ϕ(x) + ϕ(y) and ϕ(x × y) = ϕ(x) × ϕ(y). Further, if x < y, then ϕ(x) < ϕ(y). Of course,
the +, × and < are to be interpreted suitably as +
X
or +
Y
,×
X
or ×
Y
and <
X
or <
Y
. In this sense, any two
peano arithmetic systems are canonically isomorphic. Thus, there is no example of a peano arithmetic system
of any greater interest than the natural arithmetic system.
} Coda k10.1k
The real–world problem of counting objects led to the concept of naturals. Their very definition gave us
a succession function on naturals. And we stated the principle of induction on naturals. Axiomatizing on
these objects and properties led to a peano counting system, not essentially different from naturals. Further
we saw that the familiar operations of addition, multiplication and comparison of naturals are derived from
the succession function. Augmenting a peano counting system with those derived operations led to a peano
arithmetic system, not essentially different from natural arithmetic system. Thus, these two axiomatizations
have failed to expand upon the naturals. However, in the next few sections, we see how a book keeper’s
problem led to an expanded number system.
} Subtraction function k10.2k
Questions such as “A farmer has ten goats of which three died. How many goats are left?” arose early in the
development of numbers. A method of solving such questions is to stretch out three fingers and then start
counting from the fourth to the tenth and say the answer is seven. In school we are taught that if a natural
number x is the answer to this question, then from the very definition of addition, 10 = 3 + x should be true.
We also learn how to solve such equations. This method of solution is valid for all equations of the form
m = n + x for natural numbers m and n with m > n. Indeed, since m > n if and only if m = n + k for a
natural k, the unique answer to this equation is k.
This yields a subtraction function f
−
: L → N where L = {(m, n)|m, n ∈ N, n < m}. We abbreviate f
−
(m, n)
by m − n. By definition, m − n = k if and only if (m − n) + n = m. In this sense, we say that addition is the
opposite of subtraction. One can also verify that for any two naturals m and n, (m + n) − n = m. The latter
is interpreted as subtraction being the opposite of addition.
So long as natural numbers are used for counting physical objects like goats, sheep, chairs etc., questions
such as ‘three goats minus seven goats’ or ‘four chairs minus ten chairs’ are not meaningful. Thus there does
not appear a need to extend the domain of the subtraction function. And likewise we say an equation like
3 = 10 + x has no answer or more precisely no solution in natural numbers.
} An imaginary number which is not a natural number k10.3k
The following example forces us to consider such equations for which there are no solutions in natural numbers.
Suppose you have three hundred rupees in your bank and you write a cheque for a thousand rupees. The
usual procedure followed by the bank is to return the cheque marked for insufficiency of funds and slap a fee
on you. However, if the bank trusts you, or more pertinently, trusts your creditworthiness, it will honour the
cheque and make your balance as not seven hundred rupees but that you owe the bank seven hundred rupees.
Instead of the cumbersome phrase, the bank says your balance is ‘negative seven hundred rupees’. This is to
mean that the bank has paid seven hundred rupees on your behalf and you are in debt.
Let us denote the new number as ‘700’. The horizontal bar, , is to distinguish this number from the natural
700 that we are already familiar.
Thus, we have hit upon a new number ‘negative seven hundred’. It is not a natural number. It is an ‘imaginary’
number.
Strictly speaking, even our concept of natural number, like all concepts, is imaginary. We can never see three
or four or thirtyseven as natural numbers, but can only see three goats or four cats or thirtyseven rupees.
With this background, 700 should be called an ‘unimaginable’ number because we cannot produce 700 goats
or sheep or rupees i.e., 700 of anything from our old paradigm. Owing to this, there was a violent rejection
of such numbers by the educated for hundreds of years.
Let us call 700 imaginary instead of ‘unimaginable’. This imaginary number is dear to our banker on several
fronts contributing to the bottom line. For if he returns your cheque and freezes your account, he would have
halted your economic activity till you get your statement which could be several days. Your beneficiary’s plans
of putting the amount to good use is on hold. The banker only profits from a silly fine. Instead, he can put
this imaginary 700 to good use by making it your balance. Then you can feel the real pain of an exhorbitant
interest charge on your imaginary balance – at a rate more than his cost. And your beneficiary might not put
the amount to immediate use – which means that the banker can potentially profit from lending it to others.
And the fine you still have to pay is the cherry on the cake.
Thus, suffering paralysis due to difficulties of imagining a number like 700 or harboring existential doubts
due to the defect of its unimaginability would interfere in the way of greater profits and make for a banker
without imagination. The banker stands absolved of such an accusation – for he adopted the use of such
numbers long before the mathematically educated could get their collective mental grip on them. Indeed the
leap from our banker’s adoption of imaginary numbers elaborated in the next section to a mathematician’s
acceptance of the same seen in the subsequenct sections took centuries.
} A banker’s advanced education k11.1k
Instead of treating 700 as an oddity, we can try to construct once and for all all such ‘negative’ numbers viz.,
1, 2, 3, . . .. But that would be defining concepts by notation which is both unilluminating and reprehensible.
A better approach is called for.
Since the banker is trying to solve the equation (Old Balance) = (Cheque Amount) + (New Balance), a
systematic way out of the situation would be to say we are trying to solve the equations m = n +x for natural
numbers m, n. Thus we can say 700 is the imaginary number which is a solution to 300 = 1000 + x.
Continuing with such statements, we say that 1 is the imaginary number which is a solution to 1 = 2 + x, 2
is the imaginary number which is a solution to 1 = 3 + x, 3 is the imaginary number which is a solution to
1 = 4 + x, etc. With this approach we seem to have a method of creating all the imaginary numbers 1, 2, 3, . . .
required for the banker.
In this way of defining, 700 is the imaginary number which is a solution to 1 = 701 + x. At once arises
the question: What is the relation between the two imaginary solutions of the equations 300 = 1000 + x
and 1 = 701 + x? Are these two imaginary quantities equal or are they different? Of course they are same!
Whether your bank pays a cheque of 1000 rupees when your balance is 300 or whether it pays a cheque of 701
rupees when your balance is 1, you are in debt of 700 rupees. Thus, in both scenarios, your balance should
be made the same imaginary number 700.
Thus, a banker’s education to advanced arithmetic begins with the definitions:
0, read as zero is the imaginary solution to each of the equations 1 = 1 + x, 2 = 2 + x, 3 = 3 + x, . . ..
1 is the imaginary number which is a solution to each of the equations 1 = 2+x, 2 = 3+x, 3 = 4+x, . . ..
2 is the imaginary number which is a solution to each of the equations 1 = 3+x, 2 = 4+x, 3 = 5+x, . . ..
3 is the imaginary number which is a solution to each of the equations 1 = 4+x, 2 = 5+x, 3 = 6+x, . . ..
k is the imaginary · · · · · · of the equations 1 = (k + 1) + x, 2 = (k + 2) + x, 3 = (k + 3) + x, . . .,
for each natural number k.
These definitions take care of one bad cheque with no further account activity till the next statement and
the mandatory top–up from the customer. But how can the banker handle those valuable customers who
write too many bad cheques? Suppose that the bad cheque which left you with a balance of 700 rupees was
followed by a cheque for 1500 rupees. Should the banker then turn away this second beneficiary because he
cannot figure out how much you would owe the bank if the second cheque was paid? Certainly not! Indeed
the banker is taught that 700 − 1500 = 2200 – which is merely rephrasing ‘You owe me 700 and you owe me
1500 more and thus you owe me 700 + 1500 = 2200 and your balance is 2200.
Such and other practical questions of figuring out your balance after a sequence of bad cheques and deposits
call for operations of addition and subtraction with these imaginary numbers mixed with natural numbers.
Thus every banker needs to know how to add and subtract any two numbers – be they natural or imaginary.
And like the pre–historic goatherd who worked out the arithmetic table of natural numbers with stones
and sticks, the medieval banker has extended the goatherd’s arithmetic by working out the addition and
subtraction of both imaginary and natural numbers. We can replicate his method and arrive at rules like
1 + 1 = 2, 1 + 2 = 3, etc. These are now taught in elementary classes.
Occasions for multiplying an imaginary number with a natural are rare, but not non–existent. As an example,
if fifty trusted customers default on topping up their balances of 700 rupees each, how much is the total loss
to the banker? Such a case leads to a definition of 700 · 50 and its inclusion in a banker’s table of arithmetic.
But a banker can lead a comfortable life without ever knowing how to multiply imaginary numbers. Will
a banker ever have to confront a problem like 700 · 6? How can any customer, no matter how financially
irresponsible, owe 700 rupees to negative–six banks? While the medieval banker did not concern himself with
such scenarios which never arise in his real professional world, the modern day primary school student who
exhibited exemplary patience with unimaginable numbers like 700 and 6 becomes suspicious of every teacher
who forces him to accept 700 · 6 = 4200, especially when the teacher cannot define 700 · 6.
} Similar equations k12.1k
Looking back at our definition of 700, we say it is the same imaginary solution to both the equations 1 = 701+x
and 2 = 702 + x. A property of these two equations is 1 + 702 = 2 + 701 = 703. Similarly this same imaginary
solution is valid for 2 = 702 + x and 3 = 703 + x, i.e., 2 + 703 = 3 + 702.
Generalizing our observation above, suppose equations p = q + x and r = s + y (over naturals) have the same
imaginary solution. Then
p = q + x
s + y = r
implies (p + s) + y = (q + r) + x
Assuming equal imaginary quantities x and y can be cancelled, we get p + s = q + r. We use the latter
equation and say that equations are similar, and denote it by (p = q + x) ≡ (r = s + y), if p + s = q + r.
The similarity, ≡, is a relation on the set of such equations. This relation is reflexive because every such
equation is similar to itself, it is symmetric because if one equation is similar to the other – then the second
equation is similar to the first. Further, it is transitive in the sense that if one equation is similar to a second
one and the same second one is similar to a third equation, then the first one is similar to the third one. These
three statements can be verified using the definition.
Recall the collections of equations which have 0, 1, 2, 3, . . . as solutions listed in their definitions earlier. These
collections are all distinct or equal. And if we include the collections which have 1, 2, 3, . . . as solutions, they
too satisfy the property that two collections are distinct or equal. Together the union of these collections is
the set of all equations under consideration.
That this property of collections of similar equations is not an accident is explored in the next section.
} Equivalence relation k13.1k
A relation on a set S is which is reflexive, symmetric and transitive is called an equivalence relation. Let ∼
be an equivalence relation. If a ∼ b, we say a is equivalent to b, for a, b ∈ S. For each a ∈ S, define the subset
[a] = {x ∈ S|x ∼ a} ⊂ S. This subset is called the equivalence class of a. Further, a is called a representative
for the class [a].
For each a ∈ S, [a] is non–empty, simply because a ∼ a ⇒ a ∈ [a]. Owing to this the set S = ∪
a∈S
[a], is the
union of all possible equivalence classes. But we can do something better.
Lemma Let ∼ be an equivalence relation on a non–empty set S. For any a, b ∈ S, we have
(i) a ∼ b if and only if [a] = [b] and
(ii) a 6∼ b if and only if [a] ∩ [b] = ∅
Proof (i) Assume a ∼ b. Then, if x ∈ [a] ⇒ x ∼ a. Given a ∼ b, by transitivity, x ∼ b ⇒ x ∈ [b]. This
implies [a] ⊂ [b]. Similarly one proves the other inclusion to conclude [a] = [b].
Conversely if [a] = [b], then a ∈ [a] = [b] ⇒ a ∼ b.
(ii) Assume a 6∼ b. Note that from (i) we can only say that [a] 6= [b], as sets and not that their intersection
is empty. If on the contrary x ∈ [a] ∩ [b], then we have x ∈ [a] and x ∈ [b] which implies x ∼ a and x ∼ b
which by reflexivity and transitivity of ∼ implies that a ∼ b, a contradiction.
Conversely, if [a] ∩ [b] = ∅, and contrary to what we want, a ∼ b, then by (i) we have [a] = [b]. Hence
we get [a] = [b] = ∅ which is false as a ∈ [a] 6= ∅, when S 6= ∅.
This lemma shows that given a subset of S which is an equivalence class, its representative need not be unique.
Further two equivalence classes are either equal or disjoint. Thus avoiding repetitions S = ∪[a] makes S into
a union of disjoint equivalence classes.
In set theory, for an indexing set Λ, let {A}
λ∈Λ
⊂ S be a collection of mutually disjoint sets whose union is
S. Such a collection is called a partition of S.
We have just seen that distinct equivalence classes partition the given set. Conversely, given any partition of
a set, there is a unique equivalence relation on the given set whose equivalence classes are exactly the subsets
of the partition.
While the concept of a partition seems more psychologically convenient than that of equivalence relation, in
practice, the latter is more easily defined than the former.
} Construction of integers k13.2k
Let A = {m = n + x|m, n ∈ N} be the set of monic (coefficient of x is 1) linear equations over naturals. Pick
any two equations p = q + x and r = s + x in A. Of course, here p, q, r and s are natural numbers. We define
a relation ∼ on A as follows:
(p = q + x) ∼ (r = s + x) iff p + s = q + r.
That ∼ is reflexive and symmetric follows from commutativity of addition of naturals. Transitivity of ∼ can
be proved by adding the two equations and cancelling common terms. Thus ∼ is an equivalence relation.
The set of integers denoted by Z is defined as A/ ∼, the collection of equivalence classes of monic linear
equations over naturals.
Unfortunately, the set A does not have well–defined objects. A more rigorous approach to define integers
follows. There is a natural bijection ϕ : A → N × N which takes the equation (m = n + x) 7→ (m, n). One can
verify that the relation ∼
0
below is an equivalence relation on N × N:
Given (p, q), (r, s) ∈ N × N, we say (p, q) ∼
0
(r, s) iff p + s = q + r.
The set of integers Z can also be redefined as N × N/ ∼
0
.
This redefinition is does not conflict with our previous definition in the sense that equations e
1
∼ e
2
in A iff
ϕ(e
1
) ∼
0
ϕ(e
2
) in N × N.
For any (m, n) ∈ N × N, its equivalence class is denoted by any one of [(m, n)], [m, n] and m n.
The latter option of denoting the equivalence class [(m, n)] by mn has its advantages. For example, suppose
we are required to check whether the classes p q and r s are equal. The definition requires us to check
whether p + s = q + r. The following although equivalent to the definition is more convenient, viz.,
p q = r s if p − q = r − s with both p > q and r > s,
p q = r s if both p = q and r = s,
p q = r s if q − p = s − r with both p < q and r < s and
p q 6= r s in every other case.
To avoid confusion, note the following examples: 4 − 2 is the natural number 2 whereas 2 − 4 is undefined for
us. However, 2 − 4 although undefined, is thought of as the integer −2 in elementary classes. For the record,
2 4 is that integer which as an equivalence class is the subset {(1, 3), (2, 4), (3, 5), . . .} of N × N.
} Reduced representatives for equivalence classes k14.1k
Let us call a representative (m, n) for the equivalence class of an integer as reduced if m = 1 or n = 1 (or both
equal 1). For example, equivalence classes like 37, 33 or 64 may be written with reduced representatives
as 3 7 = 1 5 whereas 3 3 = 1 1 and 6 4 = 3 1.
We claim that every equivalence class has a unique reduced representative. For a proof, given any two natural
numbers m and n, exclusively one of the following is true:
m > n Then, there exists a natural k such that m = n + k and hence, m n = (n + k) n = (1 + k) 1
m = n Then, m n = n n = 1 1
m < n Then, there exists a natural k such that n = m + k and hence, m n = m (m + k) = 1 (1 + k)
We can quickly verify that no two classes of distinct forms are equal. Further two classes of the first form
(n
1
+ k
1
) n
1
= (n
2
+ k
2
) n
2
if and only if k
1
= k
2
. A similar statement applies to classes of the third
form. Consequently, the collection of integers is the same as the list of classes corresponding to reduced
represenatives. Here is a list with notation of all the integers with their reduced representatives:
.
.
.
k := 1 (1 + k) = 2 (2 + k) = 3 (3 + k) = · · · = m (m + k) = · · · for every m ∈ N and each k ∈ N
.
.
.
2 := 1 3 = 2 4 = 3 5 = · · · = m (m + 2) = · · · for every m ∈ N
1 := 1 2 = 2 3 = 3 4 = · · · = m (m + 1) = · · · for every m ∈ N
0 := 1 1 = 2 2 = 3 3 = · · · = n n = · · · for every n ∈ N
ˆ
1 := 2 1 = 3 2 = 4 3 = · · · = (n + 1) n = · · · for every n ∈ N
ˆ
2 := 3 1 = 4 2 = 5 3 = · · · = (n + 2) n = · · · for every n ∈ N
.
.
.
ˆ
k := (1 + k) 1 = (2 + k) 2 = (3 + k) 3 = · · · = (n + k) n = · · · for every n ∈ N and each k ∈ N
.
.
.
Thus, the set of integers,
Z = {. . . , 3, 2, 1, 0,
ˆ
1,
ˆ
2,
ˆ
3, . . .}.
} A bank balance of Rs.
700 k15.1k
Recall our example of a bounced cheque which started the discussion about integers. The discussion so far
helps us understand a bank statement which says that one’s balance is Rs. 700. It means, that your balance is
the equivalence class of the equation x + 1000 = 300. Paradoxically, the bank is telling you that your balance
is the equivalence class of the very equation it cannot solve to figure out your balance. This abstract solution
par excellence deserves to be christened and we shall do so as
Echtecstasy Apothegm The answer to a question one could not answer is the equivalence class of that unan-
swered question.
The Echtecstasy Apothegm is used repeatedly in the constructions of rationals, reals and even complex
numbers.
} Complications over motivations k15.2k
It is only natural for us to reflect on our construction of Z and see to what extent it addresses our earlier
issues with equations. Consider the following dialogue.
Question : Does the integer 700 solve the equation 300 = 1000 + x?
Answer : No.
Reason : f
+
being a function on N × N is not defined for (1000, 700). Thus the equation 300 = 1000 + 700
makes no sense.
To cover this defect, one might be tempted to ask
Question : Does the integer 700 solve the equation
ˆ
300 =
ˆ
1000 + x?
Answer : No.
Reason : We have not defined an addition function
ˆ
f
+
: Z × Z → Z. Thus the equation
ˆ
300 =
ˆ
1000 + 700
makes no sense.
Suppose we manage to define a
ˆ
f
+
: Z × Z → Z and verify
ˆ
300 =
ˆ
1000 + 700. Would this bring our quest to
an end? No, for then would arise
Questions : What is the relation between integers
ˆ
1000,
ˆ
300 and naturals 1000, 300?
How are the equations 300 = 1000 + x and
ˆ
300 =
ˆ
1000 + x related?
What is the relevance of solving an equation over Z when the banker wants you to solve an equation
over N?
A complete answer to the above questions will take several sections.
} Arithmetic of the ancients k16.1k
Suppose we define
positive integers,
ˆ
N = {
ˆ
1,
ˆ
2,
ˆ
3, . . .} and negative integers, N = {1, 2, 3, . . .}, then we have Z = N∪{0}∪
ˆ
N.
The element 0 has alredy been termed zero.
In elementary classes, we are taught rules like
• Sum of a positive integer and a negative integer corresponding to the same natural is zero.
• Adding zero to an integer does not alter the latter.
• Sum of two positive integers is a positive integer. Indeed
ˆ
k +
ˆ
l =
[
k + l tells us how to find the answer,
if we know addition of naturals.
• Sum of two negatives is a negative given as k + l = k + l.
• A positive added to a negative is a positive if the former is greater in magnitude than the latter and
vice–versa.
• Many other rules for subtraction and multiplication
The inquisitive might have worked out a plausibility of these rules using the ideas of debt and fortune. But
rules such as negative times a negative is a positive are hard to imagine with concrete representations of
negative integers. Recall how the banker rejected the case of a customer ever owing seven hundred rupees
each to negative six banks and then conclude 700 · 6 = 4200? Well the excessively curious are given the
following justification: 1 · 1 = (701 + 700) · (7 + 6) = 701 · 7 + 701 · 6 + 700 · 7 + 700 · 6. This equation simplifies
to 4199 + 700 · 6 = 1 which leads to the required result.
However, the above calculation assumes distributive property of multiplication for mixed numbers and does
not address the issue of definition of multiplication of imaginary numbers.
A more satisfying answer will be provided eventually.
} Principal and subaltern embeddings k16.2k
For each k ∈ N, define
: N → Z by k 7→
ˆ
k and
0
: N → Z by k 7→ k.
Both and
0
are injective with ranges
ˆ
N and N respectively.
We can view
ˆ
N as a peano counting system with
ˆ
1 as the distinguished element and the map f
]
given by
ˆ
k 7→
[
k + 1 as the succession function. Similarly, N is a peano counting system with 1 as the distinguished
element and the map f
[
given by k 7→ k + 1 as the succession function. Using the bijections and
0
from
naturals to positive and negative integers, we can prove that the principle of induction is valid on these two
subsets of integers.
Futher, one can verify that is the canonical isomorphism between the naturals and the positive integers as
counting systems. Likewise,
0
is the canonical isomorphism between the naturals and the negative integers
as counting systems.
Informally, an injection υ : A → B is an embedding if the mathematical structure on A is analogous to the
mathematical structure on υ(A) ⊂ B. Our functions and
0
are injections on the set of naturals carrying
the set of naturals to positive and negative integers. Moreover, the peano counting structure on naturals is
analogous to the peano counting structure on the latter two sets. Hence we call as the principal embedding
and
0
as the subaltern embedding of naturals in integers.
} Philosophy of ext ensions k17.1k
We motivated the construction of integers as an attempt to expand the domain of the subtraction function
on naturals. Expanding upon this, our problem is of extending functions like f
]
: N → N and f
+
, f
−
, f
×
:
N × N → N to functions
ˆ
f
]
: Z → Z and
ˆ
f
+
,
ˆ
f
−
,
ˆ
f
×
: Z × Z → Z. What should be our guiding principle?
Clearly, the general problem of providing a function ˆg : X → Y given a function g : A → B is ill–posed. If we
are provided with functions i : A → X and j : B → Y , we may define ˆg to be an extension of g if ˆg ◦ i = j ◦ g.
But even this notion does not guarantee uniqueness of the extension.
} Succession and predecession function on integers k17.2k
The succession function on positive integers, f
]
is given by
ˆ
k 7→
[
k + 1, for each positive integer
ˆ
k. This can
be viewed as mapping the integer (a + k) a to ((a + k) + 1) a for any natural a. Writing the succession
function in this form enables us to extend f
]
to all of Z i.e.,
ˆ
f
]
: Z → Z given by m n 7→ (m + 1) n for all m, n ∈ N.
ˆ
f
]
is called the succession function on integers. Of course, it restricts to the succession function on positive
integers.
ˆ
f
]
commutes with the f
]
on positive integers via the inclusion map. Moreover,
ˆ
f
]
commutes with
succession function on naturals via the principal embedding, i.e.,
ˆ
f
]
◦ = ◦ f
]
. In this sense,
ˆ
f
]
on integers is
a natural extension of f
]
on naturals. Owing to this we write the integral succession function
ˆ
f
]
simply as f
]
.
As an aside we show the well–definedness of our succession function. The function f : N × N → N × N given
by f(m, n) = (m + 1, n) descends to f
∗
: N × N → Z given by f
∗
(m, n) = (m + 1) n. Note the remarkable
property of f
∗
, viz., if (m, n) ∼ (p, q) in N × N, then f
∗
(m, n) = f
∗
(p, q). Hence, f
∗
can be lifted to f
]
: Z → Z
with f
]
(m n) = (m + 1) n.
One can show that f
]
is a bijection. Its inverse is called the predecession function and denoted by f
[
. It is
given as m n 7→ m (n + 1). f
[
restricts to the successor function on negative integers.
} Induction on integers k17.3k
Define
entire integers, E = N ∪ {0} and whole integers, W = {0} ∪
ˆ
N.
Let 0 be their common distinguished element with f
]|E
and f
[|W
as their succession functions respectively.
Using the principal and subaltern embeddings, we can prove that the principle of induction is valid on E and
W . Therefore, E and W are peano counting systems.
One can use this decomposition of integers to prove the bidirectional
Principle of induction for integers Suppose S ⊂ Z such that
0 ∈ S and
if k ∈ S ∩ E then f
[
(k) ∈ S while
if k ∈ S ∩ W then f
]
(k) ∈ S.
Then S = Z.
} Addition of integers k18.1k
How shall we add two integers? If x and y are integers solving
m = n + x for m, n ∈ N
p = q + y for p, q ∈ N,
then (m + p) = (n + q) + (x + y)
The above heuristic suggests a way of defining an addition function
ˆ
f
+
: Z × Z → Z. Let us abbreviate
ˆ
f
+
(x, y) by x + y and define m n + p q = (m + p) (n + q). We have called it a heuristic because the
above calculation has the intermediate steps: (n + x) + (q + y) = ((n + x) + q) + y = (n + (x + q)) + y =
(n + (q + x)) + y = ((n + q) + x) + y = (n + q) + (x + y). These steps assume that integers can be added with
naturals and that this mixed addition is commutavie and associative!
Perhaps no amount of logic can prove our definition for addition function. We have the following properties
regarding addition.
Well − definedness Since a given equivalence class has more than one representative, we should show that our
definition of
ˆ
f
+
depends only on the classes and not on the representatives. Suppose m, n, m
0
, n
0
, p, q, p
0
, q
0
are naturals such that
if m ⊕ n = m
0
⊕ n
0
, then m + n
0
= n + m
0
(1)
and if p ⊕ q = p
0
⊕ q
0
, then p + q
0
= q + p
0
, (2)
by adding (1) and (2) (m + p) + (n
0
+ q
0
) = (n + q) + (m
0
+ p
0
) (3)
and hence (m + p) ⊕ (n + q) = (m
0
+ p
0
) ⊕ (n
0
+ q
0
), (4)
which implies m ⊕ n + p ⊕ q = m
0
⊕ n
0
+ p
0
⊕ q
0
. (5)
Compatibility Is adding two naturals a and b similar to adding their analogs ˆa and
ˆ
b in Z? This demands that
ˆ
f
+
◦ ( × ) = ◦ f
+
, i.e.,
(a) + (b) = (a + 1) 1 + (b + 1) 1
= (a + b + 2) 2
= (a + b + 1) 1
= (a + b)
Owing to this compatibility we drop the caret and write
ˆ
f
+
as f
+
. In anticipation of this, we abbreviated
ˆ
f
+
(x, y) by x + y for integers x and y.
Similarly, addition is compatible with the subaltern embedding.
Commutativity Addition of integers is commutative, i.e., for any integers x and y, x + y = y + x. For a proof,
take natural numbers m, n, p and q such that x = m n and y = p q. Then x +y = (m + p) (n+ q) =
(p + m) (q + n) = y + x, i.e., commutativity of addition of naturals induces commutativity of addition
of integers.
Associativity Addition of integers is associative, i.e., for any integers x, y and z, (x + y) + z = x + (y + z). As
above, associativity of addition of naturals induces this property.
Rules
0 is the identity of addition If x is any integer, then x + 0 = 0 + x = 0. To prove this, one just observes
that x + 0 = m n + l l = (m + l) (n + l) = m n = x for any natural numbers l, m and n.
existence of additive inverse If x is any integer, then there exists an integer y such that x+y = y + x = 0.
If x = 0, we can take y = 0. If x =
ˆ
k, we can take y = k and vice–versa. Alternately, for x = mn,
take y = n m.
sum of positives If x =
ˆ
k and y =
ˆ
l are two integers, then x + y = y + x =
[
k + l. We can reinterpret this
as the compatibility property above.
sum of negatives If x = k and y = l are two integers, then x + y = y + x = k + l. This is the rule which
is taught as sum of two negatives is a negative. Note that this rule further gives the sum of two
negatives in terms of addition of naturals. To prove this consider x + y = 1 (1 + k) + 1 (1 + l) =
2 (2 + k + l) = 1 (1 + k + l) = k + l.
sum of a positive and a negative Let x = k and y =
ˆ
l be two integers. Then there are three cases for
finding the value of x + y = y + x as equal to (i)
[
l − k if k < l, (ii) 0 if k = l and (iii) k − l if k > l.
These can be verified as earlier.
Repeated succession and predecession Recall that the addition function on naturals was derived from its suc-
cession function. Likewise, we can immediately verify that the addition of a positive integer is repeated
succession while addition of a negative integer is repeated predecession. More elaborately, for every
x ∈ Z we have
x + 0 = m and
x + f
[
(y) = f
[
(x + y) if y ∈ E while
x + f
]
(y) = f
]
(x + y) if y ∈ W .
Conversely, we can use the above equations to define the addition function on integers and derive its properties.
This approach makes the arithmetic of integers a derivative of the sucession function and induction principle.
} Subtraction of integers k19.1k
Writing x − y for f
−
(x, y), we define a subtraction function
ˆ
f
−
: Z × Z → Z as follows. Let the integer
x = m n and y = p q for natural numbers m, n, p and q. We define x − y = (m + q) (n + p). One
can verify that this definition is independent of the choice of represenatatives for equivalence classes. It is
compatible with subtraction of naturals whenever defined, i.e., (m −n) = (m)− (n), for all naturals m > n.
Owing to this property, we drop the caret and denote the subtraction function
ˆ
f
−
by f
−
.
Subtraction is neither associative not commutative. Subtraction and addition are opposites of each other,
viz., for all x, y ∈ Z, (x + y) − y = x and (x − y) + y = x. This can be established by a bidirectional induction
on y.
Moreover, subtraction is no more than repeated predecession and succession. More elaborately, for every
x ∈ Z let
x − 0 = x and
x − f
[
(y) = f
]
(x − y) if y ∈ E while
x − f
]
(y) = f
[
(x − y) if y ∈ W
This can be verified from our definition of subtraction. One can turn around this property and use it to define
subtraction of integers using the bidirectional principle of induction on integers. Such a definition coincides
with our earlier definition.
} Multiplication of integers k20.1k
How shall we multiply two integers? If x and y are integers solving
m = n + x for m, n ∈ N (1)
p = q + y for p, q ∈ N, (2)
then (1) implies mq = nq + xq (3)
and (2) implies np = nq + ny (4)
whereas (1) and (2) implies mp = nq + ny + xq + xy (5)
now (5) implies mp + nq = (nq + xq) + (nq + ny) + xy (6)
using (3) and (4) in (6) get (mp + nq) = (mq + np) + xy (7)
The above heuristic suggests a way of defining
ˆ
f
×
: Z × Z → Z. let us abbreviate
ˆ
f
×
(x, y) by x · y. Then,
(m n) · (p q) = (mp + nq) (mq + np). We have the following properties regarding multiplication.
Well − definedness As in the case of addition, we show that our function
ˆ
f
×
is independent of choice of
representatives for the equivalence classes and hence well–defined.
Compatibility
ˆ
f
×
is compatible with f
×
of N, i.e., for all a, b ∈ N, we have (f
×
(a, b)) =
ˆ
f
×
((a), (b)), i.e.,
◦ f
×
=
ˆ
f
×
◦ ( × ). Indeed,
(a) · (b) = ((a + 1) 1) · ((b + 1) 1)
= ((a + 1)(b + 1) + (1)(1)) ((a + 1)(1) + (1)(b + 1))
= (2 + a + b + ab) (2 + a + b)
= (1 + ab) 1
= (a · b)
Owing to this compatibility, we write f
×
instead of
ˆ
f
×
.
It is remarkable that unlike addition, multiplication is not compatible with the subaltern embedding.
Does this enable us to unambiguously identify the positive and negative integers?
Commutativity, associativity, distributivity Using bidirectional induction principle, we can verify that multipli-
cation is commutative and associative. Further, multiplication distributes over addition and subtraction.
Rules
multiplication by 0 If x is any integer, then x · 0 = 0 · x = 0. To prove this, one just observes that
x · 0 = (m n) · (l l) = (ml + nl) (ml + nl) = 0 for any natural numbers l, m and n.
1 is the multiplicative identity If x is any integer, then x · 1 = 1 · x = x. To prove this, one just observes
that x·1 = (mn)·((l+1)l) = (m(l+1)+n(l))(m(l)+n(l+1)) = (ml+m+nl)(ml+nl+n) =
m n = x for any natural numbers l, m and n.
product of positives If x =
ˆ
k and y =
ˆ
l are two integers, then x · y = y · x =
d
k · l. We can reinterpret this
as the compatibility property above.
product of negatives If x = k and y = l are two integers, then x·y = y ·x =
d
k · l. This is the rule which is
taught as product of two negatives is a negative. Note that this rule further gives the product of two
negatives in terms of multiplication of naturals. To prove this consider x·y = (1 (1+k))·(1(1+
l)) = (1(1)+(1+k)(1+l))(1(1+l)+(1+k)(1)) = (2+k +l+kl)(2+k +l) = (1+kl)1 =
d
k · l.
product of a positive and a negative Let x =
ˆ
k and y = l be two integers. Then the product x · y = k · l.
For a proof, take x · y = ((1 + k) 1) · (1 (1 + l)) = (2 + k + l) (2 + k + l + kl) = kl.
Repeated addition and multiplication Recall that the multiplication function on naturals was derived from its
addition function. Likewise, we can immediately verify that the multiplication of a positive integer is
repeated addition while multiplication of a negative integer is repeated subtraction. More elaborately,
for every x ∈ Z we have
x · 0 = 0 and
x · f
[
(y) = xy − x if y ∈ E while
x · f
]
(y) = xy + x if y ∈ W .
Conversely, we can use the above equations to define the mutiplication function on integers and derive its
properties.
} Ordering integers k21.1k
Given two integers x and y, suppose x = m n and y = p q for naturals m, n, p and q. We define
x < y if and only if m + q < n + p.
< is read as ‘lesser than’. One can verify the following properties.
Well − definedness The comparison < is independent of choice of representatives for the equivalence classes x
and y and hence well–defined.
Compatibility with natural ordering < is compatible with < of N, i.e., for all a, b ∈ N, we have a < b if and
only if (a) < (b). It is in anticipation of this that we have used the same symbol used for naturals to
compare integers.
Linearity Given any two integers x and y, either x < y or x = y or y < x. This follows from the linearity of
order relation on naturals.
Compatibility with succession and predecession If x is any integer, then f
[
(x) < x < f
]
(x). For a proof, one
takes x = m n for natural m and n and verifes that m (n + 1) < m n < (m + 1) n in integers
since m + n < (n + 1) + m = n + (m + 1) = (m + n) + 1 in naturals.
Transitivity Given three integers x, y and z, if x < y and y < z then x < z. Take x = mn, y = pq, z = rs
for naturals m, n, p, q, r and s. From data, m+q < n+p and p+s < q+r which implies m+q+s < n+p+s
and n + p + s < n + q + r by compatibility with addition. By transitivity of order relation in naturals,
we have m + q + s < n + q + r. By compatibility with subtraction, we have m + s < n + r, i.e., x < z.
Compatibility with addition If x and y are integers such that x < y, then for any integer z we have x+z < y +z.
If x, y, z and w are integers such that x < y and z < w, then x + z < y + w.
Compatibility with multiplication If x and y are integers such that x < y, then for any integer z such that 0 < z
we have xz < yz.
If x and y are integers such that x < y, then for any integer w such that w < 0 we have yw < xw.
Rules
comparison Given any two naturals k and l such that k < l in N, then l < k < 0 <
ˆ
k <
ˆ
l in Z. This rule
summarizes the entire order relation on integers by
· · · < 3 < 2 < 1 < 0 <
ˆ
1 <
ˆ
2 <
ˆ
3 < · · ·
} Altered notation for integers k22.1k
We have seen that the function n 7→ ˆn from naturals to
ˆ
N is an isomorphism which is compatible with
succession, addition, subtraction, multiplication and order relation. Owing to this identification, we simply
drop the caret from the elements in
ˆ
N.
Also, for any natural k, 0 − k = k in Z. This is used to write elements of N as −k in place of k. Analogously,
if we want to emphasize that k is the positive integer
ˆ
k, we write +k.
Thus our set of integers Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}.
} Inextensibility of integers k22.2k
What if we try to repeat the process we used to get integers from naturals? Can we get a number system
which extends integers?
Indeed, show that repetition of this process yields a set with counting and arithmetic properties same as
integers. More elaborately, define (x, y) ∼ (z, w) on Z × Z if and only if x + w = y + z. Denote the equivalence
classes by Z
?
. Let [x, y] 7→ [x + 1, y] be the function
ˆ
f
]
which is a bijection on Z
?
. The principal embedding
∗
: Z → Z
?
sending t 7→ [t, 0] is a bijection which commutes with the two succession functions, f
]
and
ˆ
f
]
. The
principal embedding
∗
being a bijection means we do not have Z
?
‘bigger’ than Z. And since the succession
functions commute, the arithmetic on Z
?
is fully analogous to the one on Z.
} Universal property of integers k22.3k
This section illustrates that the entire process of constructing integers is nothing more than making a bijection
out of the succession function of naturals in a minimal way.
A set C with a bijection f
C
]
: C → C is called a complete counting system. A complete counting system is
said to be an extension of a peano counting system P (with successor function f
P
]
) if there exists an injection
i : P → C which satisfies f
C
]
◦ i = i ◦ f
P
]
. Such a C is minimal if for any extension Z of P, there exists an
injection j : C → Z which satisfies f
Z
]
◦ j = j ◦ f
C
]
.
With these definitions, one can prove that Z is a minimal complete counting system extending N. More
generally, one can prove that there exists a minimal complete counting system extending any given peano
counting system. Further, any two such minimal extensions are isomorphic. Each such minimal extension is
in fact an integral counting system discussed in the next section.
Given a collection {M
λ
}
λ∈Λ
of minimal completing extensions of a peano counting system, one is tempted to
put an equivalence relation on their union to obtain ‘the isomorphism class’ of minimal completing extensions
which in itself is a minimal completing system for the given peano counting system. But the error lies in
the fact that attempting to include every such minimal completing extension in Λ leads to a self–referential
definition of the latter set.
} Axioms for an integral counting system k23.1k
A set I is an integral counting system if the following axioms hold
(I
1
) There is a distinguished element α ∈ I.
(I
2
) I = B ∪ F for some B, F ⊂ I with B ∩ F = {α}.
One of them, say, B is arbitrarily called the backward subset and F is called the forward subset of I.
(I
3
) B and F are peano counting systems with α as their distinguished element.
Their succession functions are denoted respectively by σ
B
and σ
F
.
Take I = Z, α = 0, B = E and F = W . If we let σ
B
= f
[|E
and σ
F
= f
]|W
, they act as succession functions
for B and F. Thus, the set of integers is an example of integral counting system.
} Derived properties of an integral system k23.2k
(I
4
) I satisfies the following bidirectional induction principle:
If S ⊂ I such that
(i) α ∈ S and
(ii) if x ∈ S ∩ B, then σ
B
(x) ∈ S and if y ∈ S ∩ F, then σ
F
(y) ∈ S,
then S = I.
For a proof, apply induction on S ∩ B and S ∩ F to get them equal to B and F. And, since I = B ∪ F,
we have S = I.
(I
5
) There is a unique function f
]
: I → I called the succession function on I satisfying
(I
5a
) f
]
is bijective with its inverse f
[
called predecession
(I
5b
) f
[|B
= σ
B
and f
]|F
= σ
F
For a proof, define f
]
as follows
f
]
(α) = σ
F
(α)
having defined f
]
(x) for x ∈ F, define f
]
(σ
F
(x)) = σ
F
(x) and
having defined f
]
(y) for y ∈ B, define f
]
(σ
B
(y)) = y
By induction, f
]
is well–defined. By definition f
]
restricted to F is the succession function σ
F
and hence
is injective. Likewise, f
]
restricted to B is injective. The range of the former F \ {α} is disjoint from the
range of the latter which is B. Consequently, f
]
is an injection and a surjection.
} Isomorphism of integral counting systems k23.3k
Two integral counting systems I and J are isomorphic if
ϕ
|B
I
and ϕ
|F
I
are canonical isomorphisms from peano systems B
I
and F
I
to peano systems B
J
and F
J
respectively.
From our study of isomorphisms between peano systems, we conclude that such a ϕ is canonically given. Thus
there are no more interesting integral counting systems than integers.
} Arithmetic on integral counting systems k23.4k
An integral counting system I has the following properties.
(I
6
) Write I = P ∪ {α} ∪
ˆ
P, for P = B \ {α} and
ˆ
P = F \ {α}. View P and
ˆ
P as peano counting systems with
f
[
(α) and f
]
(α) as their distinguished elements and f
[|P
and f
]|
ˆ
P
as their succession functions. We shall
call elements of P negative and elements of
ˆ
P as positive. Further, the canonical isomorphisms from a
peano counting system P to P and
ˆ
P are called the subaltern and the principal embeddings. We denote
the latter two by
0
and .
(I
7
) Writing p + q for
ˆ
f
+
(p, q), we define an addition function
ˆ
f
+
: I × I → I. For every x ∈ I let
x + α = x and
for y ∈ B having defined x + y, let x + σ
B
(y) = f
[
(x + y) while
for y ∈ F having defined x + y, let x + σ
F
(y) = f
]
(x + y)
Addition is associative and commutative. α acts as the additive identity and every element of I has an
additive inverse.
Further, if P is any peano arithmetic system, then the addition
ˆ
f
+
on I is a compatible extension of f
+
of
P via the principal embedding. A precise version of this is: for all p, q ∈ P, we have (p+q) = (p)+(q),
i.e., ◦ f
+
=
ˆ
f
+
◦ ( × ). Owing to this compatibility, we drop the ˆ and denote addition on I simply by
f
+
. Similarly, addition is compatible with the subaltern embedding.
(I
8
) Writing p − q for
ˆ
f
−
(p, q), we define a subtraction function f
−
: I × I → I. For every x ∈ I let
x − α = x and
for y ∈ B having defined x − y, let x − σ
B
(y) = f
]
(x − y) while
for y ∈ F having defined x − y, let x − σ
F
(y) = f
[
(x − y).
Subtraction is neither associative nor commutative. Addition and subtraction are opposites of each
other in the following sense: for all x, y ∈ I, we have (x−y)+ y = x and (x+y)−y = x, a fact which can
be established by bidirectional induction on y. Subtraction in I is a compatible extension of subtraction
in P.
(I
9
) Writing p × q for
ˆ
f
×
(p, q), we define a multiplication function
ˆ
f
×
: I × I → I. For every x ∈ I let
x × α = α and
for y ∈ B having defined x × y, let x × σ
B
(y) = x × y − x while
for y ∈ F having defined x × y, let x × σ
F
(y) = x × y + x.
Multiplication is associative and commutative. f
]
(α) acts as the multiplicative identity. Every element
other than the distinguished element has a multiplicative inverse.
Multiplication distributes over addition and subtraction.
Further
ˆ
f
×
is compatible with f
×
of P in the following sense: for all p, q ∈ P, we have (p×q) = (p)×(q),
i.e., ◦ f
×
=
ˆ
f
×
◦ ( × ). Owing to this compatibility, we write f
×
instead of
ˆ
f
×
. Multiplication is not
compatible with the subaltern embedding.
(I
10
) We define a relation <
ˆ
on I such that
for x, y ∈ I, x <
ˆ
y if and only if y = x + r for some r ∈ W
<
ˆ
is transitive i.e., for x, y, z ∈ I, if x <
ˆ
y and y <
ˆ
z, then x <
ˆ
z. Hence <
ˆ
is an order. Further, one
can prove that <
ˆ
is a strict linear order.
This <
ˆ
is compatible with the < of P. That is, for p, q ∈ P, if p < q, then (p) <
ˆ
(q). Owing to this
property, we drop theˆand simply write < even in I.
The order relation is compatible with addition and multiplication i.e., if for x, y ∈ I it is known that
x < y then x + a < y + a and x × b < y × b for any a ∈ I and any b ∈
ˆ
P.
An integral counting system satisfying the properties (I
6
)–(I
10
) is called an integral arithmetic system. The
canonical isomorphism between two integral counting systems commutes with their respective succession
functions. Owing to this the arithmetic structures are also isomorphic. Thus, there are no more interesting
integral arithmetic systems than integers.
} Bank statement k25.1k
Finally, we can understand the bank statement about our bounced cheque. x = −700 = 1 701 is a solution
to the equation 301 1 = 1001 1 + x in Z.
The relevance of solving
ˆ
300 =
ˆ
1000 + x over Z when we were assigned to solve 300 = 1000 + x over N and
other such questions are answered by the following observation. For any m, n ∈ N,
x = k ∈ N is a solution to x + m = n if and only if x = (k) ∈ Z is a solution to x + (m) = (n),
where , the principal embedding of naturals into positive integers provides positive integers as an arithmetic
system mathematically indistinguishable from the natural arithmetic system.
} Division of int egers k25.2k
No doubt you have been asked to solve problems like ‘If 12 candies are divided equally among 3 kids, how
many candies does each kid get?’ The standard solution technique asks you to assume that the answer is x.
The data says 12 = x+x+x = 3x. By hit–and–miss trials, an (the?) answer is found to be 4. A generalization
of this observation is the definition of f
÷
on M below.
if (x, y) ∈ M = {(sy, y)|s, y ∈ Z, y 6= 0} define f
÷
(x, y) = f
÷
(sy, y) = s
This is abbreviated as x ÷ y = s or as x/y = s or even
x
y
= s. What happens if we allow y = 0 in M?. Then,
for any s ∈ Z, (sy, y) = (s · 0, 0) = (0, 0) and we will not be able to uniquely define 0/0.
The need for expanding the domain of f
÷
presented itself fairly early. For example, if the problem had 13
candies in place of 12, you would not be able to find an integer solving 13 = 3x. In place of candies, if you
had 13 cakes, in practice you would say each kid would get 4 cakes and a bit more. This bit is found by
dividing the cake equally into three parts. Thus, we have hit upon a new ‘imaginary’ number or magnitude
13/4 or 4
1
3
– which is not an integer. More explicitly, we say a magnitude of 13/4 cakes is that amount of
a cake such that if we had four times that amount, we would have 13 cakes. Now that we have hit upon a
new kind of magnitude, we might as well gather together all such magnitudes called rational numbers. They
are introduced in elementary classes as being denoted by p/q where p, q ∈ Z. In such magnitudes q = 0 is
disallowed.
It would be superfluous to criticize such mostly notational introduction analogous to integers. With the
recognition that rational magnitudes are an attempt to solve equations of the form p = qx for p, q ∈ Z, q 6= 0
we give a formal definition of rationals in the next section.
} Construction of rationals k25.3k
On the set of equations, B = {p = qx|p, q ∈ Z, q 6= 0}, verify that the relation ∼ below is an equivalence
relation:
Given p = qx and r = sy in B, we say (p = qx) ∼ (r = sy) iff ps = qr.
The set of rationals is defined as B/ ∼, the collection of equivalence classes. It is denoted by Z.
Unfortunately, the set B does not have well defined objects. A more rigorous approach to define rationals
follows. There is a natural bijection ϕ : B → Z × (Z \ {0}) which takes the equation (p = qx) 7→ (p, q). Verify
that the relation ∼
0
below is an equivalence relation:
Given (p, q), (r, s) ∈ Z × (Z \ {0}), we say (p, q) ∼
0
(r, s) iff ps = qr.
The set of rationals, Q can also be defined as Z × (Z \ {0})/ ∼
0
. This definition is equivalent to our previous
definition in the sense that equations e
1
∼ e
2
from B iff ϕ(e
1
) ∼
0
ϕ(e
2
) in Z × (Z \ {0}). Owing to this, ∼
0
is
denoted by ∼.
An equivalence class of the form [(p, q)] is denoted by [p, q] or p q. In such a representation, p is called the
numerator and q is called the denominator of the fraction p q.
To avoid confusion, note the following examples: 12/3 is the natural number 4, where as 13/4 is undefined
for us. However, 13/4 although undefined, is treated as a rational number in elementary classes. For the
record, the rational 13 4 is the subset {(13, 4), (26, 8), (39, 12), . . . , (−13, −4), (−26, −8), (−39, −12), . . .} of
Z × (Z \ {0}).
} Reduced representatives for equivalence classes k26.1k
We say that a representative (p, q) for the equivalence class of a rational is reduced if q > 0 and the gcd(p, q) =
1. Given rationals like 0(−18), (−12)(−3) and 2418, we find that 0(−18) = 01, (−12)(−3) = 41
24 18 = 4 3 gives the rationals with reduced representatives.
As an exercise, let us find reduced representatives for all rationals of the form p 18 for integral p. Consider
the following cases:
p = 0 In this special case, the rational 0 18 = 0 1 and (0,1) is a reduced represenative.
gcd(p, 18) = 1 Then (p, 18) is a reduced represenatitve for the rational p 18. However, it is instructive to
write p in a special form as follows.
The set P
18
= {a ∈ Z|gcd(a, 18) = 1, 0 < a < 18} = {1, 5, 7, 11, 13, 17}. Moreover, every integer p such
that gcd(p, 18) = 1 can be written in the form p = a + 18k for unique a ∈ P
18
and k ∈ Z.
gcd(p, 18) > 1 Examples for such p are: p = ±2, ±3, ±4, ±6, ±8, . . .. As an example we pick p = 4. Then,
4 18 = 2 9 and gcd(2, 9) = 1. Similarly, in other cases. Hence we say rationals such as 4 18 or
9 18 are not in their reduced form.
We prove below that every rational pq has a reduced representative. By the observation pq = (−p)(−q),
we can assume that the denominator q > 0. By the division algorithm, p = qs + r for r, s ∈ Z such that
0 ≤ r < q. We analyse the various cases below.
p = 0 Then by division algorithm, 0 = q(0) + 0, i.e., (0)(1) = (q)(0), and we have 0 q = 0 1. We pick
(0, 1) as a reduced representative for this equivalence class. If (m, n) is any representative for 0 q,
with n > 0 and gcd(m, n) = 1, then we see that 0n = mq implies m = 0 and since n > 0, gcd(0, n) = 1
implies n = 1. Thus, (0, 1) is the unique reduced represenatative for this class.
p 6= 0, r = 0 Since (p)(1) = (q)(s), p q = s 1. We say that (s, 1) is a reduced form representative for
the class p q. For every 0 6= s ∈ Z, there is one such representative. As in the previous case, such a
represenatative is unique.
p 6= 0, r > 0, gcd(r, q) = d > 1 Then, gcd(p, q) = d and we can find integers m and n > 0, uniquely, such
that p = md and q = nd with (m, n) = 1. Hence p q = m n with m and n relatively prime. Division
algorithm for the latter two yields m = ns
0
+ r
0
, with s
0
= s and r
0
=
r
d
> 0 and gcd(r
0
, n) = 1. We are
led to the next case.
p 6= 0, r > 0, gcd(r, q) = 1 Then, gcd(p, q) = 1 and (p, q) is a reduced representative for the class p q.
Uniqueness can be proved as in the (0, 1) case above.
It is instructive to list all such p as follows.
Define P
q
= {a ∈ Z|0 < a < q, (a, q) = 1}, then P
q
is a finite set which can be determined for any
given natural q. The remainder r ∈ P
q
. Using this set, we can find all p such that gcd(p, q) = 1,
via p = qs + r for s ∈ Z and r ∈ P
q
. Each such p makes (p, q) a reduced representative for the class
p q.
In brief, the collection of pairs of integers from {(s, 1)|s ∈ Z}
S
(∪
∞
q=2
{(qs + a, q)|a ∈ P
q
, s ∈ Z} provides a
unique reduced representative for all rationals. What follows is an attempt to list all rationals using reduced
representatives and without duplication.
0 1,
· · · −3 1, −2 1, −1 1, 1 1, 2 1, 3 1 · · ·
· · · −5 2, −3 2, −1 2, 1 2, 3 2, 5 2 · · ·
· · · −8 3, −5 3, −2 3, 1 3, 4 3, 7 3 · · ·
· · · −7 3, −4 3, −1 3, 2 3, 5 3, 8 3 · · ·
· · · −11 4, −7 4, −3 4, 1 4, 5 4, 9 4 · · ·
· · · −9 4, −5 4, −1 4, 34, 7 4, 11 4 · · ·
.
.
.
.
.
.
} Principal embedding k27.1k
Let x denote any integer. Define
: Z → Q given by x 7→ x 1.
The function is an injection whose range is all integral rationals, i.e., the set
ˆ
Z = {m n|0 6= n, m ∈ Z, m =
sn for some s ∈ Z} ⊂ Q .
ˆ
Z may be viewed as an integral counting system as follows. The rationals of the form p 1 for p > −1 and
those with p < 1 can be viewed as two peano counting systems with the rational 0 1 as their common
distinguished element. The succession function on the integral rationals is the one given as p1 7→ (p+1)1.
The latter extends to a succesion
ˆ
f
]
: Q → Q given by
ˆ
f
]
(x y) = (x + y) y. One can verify that
ˆ
f
]
is a
bijection. Further,
ˆ
f
]
◦ = ◦ f
]
.
The function is thus the canonical isomorphism between integers and integral rationals as integral counting
systems (composed with the inclusion of integral rationals in integers). It is called the principal embedding
of integers in rationals.
} Arithmetic of rationals k27.2k
There now remains the task of extending from integers to rationals the arithmetic operations of addition,
subtraction, multiplication, division and comparison. The extended addition, subraction and multiplication
are functions on Q × Q taking values in Q. However, the division function although taking values in Q is
defined on Q × (Q \ {0}). Of course, the comparison is a relation on Q.
For simplicity, we use the same symbols +, −, ·, / and < as in integers for these operations. Given α, β ∈ Q,
pick representatives such that α = p q and β = r s. Of course, p, q, r, s are integers with q and s being
non–zero.
We define the following:
sum α + β = p q + r s := (ps + qr) (qs)
difference α − β = p q − r s := (ps − qr) (qs)
product α · β = p q · r s := (pr) (qs)
quotient α/β = p q/r s := (ps) (qr), assuming r 6= 0, i.e., β 6= 0.
comparison We say α = p q is less than β = r s written as α < β if
either qs > 0 and ps < rq
or qs < 0 and ps > rq
To simplify presentation we have used the same symbols in both Z and Q. The choice can be deciphered from
context.
One can verify that each of the above definitions is well–defined in the sense that the statements are indepen-
dent of the choice of the representatives for α and β.
Further, addition is associative and commutative with the zero rational 0 1 as the identity. This identity is
denoted by 0, the same as in integers. Every rational has an additive inverse.
Subtraction and addition are opposites of each other in the sense that (x + y) − y = x and (x − y) + y = x
for any two rationals x and y.
Multiplication is associative and commutative with the rational one, 1 1, as the identity. Every non–zero
rational has a multiplicative inverse.
Division and multiplication are inverses of each other in the sense that (x · y)/y = x and (x/y) · y = x for any
two rationals x, y 6= 0.
Both multiplication and division distribute over addition and subtraction.
The comparison relation is a strict linear order relation on rationals. Every comparison relation is preserved
under addition or subtraction of any rational to both the rationals under comparison. A rational is said to
be positive if zero is less than that rational. Whereas, it is said to be negative if the said rational is less than
zero. Under multiplication and division by a fixed rational, every order relation is preserved if such a rational
is positive wheras it gets inverted if the rational is negative.
Finally, these operations are compatible with the operations on integers via the principal embedding. If x
and y are any two integers, (x + y) = (x) + (y), (x − y) = (x) − (y), (x · y) = (x) · (y) and x < y if
and only if (x) < (y). This makes integers isomorphic to integral rationals as integral arithmetic systems.
Moreover, whenever x/y is defined for integers x and y, (x/y) = (x)/(y). Thus the identification of integers
with integral rationals is compatible with division whenever defined. Owing to this complete agreement, we
may abbreviate integral rationals p 1 as p. With this simplfication, our division of integers 12/4 = 3 is the
same both in integers and rationals. Further, we may recover our elementary class treatment of 13/4 as a
rational via (13 1)/(4 1) = 13/4 = 13 4.
} Inextensibility of rationals k28.1k
Let us repeat the process of obtaining rationals starting with rationals. On Q×(Q \{0}) define an equivalence
relation as (x, y) ∼ (z, w) if and only if xw = yz. Denote the equivalence classes by Q
?
. One can define
addition, subtraction, multiplication, etc. on Q
?
with properties same as in the case of rationals. These
operations are compatible with the principal embedding
0
: Q → Q
?
given by x 7→ [x, 1]. However, the
principal embedding is a bijection. Thus we have nothing new.
} Duad hoop hop k28.2k
On N × N × N, investigate the relation (l, m, n) ∼ (p, q, r) if lq + mr = pm + qn.
} Axiomatic rationals k29.1k
As an exercise, integers:integral counting/arithmetic systems::rationals:??
zzzzz
