Countability depth: listings, trees and mistaken enumerations

Learning goals and preparation

Saying “put the elements in a list” hides the main work: describing the order, proving every element appears at a finite index, and accounting for repetitions or empty cases. This chapter compares increasing listings, diagonal listings and trees of finite strings. It also audits plausible but false arguments about infinite objects. Prerequisites are functions, natural-number well-ordering, finite products, geometric series and the earlier diagonal theorem.

We use $\mathbb N=\{0,1,2,\ldots\}$. Countable means finite or countably infinite. An empty set is countable, although no map from the nonempty set $\mathbb N$ can be onto it. This small exception matters when reformulating the definition by surjections.

1. Three equivalent tests, with the empty case isolated

For a nonempty set $A$, the following are equivalent: $A$ is countable; there is an injection $A\to\mathbb N$; there is a surjection $\mathbb N\to A$.

Proof. A finite nonempty set can be assigned finitely many distinct natural indices, and an infinite enumerated set has a bijection by definition, proving the injection test. Given a surjection $f:\mathbb N\to A$, assign to each $a$ the least index $n$ with $f(n)=a$. Well-ordering makes that index exist and makes the assignment injective. Conversely suppose $j:A\to\mathbb N$ is injective. Its image $S$ is a subset of $\mathbb N$. If $S$ is finite, $A$ is finite. If $S$ is infinite, list its elements increasingly by repeatedly selecting the least unused element. This process never stops. Every $s\in S$ appears because only finitely many natural numbers are smaller than $s$; it cannot be passed over forever while smaller unused indices are selected. Applying the inverse of $j$ on $S$ yields an enumeration of $A$. For a finite nonempty $A$, repeating a fixed entry after its finite list supplies a surjection from $\mathbb N$. This establishes all cases without requiring the listing itself to be injective.

The least-index construction removes duplicates from an arbitrary listing. It is not generally an efficient algorithm, nor does countability assert that membership or the listing is computable. Existence of a mathematical enumeration and existence of an effective computer program are different claims.

2. An enumeration need not respect numerical order

Every infinite subset of $\mathbb N$ has the increasing enumeration just proved. The same is false for $\mathbb Z$: a strictly increasing sequence has a first value and cannot later reach any smaller integer, so it cannot cover all integers. The familiar enumeration $0,1,-1,2,-2,\ldots$ sacrifices increasing order in order to be exhaustive.

Even $\mathbb Q\cap[0,1]$ cannot be enumerated in strictly increasing order. An exhaustive increasing list must begin with zero, since otherwise zero is already missed. Let its next entry be $q_1>0$. Then the rational $q_1/2$ lies strictly between the first two entries and can never occur later in an increasing list. The contradiction is not that rationals are uncountable; it is that this particular order requirement is impossible.

Theorem

The rationals are countable

The set $Q$ of rational numbers is at most countable, and in fact countably infinite.

Every positive rational has a unique lowest-terms representation $p/q$, where $p,q\in\{1,2,3,\ldots\}$ and $\gcd(p,q)=1$. Put $p/q$ in row $p$ and column $q$ of a grid. Scan the grid by the finite diagonals $p+q=2,3,4,\ldots$. Within each diagonal, scan in increasing numerator (any fixed order would do), and retain only coprime pairs. The beginning is

$$1,\ \frac12,\ 2,\ \frac13,\ 3,\ \frac14,\ \frac23,\ \frac32,\ 4,\ldots.$$

Worked example

Why the rational diagonal scan works

Take $7/5$. It is already in lowest terms and lies on the diagonal $p+q=12$. Only finitely many diagonals precede diagonal $12$, and diagonal $12$ contains only finitely many pairs. Thus $7/5$ is reached at a finite position. Conversely, retaining only coprime pairs means that two recorded pairs cannot represent the same positive rational: uniqueness of lowest terms forces $(p,q)$ to be the same pair. The scan is therefore both onto $Q_{+}$ and one-to-one.

