Discrete Mathematics and Proof

Countable sets

An infinite set can never be counted to the end. When can its members still be put in one list, first, second, third and on forever, so that each of them has a place?

You need

Matching two sets one to oneDiscrete Mathematics and Proof

Unlocks

Uncountable sets and the diagonal argumentDiscrete Mathematics and Proof

Where you are 4 in Infinite sets

Logic, proof and discrete math6

Sets15

Infinite sets4

Matching two sets one to one

Countable sets

Uncountable sets and the diagonal argument Cantor's theorem: no set matches its power set

Why this exists

Matching two sets one to one defined “same size” by a bijection and found that \mathbb{N} is the same size as the even natural numbers, and that a full hotel with one room for each natural number can take one more guest. Throughout, \mathbb{N} = \{0, 1, 2, \dots\}.

Matching a set with \mathbb{N} is the same as writing its members in one list that never ends, each member at some numbered position. The surprise is how much can be listed: the integers, the pairs of natural numbers, every fraction, every finite piece of text.

Definition

Day 1: countable and countably infinite

A set A is countably infinite when it is the same size as \mathbb{N}, that is, when there is a bijection f : \mathbb{N} \to A. Some books write \lvert A \rvert = \aleph_0.

A set is countable when it is finite or countably infinite. Some books use “countable” for countably infinite only (and call such a set “denumerable”); check which meaning a book uses before quoting one of its theorems.

A list of A is a sequence a_0, a_1, a_2, \dots, one term for each n \in \mathbb{N}, in which every member of A appears exactly once. Writing a_n = f(n) turns a bijection f : \mathbb{N} \to A into a list and back.

Day 2: building countable sets

Day 2 needs two words. A string over a finite set of symbols (an alphabet) is a finite sequence of symbols, such as \texttt{cab} over \{\texttt{a}, \texttt{b}, \texttt{c}\}; the empty string has no symbols. A number is algebraic when it is a root of a nonzero polynomial with integer coefficients.

Intuition

Figure 1Listing \mathbb{N} \times \mathbb{N} one diagonal at a time. The pair (a, b) sits on diagonal a + b, and its position is \displaystyle \frac{(a + b)(a + b + 1)}{2} + b.

A list is a hotel register: guest a_n is in room n, every room is filled, and no guest has two rooms. A proof gives a route that reaches each member after finitely many steps.

The route matters. Walking along the bottom row of Figure 1, (0, 0), (1, 0), (2, 0), \dots, never reaches (0, 1): that walk lists only one row. Walking the diagonals instead, each finite, reaches every pair. The pair (a, b) is on diagonal a + b; the diagonals before it hold 1 + 2 + \dots + (a + b) pairs, a triangular number, and inside its own diagonal (a, b) comes b places after the start.

Results

Day 1

1. Lists. A is countably infinite if and only if A has a list a_0, a_1, a_2, \dots with every member appearing exactly once.

2. The integers. \mathbb{Z} is countably infinite. One list is 0, -1, 1, -2, 2, -3, 3, \dots, given by

f(n) = \begin{cases} \dfrac{n}{2} & \text{if } n \text{ is even}, \\[2mm] -\dfrac{n + 1}{2} & \text{if } n \text{ is odd}, \end{cases}

and the position of the integer m is z(m) = 2m if m \ge 0 and z(m) = -2m - 1 if m < 0.

3. Subsets of \mathbb{N}. Every subset of \mathbb{N} is countable. An infinite subset is listed in increasing order.

4. An injection is enough. A is countable if and only if there is an injection A \to \mathbb{N}. A nonempty A is countable if there is a surjection \mathbb{N} \to A.

5. Subsets. Every subset of a countable set is countable.

6. Pairs. \mathbb{N} \times \mathbb{N} is countably infinite, by the bijection

p(a, b) = \frac{(a + b)(a + b + 1)}{2} + b.

Day 2

7. Finite unions. If A and B are countable, so is A \cup B. So is the union of any finitely many countable sets.

