Manuel Kauers Hagenberg, December 17, 2002 RISC-Linz

Computer Algebra Exercises

Solution 1

Ex. (1) Two sets A and B have the same cardinality iff there is a injective map from A to B and another one from B to A. The canonical embedings of ℕ to ℤ and ℚ are injective, so it just remains to show that there are also injective maps 1. from ℤ to ℕ, and 2. from ℚ to ℕ.

1. ℤ → ℕ. Obviously,

m: ℤ → ℕ, m(z) = \{ \begin{matrix}1 & z = 0 \\ 2z & z > 0 \\ 1 − 2z & z < 0 \end{matrix}

does the job.

2. ℚ → ℕ. As ℤ and ℕ have the same cardinality, it is sufficient to show that ℚ^{+} := {q ∈ ℚ : q > 0} and ℕ have the same cardinality. We show that ℕ^{2} and ℕ have the same cardinality, which implies the claim by the canonical (injective) embeding ℚ^{+} ↪ ℕ^{2}.

Consider

q: ℕ^{2} → ℕ, q(n, m) = \frac{(n + m + 2) · (n + m + 1)}{2} − m.

This function is an enumeration of ℕ^{2} as might be clarified by the following table where q(n, m) is written down in row n and column m.

\begin{matrix}1 & 2 & 4 & 7 & 11 & 16 & 22 & 29 & 37 & 46 & ⋯ \\ 3 & 5 & 8 & 12 & 17 & 23 & 30 & 38 & 47 & 57 & ⋯ \\ 6 & 9 & 13 & 18 & 24 & 31 & 39 & 48 & 58 & 69 & ⋯ \\ 10 & 14 & 19 & 25 & 32 & 40 & 49 & 59 & 70 & 82 & ⋯ \\ 15 & 20 & 26 & 33 & 41 & 50 & 60 & 71 & 83 & 96 & ⋯ \\ 21 & 27 & 34 & 42 & 51 & 61 & 72 & 84 & 97 & 111 & ⋯ \\ 28 & 35 & 43 & 52 & 62 & 73 & 85 & 98 & 112 & 127 & ⋯ \\ 36 & 44 & 53 & 63 & 74 & 86 & 99 & 113 & 128 & 144 & ⋯ \\ 45 & 54 & 64 & 75 & 87 & 100 & 114 & 129 & 145 & 162 & ⋯ \\ 55 & 65 & 76 & 88 & 101 & 115 & 130 & 146 & 163 & 181 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}

Ex. (2) We show that [0, 1) ⊆ ℝ is overcountable (überabzählbar) which implies the claim. Using a binary encoding we can identify [0, 1) with the set S of all sequences over {0, 1}. Now, assume that S is countable, S = {s_{1}, s_{2}, s_{3}, … } with

s_{1} = (s_{11}, s_{12}, s_{13}, …),
s_{2} = (s_{21}, s_{22}, s_{23}, …),
s_{3} = (s_{31}, s_{32}, s_{33}, …),
⋮

Consider the sequence

σ = (σ_{i})_{i=1}^{∞}, σ_{i} = 1 − s_{ii} (i ∈ ℕ).

Since S is countable and σ ∈ S, there must be some n ∈ ℕ with σ = s_{n}. But then, by definition of σ,

s_{nn} = 1 − s_{nn}

leads to a contradiction. . Ex. (3) We have to show that (Q(R), +) and (Q(R), ·) are abelian groups and that the distributive law holds.

1. (Q(R), +) is an abelian group:

(a) Associativity:

[(a, b) + (c, d)] + (e, f) = (ad + cb, bd) + (e, f)
= ((ad + cb)f + ebd, bdf)
= (adf + cbf + bde, bdf)
= (adf + b(cf + de), bdf)
= (a, b) + (cf + de, df)
= (a, b) + [(c, d) + (e, f)]

(b) Commutativity carries over from R,

(c) The additive unit is (0, 1).

(d) The additive inverse to (a, b) is (−a, b).

2. (Q(R), ·) is an abelian group:

(a) Associativity:

[(a, b) · (c, d)] · (e, f) = (ac, bd) · (e, f) = (ace, bdf) = (a, b) · (ce, df)
= (a, b) · [(c, d) · (e, f)].

(b) Commutativity carries over from R.

(c) The multiplicative unit is (1, 1).

(d) The multiplicative inverse to (a, b) is (b, a).

3. Distributivity:

[(a, b) + (c, d)] · (e, f) = (ad + bc, bd) · (e, f) = (ade + bce, bdf)
∼ (adef + bcef, bdf^{2}) = ((ae)(df) + (bf)(ce), (bf)(df))
= (ae, bf) + (ce, df) = (a, b)(e, f) + (c, d)(e, f).

This complets the proof. .

Ex. (4) We claim that c := gcd(a, b) does the job. Proof. We have to show that ⟨c⟩ = ⟨a, b⟩. “⊆”: Let z = ma + nb ∈ ⟨a, b⟩. Then, as c is the gcd of a and b, there are numbers a′, b′ ∈ ℤ such that a = a′c and b = b′c. Now,

z = ma + nb = ma′c + nb′c = (ma′ + nb′) · c,

and hence z ∈ ⟨c⟩. “⊇”: Let z = kc ∈ ⟨c⟩. According to the extended Euclidean algorithm, there are numbers s, t ∈ ℤ such that c = sa + tb. Now,

z = kc = k · (sa + tb) = ks a + kt b,

and hence z ∈ ⟨a, b⟩. .

To find the special c of ⟨10982, 55862⟩, we have to find the gcd of those numbers. We apply the Euclidean algorithm:

55862 = 5 · 10982 + 952
10982 = 11 · 952 + 510
952 = 1 · 510 + 442
510 = 1 · 442 + 68
442 = 6 · 68 + 34
68 = 2 · 34 + 0.

We have found that gcd(a, b) = 34, so ⟨10982, 55862⟩ = ⟨34⟩.

Ex. (5) Proof. I assume α, β ≠ 0. Let q = pquot(αa, βb) and r = prem(αa, βb). Then,

lc(βb)^{m−n+1}(αa) = q · βb + r
⟺  β^{m−n+1}α lc(b)^{m−n+1}a = βq · b + r
⟺  lc(b)^{m−n+1}a = \underbrace{α^{−1}β^{n−m}q}_{=pquot(a,b)} + \underbrace{α^{−1}β^{n−m−1}r}_{=prem(a,b)} .

Rearranging terms yields

αβ^{m−n} pquot(a, b) = pquot(αa, βb)

and

αβ^{m−n+1} prem(a, b) = prem(αa, βb)

as desired. .