The same argument explicitly proves both directions. No positive rational is missed because it has a lowest-terms pair, and no positive rational is repeated because that pair is unique. If the resulting list is $q_1,q_2,q_3,\ldots$, then

$$0,q_1,-q_1,q_2,-q_2,q_3,-q_3,\ldots$$

lists all of $Q$ exactly once. Zero occurs once, and every nonzero rational has one sign and one positive absolute value. Hence $Q$ is countable. It is not finite: the inclusion $n\mapsto n$ from $N$ into $Q$ is injective, so $Q$ contains infinitely many distinct integers.

Constructive replacement. List integer numerator and positive denominator pairs by a finite height, such as increasing $|a|+b$, and within each height by increasing numerator. Output $a/b$ and remove duplicate values at their first occurrence if desired. Every rational has at least one such pair with finite height and finitely many preceding pairs, proving coverage. Rational density does not obstruct this nonmonotone listing.

3. Count a family of finite descriptions

All finite integer strings can be listed by a height that controls both length and entry magnitude. For instance, first list the empty string; for each positive height $H$, list all strings of length at most $H$ whose entries have magnitude at most $H$, retaining a string only at its first appearance. Each stage has finitely many candidates. Every finite string has some finite length and maximum magnitude, hence appears by a sufficiently large stage.

Integer polynomials are enumerated by the coefficient strings just constructed; trailing zeros may duplicate descriptions. Exclude the zero polynomial when invoking finite root bounds.

Polynomials as finite formal sums

Definition

Polynomial over R

A polynomial with real coefficients is a formal sum

$$p(x)=\sum_{i=0}^{\infty} a_i x^i$$

where each $a_i\in R$ and all but finitely many coefficients are zero. The set of all such polynomials is denoted by $R[x]$.

The word "formal" matters. A polynomial is not merely a function value at one particular $x$; it is the whole list of coefficients, with only finitely many nonzero entries. Once the coefficients are fixed, the polynomial expression is fixed.

Concept lensStructural

Coefficients first, values after substitution

Two formal polynomials are equal precisely when every corresponding coefficient agrees, including omitted zero coefficients. Thus $1+x$ and $1+x+0x^2$ are equal. Evaluating at a real number $t$ instead produces the number $p(t)=\sum_i a_it^i$. The infinite summation notation involves no convergence question: only finitely many summands are nonzero.

An evaluated value contains less information than the coefficient list. For example, $x$ and $x^2$ both give $0$ at $t=0$ but have different coefficients. Over $\mathbb R$, agreement at every real input does imply polynomial equality; later in this note the root bound will justify that converse. Until then, coefficient equality is the definition, and evaluation is an operation applied to the already-defined object.

If at least one coefficient is nonzero, the degree of $p(x)$ is the largest index $i$ for which $a_i\ne0$. If every coefficient is zero, we call $p(x)$ the zero polynomial and set

$$\deg(0)=-\infty.$$

This convention lets degree formulas include the zero polynomial without many exceptional cases.

A nonzero constant has degree $0$, since its constant coefficient is its highest nonzero coefficient. The zero polynomial has no such coefficient and is not a degree-zero polynomial. In degree comparisons $-\infty$ is smaller than every nonnegative integer; use $\max(-\infty,m)=m$ and $(-\infty)+m=-\infty$, including $m=-\infty$. These are conventions for degree bookkeeping, not claims that a polynomial has a negative integer exponent. The zero polynomial has no leading coefficient and is not monic.

A polynomial is monic if its leading coefficient is $1$. For instance, $x^3-4x+7$ is monic, while $2x^3-4x+7$ is not.

Common mistake

Do not read the displayed last term as the degree

If a polynomial is written as

$$p(x)=a_0+a_1x+\cdots+a_nx^n,$$

then $\deg(p)=n$ only when $a_n\ne0$. The notation by itself does not guarantee that the displayed final coefficient is nonzero.

Addition, multiplication, and degree

Let

$$p(x)=\sum_{i=0}^{\infty}a_ix^i,\qquad q(x)=\sum_{i=0}^{\infty}b_ix^i.$$