8. The rationals. \mathbb{Q} is countably infinite.

9. Strings. For a finite nonempty alphabet, the set of all strings over it is countably infinite.

10. Polynomials. The set of polynomials with integer coefficients is countably infinite.

11. Countable unions (stated). If A_0, A_1, A_2, \dots are countable, then A_0 \cup A_1 \cup A_2 \cup \cdots is countable. So the set of algebraic numbers is countable.

Why it is true

Result 1. Proof. Given a bijection f : \mathbb{N} \to A, put a_n = f(n). Surjectivity says every member of A appears; injectivity says none appears twice. Conversely, a list with every member exactly once defines f(n) = a_n, which is onto and one to one for the same two reasons. \square

Result 2. Proof. For n even, \displaystyle f(n) = \frac{n}{2} \ge 0; for n odd, \displaystyle f(n) = -\frac{n+1}{2} \le -1. So f maps into \mathbb{Z}, and z maps into \mathbb{N}, with z(m) even when m \ge 0 and odd when m < 0. Check both composites. If n = 2k then z(f(n)) = z(k) = 2k = n; if n = 2k + 1 then f(n) = -(k + 1) < 0 and z(f(n)) = 2(k + 1) - 1 = n. If m \ge 0 then f(z(m)) = f(2m) = m; if m < 0 then -2m - 1 is odd and \displaystyle f(-2m - 1) = -\frac{-2m}{2} = m. So z is an inverse of f, and a function with an inverse is a bijection (Composing functions between sets, and when an inverse exists). \square

Result 3. Proof. A finite subset is countable by definition. Let B \subseteq \mathbb{N} be infinite. Let b_0 be the least member of B, which exists by the well-ordering principle (Strong induction and well-ordering). Given b_k, the set B has a member greater than b_k, for otherwise B \subseteq \{0, 1, \dots, b_k\} would be finite; let b_{k+1} be the least such member. Then b_0 < b_1 < b_2 < \cdots, so j < k gives b_j < b_k and the list has no repeats. By induction b_k \ge k, since b_0 \ge 0 and b_{k+1} > b_k \ge k.

Every member b of B appears. Some k has b_k \ge b (for example k = b), so take the least such k. If k = 0, then b_0 \le b because b_0 is least in B, so b = b_0. If k \ge 1, then b_{k-1} < b, so b is a member of B greater than b_{k-1}, and b_k is the least of those, so b_k \le b. Either way b = b_k. By Result 1, B is countably infinite. \square

Result 4. Proof. If A is finite, list it as a_1, \dots, a_n and send a_i to i; if A is countably infinite, the inverse of a bijection \mathbb{N} \to A is an injection A \to \mathbb{N}. Conversely, let g : A \to \mathbb{N} be an injection. Then g is a bijection from A onto its image g(A) \subseteq \mathbb{N}, which is countable by Result 3. If g(A) is finite, so is A; if g(A) is countably infinite, composing a bijection \mathbb{N} \to g(A) with g^{-1} gives a bijection \mathbb{N} \to A.

For the second sentence, let s : \mathbb{N} \to A be onto. For each x \in A the set \{n : s(n) = x\} is a nonempty subset of \mathbb{N}; let g(x) be its least member. If g(x) = g(y) then x = s(g(x)) = s(g(y)) = y, so g is an injection. \square

Result 5. Proof. Let S \subseteq A with A countable. Result 4 gives an injection g : A \to \mathbb{N}, and g restricted to S is still an injection. By Result 4, S is countable. \square

Result 6. Proof. Write \displaystyle T_d = \frac{d(d+1)}{2}, so T_0 = 0 and T_{d+1} = T_d + d + 1. A pair with a + b = d has 0 \le b \le d, so

T_d \le p(a, b) \le T_d + d = T_{d+1} - 1.

