For these proofs, $R=\mathbb R$, $Q=\mathbb Q$, $C=\mathbb C$, $Z=\mathbb Z$, and $N=\mathbb N=\{0,1,2,\ldots\}$.

Functions used for comparing sets

Let $f:X\to Y$ be a function. Its image is

$$f(X)=\{f(x)\mid x\in X\}\subseteq Y,$$

and its preimage of $B\subseteq Y$ is

$$f^{-1}(B)=\{x\in X\mid f(x)\in B\}.$$

The notation $f^{-1}(y)$ can mean the preimage of the singleton $\{y\}$; it does not mean that an inverse function exists. An inverse function exists only when the map is bijective.

Definition

Injection, surjection, and bijection

The function $f:X\to Y$ is injective if

$$f(x_1)=f(x_2)\Longrightarrow x_1=x_2 \qquad (x_1,x_2\in X).$$

Thus every element of $Y$ has at most one preimage. It is surjective if

$$\forall y\in Y\;\exists x\in X\text{ such that }f(x)=y,$$

or equivalently $f(X)=Y$; every element of the codomain is hit. It is a bijection if it is both injective and surjective.

The codomain matters. For example, $f:N\to N$ defined by $f(n)=n+1$ is injective but not surjective because $0$ is not hit. If its codomain were $N\setminus\{0\}$, the same rule would be bijective. A claim about cardinality must therefore state both the domain and codomain.

Worked example

Checking the three properties

Consider $u:\{0,1,2\}\to\{a,b,c,d\}$ with

$$u(0)=a,\qquad u(1)=c,\qquad u(2)=a.$$

The map is not injective because $u(0)=u(2)$ although $0\ne2$. It is not surjective because $b$ and $d$ are not outputs. This small example separates the two conditions: injectivity concerns repeated outputs, whereas surjectivity concerns omitted codomain elements.

Same cardinality and countability

Concept lensStructural

Cardinality as counting and as matching

With finite sets, size can feel like an inventory: count the elements. For arbitrary sets, the definition replaces inventory with a matching test: can every element of $X$ be paired with exactly one element of $Y$, and vice versa? This is why $N$ and the even natural numbers $2N=\{0,2,4,\ldots\}$ have the same cardinality via $n\mapsto 2n$, even though $2N$ is a proper subset of $N$. The bijection records equal size; proper containment alone does not imply strictly smaller cardinality.

Definition

Same cardinality

Sets $X$ and $Y$ have the same cardinality, written

$$|X|=|Y|,$$

if there is a bijection $f:X\to Y$.

The elements being paired need not be alike. A pairing between numbers and ordered pairs is just as legitimate as a pairing between two lists of numbers. For finite sets this agrees with ordinary counting.

Definition

Finite set

A set $X$ is finite if $|X|=|n|$ for some $n\in N$, where we represent $n$ by the finite label set $n=\{0,\ldots,n-1\}$; when $n=0$, this means $n=\varnothing$. We then write $|X|=n$. The empty set is finite, with $|\varnothing|=0$.

Definition

Countable and at most countable

A set $X$ is countable in this course if it is finite or if

$$|X|=|N|.$$

Equivalently, it is at most countable when it is finite or countably infinite. Some texts use “countable” only for the infinite case, so the phrase “at most countable” removes that convention ambiguity. A set that is not at most countable is uncountable.

For a countably infinite set, an enumeration is a sequence $x_0,x_1,x_2,\ldots$ containing every element exactly once. Saying “exactly once” combines surjectivity of the listing with injectivity of its index map. Merely writing down an infinite sequence is not enough: it must be clear why no element is omitted and why repetitions do not occur.

Explicit countable sets

The integers

Theorem

The integers are countable

$|Z|=|N|$.

Assume $N=\{0,1,2,\ldots\}$. Define

$$e(0)=0,\qquad e(2k-1)=k,\qquad e(2k)=-k\quad(k\ge1).$$

This gives the list $0,1,-1,2,-2,3,-3,\ldots$.

Proof. Every integer is either $0$, a positive integer $k$, or a negative integer $-k$ with $k\ge1$. These occur respectively at index $0$, index $2k-1$, and index $2k$. Hence $e$ is surjective. The three cases have disjoint values, and within the positive or negative cases the displayed indices determine $k$ uniquely, so $e$ is injective. Therefore $e$ is a bijection. If $N$ is indexed from $1$, shift the indices by one; the cardinality statement is unchanged.

This is the basic infinite-set surprise: adding all negative integers to $N$ does not create a larger cardinality. The comparison concerns the existence of a bijection, not whether one set contains the other.

The rationals

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.

Figure. The diagonal scan turns a two-dimensional grid into one sequence; the lowest-terms condition removes duplicate names for the same rational.