Their sum is formed coefficient-by-coefficient:

$$p(x)+q(x)=\sum_{i=0}^{\infty}(a_i+b_i)x^i.$$

Their product is given by the convolution rule:

$$p(x)q(x)=\sum_{i=0}^{\infty}d_ix^i,\qquad d_i=\sum_{k=0}^{i}a_kb_{i-k}.$$

Only finitely many terms contribute, so the product is again a polynomial.

Theorem

Degree rules

For $p(x),q(x)\in R[x]$,

1. $\deg(p+q)\le \max\{\deg p,\deg q\}$;
2. $\deg(pq)=\deg p+\deg q$.

The second identity uses the fact that the coefficient field has no zero divisors.

The inequality in the first rule can be strict because leading terms may cancel. For example,

$$(x^2+1)+(-x^2+x)=x+1.$$

The product rule is stronger: if $p$ and $q$ are nonzero with leading coefficients $a_r$ and $b_s$, then the coefficient of $x^{r+s}$ in $pq$ is $a_rb_s$, which is nonzero.

To see why no higher product term survives, let $\deg p=r$ and $\deg q=s$. A contribution $a_kb_{i-k}$ at an index $i>r+s$ must have either $k>r$ or $i-k>s$, so one coefficient is zero. At index $r+s$, only the pair $k=r$, $i-k=s$ can contribute. Its product is nonzero because the coefficients belong to a field. Consequently a product of two nonzero polynomials cannot be the zero polynomial.

For addition, every coefficient above $\max(r,s)$ is zero. If the degrees are unequal, the higher leading term has no counterpart to cancel, so the bound is attained. With equal degrees, cancellation can continue through all coefficients: $p+(-p)=0$ has degree $-\infty$. If either factor in a product is zero, the product is zero and the stated conventions give the same rule.

Theorem

Division algorithm for polynomials

Let $f(x),g(x)\in R[x]$ with $g(x)\ne0$. Then there exist unique polynomials $q(x),r(x)\in R[x]$ such that

$$f(x)=g(x)q(x)+r(x),\qquad \deg r\lt\deg g.$$

For existence, consider the nonempty set

$$S=\{f-gs:s\in\mathbb R[x]\}.$$

It contains $f$ by taking $s=0$. If $0\in S$, choose $q$ with $f-gq=0$ and take $r=0$; the remainder condition follows from $\deg0=-\infty$. Otherwise every element of $S$ has nonnegative integer degree, so well-ordering gives an element $r_0=f-gq_0$ of least degree.

Suppose $\deg r_0=k\ge j=\deg g$, with leading coefficients $c_k$ and $b_j$ respectively. Since $b_j\ne0$, the field permits the coefficient $c_k/b_j$. Form

$$r_1=r_0-g\left(\frac{c_k}{b_j}x^{k-j}\right) =f-g\left(q_0+\frac{c_k}{b_j}x^{k-j}\right).$$

The exponent $k-j$ is nonnegative, so the added expression is a polynomial and $r_1$ is still in $S$. The two leading terms $c_kx^k$ cancel and all remaining terms have degree below $k$. If $r_1=0$, it contradicts $0\notin S$; otherwise its smaller degree contradicts minimality. Therefore $\deg r_0\lt\deg g$, and $q_0,r_0$ supply the required pair.

Uniqueness is just as important as existence. If

$$f=gq_1+r_1=gq_2+r_2$$

with both remainders of degree less than $\deg g$, then

$$g(q_1-q_2)=r_2-r_1.$$

The left side is either zero or has degree at least $\deg g$; the right side has degree strictly less than $\deg g$. Thus both sides must be zero, so $q_1=q_2$ and $r_1=r_2$.

Proof X-Ray

Where the uniqueness contradiction occurs