The blocks \{T_d, \dots, T_{d+1} - 1\} for d = 0, 1, 2, \dots do not overlap, since T_d increases, and they cover \mathbb{N}, since T_0 = 0 and T_{d+1} > d. Injective: if p(a, b) = p(a', b') = n, both pairs lie on the diagonal d whose block holds n, so b = n - T_d = b' and a = d - b = a'. Surjective: given n, find the block T_d \le n \le T_{d+1} - 1, put b = n - T_d, which lies between 0 and d, and a = d - b; then p(a, b) = T_d + b = n. \square

Result 7. Proof. Take injections f : A \to \mathbb{N} and g : B \to \mathbb{N} (Result 4) and define h : A \cup B \to \mathbb{N} by

h(x) = \begin{cases} 2f(x) & \text{if } x \in A, \\ 2g(x) + 1 & \text{if } x \in B \setminus A. \end{cases}

Each x falls in exactly one case. If h(x) = h(y), the two values have the same parity, so x and y fall in the same case; then f(x) = f(y) or g(x) = g(y), and x = y. So h is an injection and A \cup B is countable. For finitely many sets, use induction on their number: A_1 \cup \dots \cup A_{k+1} = (A_1 \cup \dots \cup A_k) \cup A_{k+1} is a union of two countable sets. \square

Result 8. Proof. Each rational q can be written in exactly one way as \displaystyle \frac{m}{n} in lowest terms with n \ge 1 (Rational numbers). Put c(q) = p(z(m), n), with z from Result 2. If c(q) = c(q'), then (z(m), n) = (z(m'), n') because p is injective, so m = m' because z is injective, and n = n'; hence q = q'. So \mathbb{Q} is countable (Result 4), and it is infinite because it contains \mathbb{Z}. \square

Result 9. Proof. Name the k symbols 1, 2, \dots, k and read a string s_1 s_2 \dots s_n as the numeral with digits s_1, \dots, s_n in base k + 1:

\begin{aligned} &c(s_1 s_2 \dots s_n) \\ &\quad = s_1 (k+1)^{n-1} + \dots + s_n, \end{aligned}

with the empty string sent to 0. A natural number has only one base-(k+1) numeral without leading zeros (Numbers in other bases), and no digit here is 0, so the numeral gives back both the length and every symbol: c is injective. There are infinitely many strings (one of each length), so by Result 4 the set is countably infinite. \square

Result 10. Proof. Write the polynomial c_0 + c_1 x + \dots + c_n x^n with c_n \ne 0 as the string of its coefficients c_0, c_1, \dots, c_n in decimal, separated by commas, over the 12 symbols 0, 1, \dots, 9, the minus sign and the comma (the zero polynomial as \texttt{0}). Different polynomials give different strings, so this is an injection into a countable set, and by Results 4 and 9 the polynomials are countable; the constants alone make them infinite. \square

Result 11, sketch. List each A_i (allowing repeats) as a_{i,0}, a_{i,1}, \dots, skipping empty sets. Then (i, j) \mapsto a_{i,j} is onto the union from a subset of \mathbb{N} \times \mathbb{N}, so the union is countable by Results 4, 5 and 6. The step “list each A_i” picks one list from infinitely many sets at once, which quietly uses a weak form of the axiom of choice; in Results 7 to 10 every list was given by a formula, so no choice was needed. For algebraic numbers: there are countably many nonzero polynomials (Result 10), and each has at most as many roots as its degree, so the algebraic numbers are a countable union of finite sets.

Worked examples

Example 1

Day 1: positions in the list of the integers

In the list 0, -1, 1, -2, 2, \dots of Result 2, find a_{100} and a_{101}, and find the positions of -50 and 37.

Solution

The index 100 is even, so \displaystyle a_{100} = \frac{100}{2} = 50. The index 101 is odd, so \displaystyle a_{101} = -\frac{101 + 1}{2} = -51. For positions use z: -50 < 0, so its position is z(-50) = -2(-50) - 1 = 99; and 37 \ge 0, so its position is z(37) = 74.

