INTEGER AND RATIONAL NUMBERS
Theorem 7.10 Both the integers and the rational numbers are countable.
Proof By Theorem 4.4 we know that N × N is countable. there exists the
natural embedding of Z into N × N by identifying [a, b] with its canonical
representative (a-b, 0) or (0, b-a). Thus there exists a bijection from Z to
a subset of a countable set, hence Z is countable. Again by Theorem 4.4 we
know that Z × Z is countable, and there exists the natural embedding of Q
into Z×Z by identifying [a, b] with its canonical representative, (c, d) where
d is positive and minimal . Thus there exists a bijection from Q to a subset
of a countable set, hence Q is countable.
Let Z* represent the image of the embedding of Z into Q. Also let
and 
represent respectively the images of the embeddings of the positive
and negative integers into the rationals .
The Archimedian Property
Theorem 7.11 Archimedian Property 
such that r < n.
Proof Let r = [a, b], if r ≤ 1, then r < 2 and we are done. If r > 1, then
without loss of generality, both a, and b are positive integers , and
b(a + 1) ≥ a + 1 > a
=> [a, b] < [a + 1, 1] ∈ .
Lemma For positive rational numbers r and s, if r > s, then r -1 < s-1.
Proof First we note that if r = [a, b], then r -1 = [b, a],
this is immediate
by computing [a, b] · [b, a] = [ab, ab] = [1, 1]. Now let r = [a, b] and s = [c,
d].
For any integer, a, the product of a with itself b times,
where b is a
positive integer is denoted ab.
Exercise Prove that for any positive integer, n, there exists an integer of
the form 2m for some positive integer m, such that 2m > n. (Hint: use
induction).
Solution For n = 1, 1 < 2 = 21. Now assume n < 2m for some m, then
Exercise Prove that for any positive rational number, q, there exists a
rational number of the form 2n, where 2n > q, and where n is the embedded
image of a positive integer.
Solution Let q = (a, b) where a and b are positive integers. We then have
(a, b) ≤ (a, 1) < (2n, 1) for some n.
The Division Algorithm
Theorem 7.12 The division algorithm If a and d are integers with d > 0,
then there exist unique integers q and r such that a = dq +r and 0 ≤ r < d.
Proof This result is a consequence of the well ordering property.
Let 
, and let
, S' is thus
the embedded image of some subset of N, and thus if it is
non-empty it must
have a least element .
If a ≥ 0, then let n = 0, and thus x = a - 0 = a ≥ 0. Thus a ∈ S'. If
a < 0, then let n = a, thus x = a-ad = a(1-d) ≥ 0. Thus a-ad ∈ S'. Thus
S' ≠ 
. Since S' ≠ , and is embedded image of a subset of N, S' has a least
element. Let the least element be r. Thus we have r = a - dq ≤ s
and a = dq + r where r ≥ 0.
We now must show r < d. We have a - d(q + 1) = a - dq - d = r - d,
thus r - d ∈ S. Since r is the least element in S' and r - d < r we have
r - d < 0 => r < d. We thus have a = dq + r with 0 ≤ r < d.
Now we have to show that q and r are unique. Suppose
and
where 
and
. Without loss of generality
we may assume 
. We thus have
. We note that
. Thus 
is a multiple of d
and non -negative. We thus have 
and
. Thus 
,
and thus 
.
Exercises
1. Verify that the relation (a, b) ≡ (c, d)
a+d = b+c is an equivalence
relation on N × N, but not on α × α where α > ω.
2. Verify that the relation (x, y) ≡ (z,w)
xw = yz is an equivalence
relation on Z × (Z - { 0 })
For any Integral Domain D show:
3. 
and where e is the additive identity .
4. u · (-u) = -u, where u is the multiplicative identity .
5. (-u) · (-u) = u, where u is the multiplicative identity .
6. If a, z ∈ D and a + z = a, then show z = e.
Solution to 3: a = a · u = a · (u + e) = a + a · e => a · e = e:
7. If v, a ∈ F, where F is a field and a · v = a, then show v = u.
8. Show that every Field is an Integral Domain.
Mathematical Induction is often used to prove certain identities. Exer-
cise 9 and its solution exemplifies how this is done. Exercise 10 is left
as practice.
9. Show that 
Solution to 9: Let 
i.
thus 1 ∈ A.
ii. Assume m ∈ A, then
Thus m + 1 ∈ A. Therefore by Mathematical Induction A = N,
and
10. Show that 
:
| Prev | Next |