Assume the quotients differ. Their difference is then a nonzero polynomial, whose degree is at least $0$. Multiplying by nonzero $g$ makes the left side have degree at least $\deg g$. On the right, subtraction may cancel terms, but cannot increase the degree beyond that of the larger remainder. Thus the two sides cannot be equal. The quotients must agree, and substituting back forces the remainders to agree too. This argument uses the degree bound and the nonzero-divisor hypothesis together.

Remainders from evaluation

When the divisor is linear, the division algorithm becomes especially powerful.

Theorem

Remainder theorem

Let $f(x)\in R[x]$ and $a\in R$. When $f(x)$ is divided by $x-a$, the remainder is $f(a)$.

Indeed, the remainder has degree less than $1$, so it is a constant $R$. Writing

$$f(x)=(x-a)q(x)+R$$

and substituting $x=a$ gives $f(a)=R$.

Here $R=f(a)$ is regarded as a constant polynomial in the division identity; it may be zero. We do not divide the identity by $x-a$ and then substitute $x=a$, since that would divide by zero. Evaluation is legitimate directly in the polynomial identity.

Polynomial divisibility means that $g\mid f$ if $f=gq$ for some polynomial $q$ in the same coefficient field. For nonzero $g$, this is equivalent to having zero remainder. In particular, every polynomial divides the zero polynomial, although division with remainder requires a nonzero divisor.

Theorem

Factor theorem

For $f(x)\in R[x]$ and $a\in R$,

$$(x-a)\mid f(x)\quad\Longleftrightarrow\quad f(a)=0.$$

The factor theorem translates between algebraic factorization and roots. It is one of the main reasons roots become useful: a root supplies a linear factor, and a linear factor supplies a root.

How many roots can a nonzero polynomial have?

The factor theorem gives a degree bound on roots.

Theorem

Root bound

A nonzero polynomial of degree $n$ over $R$ or $C$ has at most $n$ distinct roots.

The base case is degree $0$: a nonzero constant never evaluates to zero. Assume the bound for degree $n$, and let $f$ have degree $n+1$. If it has no roots, the claim already holds. Otherwise choose a root $a$. The factor theorem gives $f(x)=(x-a)q(x)$, where $q$ is nonzero and has degree $n$ by the product rule.

For any distinct root $b\ne a$, evaluation gives $0=(b-a)q(b)$. The scalar $b-a$ is nonzero in the coefficient field, so $q(b)=0$. By induction there are at most $n$ such distinct roots, plus the one value $a$. This proves the bound for degree $n+1$. The argument does not require $q(a)\ne0$: even if $a$ is also a root of $q$, it is still only one value in the set of roots.

An immediate consequence is that a polynomial of degree at most $n$ with $n+1$ distinct roots must be the zero polynomial. This is a uniqueness theorem: too many zeros force every coefficient to vanish.

The root bound also needs its exact hypotheses. The zero polynomial vanishes at every input and is excluded. The word “distinct” counts values, rather than the number of times a factor occurs. Applying the bound to $p-q$ shows that polynomials of degree at most $n$ agreeing at $n+1$ distinct inputs are equal: otherwise their nonzero difference would have too many roots. Agreement at every real input is a special case, completing the connection between formal polynomials and their evaluated functions.

Countable products and unions with supplied enumerations

Let $I\subseteq\mathbb N$. For each $i\in I$, suppose a domain $D_i\subseteq\mathbb N$ and a surjection $e_i:D_i\to A_i$ are given together as one family of data. Empty sets use $D_i=\varnothing$; a finite list may use a finite $D_i$. Under these hypotheses $\bigcup_{i\in I}A_i$ is countable. Likewise, the product of two sets with supplied enumerations is countable.

Proof. Fix the bijection $\pi:\mathbb N^2\to\mathbb N$ given by

$$\pi(i,k)=\frac{(i+k)(i+k+1)}2+k.$$

It scans successive finite diagonals. For a union, retain only pairs with $i\in I$ and $k\in D_i$, and, in order of their $\pi$-indices, output $e_i(k)$. Every member of the union occurs because its supplied map is surjective. For each output $x$, the set of indices at which $x$ occurs is a nonempty subset of $\mathbb N$, so it has a unique least member. Assigning $x$ that least index is injective: one index corresponds to one pair and hence one output. Thus the union is countable; the empty union is immediate. This construction uses the supplied enumeration of each set.