Check: 99 is odd and \displaystyle f(99) = -\frac{100}{2} = -50; 74 is even and f(74) = 37.

Example 2

Day 1: a subset of the integers

Let S = \{n \in \mathbb{Z} : 5 \mid n^2 + 1\}. Prove that S is countably infinite, and write the first eight terms of the list that the proofs of Results 3 and 5 produce, using z.

Solution

S \subseteq \mathbb{Z}, and \mathbb{Z} is countable, so S is countable by Result 5. To see S is infinite, look at remainders on division by 5. If n = 5k + 2 then n^2 + 1 = 25k^2 + 20k + 5 = 5(5k^2 + 4k + 1), so every 5k + 2 with k \in \mathbb{N} is in S, infinitely many different integers. A countable infinite set is countably infinite.

The same computation for each remainder gives n^2 + 1 remainders 1, 2, 0, 0, 2 for n = 5k, \dots, 5k + 4, so S is the integers leaving remainder 2 or 3. The proof of Result 5 sends S into \mathbb{N} by z, and Result 3 lists the image in increasing order. The smallest positions z(n) are 3, 4, 5, 6, 13, 14, 15, 16, held by n = -2, 2, -3, 3, -7, 7, -8, 8. So the list of S begins -2, 2, -3, 3, -7, 7, -8, 8.

Example 3

Day 1: coding and decoding pairs

Find p(4, 7), and find the pair whose code is 100.

Solution

The pair (4, 7) is on diagonal 11, so \displaystyle p(4, 7) = \frac{11 \cdot 12}{2} + 7 = 66 + 7 = 73.

To decode 100, find the block it lies in: \displaystyle T_{13} = \frac{13 \cdot 14}{2} = 91 and T_{14} = 105, so 91 \le 100 \le 104 and d = 13. Then b = 100 - 91 = 9 and a = 13 - 9 = 4. Check: p(4, 9) = 91 + 9 = 100.

Example 4

Day 1: a second proof that pairs are countable

Prove that q(a, b) = 2^a 3^b is an injection \mathbb{N} \times \mathbb{N} \to \mathbb{N} that is not onto, and explain why it still proves \mathbb{N} \times \mathbb{N} countable.

Solution

If 2^a 3^b = 2^c 3^d, the two sides are prime factorizations of one number, and by the fundamental-theorem-of-arithmetic the factorization is unique, so a = c and b = d. So q is injective. It is not onto: 5 has the prime factor 5, so 5 \ne 2^a 3^b for any a, b.

Result 4 asks only for an injection into \mathbb{N}, so \mathbb{N} \times \mathbb{N} is countable; it is infinite, so countably infinite.

Example 5

Day 2: codes for fractions

With the injection c(q) = p(z(m), n) of Result 8, find the codes of \displaystyle -\frac{2}{3}, \displaystyle \frac{1}{2} and \displaystyle \frac{4}{6}, and decide whether 5 is the code of any rational number.

Solution

For \displaystyle -\frac{2}{3}: m = -2, z(-2) = 3, n = 3, so \displaystyle c = p(3, 3) = \frac{6 \cdot 7}{2} + 3 = 24. For \displaystyle \frac{1}{2}: z(1) = 2, so \displaystyle c = p(2, 2) = \frac{4 \cdot 5}{2} + 2 = 12. The fraction \displaystyle \frac{4}{6} is first put in lowest terms, \displaystyle \frac{2}{3}, so z(2) = 4 and \displaystyle c = p(4, 3) = \frac{7 \cdot 8}{2} + 3 = 31. Lowest terms are what make each rational get one code, though \displaystyle \frac{2}{3} and \displaystyle \frac{4}{6} are written differently.

Decode 5: T_2 = 3 \le 5 \le 5, so d = 2, b = 2, a = 0. That is m = f(0) = 0 and n = 2, the fraction \displaystyle \frac{0}{2}, not in lowest terms. So no rational has code 5; c is an injection, not a bijection, which is all Result 4 needs.