Density is a different property. The rationals meet every nonempty open interval of the real line, but the diagonal procedure still places them in a single list. Dense does not mean uncountable.

Products of countable sets

The grid argument also gives a useful explicit pairing of two copies of $N$. For $a,b\in N$, let

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

All pairs with fixed $a+b=s$ form a finite diagonal, and the triangular number $s(s+1)/2$ skips exactly the preceding diagonals. Therefore $\pi$ lists every pair once. More formally, from $n=\pi(a,b)$ one recovers the unique diagonal $s$ satisfying $s(s+1)/2\le n\lt (s+1)(s+2)/2$, then $b=n-s(s+1)/2$ and $a=s-b$. Thus $\pi:N\times N\to N$ is a bijection.

Theorem

A countable triple is countable

$|N\times N\times N|=|N|$.

Proof. Define

$$\Phi(a,b,c)=\pi(\pi(a,b),c).$$

Both applications of $\pi$ are bijections, so their composition is a bijection from $N^3$ to $N$. The inverse first recovers $(\pi(a,b),c)$ and then recovers $(a,b)$. This is the concrete content of “countable times countable times countable”: a finite-dimensional grid can be scanned by successive finite diagonals. The argument also handles empty factors in the usual way: if one factor is empty, the product is empty and therefore finite; the displayed bijection concerns three copies of $N$.

The same pairing handles a finite number of labelled copies of a countable set. For example, map $(n,0)$ and $(n,1)$ into $N$ by $(n,i)\mapsto\pi(n,i)$. The map is injective, so two copies of $N$ can be stored in one copy of $N$; applying the inverse pairing to the appropriate coordinates recovers the label and the original number. This explains why an infinite list can absorb a finite amount of extra bookkeeping. It does not say that every enlargement has the same size: the existence of the particular map must still be proved.

More generally, cardinality comparisons can be transported through maps. If $X\to Y$ and $Y\to Z$ are injections, their composition gives $|X|\le|Z|$. If both maps are bijections, the composition is a bijection. These two simple rules are the bookkeeping behind the integer, rational, and triple enumerations in this section.

Cardinal inequalities

Definition

Cardinal inequality

For sets $X$ and $Y$, write

$$|X|\le |Y|$$

if there exists an injection $X\to Y$. Write $|X|\lt|Y|$ if $|X|\le|Y|$ and $|X|\ne|Y|$.

The arrow direction is essential: an injection from $X$ into $Y$ says that $Y$ has enough distinct locations to store every element of $X$, so the domain is the no-larger side. The inclusion $N\to Z$, $n\mapsto n$, proves $|N|\le|Z|$; it does not alone prove equality. The enumeration of $Z$ supplies the reverse size comparison, or the explicit bijection above supplies equality directly.

Worked example

A finite comparison with unused codomain elements

The map $r:\{1,2,3\}\to\{a,b,c,d\}$ given by $r(1)=b$, $r(2)=d$, $r(3)=a$ is injective. Thus $|\{1,2,3\}|\le|\{a,b,c,d\}|$. It is not surjective because $c$ is unused, which is exactly why the inequality may be strict.

Theorem

Cardinal inequalities form a partial-order pattern

The relation $\le$ is reflexive, transitive, and antisymmetric on cardinalities. Consequently $\lt$ is irreflexive and transitive.

Proof. Reflexivity follows from the injective identity map $id_X:X\to X$. For transitivity, if $f:X\to Y$ and $g:Y\to Z$ are injections, then $g\circ f$ is injective: equality of its outputs first gives equality of the $f$ outputs, then equality of inputs. Antisymmetry is precisely the Cantor-Bernstein theorem below. Finally, $|X|\lt|X|$ is impossible because $|X|=|X|$; transitivity of strict inequality follows by combining transitivity of $\le$ with the unequal-cardinality conditions.

There is no set whose elements are all sets. Assuming such a universal set would permit a Russell-type self-membership construction and a contradiction. Accordingly, $\le$ is not being presented as one relation with a global “set of all sets” as its domain. The partial-order statements are about any chosen collection of sets, or the cardinalities represented by that collection, that we are comparing. This qualification is foundational bookkeeping; it does not change any of the maps or proofs above.

A surjection $X\to Y$ intuitively says that $Y$ is no larger than $X$, but turning that intuition into an injection $Y\to X$ requires selecting one preimage for each $y\in Y$. The next note examines that choice issue; here we use injections and bijections directly, without assuming a choice function.

Countable unions of countable sets

Theorem

A countable union of countable sets is countable

Assuming the axiom of choice, if ${A_n}_{n\in N}$ is a countable family of countable sets, then

$$A=\bigcup_{n\in N} A_n$$

is countable.

The empty-union case is immediate: if $A=\varnothing$, the empty function is an injection into $N$. Now assume $A$ is nonempty. Since each $A_n$ is countable, for each index $n$ there exists an injection