For a product $A\times B$, use the supplied maps $a:D\to A$ and $b:E\to B$ and retain only pairs $(j,k)\in D\times E$. The output $(a(j),b(k))$ reaches every product element; assigning the least valid $\pi$-index of each output proves countability as above. If either factor is empty, the product is empty.

Uniform rational lists. Fix an enumeration of $\mathbb Q$ as $q_0,q_1,\ldots$. For each fixed $n\ge1$, enumerate index tuples in $\mathbb N^n$ by increasing coordinate sum and then lexicographically, and send $(i_1,\ldots,i_n)$ to $(q_{i_1},\ldots,q_{i_n})$. Every tuple occurs; each diagonal is finite. For $n=0$ use the single empty tuple. These rules supply the lists simultaneously for all $n$, so the union of finite rational strings is countable without choosing unspecified lists.

A nonzero rational-coefficient polynomial has finitely many real roots. For each nonzero polynomial in the supplied countable list, list its real roots in increasing order, using an empty list if it has none. Every finite subset of $\mathbb R$ has a unique increasing listing, so this rule supplies the entire family of root lists without an arbitrary choice of enumerations. Their union is the set of real algebraic numbers, hence it is countable.

A real number described by a particular kind of finite string belongs to at most a countable family of such descriptions. This does not show that every real number has such a description. Uncountability demonstrates why the latter assumption cannot be inserted without proof.

4. Finite tree nodes and infinite branches are different objects

Let $W_n$ be the set of binary strings of length $n$. It has $2^n$ elements. Listing strings by length and then lexicographically shows that $W=\bigcup_{n\ge0}W_n$ is countable. The empty string is the single length-zero node.

An infinite binary sequence is not one of those finite nodes. It is a compatible choice of one node at every level, forming an infinite branch. If a proposed list of branches is $b^{(0)},b^{(1)},\ldots$, define a new branch $d$ by $d_n=1-b^{(n)}_n$. The new branch differs from branch $n$ at its $n$th coordinate, so no entry equals it. Thus infinite branches are uncountable even though the collection of all finite nodes is countable.

Audit a false argument. “Every infinite sequence consists of its countably many finite prefixes, and all finite prefixes form a countable set; therefore all infinite sequences form a countable set.” The premise concerns membership of prefixes in $W$, but the conclusion treats a family of subsets of $W$ as though it were a subset of $W$. A branch is a whole compatible subset of nodes, not an individual node. The power set of a countable set can be uncountable. The countable-union theorem would require a countable index set of branches; assuming that index set already assumes the conclusion.

5. A countable basis does not mean countably many open sets

The open intervals with rational endpoints form a countable family. Every open subset $U\subseteq\mathbb R$ is a union of members of that family: around each $x\in U$, find a small contained interval, then use rational density to choose rational endpoints on either side of $x$ within it. Taking every rational interval contained in $U$ recovers exactly $U$.

Nevertheless there are uncountably many open sets: the map $a\mapsto(a,\infty)$ is injective from $\mathbb R$ into that collection. If $a<b$, a point between them belongs to the first half-line but not the second. There is no contradiction. Each individual open set uses a subcollection of a countable basis, but there are uncountably many subcollections. The distinction is the same nodes-versus-branches error in a different setting.

6. Optional geometric extension: uncountability can fit inside very short covers

For a binary sequence $b=(b_0,b_1,\ldots)$, define $x_b=\sum_{n\ge0}2b_n/3^{n+1}$. The geometric series bounds it in $[0,1]$. Put $s_k=b_{k-1}$ and $\Phi((s_k)_{k\ge1})=\sum_{k=1}^{\infty}2s_k/3^k$; this is the same map with indices renamed.

To justify injectivity without a false claim that ordinary ternary expansions are always unique, suppose two binary sequences first differ at index $m$. Their leading difference has magnitude $2/3^m$, while the largest possible magnitude of the tail is

