Try our Free Online Math Solver!

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 (ab, 0) or (0, ba). 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
nonempty 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 = aad = a(1d) ≥ 0. Thus aad ∈ 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 