Example 6

Day 2: a union with overlap

Let \displaystyle X = \mathbb{Q} \cup \{\sqrt{k} : k \text{ a positive integer}\}. Prove X countable, using the proof of Result 7, and find the codes of \displaystyle \frac{1}{2}, \displaystyle \sqrt{2} and \displaystyle \sqrt{4}.

Solution

Take A = \mathbb{Q} with the injection c of Result 8, and \displaystyle B = \{\sqrt{k}\} with the injection \displaystyle \sqrt{k} \mapsto k (two different positive integers have different square roots). Result 7 gives h(x) = 2c(x) for x \in \mathbb{Q} and \displaystyle h(\sqrt{k}) = 2k + 1 for \displaystyle \sqrt{k} \notin \mathbb{Q}.

So \displaystyle h(\frac{1}{2}) = 2 \cdot 12 = 24 and \displaystyle h(\sqrt{2}) = 2 \cdot 2 + 1 = 5, since \displaystyle \sqrt{2} is irrational. But \displaystyle \sqrt{4} = 2 is rational, so it is coded as a member of A: \displaystyle c(2) = p(z(2), 1) = p(4, 1) = \frac{5 \cdot 6}{2} + 1 = 16 and h(2) = 32. The rule “B \setminus A” in the second case is what keeps one point from getting two codes.

Example 7

Day 2: Ilkay’s strings

Ilkay writes words over the alphabet \{\texttt{a}, \texttt{b}, \texttt{c}\}, numbered 1, 2, 3. Using Result 9, find the codes of \texttt{cab} and \texttt{ba}, and decode 27. Then explain why the polynomials 3x^2 - x + 5 and x^3 - 2 are members of a countable set.

Solution

With k = 3 the base is 4. So c(\texttt{cab}) = 3 \cdot 16 + 1 \cdot 4 + 2 = 54 and c(\texttt{ba}) = 2 \cdot 4 + 1 = 9. To decode, write 27 in base 4: 27 = 1 \cdot 16 + 2 \cdot 4 + 3, digits 1, 2, 3, so 27 = c(\texttt{abc}).

Their coefficient strings \texttt{5,-1,3} and \texttt{-2,0,0,1} are strings over the 12-symbol alphabet of Result 10. That alphabet is finite, so its strings are countable (Result 9), and polynomials with integer coefficients inject into them.

Boundaries

Which “countable”. In this lesson a finite set is countable. In a book where “countable” means countably infinite, “every subset of a countable set is countable” is false: \{0\} is a subset of \mathbb{N}.

Every member needs a finite position. “First all the natural numbers, then all the negative integers” is not a list: -1 would have no index n \in \mathbb{N}.

A list need not follow size. \mathbb{Q} is countable, but no list of it is in increasing order (Exercise 22). Result 3’s increasing list works only because every nonempty subset of \mathbb{N} has a least member.

Finite strings only. Result 9 needs finite strings. Infinite strings of 0s and 1s are not countable, nor is \mathbb{R} (Uncountable sets and the diagonal argument).

Where this goes next

Every set built here was countable, so a set that is not needs a new idea. The Uncountable sets and the diagonal argument supplies it: every list of real numbers misses one.

Exercises

Day 1: lists and codes

In the list of Result 2, find a_{40} and a_{77}, and the positions of -13 and 13.
Give a list of the odd integers, a formula for its nth term, and prove the formula is a bijection from \mathbb{N}.
Find p(6, 2) and p(0, 9), and decode 27 and 60.
Prove that \displaystyle p(d, 0) = \frac{d(d+1)}{2} and that p(0, d) + 1 = p(d + 1, 0) for every d \in \mathbb{N}. What do these say about the path in Figure 1?
Let D be the set of natural numbers whose decimal digits are all 1 or 2. Prove D countably infinite and write its first eight terms in increasing order.
Prove \mathbb{N} \times \mathbb{N} \times \mathbb{N} countable in two ways: by (a, b, c) \mapsto p(p(a, b), c) and by (a, b, c) \mapsto 2^a 3^b 5^c. Compute both codes of (1, 2, 3).
Is (a, b) \mapsto 2^a + 3^b an injection \mathbb{N} \times \mathbb{N} \to \mathbb{N}?
Prove \mathbb{Z} \times \mathbb{Z} countable with (m, n) \mapsto p(z(m), z(n)), and find the code of (-1, 2).