$$\sum_{k=m+1}^{\infty}\frac2{3^k}=\frac1{3^m}.$$

The leading difference is strictly larger, so it cannot be cancelled.

Thus the set $K$ of all these values is uncountable.

Fixing the first $n$ digits places each value in one of $2^n$ closed intervals, each of length $3^{-n}$, because the remaining tail ranges from zero to $3^{-n}$. Hence $K$ has a finite cover with total interval length $(2/3)^n$, tending to zero. This is only a statement about explicit finite cover lengths; no measure-theory terminology is required. It shows why cardinality alone should not be identified with geometric length.

Graded construction and audit tasks

1. Definition edge case. Explain why “countable if and only if there is a surjection from $\mathbb N$” needs a nonempty qualification, and give a version correct for every set.
2. Order. Prove there is no strictly increasing enumeration of $\mathbb Q\cap(0,1)$, this time without an available minimum zero.
3. Coverage. Specify an exhaustive listing of all rational-coefficient polynomials using finite strings, and identify both sources of duplicate descriptions.
4. Tree distinction. Prove that the binary sequences eventually equal to zero form a countable set, while all infinite binary sequences do not. State what “eventually” permits to depend on the sequence.
5. Open-set audit. A student says a union of members of a countable basis has only countably many possible values. Identify the conflated objects and provide an injective counterexample family.
6. Geometric bound. In the optional construction of $K$, show that for every $\varepsilon>0$ there is a finite interval cover with total length less than $\varepsilon$. Why does this not provide an enumeration of $K$?

Full solutions

1. The empty set is finite and hence countable, but any function from $\mathbb N$ must assign a value to zero, so it cannot have empty target. A correct formulation is “$A$ is countable if it is empty or is the image of a surjection from $\mathbb N$.” Equivalently for all sets, countability is the existence of an injection $A\to\mathbb N$, including the empty function.
2. Any proposed increasing enumeration has first term $q_0\in(0,1)$. The rational $q_0/2$ also belongs to the set but is smaller than that first term and cannot appear later in a strictly increasing sequence. Thus it is not exhaustive. This contradiction uses the first term rather than a minimum of the set.
3. First enumerate rationals via integer/positive-denominator pairs. For each finite length, enumerate tuples of rational indices by repeated diagonal enumeration; interleave the lengths. Output the polynomial having that coefficient tuple. Duplicate rational representations can give the same coefficient, and trailing zero coefficients give different-length strings for the same polynomial. Removing repetitions is optional for countability; every polynomial has a finite tuple and is therefore reached.
4. For each cutoff $N$, a sequence that is zero from index $N$ onward is determined by its first $N$ bits, so there are $2^N$ possibilities. Listing by cutoff then finite prefix gives countability of their union. The cutoff can depend on the sequence; no common cutoff is claimed. For unrestricted infinite sequences, the diagonal construction above defeats every proposed listing, giving uncountability. Being a countable union over cutoffs covers only the eventually-zero family, not every branch.
5. The basis is a countable set of individual intervals; its subcollections form a power set, not the basis itself. Distinct subcollections can produce many different unions. The open half-lines $(a,\infty)$ for real $a$ are already an uncountable family by the injectivity argument above, so the claimed count is impossible.
6. Choose $n$ with $(2/3)^n<\varepsilon$. Group the points by their first $n$ digits and take the corresponding $2^n$ closed intervals, each of tail width $3^{-n}$. This finite cover has the required total length. Each interval can still contain uncountably many distinct continuations, and a cover by sets is not a listing of their individual elements. The injective binary-sequence construction independently proves $K$ uncountable.

Summary and terms

An exhaustive listing reaches every element at a finite position; it need not be sorted or computable. A finite description is one finite string, while a family of infinite compatible descriptions can be uncountable. A basis is a collection used to generate open sets, not the collection of all its subcollections. Prove the coverage property of a listing and identify the actual objects being counted before applying a countable-union argument.