# 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 a^{b}.

**Exercise **Prove that for any positive integer, n, there exists an integer of

the form 2^{m} for some positive integer m, such that 2^{m} > n. (Hint: use

induction).

**Solution** For n = 1, 1 < 2 = 2^{1}. Now assume n < 2^{m} for some m, then

**Exercise** Prove that for any positive rational number, q, there exists a

rational number of the form 2^{n}, where 2^{n} > 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) < (2^{n}, 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 |