Day 1: reasoning

Prove: if A is countable and g : A \to B is onto, then B is countable.
Let A be countably infinite. Prove that A has a subset B with both B and A \setminus B countably infinite.
Find the flaw: “The map (a, b) \mapsto a + b is onto \mathbb{N}, so \mathbb{N} \times \mathbb{N} is countable.”
Prove: A is countable if and only if A is empty or there is a surjection \mathbb{N} \to A.

Day 2: codes and constructions

Find the codes \displaystyle c(\frac{3}{4}) and \displaystyle c(-\frac{1}{5}) of Result 8.
Which rational numbers have codes 25 and 13?
Over Ilkay’s alphabet, find c(\texttt{acca}), decode 39, and explain why 20 is not a code.
List the strings over \{\texttt{a}, \texttt{b}, \texttt{c}\} by length, and in dictionary order within a length, starting with the empty string as term 0. In which positions are \texttt{cc} and \texttt{aaa}?
Prove that the set of circles in the plane with integer center coordinates and positive integer radius is countable, and find the code p(p(z(m), z(n)), r) of the circle with center (1, -2) and radius 3.
Prove that the set of points in the plane with both coordinates rational is countable.
Prove that the set of polynomials with rational coefficients is countable.

Day 2: reasoning

Prove that the union of three countable sets A, B, C is countable with one injection that uses remainders on division by 3.
Prove that the set of all finite sequences of natural numbers is countable, using (a_1, \dots, a_n) \mapsto 2^{a_1 + 1} 3^{a_2 + 1} \cdots p_n^{a_n + 1}, where p_n is the nth prime and the empty sequence goes to 1.
Prove that no list a_0, a_1, a_2, \dots of \mathbb{Q} has a_0 < a_1 < a_2 < \cdots.

Answers