$$i_n:A_n\to N.$$

When $A_n=\varnothing$, the unique empty function is such an injection. We use the axiom of choice to choose the whole family of injections ${i_n}$ simultaneously, including those empty-member cases. This is a choice issue about the family of witnesses; it is not a claim that a countable union of arbitrary uncountable sets is countable.

Now define

$$h:A\to N\times N,\qquad h(x)=(n(x),i_{n(x)}(x)),$$

where

$$n(x)=\min\{n\in N\mid x\in A_n\}.$$

The index set is nonempty because $x$ belongs to the union, and the well-ordering of $N$ gives its least element. This consequence of induction is proved in 6.3 Intervals, Cantor set, density, and well-ordering. The map $h$ is injective. If $h(x)=h(x')$, equality of the first coordinates gives $n(x)=n(x')=n$. Equality of the second coordinates then gives $i_n(x)=i_n(x')$, and the injectivity of $i_n$ gives $x=x'$.

Finally, diagonal enumeration gives an injection $N\times N\to N$, so composing it with $h$ makes $A$ countable. List $(0,0)$, then the pairs whose coordinates sum to $1$, then those whose coordinates sum to $2$, and so on; each pair appears at a finite stage. The index set and every member must be countable: an uncountable index set of singletons, or one uncountable member, can make the union uncountable. Empty members contribute no element.

Common mistake

Countable union is not the same as arbitrary union

The theorem here is about a countable family ${A_n}$. It does not say that an arbitrary union of countable sets must be countable.

Theorem

$Q$ is dense in $R$

Let $r\in R$ and let $\epsilon\gt 0$. By the Archimedean property, choose $n\in N$ such that

$$n\gt\frac1\epsilon, \qquad\text{so}\qquad \frac1n\lt\epsilon.$$

Choose the largest integer $m_0$ satisfying

$$m_0\le nr.$$

Then

$$m_0\le nr\lt m_0+1.$$

Dividing by $n$ gives

$$0\le r-\frac{m_0}{n}\lt\frac1n\lt\epsilon.$$

Thus

$$q=\frac{m_0}{n}\in Q$$

satisfies $|r-q|\lt\epsilon$. Therefore $Q$ is dense in $R$.

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.

Density, countability and rational intervals

A set $D\subseteq\mathbb R$ is dense if every nonempty open interval contains an element of $D$. Rational density implies irrational density: fix an irrational $\alpha$ and choose rational $q\in(a-\alpha,b-\alpha)$. Then $q+\alpha\in(a,b)$ is irrational. Thus a countable set can be dense, and two disjoint dense sets can coexist. Density and cardinality answer different questions.

Examples

Countable dense rational points. The rational points can be indexed even though every interval contains infinitely many of them. Listing them by denominator and numerator does not make them isolated.

Finite rational data. For each fixed $n$, rational $n$-tuples form a countable set by repeated products. The union over $n$ shows that all finite rational strings are countable; in particular, rational-coefficient polynomials are countable. Every nonzero polynomial has finitely many roots, so the algebraic real numbers are countable. Since $\mathbb R$ is uncountable, transcendental numbers exist.

Practice

P01. Let $\mathbb N=\{0,1,2,\ldots\}$. Give an explicit listing of all integers and a bijection from $\mathbb N$ to the even nonnegative integers.

P02. Show that removing a countable set from an uncountable set leaves an uncountable set.

P03. Prove that every interval $(a,b)$ with $a<b$ contains an irrational number, using rational density.

P04. Prove that the set of open intervals with rational endpoints is countable and that every open subset of $\mathbb R$ is a union of a subcollection of those intervals.

Full solutions

P01. List the integers as $0,1,-1,2,-2,\ldots$. The map $n\mapsto2n$ is a bijection from $\mathbb N$ to the even nonnegative integers.

P02. If the removed set and the remainder were both countable, their union would be countable, contradicting the uncountability of the original set. If the removed set is not a subset of the original set, use its intersection with the original set instead.

P03. Fix an irrational $\alpha$, such as $\sqrt2$. Rational density gives $q\in(a-\alpha,b-\alpha)\cap\mathbb Q$. Then $q+\alpha\in(a,b)$. If it were rational, subtracting $q$ would make $\alpha$ rational, a contradiction.

P04. Pairs of rationals are countable, so the subset whose first coordinate is less than the second is countable. If $x$ is in an open set $U$, choose $\varepsilon>0$ with $(x-\varepsilon,x+\varepsilon)\subseteq U$, then choose rationals $r\in(x-\varepsilon,x)$ and $s\in(x,x+\varepsilon)$. The interval $(r,s)$ contains $x$ and lies in $U$. The union of all such intervals is exactly $U$; for $U=\varnothing$ the union is empty.