a_{40} = 20, \displaystyle a_{77} = -\frac{78}{2} = -39. Positions: z(-13) = 25, z(13) = 26.
1, -1, 3, -3, 5, -5, \dots, given by o(n) = n + 1 for n even and o(n) = -n for n odd. It is o(n) = 2f(n) + 1, the composite of f with m \mapsto 2m + 1, a bijection from \mathbb{Z} onto the odd integers (injective; 2k + 1 comes from k). Composites of bijections are bijections.
p(6, 2) = 36 + 2 = 38; p(0, 9) = 45 + 9 = 54. 27: T_6 = 21 \le 27 \le 27, so b = 6, a = 0: (0, 6). 60: T_{10} = 55 \le 60 \le 65, so b = 5, a = 5: (5, 5).
p(d, 0) = T_d + 0. p(0, d) + 1 = T_d + d + 1 = T_{d+1} = p(d + 1, 0). Each diagonal begins on the bottom row with a triangular number, and the step after the top of one diagonal is the start of the next.
D \subseteq \mathbb{N}, so countable (Result 3); it contains 1, 11, 111, \dots, so infinite. First eight: 1, 2, 11, 12, 21, 22, 111, 112.
p(p(a, b), c) is a composite of injections ((a, b, c) \mapsto (p(a, b), c) is injective since p is), and 2^a 3^b 5^c is injective by unique factorization. Codes: p(1, 2) = 8, then p(8, 3) = 66 + 3 = 69; and 2 \cdot 9 \cdot 125 = 2250.
No: 2^2 + 3^0 = 5 = 2^1 + 3^1.
Injective: p is injective and so is z, so equal codes give z(m) = z(m') and z(n) = z(n'). Infinite, as it contains \mathbb{Z} \times \{0\}. Code: z(-1) = 1, z(2) = 4, p(1, 4) = 15 + 4 = 19.
Proof. If B is empty it is finite. Otherwise A is nonempty. If A is finite, B = g(A) has at most as many members, so it is finite. If A is countably infinite with bijection f : \mathbb{N} \to A, then g \circ f is onto B, and Result 4 applies. \square
Proof. Take a bijection f : \mathbb{N} \to A and let B be the image of the even naturals E. As f is one to one, A \setminus B is the image of the odd naturals O, and f matches E with B and O with A \setminus B. Both E and O are countably infinite (Result 3), so composing gives bijections from \mathbb{N}. \square
True conclusion, wrong reason. Result 4 needs an injection into \mathbb{N} or a surjection from \mathbb{N}; a map onto \mathbb{N} goes the wrong way: x \mapsto \lfloor \lvert x \rvert \rfloor maps \mathbb{R} onto \mathbb{N}, yet \mathbb{R} is not countable.
Proof. If A is empty, it is finite; if there is a surjection, Result 4 applies. Conversely, a bijection \mathbb{N} \to A is onto. A finite nonempty A lists as a_1, \dots, a_k; put s(n) = a_{n+1} for n < k and s(n) = a_k for n \ge k, which is onto. \square
\displaystyle \frac{3}{4}: z(3) = 6, p(6, 4) = 55 + 4 = 59. \displaystyle -\frac{1}{5}: z(-1) = 1, p(1, 5) = 21 + 5 = 26.
25: T_6 = 21, so b = 4, a = 2; m = f(2) = 1, n = 4: \displaystyle \frac{1}{4}, in lowest terms. 13: T_4 = 10, so b = 3, a = 1; m = f(1) = -1, n = 3: \displaystyle -\frac{1}{3}.
c(\texttt{acca}) = 64 + 48 + 12 + 1 = 125. 39 = 2 \cdot 16 + 1 \cdot 4 + 3, digits 2, 1, 3: \texttt{bac}. 20 = 1 \cdot 16 + 1 \cdot 4 + 0 has digit 0, which names no symbol.
Term 0 is the empty string, terms 1 to 3 the three one-letter strings, terms 4 to 12 the nine two-letter strings. So \texttt{cc}, the last of those, is term 12, and \texttt{aaa} is term 13.
A circle is fixed by its center (m, n) and radius r, and the code is injective as a composite of injections (z, p twice), so Result 4 applies. z(1) = 2, z(-2) = 3, p(2, 3) = 15 + 3 = 18, \displaystyle p(18, 3) = \frac{21 \cdot 22}{2} + 3 = 234.
Proof. (x, y) \mapsto p(c(x), c(y)), with c from Result 8, is injective: equal codes give c(x) = c(x') and c(y) = c(y'). Result 4. \square
Proof. Write each such polynomial in a standard string, as in Result 10, with each coefficient a fraction in lowest terms; add the symbol / to make 13 symbols. Different polynomials give different strings, so Results 4 and 9 apply. \square
Proof. With injections f, g, k into \mathbb{N}, put h(x) = 3f(x) on A, h(x) = 3g(x) + 1 on B \setminus A, h(x) = 3k(x) + 2 on C \setminus (A \cup B). Each x is in one case; equal values have the same remainder, so the same case, and then the same f, g or k value. \square
Proof. Every exponent a_i + 1 is at least 1, so by unique factorization the code shows the number of primes used (the length n) and each exponent, hence each a_i. So the map is injective, and Result 4 applies. \square
Proof. Suppose such a list exists. The midpoint \displaystyle \frac{a_0 + a_1}{2} is rational and lies strictly between a_0 and a_1, so it equals some a_k. Then k \ne 0, 1, so k \ge 2 and a_k > a_1, a contradiction. \square