Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Countability and the Uncountability of R: Examples and Counterexamples

1 · Prerequisites

2 · Summary

Objective. This companion page works the machinery of countability-and-uncountability on concrete sets and boundary cases. Every item uses the parent page, its established prerequisite closure, or earlier items on this companion page; nothing outside this page depends on anything homed here. The rational enumeration and the algebraic-number item also use the finite-sum and natural-power interfaces of roots-and-rational-powers. Each item states its hypotheses and checks its arguments locally, and the page makes no claim beyond the statements of its items; in particular no decimal expansion, series or complex algebraic-closure machinery is used anywhere.

Examples and counterexamples

The items are listed in the order in which they appear in the page inventory; same-page dependencies always point backwards.

The integers are countably infinite: $Z \approx N$ transports the product bijection to the integers by two injections and Schröder-Bernstein.
Deleting one point of a countably infinite set leaves a set equinumerous with it deletes one point of a countably infinite set by an explicit shift, and contrasts this with the finite case.
$P (N)$ is uncountable instantiates Cantor's theorem at $N$ and draws the strict-domination conclusion.
The set of binary sequences is equinumerous with $P (N)$ , hence uncountable identifies binary sequences with subsets of $N$ by characteristic functions.
The rationals in an interval are countably infinite while the interval is uncountable separates density from cardinality inside an interval.
The complement of an at most countable set of reals is uncountable deletes an at most countable set of reals by a two-set interleaving with no choice.
A nonempty surjective image of $N$ need not be equinumerous with $N$ and The empty set is at most countable but no function from $N$ is onto it record the two boundary defects of the onto criterion: repetitions, and the empty set.
An explicit enumeration of the rationals, with repetitions and then without them writes a completely specified surjection $N \to Q$ and then deletes repetitions by least new index.
A real coefficient list of degree d has at most d real roots bounds the real root set of a finite real coefficient list, by finite synthetic division.
Real algebraic numbers are countably infinite, without choice codes integer coefficient lists, uses that bound, and injects the real algebraic numbers into $N$ ; their complement is uncountable.
Cantor diagonal construction misses every prescribed list of binary sequences performs the literal diagonal construction.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-generatedjudge pass (gpt-6.1-sol)Open item page →

The integers are countably infinite: $Z \approx N$

Example

$Z \approx N$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ): the integers are countably infinite (Finite, countably infinite, countable, uncountable). The argument is the two-injection route of The Schröder-Bernstein theorem rather than a closed formula. The map $n \mapsto [(n, 0)]$ is injective (The naturals embed in the integers), and the quotient map $π (a, b) = [(a, b)]$ is a surjective function $N \times N \to Z$ (Let $\sim$ be an equivalence relation on $A$ with quotient map $π : A \to A / \sim$ , and let $f : A \to B$ . There is a function $g : A / \sim \to B$ with $g \circ π = f$ if and only if $a \sim a^{'}$ implies $f (a) = f (a^{'})$ ; and such a $g$ is then unique, The integers as equivalence classes of pairs of naturals); composing $π$ with the bijection $β$ of $N \times N \approx N$ exhibits $Z$ as a surjective image of $N$ , and A nonempty set is at most countable iff it is a surjective image of $N$ then supplies an injection $Z \to N$ explicitly as $j (x) = \min {k \in N : π (β (k)) = x}$ . Every ingredient is a definition or a canonical least element, so no choice principle is used; A product of two at most countable sets is at most countable then gives that $Z \times Z$ is at most countable as well.

Facts & Assumptions

Given: The naturals $N$ (The natural numbers $N$ (von Neumann)), the integers $Z = (N \times N) / \sim$ with classes $[(a, b)]$ for the equivalence relation $(a, b) \sim (c, d) ⟺ a + d = b + c$ (The integers as equivalence classes of pairs of naturals, The integer-defining relation is an equivalence relation), the embedding $n \mapsto [(n, 0)]$ of $N$ in $Z$ (The naturals embed in the integers), and the quotient map $π = {((a, b), C) : C = [(a, b)]}$ (Let $\sim$ be an equivalence relation on $A$ with quotient map $π : A \to A / \sim$ , and let $f : A \to B$ . There is a function $g : A / \sim \to B$ with $g \circ π = f$ if and only if $a \sim a^{'}$ implies $f (a) = f (a^{'})$ ; and such a $g$ is then unique).

[F1]

The map $n \mapsto [(n, 0)]$ is injective (The naturals embed in the integers).

[F2]

$π$ is a surjective function $N \times N \to Z$ with $π (a, b) = [(a, b)]$ (Let $\sim$ be an equivalence relation on $A$ with quotient map $π : A \to A / \sim$ , and let $f : A \to B$ . There is a function $g : A / \sim \to B$ with $g \circ π = f$ if and only if $a \sim a^{'}$ implies $f (a) = f (a^{'})$ ; and such a $g$ is then unique, The integers as equivalence classes of pairs of naturals).

[F3]

$N \times N \approx N$ : there is a bijection $β : N \to N \times N$ , the inverse of the exhibited bijection $N \times N \to N$ ( $N \times N \approx N$ , Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Injection, surjection, bijection).

[F4]

For a nonempty set $A$ : $A$ is at most countable if and only if there is a surjection $s : N \to A$ , and from such an $s$ the rule $j (a) = \min {k \in N : s (k) = a}$ defines an injection $A \to N$ (A nonempty set is at most countable iff it is a surjective image of $N$ ).

[F5]

If $A ⪯ B$ and $B ⪯ A$ then $A \approx B$ (The Schröder-Bernstein theorem); if $A$ and $B$ are at most countable then so is $A \times B$ (A product of two at most countable sets is at most countable).

[F6]

$A$ is countably infinite when $A \approx N$ and at most countable when it is finite or countably infinite (Finite, countably infinite, countable, uncountable); $A ⪯ B$ means an injection $A \to B$ exists (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ); a composite of surjections is a surjection (Injection, surjection, bijection, A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain).

Verification

technique · direct

1.1F2

$π$ is a surjective function $N \times N \to Z$ : this is the general quotient map statement applied to the equivalence relation of The integers as equivalence classes of pairs of naturals, whose equivalence-class property is The integer-defining relation is an equivalence relation.

1.2F3

$β : N \to N \times N$ is a bijection, and in particular a surjection.

1.3F1F6

The map $n \mapsto [(n, 0)]$ is an injection $N \to Z$ , so $N ⪯ Z$ .

2.1step 1.1step 1.2F6

The composite $π \circ β : N \to Z$ is a surjection, as a composite of the surjections $β$ and $π$ ; hence $Z$ is a surjective image of $N$ , and $Z \neq \emptyset$ because $[(0, 0)] \in Z$ .

3.1step 2.1F4

Applying [F4] to the nonempty set $Z$ and the surjection $π \circ β$ of step 2.1 gives an injection $j : Z \to N$ , explicitly $j (x) = \min {k \in N : π (β (k)) = x}$ ; hence $Z ⪯ N$ .

4.1step 1.3step 3.1F5F6

Since $N ⪯ Z$ by step 1.3 and $Z ⪯ N$ by step 3.1, Schröder-Bernstein gives $Z \approx N$ , so the integers are countably infinite.

5.1step 4.1F4F5∎

With step 4.1, both $Z$ and $Z$ are at most countable, so their product $Z \times Z$ is at most countable by [F5]. The injection $j$ is defined by the least element of a nonempty set of naturals and $β$ is the inverse of an exhibited bijection, so no choice principle is used.

Remarks

The route through $N \times N$ is the same device that will enumerate $Q$ : $Z$ is a quotient of $N \times N$ , the pairing $β$ lists pairs, and the least-index rule turns a list with repetitions into an injection. Nothing here needs a closed formula for a bijection $Z \to N$ .
For each fixed positive integer $k$ , the product of $k$ copies of $Z$ is at most countable, by $k - 1$ applications of A product of two at most countable sets is at most countable.

ExampleConstruction: Literature-sourcedVerification: AI-generatedjudge pass (gpt-6.1-sol)Open item page →

Deleting one point of a countably infinite set leaves a set equinumerous with it

Example

Let $X$ be countably infinite (Finite, countably infinite, countable, uncountable) and let $x \in X$ . Then $X \approx X ∖ {x}$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ): deleting one point leaves a set of the same size, and $X ∖ {x}$ is a proper subset of $X$ (Subset $x \subseteq y$ , proper subset $x ⊊ y$ , and the separation notation ${z \in x : φ (z)}$ , The difference $a ∖ b$ , the symmetric difference $a △ b$ , and the complement $X ∖ a$ relative to a set $X$ ). The basic instance is $X = N$ , $x = 0$ , where the successor map $σ$ is a bijection $N \to N ∖ {0}$ (The von Neumann naturals form a Peano system, Every nonzero natural number is a successor); a general $X$ transports a shift of $N$ along a bijection $N \to X$ . No finite set shares the behaviour: by claim 5 of The pigeonhole principle on $N$ no finite set is equinumerous with a proper subset of itself. No choice principle is used.

Facts & Assumptions

Given: A countably infinite set $X$ and a point $x \in X$ ; the von Neumann naturals $N = ω$ with $0 = \emptyset$ and successor $σ$ (The natural numbers $N$ (von Neumann)); and the additive order $m \leq n ⟺ \exists k \in N (m + k = n)$ , $m < n ⟺ (m \leq n and m \neq n)$ (Order on the natural numbers). Write $A \approx B$ when a bijection $A \to B$ exists (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[F1]

$X$ is countably infinite exactly when $X \approx N$ (Finite, countably infinite, countable, uncountable).

[F2]

$σ$ is injective, $σ (n) \neq 0$ for every $n \in N$ , and every $n \neq 0$ equals $σ (m)$ for some $m \in N$ (The von Neumann naturals form a Peano system, Every nonzero natural number is a successor).

[F3]

Discreteness and linearity of the order: $m < n ⟺ σ (m) \leq n$ for all $m, n \in N$ (Discreteness: $σ (n)$ is the immediate successor); $\leq$ is reflexive, antisymmetric, transitive and total ( $\leq$ is a linear order on $N$ ); and $m + 0 = m$ , $m + σ (k) = σ (m + k)$ for all $m, k$ (Addition of natural numbers).

[F4]

Exactly one of $m < n$ , $m = n$ , $n < m$ holds (Trichotomy of the order on $N$ ).

[F5]

A composite of bijections is a bijection; the inverse of a bijection is a bijection; and the restriction of a bijection to a subset is a bijection onto the image of that subset ( $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = Δ_{A}$ and $f \circ g = Δ_{B}$ ; such a $g$ is unique, equals the inverse relation $f^{- 1}$ , and is itself a bijection, For $f : A \to B$ and $g : B \to C$ : if both are injective so is $g \circ f$ ; if both are surjective so is $g \circ f$ ; if $g \circ f$ is injective so is $f$ ; and if $g \circ f$ is surjective so is $g$ , Injection, surjection, bijection).

[F6]

Claim 5 of The pigeonhole principle on $N$ : if $A \subseteq n$ and $n \approx A$ for a natural number $n$ , then $A = n$ ; transporting along a bijection, no finite set is equinumerous with a proper subset of itself.

[F7]

$z \in X ∖ {x}$ holds exactly when $z \in X$ and $z \neq x$ , since $z \in {x}$ exactly when $z = x$ (The difference $a ∖ b$ , the symmetric difference $a △ b$ , and the complement $X ∖ a$ relative to a set $X$ , The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ ); in particular $X ∖ {x} \subseteq X$ (Subset $x \subseteq y$ , proper subset $x ⊊ y$ , and the separation notation ${z \in x : φ (z)}$ ).

[F8]

The image and preimage of a set under a function (The image $R [A]$ and the preimage $R^{- 1} [B]$ of a set under a relation): $f [S] = {f (s) : s \in S}$ , and if $f$ is injective then $t \in f [S]$ has exactly one preimage in $S$ .

Verification

technique · direct

1.1F3F4construct

For $n \in N$ put $φ_{n} : = {(k, v) \in N \times N : (k < n \land v = k) \lor (n \leq k \land v = σ (k))}$ , a set by Separation, and read it as a map. It is a function $N \to N ∖ {n}$ . Indeed, for each $k \in N$ the two clauses are exhaustive and mutually exclusive: if $k < n$ then $n \leq k$ fails, since $k < n$ gives $k \leq n$ and $k \neq n$ while $n \leq k$ would let antisymmetry give $k = n$ ; and if $k < n$ fails then $k = n$ or $n < k$ by trichotomy, so $n \leq k$ holds by reflexivity or by $n < k$ implying $n \leq k$ . Hence exactly one value $v$ is paired with $k$ , and $v$ is $k \in N$ or $σ (k) \in N$ , so $dom φ_{n} = N$ . The values avoid $n$ : in the first clause $v = k \neq n$ ; in the second clause $v = σ (k) \neq n$ , because $σ (k) = n \leq k$ would give $σ (k) \leq k$ and hence $k < k$ by discreteness, which is impossible since $k < k$ would require $k \neq k$ .

1.2F7

$X ∖ {x}$ is a proper subset of $X$ . By [F7] it is a subset of $X$ ; it differs from $X$ because $x \in X$ while $x \notin X ∖ {x}$ , as $x = x$ .

1.3F5F6

No finite set is equinumerous with a proper subset of itself. Let $F$ be finite, let $A \subseteq F$ with $A \neq F$ , and suppose towards a contradiction that $h : F \to A$ is a bijection. Fix $k \in N$ and a bijection $ψ : F \to k$ , possible since $F$ is finite. Then $A \approx ψ [A]$ via the restriction of $ψ$ to $A$ by [F5], and $ψ [A] \approx A \approx F \approx k$ by symmetry and transitivity of $\approx$ , so $ψ [A] \subseteq k$ satisfies $k \approx ψ [A]$ ; claim 5 of [F6] gives $ψ [A] = k$ . Then $F \subseteq A$ : for $f \in F$ the value $ψ (f) \in k = ψ [A]$ equals $ψ (a)$ for some $a \in A$ , so $f = a$ by injectivity of $ψ$ . With $A \subseteq F$ this gives $A = F$ , contradicting $A \neq F$ .

1.4F2

For $X = N$ and $x = 0$ the witness is the successor map: $σ$ is injective and never zero by [F2], so it is a function $N \to N ∖ {0}$ , and it is onto $N ∖ {0}$ because every $n \neq 0$ is a successor by [F2]. Hence $σ$ is a bijection $N \to N ∖ {0}$ .

1.5F1F5F8

Since $X$ is countably infinite, [F1] supplies a bijection $e : N \to X$ ; let $n \in N$ with $e (n) = x$ , which exists because $e$ is onto. Then $e [N ∖ {n}] = X ∖ {x}$ : if $t = e (k)$ with $k \neq n$ then $t \neq x$ , since $t = x = e (n)$ would force $k = n$ by injectivity of $e$ ; conversely, if $t \in X$ and $t \neq x$ , then $t = e (k)$ for some $k$ by surjectivity and $k \neq n$ since $e (n) = x \neq t$ .

2.1step 1.1F2F3F4

$φ_{n}$ is injective. Let $φ_{n} (k) = φ_{n} (l)$ and split each of $k, l$ by trichotomy; the alternatives $k = n$ and $n < k$ both assign the value $σ (k)$ , and $n \leq k$ in both. If $k < n$ and $l < n$ the values are $k$ and $l$ , so $k = l$ . If $n \leq k$ and $n \leq l$ the values are $σ (k)$ and $σ (l)$ , so $k = l$ by injectivity of $σ$ . In a mixed case, say $k < n$ and $n \leq l$ , the values are $k$ and $σ (l)$ with $l = n$ or $n < l$ : if $l = n$ then $k = σ (n) \leq n$ because $k < n$ gives $k \leq n$ , so $σ (n) \leq n$ and discreteness gives $n < n$ , impossible; if $n < l$ then $k = σ (l) \leq n$ , so discreteness gives $l < n$ , contradicting $n < l$ by trichotomy. The case $n \leq k$ with $l < n$ is symmetric. Hence $k = l$ in every case.

2.2step 1.5F5

The restriction $e_{0}$ of $e$ to $N ∖ {n}$ , read as a map into $X ∖ {x}$ , is a bijection $N ∖ {n} \to X ∖ {x}$ : it is injective, being a restriction of the injection $e$ , and it is onto, since its image is $e [N ∖ {n}] = X ∖ {x}$ by step 1.5.

3.1step 1.1step 2.1F2F3F4

$φ_{n}$ is surjective onto $N ∖ {n}$ . Let $m \in N$ with $m \neq n$ . If $m < n$ then $φ_{n} (m) = m$ ; if $n < m$ then $n \leq m$ with $n \neq m$ , so $m = n + j$ for some $j \neq 0$ , $j = σ (i)$ by [F2], and $m = n + σ (i) = σ (n + i)$ by [F3]. Then $k : = n + i$ satisfies $n \leq k$ (witnessed by $i$ ) and $φ_{n} (k) = σ (k) = m$ . So $φ_{n}$ is onto $N ∖ {n}$ , and with step 2.1 it is a bijection $N \to N ∖ {n}$ .

4.1step 3.1step 2.2F5

The composite $e_{0} \circ φ_{n} \circ e^{- 1} : X \to X ∖ {x}$ is a bijection: $e^{- 1}$ is a bijection $X \to N$ by [F5], $φ_{n}$ is a bijection $N \to N ∖ {n}$ by step 3.1, and $e_{0}$ is a bijection $N ∖ {n} \to X ∖ {x}$ by step 2.2, so by [F5] the composite is a bijection. Hence $X \approx X ∖ {x}$ .

5.1step 1.2step 1.3step 1.4step 4.1∎

Therefore $X \approx X ∖ {x}$ by step 4.1, the set $X ∖ {x}$ is a proper subset of $X$ by step 1.2, the case $X = N$ , $x = 0$ is the successor bijection of step 1.4, and no finite set is equinumerous with a proper subset of itself by step 1.3. Every map used is defined by an explicit rule or is the unique inverse of a bijection, so no choice principle is used.

Remarks

The shift $φ_{n}$ is the identity below $n$ and the successor above it; the point $n$ itself is absorbed into the second clause, and the value $n$ is skipped. Deleting $x$ from $X$ is exactly conjugating this one missing value through the bijection $e$ .
The contrast with finite sets is the reason the example is worth stating: The pigeonhole principle on $N$ claim 5 shows that deleting a point from a finite set always changes its size, so "same size after deleting a point" is a genuine feature of the infinite case rather than an accident of the notation.

ExampleConstruction: Literature-sourcedVerification: AI-generatedjudge pass (gpt-6.1-sol)Open item page →

$P (N)$ is uncountable

Example

The power set $P (N)$ is uncountable (Finite, countably infinite, countable, uncountable): there is no surjection $N \to P (N)$ (Cantor's theorem: $A ≺ P (A)$ ), so $N ≺ P (N)$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ). The proof combines Cantor's theorem with The Schröder-Bernstein theorem: the map $n \mapsto {n}$ is injective (The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ , ${a, b} = {c, d}$ if and only if ( $a = c$ and $b = d$ ) or ( $a = d$ and $b = c$ ); in particular ${a} = {c, d}$ if and only if $a = c = d$ ), so $N ⪯ P (N)$ ; and if $P (N)$ were at most countable then $P (N) ⪯ N$ , so Schröder-Bernstein would give a bijection $P (N) \to N$ , hence a surjection $N \to P (N)$ , contradicting Cantor's theorem. No choice principle is used.

Facts & Assumptions

Given: The von Neumann naturals $N$ with $0 = \emptyset$ and successor $σ$ (The natural numbers $N$ (von Neumann)), the order $m < n ⟺ m \in n$ with $n = {m \in N : m < n}$ (Order on the natural numbers, On $N$ the order is membership: $m < n ⟺ m \in n$ ), and the power set $P (N) = {z : z \subseteq N}$ (The power set $P (x) = {z : z \subseteq x}$ ).

[F1]

$A$ is finite when $A \approx n$ for some $n \in N$ , countably infinite when $A \approx N$ , at most countable when it is finite or countably infinite, and uncountable when it is not at most countable (Finite, countably infinite, countable, uncountable).

[F2]

$A \approx B$ means a bijection $A \to B$ exists, $A ⪯ B$ means an injection $A \to B$ exists, and $A ≺ B$ means $A ⪯ B$ and not $A \approx B$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[F3]

Every element of a natural number is a natural number, and $m \subseteq N$ for every $m \in N$ (On $N$ the order is membership: $m < n ⟺ m \in n$ ).

[F4]

${a} = {c, d}$ if and only if $a = c$ and $a = d$ ( ${a, b} = {c, d}$ if and only if ( $a = c$ and $b = d$ ) or ( $a = d$ and $b = c$ ); in particular ${a} = {c, d}$ if and only if $a = c = d$ ); and $t \in {a}$ exactly when $t = a$ (The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ ).

[F5]

Cantor's theorem: there is no surjection $A \to P (A)$ for any set $A$ (Cantor's theorem: $A ≺ P (A)$ ).

[F6]

Schröder-Bernstein: if $A ⪯ B$ and $B ⪯ A$ then $A \approx B$ (The Schröder-Bernstein theorem).

[F7]

A bijection is a surjection, a composite of injections is an injection, and the inverse of a bijection is a bijection (Injection, surjection, bijection, $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = Δ_{A}$ and $f \circ g = Δ_{B}$ ; such a $g$ is unique, equals the inverse relation $f^{- 1}$ , and is itself a bijection).

Verification

technique · direct

1.1F3F4F7

The map $s : N \to P (N)$ , $s (n) = {n}$ , is well defined because ${n} \subseteq N$ by [F3], and it is injective: if ${n} = {m}$ then [F4] gives $n = m$ directly. Hence $N ⪯ P (N)$ .

1.2F1F3F7

If $P (N)$ is at most countable then $P (N) ⪯ N$ . If $P (N) \approx N$ , any bijection $P (N) \to N$ is an injection. If instead $P (N) \approx m$ for some $m \in N$ , fix a bijection $ψ : P (N) \to m$ ; the inclusion map $m \to N$ is available by [F3] and is injective, and the composite of the two injections is an injection $P (N) \to N$ . These are the two alternatives in [F1].

2.1step 1.1step 1.2F5F6F7

Therefore $P (N)$ is not at most countable. Suppose it were. Then $P (N) ⪯ N$ by step 1.2 and $N ⪯ P (N)$ by step 1.1, so [F6] supplies a bijection $P (N) \to N$ ; its inverse is a bijection $N \to P (N)$ by [F7], hence a surjection $N \to P (N)$ , contradicting Cantor's theorem [F5].

3.1step 1.1F1F2F5F7∎

Hence $P (N)$ is uncountable, and $N ≺ P (N)$ : the injection of step 1.1 gives $N ⪯ P (N)$ , while $N \approx P (N)$ would give a bijection $N \to P (N)$ and hence a surjection, contradicting [F5]; so not $N \approx P (N)$ and the strict relation holds by [F2]. No step selects an element from a nonempty family: the only objects named are ${n}$ , a fixed bijection, and its inverse.

Remarks

The argument is the statement of Cantor's theorem: $A ≺ P (A)$ in the "strictly larger" form $N ≺ P (N)$ instantiated at $N$ ; what is added here is the passage from "not at most countable" to the strict domination, which uses Schröder-Bernstein in the contrapositive direction as above.
Finiteness of $P (N)$ is impossible for the same reason: a bijection $P (N) \to m$ would compose with the inclusion $m \subseteq N$ to dominate $P (N)$ by $N$ , which step 2.1 rules out. No separate finite argument is needed.

ExampleConstruction: Literature-sourcedVerification: AI-generatedjudge pass (gpt-6.1-sol)Open item page →

The set of binary sequences is equinumerous with $P (N)$ , hence uncountable

Example

Let ${0, 1}^{N}$ be the set of all functions $N \to {0, 1}$ , where $0 = \emptyset$ and $1 = σ (0)$ (The set $B^{A}$ of all functions $A \to B$ , The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ ). The map $S \mapsto χ_{S}$ sending $S \subseteq N$ to its characteristic function, $χ_{S} (n) = 1$ for $n \in S$ and $χ_{S} (n) = 0$ for $n \notin S$ , is a bijection $P (N) \to {0, 1}^{N}$ (The power set $P (x) = {z : z \subseteq x}$ , Injection, surjection, bijection). Hence ${0, 1}^{N} \approx P (N)$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ) and the set of binary sequences is uncountable (Finite, countably infinite, countable, uncountable, $P (N)$ is uncountable). This is the function-space form of Cantor's diagonal argument, and it is the form in which the library records that infinite products of at-most-countable sets need not be at most countable. No choice principle is used.

Facts & Assumptions

Given: The von Neumann naturals $N$ with $0 = \emptyset$ and $1 = σ (0)$ (The natural numbers $N$ (von Neumann)), the unordered pair ${0, 1}$ (The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ ), and the set ${0, 1}^{N}$ of functions $N \to {0, 1}$ (The set $B^{A}$ of all functions $A \to B$ , For sets $A$ and $B$ the collection of all functions $A \to B$ is a set, being a subset of $P (A \times B)$ ). Membership in ${0, 1}$ is membership in $N$ : $t \in {0, 1}$ exactly when $t = 0$ or $t = 1$ .

[F1]

$1 \neq 0$ , since $1 = σ (0)$ and $σ (n) \neq 0$ for every $n \in N$ (The von Neumann naturals form a Peano system).

[F2]

Separation and set notation: for a set $X$ and a property, ${z \in X : φ (z)}$ is the set of elements of $X$ with that property (The Axiom Schema of Separation: for each formula $φ$ , $\forall \overset{ˉ}{p} \forall x \exists y \forall z (z \in y \leftrightarrow (z \in x \land φ (z, \overset{ˉ}{p})))$ ); $S \subseteq N$ means every element of $S$ is an element of $N$ , and $P (N) = {z : z \subseteq N}$ (Subset $x \subseteq y$ , proper subset $x ⊊ y$ , and the separation notation ${z \in x : φ (z)}$ , The power set $P (x) = {z : z \subseteq x}$ ).

[F3]

A function is a relation with a unique value at each point of its domain; $f : A \to B$ means $dom f = A$ and $ran f \subseteq B$ ; and two functions with the same domain and the same values are equal (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain, The Axiom of Extensionality: $\forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \to x = y)$ ). Ordered pairs are those of the Cartesian product $A \times B$ (The Cartesian product $A \times B : = {z \in P (P (A \cup B)) : \exists a \in A \exists b \in B z = (a, b)}$ ).

[F4]

Injection, surjection, bijection; images and preimages (Injection, surjection, bijection, The image $R [A]$ and the preimage $R^{- 1} [B]$ of a set under a relation).

[F5]

$A \approx B$ means a bijection $A \to B$ exists; $\approx$ is symmetric and transitive (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ); $A$ is finite when $A \approx n$ for some $n \in N$ , countably infinite when $A \approx N$ , at most countable when it is one of the two, and uncountable when it is not at most countable (Finite, countably infinite, countable, uncountable).

[F6]

$P (N)$ is uncountable ( $P (N)$ is uncountable).

Verification

technique · direct

1.1F2F3givenconstruct

For $S \subseteq N$ the set $χ_{S} : = {(n, v) \in N \times {0, 1} : (n \in S \land v = 1) \lor (n \notin S \land v = 0)}$ exists by Separation, and it is a function $N \to {0, 1}$ with $χ_{S} (n) = 1$ for $n \in S$ and $χ_{S} (n) = 0$ for $n \notin S$ . Indeed, for each $n \in N$ exactly one of $n \in S$ , $n \notin S$ holds, so exactly one value $v \in {0, 1}$ is related to $n$ , namely $1$ in the first case and $0$ in the second; and $0, 1 \in {0, 1}$ by the definition of the unordered pair.

2.1step 1.1F1F3

The assignment $S \mapsto χ_{S}$ is injective. If $χ_{S} = χ_{T}$ as sets of ordered pairs, then for every $n \in N$ one has $n \in S$ iff $χ_{S} (n) = 1$ iff $χ_{T} (n) = 1$ iff $n \in T$ : the outer equivalences are step 1.1, and in the middle, a function value that is not $1$ is $0$ , which differs from $1$ by [F1], so $χ_{T} (n) = 1$ holds exactly when $χ_{T} (n) \neq 0$ , that is exactly when $n \in T$ . Hence $S = T$ by Extensionality of sets.

2.2step 1.1F2F3

The assignment $S \mapsto χ_{S}$ is surjective. Let $f : N \to {0, 1}$ and put $S_{f} : = {n \in N : f (n) = 1}$ , a subset of $N$ by Separation. For each $n$ , either $f (n) = 1$ or $f (n) = 0$ because $f (n) \in {0, 1}$ ; in the first case $n \in S_{f}$ and step 1.1 gives $χ_{S_{f}} (n) = 1 = f (n)$ , and in the second case $n \notin S_{f}$ and $χ_{S_{f}} (n) = 0 = f (n)$ . Thus $χ_{S_{f}}$ and $f$ have the same domain $N$ and the same values, so they are equal by [F3], and $f$ is in the image of the assignment.

3.1step 2.1step 2.2F4F5

By steps 2.1 and 2.2 the characteristic-function map is a bijection $P (N) \to {0, 1}^{N}$ , so ${0, 1}^{N} \approx P (N)$ by [F5].

4.1step 3.1F5F6

The set ${0, 1}^{N}$ is uncountable. If it were at most countable, then ${0, 1}^{N} \approx m$ for some $m \in N$ or ${0, 1}^{N} \approx N$ by [F5]; symmetry and transitivity of $\approx$ with step 3.1 would give $P (N) \approx m$ or $P (N) \approx N$ , so $P (N)$ would be at most countable, contradicting [F6].

5.1step 3.1step 4.1∎

Therefore the binary sequences form a set equinumerous with $P (N)$ and are uncountable, as claimed. The only objects constructed are the characteristic functions, defined by an explicit formula from $S$ , and the set $S_{f}$ , separated from $N$ by the condition $f (n) = 1$ ; at no point is an element selected from a nonempty family of sets, so no choice principle is used.

Remarks

The construction is the function-space form of Cantor's diagonal argument: reading $S$ as a subset of $N$ and $s (n) = χ_{S} (n)$ as a binary sequence, the passage $S \mapsto χ_{S}$ identifies $P (N)$ with ${0, 1}^{N}$ , and the diagonal set of Cantor's theorem: $A ≺ P (A)$ reappears here as the sequence that flips every diagonal bit.
This example is the case $A = N$ of the fact that infinite products of at-most-countable sets need not be at most countable, in agreement with $P (N)$ is uncountable: the product is the power set in characteristic-function guise.

ExampleConstruction: Literature-sourcedVerification: AI-generatedjudge pass (gpt-6.1-sol)Open item page →

The rationals in an interval are countably infinite while the interval is uncountable

Example

Let $R$ be a complete ordered field (Complete ordered field (least-upper-bound property)), let $ε : Q \to R$ be the canonical embedding and write $Q_{R} = ε [Q]$ (The unique embedding of ℚ into an ordered field). For $a < b$ in $R$ put $S_{a, b} = {x \in Q_{R} : a < x < b}$ and $I_{a, b} = {x \in R : a < x < b}$ . Then

(i) $S_{a, b} \approx N$ : the rationals of any nondegenerate interval are countably infinite (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A ⪯ B$ );
(ii) $I_{a, b} ∖ Q_{R}$ is uncountable, although $S_{a, b}$ is an at most countable subset of $I_{a, b}$ that is dense in it (ℚ is dense in every Archimedean ordered field) and $I_{a, b}$ itself is uncountable (Every nondegenerate interval of $R$ is uncountable).

Cardinality and order-density are independent properties of a subset of $R$ . Both parts are theorems of ZF: the enumeration in (i) is built by a canonical least-index recursion, and (ii) interleaves two given enumerations.

Facts & Assumptions

Given: A complete ordered field $R$ (Complete ordered field (least-upper-bound property), Ordered field), reals $a < b$ , the canonical embedding $ε : Q \to R$ with $Q_{R} = ε [Q]$ (The unique embedding of ℚ into an ordered field), and the sets $S_{a, b} \subseteq I_{a, b}$ (The image $R [A]$ and the preimage $R^{- 1} [B]$ of a set under a relation, Subset $x \subseteq y$ , proper subset $x ⊊ y$ , and the separation notation ${z \in x : φ (z)}$ ).

[F1]

$R$ is Archimedean (Every complete ordered field is Archimedean, Archimedean ordered field), and $ε$ is injective, so $Q_{R} \approx Q$ and $Q \approx N$ (The unique embedding of ℚ into an ordered field, $Q$ is countably infinite, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[F2]

Density: for any $x < y$ in $R$ there is $q \in Q$ with $x < ε (q) < y$ (ℚ is dense in every Archimedean ordered field). Applied with $x : = a$ , $y : = b$ this gives $S_{a, b} \neq \emptyset$ , and applied to $x < y$ with $a \leq x < y \leq b$ it gives an element of $S_{a, b}$ between them, so $S_{a, b}$ is dense in $I_{a, b}$ .

[F3]

A subset of an at most countable set is at most countable (Every subset of an at most countable set is at most countable); a nonempty at most countable set is a surjective image of $N$ , and conversely a surjective image of $N$ is at most countable (A nonempty set is at most countable iff it is a surjective image of $N$ ).

[F4]

Well-ordering: every nonempty subset of $N$ has a least element (The well-ordering principle). Recursion: for a set $X$ , $x_{0} \in X$ and $F : X \to X$ there is $r : N \to X$ with $r (0) = x_{0}$ and $r (σ (n)) = F (r (n))$ (The recursion theorem). Induction holds on $N$ (The principle of mathematical induction), and $m < σ (n)$ exactly when $m \leq n$ (On $N$ the order is membership: $m < n ⟺ m \in n$ ). The inverse of a bijection is a bijection ( $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = Δ_{A}$ and $f \circ g = Δ_{B}$ ; such a $g$ is unique, equals the inverse relation $f^{- 1}$ , and is itself a bijection).

[F5]

Schröder-Bernstein: injections both ways give a bijection (The Schröder-Bernstein theorem); $A ⪯ B$ means an injection $A \to B$ exists (Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Injection, surjection, bijection).

[F6]

The open interval is uncountable: $I_{a, b}$ is not at most countable (Every nondegenerate interval of $R$ is uncountable, Finite, countably infinite, countable, uncountable).

[F7]

Set algebra: $x \in I_{a, b} ∖ Q_{R}$ exactly when $x \in I_{a, b}$ and $x \notin Q_{R}$ (The difference $a ∖ b$ , the symmetric difference $a △ b$ , and the complement $X ∖ a$ relative to a set $X$ ); $N \times N \approx N$ through the pairing of $N \times N \approx N$ , whose inverse is a bijection $N \to N \times N$ .

Verification

technique · direct

1.1F1F4

$Q_{R}$ is countably infinite. Since $ε$ is injective, it is a bijection of $Q$ onto its image $Q_{R}$ ; by [F1] there is a bijection $Q \to N$ , and composing its inverse with $ε$ exhibits a bijection $e : N \to Q_{R}$ . In particular $Q_{R}$ is at most countable.

2.1step 1.1F2F3

$S_{a, b}$ is at most countable, nonempty, and dense in $I_{a, b}$ . It is a subset of $Q_{R}$ , so [F3] applies; it is nonempty and dense by [F2].

2.2step 1.1F2F4

The step function $F$ is well defined on $I_{a, b}$ . Fix the bijection $e : N \to Q_{R}$ of step 1.1. For $x \in I_{a, b}$ the set ${k \in N : x < e (k) < b}$ is nonempty by [F2] applied to $x < b$ , and it is a subset of $N$ , so it has a least element $k (x)$ by [F4]; put $F (x) : = e (k (x))$ , a rational with $x < F (x) < b$ . Likewise ${k : a < e (k) < b}$ is nonempty by [F2] applied to $a < b$ , and its least element $k_{0}$ gives the seed $r_{0} : = e (k_{0}) \in S_{a, b}$ .

3.1step 2.2F4

The recursion $r (0) : = r_{0}$ , $r (σ (n)) : = F (r (n))$ produces a strictly increasing injection $r : N \to S_{a, b}$ . Since $F$ maps $I_{a, b}$ into itself — $x < F (x) < b$ and $a < x$ give $a < F (x)$ — the recursion theorem applies with $X = I_{a, b}$ by [F4], and $r (n) \in I_{a, b}$ for all $n$ . Moreover $r (n) < r (σ (n))$ for every $n$ by the defining property of $F$ , Inductively, $m < n$ implies $r (m) < r (n)$ : the case $n = 0$ is vacuous, and $m < σ (n)$ gives $m \leq n$ , so either $m = n$ and the adjacent inequality applies, or $m < n$ and transitivity combines the induction hypothesis with $r (n) < r (σ (n))$ . Distinct indices are comparable, hence $r$ is injective. Finally every value $r (n)$ lies in $Q_{R} \cap I_{a, b} = S_{a, b}$ .

3.2step 2.1F3F6F7

Part (ii): $C : = I_{a, b} ∖ Q_{R}$ is uncountable. Suppose $C$ were at most countable. If $C = \emptyset$ then $I_{a, b} = S_{a, b}$ is at most countable by step 2.1, contradicting [F6]. Otherwise $C \neq \emptyset$ , and then [F3] applies to $S_{a, b}$ and to $C$ , which are both nonempty at most countable — $S_{a, b}$ by step 2.1 — giving surjections $f, g : N \to S_{a, b}, C$ . Define $t : N \times N \to I_{a, b}$ by $t (0, k) : = f (k)$ and $t (σ (i), k) : = g (k)$ ; every element of $I_{a, b}$ lies in $S_{a, b}$ or in $C$ by [F7], so $t$ is onto. Composing $t$ with the bijection $N \to N \times N$ of [F7] gives a surjection $N \to I_{a, b}$ , so $I_{a, b}$ is at most countable by [F3], contradicting [F6]. Hence $C$ is uncountable.

4.1step 2.1step 3.1F3F4F5

Therefore $N ⪯ S_{a, b}$ via the injection $r$ , and [F3] supplies a surjection $h : N \to S_{a, b}$ since $S_{a, b}$ is nonempty and at most countable by step 2.1. The rule $x \mapsto \min {k : h (k) = x}$ is an injection $S_{a, b} \to N$ by [F4]: equal least indices have the same $h$ -value. Schröder-Bernstein therefore gives $S_{a, b} \approx N$ ; this is (i).

5.1step 2.1step 4.1step 3.2F6∎

Collecting: $S_{a, b} \approx N$ by step 4.1, so the rationals of the interval are countably infinite; $S_{a, b}$ is dense in $I_{a, b}$ by step 2.1; and $I_{a, b} ∖ Q_{R}$ is uncountable by step 3.2 while $I_{a, b}$ is uncountable by [F6]. The increasing injection $r$ is defined by least elements of nonempty sets of naturals and a single recursion, and the two surjections in the interleaving are given by the criterion, so no choice principle is used.

Remarks

The two halves separate the two notions the interval carries: order-density (every subinterval meets the set) and cardinality (the set may be far smaller than the interval). The rationals of $(a, b)$ provide the first with the smallest possible infinite cardinality the second admits, while their complement is uncountable.
The recursion chooses the least index of a rational strictly between the current point and $b$ , so the increasing sequence $r$ is canonical once $e$ is fixed; the seed is the least-indexed rational of the interval. This sequence witnesses infinitude; it does not enumerate $S_{a, b}$ , since every term is at least $r_{0}$ while density supplies rationals in $(a, r_{0})$ . Replacing "least" by "some" would silently use dependent choice, since the next rational depends on the current one.

ExampleConstruction: AI-adaptedVerification: AI-generatedOpen item page →

The complement of an at most countable set of reals is uncountable

Example

Let $C \subseteq R$ be at most countable (Finite, countably infinite, countable, uncountable). Then $R ∖ C$ is uncountable (Finite, countably infinite, countable, uncountable). In particular deleting finitely many reals, or all rationals, leaves an uncountable set (The irrationals are uncountable), even though the deleted set may be dense (ℚ is dense in every Archimedean ordered field). The proof is the two-set union argument and spends no choice principle — in contrast to the countable-union theorem on its parent page, which assumes the Axiom of Countable Choice for countable families.

Facts & Assumptions

Given: A complete ordered field $R$ (Complete ordered field (least-upper-bound property), Ordered field), the canonical embedding $ε : Q \to R$ (The unique embedding of ℚ into an ordered field), and an at most countable set $C \subseteq R$ (Subset $x \subseteq y$ , proper subset $x ⊊ y$ , and the separation notation ${z \in x : φ (z)}$ ).

[F1]

$A$ is at most countable when $A$ is finite or countably infinite, and uncountable when it is not at most countable (Finite, countably infinite, countable, uncountable); a nonempty at most countable set is a surjective image of $N$ , and a surjective image of $N$ is at most countable (A nonempty set is at most countable iff it is a surjective image of $N$ , Injection, surjection, bijection).

[F2]

$R$ admits no surjection from $N$ ; equivalently $R$ is uncountable ( $R$ is uncountable (Cantor's nested intervals, 1874), Finite, countably infinite, countable, uncountable).

[F3]

$x \in R ∖ C$ exactly when $x \in R$ and $x \notin C$ ; hence $R = C \cup (R ∖ C)$ , because every $x$ either lies in $C$ or does not (The difference $a ∖ b$ , the symmetric difference $a △ b$ , and the complement $X ∖ a$ relative to a set $X$ , The Axiom of Extensionality: $\forall x \forall y (\forall z (z \in x \leftrightarrow z \in y) \to x = y)$ ).

[F4]

The pairing of $N \times N \approx N$ gives a bijection $N \to N \times N$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Injection, surjection, bijection).

[F5]

The rationals embedded in $R$ are at most countable: $ε$ is injective and $Q \approx N$ (The unique embedding of ℚ into an ordered field, $Q$ is countably infinite). Since $R$ is complete, it is Archimedean (Every complete ordered field is Archimedean), so the embedded rationals are dense in $R$ (ℚ is dense in every Archimedean ordered field).

Verification

technique · direct

1.1F1F2F3

$R ∖ C$ is nonempty. If it were empty then $R \subseteq C$ by [F3], so $C = R$ and $R$ would be at most countable, contradicting [F2].

2.1step 1.1F1F2F3F4

Suppose, for contradiction, that $R ∖ C$ were at most countable. If $C = \emptyset$ then $R = R ∖ C$ is at most countable, contradicting [F2]; so $C \neq \emptyset$ . By step 1.1 the complement is nonempty too, so [F1] gives surjections $f : N \to C$ and $g : N \to R ∖ C$ . Define $t : N \times N \to R$ by $t (0, k) : = f (k)$ and $t (σ (i), k) : = g (k)$ . Every real lies in $C$ or in $R ∖ C$ by [F3], and such a real is $f (k)$ or $g (k)$ , hence a value of $t$ ; so $t$ is onto. Composing with the bijection $N \to N \times N$ of [F4] gives a surjection $N \to R$ , contradicting [F2]. Hence $R ∖ C$ is not at most countable, that is, it is uncountable.

3.1F5step 2.1

The special cases follow: if $C$ is finite then it is at most countable and $R ∖ C$ is uncountable; if $C$ is the set of embedded rationals then $R ∖ C$ is the set of irrationals, uncountable, and this agrees with The irrationals are uncountable; the deleted set may be dense, since the embedded rationals are dense by [F5], yet its complement is uncountable.

4.1step 2.1step 3.1F1∎

Therefore the complement of an at most countable subset of $R$ is uncountable. The argument instantiates at most two surjections existentially and uses the criterion A nonempty set is at most countable iff it is a surjective image of $N$ , whose own proof is choice-free, so no choice principle is used; this is why the result does not need the Axiom of Countable Choice that the countable-union theorem of this page assumes for general countable families.

Remarks

The two-set interleaving is the same device as in The rationals in an interval are countably infinite while the interval is uncountable: two given enumerations, one for each part, are combined into one surjection onto the union. Nothing about the structure of $C$ is used beyond its cardinality, so the statement applies verbatim to finite sets, to the rationals, and to any at most countable set of reals.
The contrast with Countable unions of at most countable sets, assuming ${A C}_{ω}$ is genuine and worth stating: that theorem assumes the Axiom of Countable Choice because it selects one surjection for each member of a countable family, whereas here the two surjections are finitely many and given, so the union of the two sets is handled by a single explicit pairing.

CounterexampleConstruction: AI-adaptedVerification: AI-generatedjudge pass (gpt-6.1-sol)Open item page →

A nonempty surjective image of $N$ need not be equinumerous with $N$

Statement refuted

Refuted claim: if $A \neq \emptyset$ and there is a surjection $N \to A$ , then $A \approx N$ (A nonempty set is at most countable iff it is a surjective image of $N$ , Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

The witness is $A = σ (0) = {0} = 1$ , the one-element set of the von Neumann naturals, with the constant map $c : N \to A$ , $c (n) = 0$ (The natural numbers $N$ (von Neumann), The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ , A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain). The map $c$ is surjective because $0 \in A$ , and $A$ is at most countable because it is finite: the identity is a bijection $A \to σ (0)$ ; but $A \approx̸ N$ , since $N$ is equinumerous with no natural number (The pigeonhole principle on $N$ , claim 4). So a nonempty at most countable set need not be countably infinite: the enumeration a surjection provides may repeat values, and here it must (Finite, countably infinite, countable, uncountable, Injection, surjection, bijection).

Facts & Assumptions

Given: The von Neumann naturals with $0 = \emptyset$ , $σ (n) = n \cup {n}$ (The natural numbers $N$ (von Neumann)), the set $A = σ (0) = {0}$ (The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ ), and the set $c = N \times {0}$ of ordered pairs (The Cartesian product $A \times B : = {z \in P (P (A \cup B)) : \exists a \in A \exists b \in B z = (a, b)}$ ).

[F1]

$A = {0}$ and $t \in A ⟺ t = 0$ (The natural numbers $N$ (von Neumann), The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ ).

[F2]

$c = N \times {0}$ is a function with $dom c = N$ and values in $A$ : a function from $X$ to $Y$ is a set of ordered pairs with domain $X$ whose range is contained in $Y$ (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain, The Cartesian product $A \times B : = {z \in P (P (A \cup B)) : \exists a \in A \exists b \in B z = (a, b)}$ ).

[F3]

$σ (0) \neq 0$ , so $1 : = σ (0)$ differs from $0$ (The von Neumann naturals form a Peano system).

[F4]

$N \approx̸ n$ for every $n \in N$ , in particular $N \approx̸ 1$ : claim 4 of The pigeonhole principle on $N$ .

[F5]

$A$ is finite when $A \approx n$ for some $n \in N$ , and at most countable when it is finite or countably infinite (Finite, countably infinite, countable, uncountable); $\approx$ is reflexive and transitive, and a surjection is a function whose image is the whole codomain (Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Injection, surjection, bijection).

Counterexample

technique · direct

1.1F1F5

$A \approx σ (0) = 1$ via the identity map of $A$ , so $A$ is finite and hence at most countable; also $A \neq \emptyset$ because $0 \in A$ by [F1].

1.2F1F2F5

The set $c = N \times {0}$ is a function $N \to A$ : every $n \in N$ is paired with the single value $0$ , so $c$ has domain $N$ , and its only value $0$ lies in $A$ by [F1]. It is surjective, since every element of $A$ is $0 = c (n)$ for every $n$ , for instance $n = 0$ .

2.1step 1.1F4F5

$A \approx̸ N$ : if there were a bijection $A \to N$ then transitivity of $\approx$ with step 1.1 would give $N \approx 1$ with $1 \in N$ , contradicting [F4].

3.1step 1.1step 1.2step 2.1F3∎

The refuted claim therefore fails: $A$ is nonempty and there is a surjection $N \to A$ by step 1.2, yet $A \approx̸ N$ by step 2.1; and $A$ is at most countable by step 1.1. Moreover the repeated value is forced: $c (0) = 0 = c (σ (0))$ while $0 \neq σ (0)$ by [F3], so $c$ is not injective and no choice of enumeration can make this function one-to-one.

Remarks

The point of the counterexample is the exact failure mode of the onto criterion A nonempty set is at most countable iff it is a surjective image of $N$ : a surjection from $N$ need not be injective, so the at-most-countable set it presents can be finite, and the criterion's converse direction (which produces an injection $A \to N$ by least preimages) is what actually recovers a bijection with $N$ when the set is infinite.
The same witness shows that "at most countable" is strictly weaker than "countably infinite" and that "there is a surjection from $N$ " does not by itself upgrade to equinumerosity with $N$ .

CounterexampleConstruction: AI-adaptedVerification: AI-generatedjudge pass (gpt-6.1-sol)Open item page →

The empty set is at most countable but no function from $N$ is onto it

Statement refuted

Refuted claim: every at most countable set is a surjective image of $N$ .

The witness is $\emptyset$ , which is finite, hence at most countable (Finite, countably infinite, countable, uncountable); but there is no function $N \to \emptyset$ at all (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain). So the hypothesis $A \neq \emptyset$ cannot be dropped from the forward direction of A nonempty set is at most countable iff it is a surjective image of $N$ : $\emptyset$ is at most countable, yet it has no surjection from $N$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Injection, surjection, bijection).

Facts & Assumptions

Given: The empty set $\emptyset$ (There is exactly one set with no elements, written $\emptyset$ ) and the naturals $N$ with $0 = \emptyset$ (The natural numbers $N$ (von Neumann)).

[F1]

$A$ is finite when $A \approx n$ for some $n \in N$ ; $0 = \emptyset$ , so $A \approx 0$ holds exactly when $A = \emptyset$ ; and finite sets are at most countable (Finite, countably infinite, countable, uncountable, The natural numbers $N$ (von Neumann), Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[F2]

A function from $X$ to $Y$ is a set $f$ of ordered pairs with $dom f = X$ and $ran f \subseteq Y$ ; equivalently $f \subseteq X \times Y$ with $dom f = X$ (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain, The Cartesian product $A \times B : = {z \in P (P (A \cup B)) : \exists a \in A \exists b \in B z = (a, b)}$ , Relation, $dom R$ , $ran R$ , $fld R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[F3]

The empty function is the empty set, and $\emptyset$ is a function with empty domain and empty range; it is a bijection $\emptyset \to \emptyset = 0$ (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain, Relation, $dom R$ , $ran R$ , $fld R$ , and the specialisations "relation from $A$ to $B$ " and "relation on $A$ ").

[F4]

A bijection is in particular a surjection, and an at most countable nonempty set has a surjection from $N$ by the onto criterion; the criterion as stated assumes $A \neq \emptyset$ (Injection, surjection, bijection, A nonempty set is at most countable iff it is a surjective image of $N$ ).

Counterexample

technique · direct

1.1F1F3

$\emptyset \approx 0$ via the empty function, so $\emptyset$ is finite and hence at most countable.

1.2F2given

No function $f : N \to \emptyset$ exists. If $f$ were one, then $f \subseteq N \times \emptyset$ ; the product $N \times \emptyset$ is empty, so $f = \emptyset$ and $dom f = \emptyset$ , which is not $N$ since $0 \in N$ while $\emptyset$ has no elements. Equivalently, a value $f (0)$ would have to be an element of $\emptyset$ .

2.1step 1.1step 1.2F4∎

Hence $\emptyset$ is at most countable by step 1.1 but no function, and in particular no surjection, maps $N$ onto it by step 1.2, so the refuted claim fails and the nonemptiness hypothesis in the forward direction of A nonempty set is at most countable iff it is a surjective image of $N$ cannot be dropped.

Remarks

The failure is not about repetition of values, as in A nonempty surjective image of $N$ need not be equinumerous with $N$ , but about totality: a function out of $N$ must assign a value to $0$ , and there is no value to assign. This is exactly the empty case that the onto criterion A nonempty set is at most countable iff it is a surjective image of $N$ separates out.

ExampleConstruction: AI-adaptedVerification: AI-generatedOpen item page →

An explicit enumeration of the rationals, with repetitions and then without them

Example

Writing $N$ from $0$ and $J_{0} (m, n) = 2^{m} (2 n + 1)$ for the bijection $N \times N \to N ∖ {0}$ of $N \times N \approx N$ , the map $J (m, n) = 2^{m} (2 n + 1) - 1,$ the composition of $J_{0}$ with the inverse of the successor bijection $σ : N \to N ∖ {0}$ , is a bijection $N \times N \to N$ (The von Neumann naturals form a Peano system, $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = Δ_{A}$ and $f \circ g = Δ_{B}$ ; such a $g$ is unique, equals the inverse relation $f^{- 1}$ , and is itself a bijection). For $n \in N$ decode $n$ twice, writing $J^{- 1} (n) = (u, c)$ and $J^{- 1} (u) = (a, b)$ , let $z (u) = [(a, b)]$ be the integer of the difference-pair construction of The integers as equivalence classes of pairs of naturals, write $\overline{k} : = [(k, 0)] \in Z$ for the image of $k \in N$ under the canonical embedding of The naturals embed in the integers, and put $q (n) = [(z (u), \overline{c + 1})] \in Q .$ This is a completely specified surjection $N \to Q$ with $q (0) = 0$ , $q (1) = 1$ , $q (2) = 0$ , $q (3) = - 1$ (The rationals as equivalence classes of pairs of integers). Its least-first-occurrence subsequence $j \mapsto q (e (j))$ is a bijection $N \to Q$ . No lowest-terms convention, no gcd, no choice from an infinite family and no unspecified enumeration is used.

Facts & Assumptions

Given: The naturals with $0 = \emptyset$ and successor $σ$ (The natural numbers $N$ (von Neumann)), the integers $Z = (N \times N) / \sim$ with classes $[(a, b)]$ (The integers as equivalence classes of pairs of naturals), the map $k \mapsto \overline{k} = [(k, 0)]$ of $N$ into $Z$ (The naturals embed in the integers), the rationals $Q$ as classes $[(p, v)]$ of pairs of integers with $v \neq 0$ (The rationals as equivalence classes of pairs of integers), and the pairing $J_{0} (m, n) = 2^{m} (2 n + 1)$ ( $N \times N \approx N$ ).

[F1]

$J_{0}$ is a bijection $N \times N \to N ∖ {0}$ and $σ$ is a bijection $N \to N ∖ {0}$ ; hence $σ^{- 1}$ exists, is a bijection, and $J (m, n) = 2^{m} (2 n + 1) - 1 = σ^{- 1} (J_{0} (m, n))$ is a bijection $N \times N \to N$ ( $N \times N \approx N$ , The von Neumann naturals form a Peano system, $f : A \to B$ is a bijection if and only if there is a function $g : B \to A$ with $g \circ f = Δ_{A}$ and $f \circ g = Δ_{B}$ ; such a $g$ is unique, equals the inverse relation $f^{- 1}$ , and is itself a bijection, Injection, surjection, bijection). In particular $J^{- 1} (n)$ is the unique pair with $J (J^{- 1} (n)) = n$ .

[F2]

Every integer is a class $[(a, b)]$ with $a, b \in N$ , since $Z$ is the quotient of $N \times N$ ; the class $[(0, 0)]$ is the zero of $Z$ (The integers as equivalence classes of pairs of naturals, Arithmetic on the integers).

[F3]

The map $k \mapsto \overline{k} : = [(k, 0)]$ is injective and preserves addition, multiplication and order; its image is exactly the set of nonnegative integers, so the integers $v > 0$ are exactly the $\overline{k}$ with $k \neq 0$ (The naturals embed in the integers).

[F4]

Every rational has a representative $(p, v)$ with $v > 0$ : if the second component is positive one takes it as it is, and otherwise $(p, v) \sim (- p, - v)$ has positive second component (Every rational has a positive-denominator representative). A class $[(p, v)]$ with $v \neq 0$ is a rational (The rationals as equivalence classes of pairs of integers).

[F5]

$[-]$ is a class: equal rationals have equal representatives up to the relation, so writing "the" class of a computed pair is legitimate (The rationals as equivalence classes of pairs of integers); and $Q$ contains an injective copy of $N$ : the composite $n \mapsto [(\overline{n}, 1)]$ of the embeddings $k \mapsto \overline{k}$ and $j (k) = [(k, 1)]$ is injective (The naturals embed in the integers, The integers embed in the rationals).

[F6]

Well-ordering: every nonempty subset of $N$ has a least element (The well-ordering principle); no injection $σ (t) \to t$ exists, so $N$ is not equinumerous with any natural number (The pigeonhole principle on $N$ ).

[F7]

A subset of $N$ that is bounded above by some $b \in N$ is finite, and an unbounded one is countably infinite, enumerated increasingly: there is a bijection $e : N \to S$ with $e (i) < e (j)$ whenever $i < j$ (Every subset of an at most countable set is at most countable). Here $m \leq b$ means $m \subseteq b$ , so a subset bounded above by $b$ is a subset of $σ (b)$ (On $N$ the order is membership: $m < n ⟺ m \in n$ ).

[F8]

$Q$ is countably infinite when $Q \approx N$ , and $A \approx B$ means a bijection exists (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ); a composite of bijections is a bijection, and a function with domain $N$ and a rule is defined by the rule (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain, Injection, surjection, bijection).

Verification

technique · direct

1.1F1

$J$ is a bijection $N \times N \to N$ : by [F1], $J = σ^{- 1} \circ J_{0}$ is a composite of the bijection $J_{0}$ with the bijection $σ^{- 1}$ , and $2^{m} (2 n + 1) - 1$ is exactly its value, $- 1$ being the value of $σ^{- 1}$ on $N ∖ {0}$ . Hence for every $n \in N$ the pair $J^{- 1} (n)$ is defined and unique, and same for iterated decoding.

2.1step 1.1F2F3F4

The map $q$ is a well-defined function $N \to Q$ with the displayed rule. For $n \in N$ , step 1.1 gives unique $u, c \in N$ with $J (u, c) = n$ , then unique $a, b$ with $J (a, b) = u$ , so $z (u) : = [(a, b)]$ is a well-defined integer by [F2]. Since $c + 1 = σ (c) \neq 0$ by [F1] and the embedding $k \mapsto \overline{k}$ is injective, $\overline{c + 1}$ is a nonzero integer, so $(z (u), \overline{c + 1})$ is a legitimate pair of integers with nonzero second component and $q (n) : = [(z (u), \overline{c + 1})]$ is a rational, the class being formed by The rationals as equivalence classes of pairs of integers; all clauses are given by formulas, so $q$ is a function.

2.2step 1.1F2F3

The first values: $J^{- 1} (0) = (0, 0)$ because $J (0, 0) = 2^{0} \cdot 1 - 1 = 0$ , so $q (0) = [(z (0), \overline{1})]$ where $z (0) = [(0, 0)] = 0$ and $\overline{1} = 1$ , giving $q (0) = 0$ . Next $J (1, 0) = 2 - 1 = 1$ , so $J^{- 1} (1) = (1, 0)$ and $z (1) = [(1, 0)] = 1$ , giving $q (1) = [(1, 1)] = 1$ . Next $J (0, 1) = 3 - 1 = 2$ , so $J^{- 1} (2) = (0, 1)$ , $z (0) = 0$ and $q (2) = [(0, \overline{2})] = 0$ . Next $J (2, 0) = 4 - 1 = 3$ , so $J^{- 1} (3) = (2, 0)$ , and $J^{- 1} (2) = (0, 1)$ gives $z (2) = [(0, 1)] = - 1$ , so $q (3) = [(- 1, \overline{1})] = - 1$ .

3.1step 1.1step 2.1F2F3F4

$q$ is surjective. Let $x \in Q$ . By [F4] fix a representative $(p, v)$ of $x$ with $v > 0$ ; by [F2] write $p = [(a, b)]$ with $a, b \in N$ ; by [F3] write $v = \overline{k}$ with $k \in N$ , and $k \neq 0$ because $v > 0 = \overline{0}$ and $k \mapsto \overline{k}$ preserves order. Then $k = σ (c)$ for some $c \in N$ (Every nonzero natural number is a successor), so $c + 1 = k$ . Put $u : = J (a, b)$ and $n : = J (u, c)$ ; then $J^{- 1} (n) = (u, c)$ and $J^{- 1} (u) = (a, b)$ , so $z (u) = [(a, b)] = p$ and $q (n) = [(p, \overline{c + 1})] = [(p, v)] = x$ . Hence every rational is a value of $q$ .

4.1step 3.1F5F6

Let $M : = {n \in N : for all k < n, q (k) \neq q (n)}$ , the set of first occurrences of values of $q$ , a subset of $N$ by Separation. Then $M$ is infinite. Indeed, by [F5] the map $f (i) : = [(\overline{i}, 1)]$ is an injection $N \to Q$ ; for each $i$ the set $A_{i} : = {n \in N : q (n) = f (i)}$ is nonempty by step 3.1 and has a least element $m_{i}$ by [F6]. Each $m_{i}$ lies in $M$ , since for $k < m_{i}$ minimality gives $q (k) \neq f (i) = q (m_{i})$ ; and $i \mapsto m_{i}$ is injective because $f$ is. An injection $N \to M$ rules out $M \approx t$ for any $t \in N$ : composing it with a bijection $M \to t$ would be an injection $N \to t$ , whose restriction to $σ (t)$ would be an injection $σ (t) \to t$ , which [F6] forbids.

5.1step 4.1F7

$M$ is unbounded in $N$ . If $M$ were bounded above by some $b \in N$ , then $M \subseteq σ (b)$ by [F7] and $M$ would be finite by [F7], contradicting step 4.1.

6.1step 5.1F7

By step 5.1 and [F7] there is an increasing bijection $e : N \to M$ : it is the increasing enumeration of the unbounded set $M$ , with $e (i) < e (j)$ whenever $i < j$ .

7.1step 6.1

The composite $j \mapsto q (e (j))$ is injective. If $i < j$ then $e (i) < e (j)$ by step 6.1, and $e (j) \in M$ means $q (k) \neq q (e (j))$ for every $k < e (j)$ ; taking $k = e (i)$ gives $q (e (i)) \neq q (e (j))$ .

7.2step 3.1step 6.1F6

The composite $j \mapsto q (e (j))$ is surjective. Let $x \in Q$ ; by step 3.1 there is $n$ with $q (n) = x$ , and $k : = \min {n : q (n) = x}$ exists by [F6]. Then $k \in M$ , because any $k^{'} < k$ has $q (k^{'}) \neq x = q (k)$ by minimality, and $e$ is onto $M$ by step 6.1, so $k = e (j)$ for some $j$ and $x = q (k) = q (e (j))$ .

8.1step 7.1step 7.2F8∎

Therefore $j \mapsto q (e (j))$ is a bijection $N \to Q$ by steps 7.1 and 7.2, so $Q \approx N$ and $Q$ is countably infinite by [F8]. Every object was built by an explicit formula — the pairing $J$ , the decoded pairs, the classes, the least elements and the increasing enumeration of $M$ — so no choice principle is used.

Remarks

The two stages are visible in the two constructions: $q$ is an explicit enumeration with repetitions, and $M$ records the positions at which a value genuinely appears for the first time, so that $q \circ e$ is the same enumeration with repetitions deleted. The deletion uses the least element of a nonempty set of naturals at each stage, never an arbitrary choice.
The numerator $z (u)$ is not reduced with respect to the denominator, and no gcd is introduced anywhere: representatives are used as they come out of the difference-pair construction of $Z$ and the positive-denominator form of $Q$ . This is all the enumeration needs.

LemmaStatement: Literature-sourcedProof: AI-generatedOpen item page →

A real coefficient list of degree d has at most d real roots

Statement

Let $d \in N$ and let $a_{0}, a_{1}, \dots, a_{d}$ be real numbers with $a_{d} \neq 0$ (Complete ordered field (least-upper-bound property)). Using the finite sums of Finite sums and finite products, by recursion and the natural powers $x^{k}$ of Integer powers $a^{m}$ , put

$P (x) = \sum_{k = 0}^{d} a_{k} x^{k} (x \in R),$

the list always being read as the sequence that is $a_{k}$ for $k \leq d$ and $0$ for $k > d$ . Let $Z = Z (P) = {x \in R : P (x) = 0}$ . Then $Z$ is finite of cardinality at most $d$ : there is $m \in N$ with $m \leq d$ and $Z \approx m$ (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ). For $d = 0$ this says $Z = \emptyset$ .

This is a statement about finite coefficient lists and their evaluations: it requires neither a polynomial-ring construction nor any choice axiom. Only field arithmetic, finite sums and induction are used, and if $Z \neq \emptyset$ one single root is instantiated existentially, never a family of choices. It is the local prerequisite for the algebraic-number example on this page.

Facts & Assumptions

Given: A natural number $d$ , reals $a_{0}, \dots, a_{d}$ with $a_{d} \neq 0$ , and the sequence $c$ with $c_{k} = a_{k}$ for $k < σ (d)$ and $c_{k} = 0$ otherwise; $R$ is the complete ordered field (Complete ordered field (least-upper-bound property), Ordered field, Field), with finite sums $\sum_{k < n}$ as in Finite sums and finite products, by recursion and powers as in Integer powers $a^{m}$ . We prove, by strong induction on $d$ , the claim

$C (d) : for every list a_{0}, \dots, a_{d} with a_{d} \neq 0, there is m \in N, m \leq d, with Z \approx m .$

[F1]

Field arithmetic: $a b = 0$ implies $a = 0$ or $b = 0$ (A field has no zero divisors: $a b = 0 \Rightarrow a = 0$ or $b = 0$ ); $0 \cdot a = 0$ (Multiplication by zero: $0 \cdot a = 0$ ); addition, subtraction and multiplication obey the usual distributivity and associativity laws, and $a - b = 0$ implies $a = b$ .

[F2]

Finite sums (Finite sums and finite products, by recursion): $\sum_{k < 0} u_{k} = 0$ , $\sum_{k < σ (n)} u_{k} = \sum_{k < n} u_{k} + u_{n}$ , and a general block is $\sum_{k = m}^{n} u_{k} = \sum_{j < d^{'}} u_{m + j}$ for $d^{'} = n + 1 - m$ , the empty block being $0$ . Powers: $x^{0} = 1$ and $x^{n + 1} = x^{n} \cdot x$ .

[F3]

Finite sum laws (Laws of finite sums and finite products): additivity $\sum_{k < n} (u_{k} + v_{k}) = \sum_{k < n} u_{k} + \sum_{k < n} v_{k}$ , scaling $\sum_{k < n} λ u_{k} = λ \sum_{k < n} u_{k}$ , splitting $\sum_{k < n} u_{k} = \sum_{k < m} u_{k} + \sum_{k = m}^{n - 1} u_{k}$ for $m \leq n$ , and products of sums in $x$ distribute over addition in the standard way used below.

[F4]

Strong induction (Strong (complete) induction).

[F5]

Naturals (The natural numbers $N$ (von Neumann), Addition of natural numbers, Order on the natural numbers, On $N$ the order is membership: $m < n ⟺ m \in n$ , Discreteness: $σ (n)$ is the immediate successor, Every natural number is a transitive set and is not a member of itself, $\leq$ is a linear order on $N$ ): $σ (j) = j \cup {j}$ ; $m < n ⟺ m \in n$ and $n = {m \in N : m < n}$ ; $m \leq n ⟺ m \subseteq n$ ; $m < n ⟺ σ (m) \leq n$ ; $j < σ (j)$ ; $m \notin m$ ; $\leq$ is reflexive, antisymmetric and transitive, so $\leq$ composes and $m^{''} \leq m^{'} \leq e$ gives $m^{''} \leq e$ ; and $m \leq e$ gives $σ (m) \leq σ (e)$ , because $m + k = e$ implies $σ (m) + k = σ (m + k) = σ (e)$ .

[F6]

Finite sets and cardinality (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Injection, surjection, bijection): $A$ is finite when $A \approx n$ for some $n \in N$ ; $\approx$ is symmetric and transitive; the restriction of a bijection to a subset is a bijection onto the image of that subset; and $\emptyset \approx 0$ .

[F7]

Set notation (Subset $x \subseteq y$ , proper subset $x ⊊ y$ , and the separation notation ${z \in x : φ (z)}$ , The difference $a ∖ b$ , the symmetric difference $a △ b$ , and the complement $X ∖ a$ relative to a set $X$ ): $u \in S ∖ T$ exactly when $u \in S$ and $u \notin T$ , and $S \subseteq T$ means every element of $S$ lies in $T$ .

Proof

technique · induction

1.1F4F5F6F7

Subsets of a natural number, with a cardinal bound. For every $m \in N$ and every $S \subseteq m$ there is $m^{''} \in N$ with $m^{''} \leq m$ and $S \approx m^{''}$ . By strong induction on $m$ : for $m = 0$ we have $S \subseteq \emptyset$ , so $S = \emptyset \approx 0$ and $0 \leq 0$ . For $m = σ (j)$ , assume the claim for every $j^{'} < m$ and let $S \subseteq σ (j) = j \cup {j}$ . If $j \notin S$ then $S \subseteq j$ , so the hypothesis at $j$ gives $m^{''} \leq j$ with $S \approx m^{''}$ , and $m^{''} \leq j < σ (j) = m$ composes to $m^{''} \leq m$ . If $j \in S$ , then $T : = S ∖ {j} \subseteq j$ , so the hypothesis at $j$ gives $m^{''} \leq j$ and a bijection $u : T \to m^{''}$ . Extend $u$ to $u^{'} : S \to σ (m^{''})$ by $u^{'} (j) = m^{''}$ and $u^{'} (s) = u (s)$ for $s \neq j$ : the values of $u$ all lie in $m^{''}$ while $m^{''} \notin m^{''}$ , so $m^{''}$ is a new value and the extension is injective, and it is onto $m^{''} \cup {m^{''}} = σ (m^{''})$ , so $S \approx σ (m^{''})$ ; moreover $m^{''} \leq j$ gives $σ (m^{''}) \leq σ (j) = m$ . In both cases $S$ has the required cardinal bound, so the claim holds by strong induction.

1.2F1F2F6base

Base case $C (0)$ . Let $a_{0} \neq 0$ . Since $x^{0} = 1$ , the recursion for finite sums gives $\sum_{k < 1} c_{k} x^{k} = \sum_{k < 0} c_{k} x^{k} + c_{0} x^{0} = 0 + a_{0} = a_{0}$ for every $x$ , and $a_{0} \neq 0$ . Hence $Z = \emptyset \approx 0$ with $0 \leq 0$ , which is $C (0)$ .

1.3F1F2F3

The divided coefficients. Assume now $d = σ (e)$ , so $d \geq 1$ , and fix $r \in Z$ , so that $P (r) = 0$ ; write $b_{m} : = \sum_{j = 0}^{e - m} a_{m + 1 + j} r^{j}$ for $m < d$ , a finite sum of reals, and $Q (x) : = \sum_{m < d} b_{m} x^{m}$ . Then (i) $b_{d - 1} = b_{e} = \sum_{j = 0}^{0} a_{e + 1 + j} r^{j} = a_{d} r^{0} = a_{d} \neq 0$ ; and (ii) for $1 \leq k \leq e$ , splitting the sum $b_{k - 1} = \sum_{j = 0}^{e - k + 1} a_{k + j} r^{j} = a_{k} + \sum_{j = 1}^{e - k + 1} a_{k + j} r^{j} = a_{k} + r \sum_{i = 0}^{e - k} a_{k + 1 + i} r^{i} = a_{k} + r b_{k}$ , using scaling and the definition of the block sums. So $Q$ is again of the displayed form, with an explicit coefficient list of degree $e$ whose top coefficient $b_{e} = a_{d}$ is nonzero.

2.1step 1.3F1F2F3

The constant term. Scaling (ii) of step 1.3 by $r$ or, directly from the definition, $r b_{0} = \sum_{j = 0}^{e} r a_{1 + j} r^{j} = \sum_{j = 0}^{e} a_{1 + j} r^{j + 1} = \sum_{k = 1}^{d} a_{k} r^{k}$ . Adding $a_{0}$ and using the splitting of $\sum_{k < d + 1}$ at $k = 1$ gives $a_{0} + r b_{0} = \sum_{k = 0}^{d} a_{k} r^{k} = P (r) = 0$ , that is $r b_{0} = - a_{0}$ .

2.2step 1.3F4ih

Induction hypothesis for $Q$ . The coefficient list $b_{0}, \dots, b_{e}$ has $b_{e} = a_{d} \neq 0$ by step 1.3, so the strong induction hypothesis $C (e)$ at $e < d$ applies to it: the zero set $W : = {x \in R : Q (x) = 0}$ satisfies $W \approx m^{'}$ for some $m^{'} \in N$ with $m^{'} \leq e = d - 1$ .

3.1step 1.3step 2.1F1F2F3

The factorisation $P (x) = (x - r) Q (x)$ . Because $d = σ (e) = e + 1$ , splitting each sum at its last index gives $\sum_{m < d} b_{m} x^{m + 1} = \sum_{m < e} b_{m} x^{m + 1} + b_{e} x^{e + 1}$ and $\sum_{m < d} r b_{m} x^{m} = r b_{0} + \sum_{m = 1}^{e} r b_{m} x^{m}$ . Therefore, by scaling, additivity and subtraction, $(x - r) Q (x) = b_{e} x^{d} + \sum_{m < e} b_{m} x^{m + 1} - r b_{0} - \sum_{m = 1}^{e} r b_{m} x^{m}$ . Replacing $m$ by $m - 1$ in the first trailing block, $\sum_{m < e} b_{m} x^{m + 1} = \sum_{m = 1}^{e} b_{m - 1} x^{m}$ , so the two trailing blocks combine into $\sum_{m = 1}^{e} (b_{m - 1} - r b_{m}) x^{m} = \sum_{m = 1}^{e} a_{m} x^{m}$ by step 1.3(ii); and $b_{e} = a_{d}$ by step 1.3(i) while $r b_{0} = - a_{0}$ by step 2.1. Hence $(x - r) Q (x) = a_{d} x^{d} + \sum_{m = 1}^{e} a_{m} x^{m} + a_{0} = \sum_{k = 0}^{d} a_{k} x^{k} = P (x)$ , again by splitting.

4.1step 3.1F1F7

Every root of $P$ other than $r$ is a root of $Q$ . If $x \in Z$ and $x \neq r$ , then $(x - r) Q (x) = P (x) = 0$ by step 3.1, and $x - r \neq 0$ , so $Q (x) = 0$ by [F1]. Hence $x \in W$ , i.e. $Z ∖ {r} \subseteq W$ .

5.1step 4.1F7

$Z$ sits in $W$ together with possibly $r$ . By step 4.1, every $x \in Z$ either equals $r$ or lies in $W$ ; that is, $Z \subseteq {r} \cup W$ .

6.1step 1.1step 2.2step 5.1F5F6

Case $r \in W$ . Then ${r} \cup W = W$ , so $Z \subseteq W$ by step 5.1. Transport along a bijection $u : W \to m^{'}$ from step 2.2: the image $u [Z] \subseteq m^{'}$ satisfies $u [Z] \approx Z$ by restriction of $u$ , and step 1.1 applied to $u [Z] \subseteq m^{'}$ gives $m^{''} \leq m^{'}$ with $u [Z] \approx m^{''}$ ; then $Z \approx m^{''}$ by transitivity, and $m^{''} \leq m^{'} \leq e = d - 1 < d$ , so $m^{''} \leq d$ .

6.2step 1.1step 2.2step 5.1F5F6F7

Case $r \notin W$ . Extend a bijection $u : W \to m^{'}$ from step 2.2 to $u^{'} : W \cup {r} \to σ (m^{'})$ by $u^{'} (r) = m^{'}$ and $u^{'} (w) = u (w)$ for $w \in W$ : the values of $u$ all lie in $m^{'}$ while $m^{'} \notin m^{'}$ , so $u^{'}$ is injective, and it is onto $m^{'} \cup {m^{'}} = σ (m^{'})$ . Hence $W \cup {r} \approx σ (m^{'})$ , and $Z \subseteq {r} \cup W = W \cup {r}$ by step 5.1; restriction of $u^{'}$ to $Z$ gives $Z \approx u^{'} [Z]$ with $u^{'} [Z] \subseteq σ (m^{'})$ , and step 1.1 applied at $σ (m^{'})$ gives $m^{''} \leq σ (m^{'})$ with $u^{'} [Z] \approx m^{''}$ , so $Z \approx m^{''}$ ; finally $m^{'} \leq e$ gives $σ (m^{'}) \leq σ (e) = d$ by [F5], so $m^{''} \leq d$ .

7.1step 6.1step 6.2

Since $r \in W$ or $r \notin W$ , steps 6.1 and 6.2 give: for the fixed $r \in Z$ there is $m \in N$ with $m \leq d$ and $Z \approx m$ .

8.1step 7.1F6

The induction step $C (e) \Rightarrow C (d)$ . Let $d = σ (e)$ and let $a_{0}, \dots, a_{d}$ with $a_{d} \neq 0$ be a list, with zero set $Z$ . If $Z = \emptyset$ then $Z \approx 0$ and $0 \leq d$ , so $C (d)$ holds for this list. Otherwise $Z \neq \emptyset$ ; instantiating one $r \in Z$ existentially, the construction of steps 1.3 through 7.1 produces $m \leq d$ with $Z \approx m$ . In both cases $C (d)$ holds.

9.1step 1.2step 8.1F4discharge-induction: base step 1.2 and induction step 8.1∎

Conclusion. $C (0)$ is step 1.2, and $C (e) \Rightarrow C (σ (e))$ for every $e$ is step 8.1, so by strong induction $C (d)$ holds for every $d$ ; applied to the given list, the zero set $Z$ of $P$ is finite of cardinality at most $d$ , as claimed. If $d = 0$ the hypothesis $a_{d} \neq 0$ reads $a_{0} \neq 0$ and step 1.2 gives $Z = \emptyset$ . No step selects from a family: at most one root is instantiated, and all coefficients $b_{m}$ are given by explicit finite sums.

Remarks

The division is honest synthetic division. Writing the coefficients from the top down, $b_{e} = a_{d}$ and $b_{k - 1} = a_{k} + r b_{k}$ , the identity $(x - r) Q (x) = P (x)$ with $Q (x) = \sum_{m < d} b_{m} x^{m}$ holds for every $x$ , not only at $x = r$ , and the case $r = 0$ needs no division: step 2.1 uses only multiplication by $r$ .
The final count is explicit rather than decreed. Step 1.1 shows by induction that a subset of a natural number $m$ is equinumerous with some $m^{''} \leq m$ , which is exactly what the two case counts in steps 6.1 and 6.2 consume; no separate appeal to a counting principle is needed.

ExampleConstruction: Literature-sourcedVerification: AI-generatedjudge pass (gpt-6.1-sol)Open item page →

Real algebraic numbers are countably infinite, without choice

Example

Call $x \in R$ real algebraic when

$P (x) = \sum_{k = 0}^{d} a_{k} x^{k} = 0$

for some $d \in N$ and some finite list of integers $a_{0}, \dots, a_{d}$ with $a_{d} \neq 0$ , the integers being embedded in $R$ along $Z \to Q \to R$ (The integers as equivalence classes of pairs of naturals, The rationals as equivalence classes of pairs of integers, The integers embed in the rationals, The unique embedding of ℚ into an ordered field, Finite sums and finite products, by recursion, Integer powers $a^{m}$ ). Let $A$ be the set of real algebraic numbers. Then:

(i) $A$ is countably infinite; an injection $A \to N$ is specified below by the least integer-code of a coefficient list having $x$ as a root, paired with the position of $x$ in the increasing listing of that list's finite real root set;
(ii) every rational number, embedded in $R$ , lies in $A$ ;
(iii) $R ∖ A$ is uncountable.

All of this is a theorem of ZF: the coding of valid coefficient lists is an explicit surjection, the least code and the increasing root listing are canonical, and the only enumerations used in (iii) are two existentially given surjections. No claim about algebraic closures or complex algebraic numbers is made; the ambient field here is $R$ .

Facts & Assumptions

Given: $R$ a complete ordered field (Complete ordered field (least-upper-bound property), Ordered field, Field); the integers $Z = (N \times N) / \sim$ and the rationals $Q$ (The integers as equivalence classes of pairs of naturals, The rationals as equivalence classes of pairs of integers); the embedding $\overline{k} : = [(k, 0)]$ of $N$ in $Z$ (The naturals embed in the integers), the embedding $j : Z \to Q$ (The integers embed in the rationals) and the unique injective order-preserving field homomorphism $ε : Q \to R$ (The unique embedding of ℚ into an ordered field). Write $a^{*} : = ε (j (a)) \in R$ for the image of $a \in Z$ .

[F1]

The coding: $J (m, n) = 2^{m} (2 n + 1) - 1$ is a bijection $N \times N \to N$ , and $z : N \to Z$ , $z (u) = [(a, b)]$ where $(a, b) = J^{- 1} (u)$ , is a surjection onto $Z$ ; both are given by explicit formulas (An explicit enumeration of the rationals, with repetitions and then without them, $N \times N \approx N$ , The integers as equivalence classes of pairs of naturals, Injection, surjection, bijection).

[F2]

Decoding: for $n \in N$ write $J^{- 1} (n) = (d, s)$ ; the recursion theorem gives the unique $T : N \to N$ with $T (0) = s$ and $T (σ (k)) = π_{2} (J^{- 1} (T (k)))$ , and with $U (k) : = π_{1} (J^{- 1} (T (k)))$ the decoded coefficients are $a_{k} : = z (U (k))$ for $k \leq d$ (The recursion theorem, A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain). The fallback is used when $a_{d} = 0$ : the code then denotes the constant list $(1)$ , whose polynomial has no zeros. This decoding is total: every $n$ produces a list $a_{0}, \dots, a_{d}$ (The Axiom Schema of Separation: for each formula $φ$ , $\forall \overset{ˉ}{p} \forall x \exists y \forall z (z \in y \leftrightarrow (z \in x \land φ (z, \overset{ˉ}{p})))$ , The Axiom Schema of Replacement: for each formula $φ$ , if $φ$ defines a class function on $A$ then its image on $A$ is a set for the sets of decoded values).

[F3]

The local root bound: for $d \in N$ and reals $b_{0}, \dots, b_{d}$ with $b_{d} \neq 0$ , the zero set ${x \in R : \sum_{k = 0}^{d} b_{k} x^{k} = 0}$ is finite of cardinality at most $d$ (A real coefficient list of degree d has at most d real roots).

[F4]

Finite subsets and listings: every nonempty finite subset of $R$ has a maximum and a minimum (The nonempty finite subsets of $R$ are exactly the listable ones); a subset of an at most countable set is at most countable (Every subset of an at most countable set is at most countable); the order of $R$ is a linear order, so it is total, antisymmetric and transitive (Ordered field, Complete ordered field (least-upper-bound property)).

[F5]

Cardinality language: $S \approx t$ means a bijection $S \to t$ exists, and $\approx$ is symmetric and transitive; a set is finite when it is equinumerous with some natural number, countably infinite when it is equinumerous with $N$ , and at most countable when it is one of the two (Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Finite, countably infinite, countable, uncountable); a finite set is equinumerous with exactly one natural number (The pigeonhole principle on $N$ , claim 3); $σ$ is injective (The von Neumann naturals form a Peano system); and $n \notin n$ for every $n \in N$ (Every natural number is a transitive set and is not a member of itself).

[F6]

For a nonempty set $S$ : $S$ is at most countable if and only if there is a surjection $N \to S$ (A nonempty set is at most countable iff it is a surjective image of $N$ ); and if $S_{1} ⪯ S_{2}$ and $S_{2} ⪯ S_{1}$ then $S_{1} \approx S_{2}$ (The Schröder-Bernstein theorem, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ). $R$ admits no surjection from $N$ ( $R$ is uncountable (Cantor's nested intervals, 1874)).

[F7]

Field arithmetic of the embeddings: $ε$ is a field homomorphism, so $ε (u + v) = ε (u) + ε (v)$ , $ε (u v) = ε (u) ε (v)$ , $ε (0) = 0$ , $ε (1) = 1$ , and it is injective; the operations on $Q$ are well defined on classes, and for a representative $(p, v)$ of a rational $q$ one has $v \cdot q = p$ in $Q$ (The unique embedding of ℚ into an ordered field, Arithmetic on the rationals, Rational arithmetic is well defined, The rationals as equivalence classes of pairs of integers, Field).

[F8]

Well-ordering: every nonempty subset of $N$ has a least element (The well-ordering principle); and every $n \neq 0$ is $σ (m)$ for some $m$ (Every nonzero natural number is a successor). Induction is The principle of mathematical induction; the successor map is an order-preserving bijection from $m$ onto $σ (m) ∖ {0}$ by On $N$ the order is membership: $m < n ⟺ m \in n$ and the Peano properties in [F5].

Verification

technique · direct

1.1F1F2

The decoding is total and assigns to every $n$ a finite list of integers. For $n$ , [F2] gives $d, s \in N$ with $J^{- 1} (n) = (d, s)$ and the sequences $T, U$ ; then $a_{k} = z (U (k))$ is an integer for each $k \leq d$ , so $(a_{0}, \dots, a_{d})$ is a finite integer list. Define $P_{n} (x) : = \sum_{k = 0}^{d} a_{k}^{*} x^{k}$ when $a_{d} \neq 0$ , and $P_{n} (x) : = 1$ when $a_{d} = 0$ ; in both cases $P_{n} : R \to R$ is given by a finite sum of real powers, and $R_{n} : = {x \in R : P_{n} (x) = 0}$ is a set by Separation. Finally $A : = {x \in R : P_{n} (x) = 0 for some n \in N}$ is a set by Separation; every element of this set is real algebraic, since a fallback code has no roots. The converse follows from the coefficient coding below.

1.2F4F5F8

Unique increasing listings. For every finite $S \subseteq R$ and its unique $m \in N$ with $S \approx m$ , there is exactly one increasing bijection $ℓ : m \to S$ . Prove this by induction on $m$ . At $m = 0$ , $S = \emptyset$ and the empty function is the unique listing. At $m = σ (m^{'})$ , let $s = \min S$ , which exists by [F4]. Transport $T = S ∖ {s}$ into a subset of $m$ using a bijection $S \to m$ ; [F4] makes $T$ finite, say $T \approx m^{''}$ . Extending a bijection $T \to m^{''}$ by $s \mapsto m^{''}$ gives $S \approx σ (m^{''})$ , because $m^{''} \notin m^{''}$ . Uniqueness of finite cardinality and successor injectivity give $m^{''} = m^{'}$ by [F5]. The induction hypothesis, including the empty case, gives an increasing bijection $ℓ^{'} : m^{'} \to T$ . Define $ℓ (0) = s$ and $ℓ (σ (i)) = ℓ^{'} (i)$ for $i \in m^{'}$ . By [F8] these clauses cover $σ (m^{'})$ ; they give a bijection and preserve order because $s$ is strictly below every member of $T$ and successor preserves the index order. For uniqueness, any increasing bijection sends $0$ to $\min S$ ; deleting this value gives an increasing bijection $m^{'} \to T$ , unique by the induction hypothesis.

2.1step 1.1F1F2F8

Every valid list is coded. Given integers $a_{0}, \dots, a_{d}$ with $a_{d} \neq 0$ , define $u_{k} : = \min {u \in N : z (u) = a_{k}}$ for each $k \leq d$ . These sets are nonempty by [F1], and [F8] supplies unique least values, so the finite function $k \mapsto u_{k}$ is defined without choice. Form $t_{d + 1} = 0$ and $t_{k} = J (u_{k}, t_{k + 1})$ backwards for $k = d, \dots, 0$ . To justify this finite recursion with a total self-map, carry a counter $j$ and an accumulator $v$ , start at $(0, 0)$ , and send $(j, v)$ to $(σ (j), J (u_{d - j}, v))$ when $j \leq d$ , leaving the state fixed when $j > d$ . Recursion on $N \times N$ yields $(d + 1, t_{0})$ after $d + 1$ steps. Put $n = J (d, t_{0})$ . Induction on $k \leq d$ gives $T (k) = t_{k}$ and $U (k) = u_{k}$ , so code $n$ has exactly the coefficients $a_{k} = z (u_{k})$ and does not use the fallback. Thus every valid integer list occurs. Together with step 1.1 this identifies $A$ with the set of real algebraic numbers. The encoding is generally many-to-one, since different tails or integer representatives can decode to the same list.

2.2step 1.1F3F7

For every $n \in N$ the root set $R_{n}$ is finite, and if the decoded list has $a_{d} \neq 0$ then $R_{n}$ is equinumerous with some $m \leq d$ . In the fallback case $a_{d} = 0$ we have $P_{n} = 1$ and $R_{n} = \emptyset$ . Otherwise $a_{d}^{*} \neq 0$ , since the composite embedding $Z \to Q \to R$ is injective and $a_{d} \neq 0$ ; the polynomial $P_{n}$ is exactly the evaluation of the real coefficient list $a_{0}^{*}, \dots, a_{d}^{*}$ with nonzero top coefficient, so [F3] applies and $R_{n}$ is finite of cardinality at most $d$ .

3.1step 1.2step 2.2F1F4F5F8

$A$ is at most countable. Every $x \in A$ lies in $R_{n}$ for some $n$ , so the least such $n$ exists by [F8]; write $n (x) : = \min {n : P_{n} (x) = 0}$ . Then $R_{n (x)}$ is finite by step 2.2 and nonempty, say $R_{n (x)} \approx m$ with $m \in N$ , and by step 1.2 it has a unique increasing listing $ℓ_{n (x)} : m \to R_{n (x)}$ ; define $j (x) : = ℓ_{n (x)}^{- 1} (x) \in m \subseteq N$ , the position of $x$ in that listing. Define $φ (x) : = J (n (x), j (x)) \in N$ . Then $φ$ is injective: if $φ (x) = φ (x^{'})$ , injectivity of $J$ gives $n (x) = n (x^{'}) = : n$ and $j (x) = j (x^{'}) = : i$ , and both $x$ and $x^{'}$ are the value $ℓ_{n} (i)$ of the same unique listing. Hence $φ$ is a bijection of $A$ onto the subset $φ [A] \subseteq N$ , and every subset of $N$ is at most countable by [F4], so $A$ is at most countable.

3.2step 2.1F7

Every embedded rational lies in $A$ . Let $q \in Q$ and fix a representative $(p, v)$ with $v \neq 0$ . Applying the construction of step 2.1 to the integer list $(a_{0}, a_{1}) : = (- p, v)$ , of degree $d = 1$ with $a_{1} = v \neq 0$ , produces a code $n$ whose decoded polynomial is $P (x) = (- p)^{*} + v^{*} x$ . By [F7], $P (ε (q)) = ε (j (- p)) + ε (j (v)) ε (q) = ε (j (- p) + j (v) q) = ε (0) = 0$ , because $j (- p) + j (v) q = 0$ in $Q$ , that is $v \cdot q = p$ . Hence $ε (q) \in A$ .

4.1step 3.2F5F7

$N ⪯ A$ . The composite embedding $g : N \to R$ , $g (m) : = ε (j (\overline{m}))$ , is injective, as a composite of injective maps; and $g (m) \in A$ for every $m$ , since $g (m) = ε (q)$ for the rational $q = j (\overline{m})$ by step 3.2. So $g$ is an injection $N \to A$ .

5.1step 3.1step 4.1F5F6

By step 3.1 there is an injection $A \to N$ , and by step 4.1 there is an injection $N \to A$ ; Schröder-Bernstein gives $A \approx N$ , so $A$ is countably infinite.

6.1step 5.1F1F6

$R ∖ A$ is uncountable. Suppose it were at most countable. If $R ∖ A = \emptyset$ then $R = A \approx N$ by step 5.1, contradicting [F6]. Otherwise $R ∖ A$ is nonempty, so by [F6] fix a surjection $s : N \to R ∖ A$ ; by step 5.1 fix a bijection $f : N \to A$ . Define $t : N \times N \to R$ by $t (0, k) : = f (k)$ and $t (σ (i), k) : = s (k)$ ; every real is in $A$ or in $R ∖ A$ , elements of $A$ are values $f (k)$ , and elements of $R ∖ A$ are values $s (k) = t (σ (0), k)$ , so $t$ is onto. Composing $t$ with the bijection $β : N \to N \times N$ inverse to $J$ gives a surjection $N \to R$ , contradicting [F6]. Hence $R ∖ A$ is uncountable.

7.1step 3.2step 5.1step 6.1∎

Collecting the results: $A$ is countably infinite by step 5.1, every embedded rational lies in $A$ by step 3.2, and $R ∖ A$ is uncountable by step 6.1. The injection of step 3.1 is the least-code-and-root-rank map $x \mapsto J (n (x), j (x))$ , and the only selections made anywhere are least elements of nonempty sets of naturals and the unique increasing listings of finite root sets, so the argument is a theorem of ZF.

Remarks

The role of the local root bound A real coefficient list of degree d has at most d real roots is exactly to make each coded list have a finite root set, so that the increasing listing and the position $j (x)$ exist. Without it the least-code map would still be defined but its injectivity argument would have no canonical second coordinate.
The fallback clause at a top coefficient $a_{d} = 0$ keeps the decoding total: every natural number is a code, possibly of the constant polynomial $1$ , which has no roots. Invalid codes therefore contribute nothing to $A$ , while every genuine list appears by step 2.1.
No completion or algebraic-closure operation is used, and no claim is made about complex roots: the field in play is $R$ and the roots counted are real roots only. This is the convention of the source exercise, which concerns real coefficient lists.

ExampleConstruction: Literature-sourcedVerification: AI-generatedjudge pass (gpt-6.1-sol)Open item page →

Cantor diagonal construction misses every prescribed list of binary sequences

Example

Given any function $s : N \to {0, 1}^{N}$ , write $s_{n} = s (n)$ and define $d : N \to {0, 1}$ by $d (n) = 1$ if $s_{n} (n) = 0$ and $d (n) = 0$ if $s_{n} (n) = 1$ . Then $d$ differs from $s_{n}$ at coordinate $n$ for every $n$ , so $d$ is outside the range of $s$ . In particular no prescribed list of binary sequences is onto, and since ${0, 1}^{N}$ is nonempty this gives once more that it is uncountable (Finite, countably infinite, countable, uncountable, A nonempty set is at most countable iff it is a surjective image of $N$ ). This is a direct choice-free diagonal construction, not a decimal expansion argument; no sum, limit or real digit convention is required.

Facts & Assumptions

Given: The naturals $N$ with $0 = \emptyset$ and $1 = σ (0)$ (The natural numbers $N$ (von Neumann)), the unordered pair ${0, 1}$ (The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ ), the set of binary sequences ${0, 1}^{N}$ (The set $B^{A}$ of all functions $A \to B$ , For sets $A$ and $B$ the collection of all functions $A \to B$ is a set, being a subset of $P (A \times B)$ ), and an arbitrary function $s : N \to {0, 1}^{N}$ .

[F1]

$s (n)$ is a function $N \to {0, 1}$ , so $s (n) (n) \in {0, 1}$ and the expression $s_{n} (n)$ is meaningful; $t \in {0, 1}$ exactly when $t = 0$ or $t = 1$ (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain, The unordered pair ${x, y}$ and the singleton ${x} = {x, x}$ ).

[F2]

$0 \neq 1$ (The von Neumann naturals form a Peano system).

[F3]

Separation: for a set $X$ and a property of its elements, ${z \in X : φ (z)}$ is a set whose elements are exactly those $z \in X$ with the property (The Axiom Schema of Separation: for each formula $φ$ , $\forall \overset{ˉ}{p} \forall x \exists y \forall z (z \in y \leftrightarrow (z \in x \land φ (z, \overset{ˉ}{p})))$ ); ordered pairs lie in $X \times Y$ (The Cartesian product $A \times B : = {z \in P (P (A \cup B)) : \exists a \in A \exists b \in B z = (a, b)}$ ).

[F4]

Two functions with the same domain are equal exactly when they take the same value at every point of that domain; and a function $s$ is onto its codomain when every element of the codomain is a value of $s$ (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain, Injection, surjection, bijection).

[F5]

A nonempty at most countable set has a surjection from $N$ (A nonempty set is at most countable iff it is a surjective image of $N$ , Finite, countably infinite, countable, uncountable); ${0, 1}^{N}$ is nonempty, for instance the constant function $n \mapsto 0$ is an element of it.

Verification

technique · direct

1.1F1F2F3givenconstruct

The set $D : = {(n, v) \in N \times {0, 1} : (s (n) (n) = 0 \land v = 1) \lor (s (n) (n) = 1 \land v = 0)}$ exists by Separation and is a function $d : N \to {0, 1}$ with $d (n) = 1$ when $s (n) (n) = 0$ and $d (n) = 0$ when $s (n) (n) = 1$ . Indeed, for each $n$ the value $s (n) (n)$ is $0$ or $1$ by [F1], the alternatives $s (n) (n) = 0$ and $s (n) (n) = 1$ are mutually exclusive by [F2], and each branch assigns exactly one value; both values lie in ${0, 1}$ .

2.1step 1.1F1F2

For every $n \in N$ one has $d (n) \neq s (n) (n)$ . If $s (n) (n) = 0$ then $d (n) = 1 \neq 0$ by [F2]; if $s (n) (n) = 1$ then $d (n) = 0 \neq 1$ by [F2]. These are the only two cases by [F1].

3.1step 2.1F4

For every $n$ the functions $d$ and $s (n)$ differ, because at the point $n$ their values differ by step 2.1; hence $d$ is not a value of $s$ , that is, $d$ is outside the range of $s$ . So $s$ is not onto ${0, 1}^{N}$ , and no prescribed list of binary sequences is onto.

4.1step 3.1F5

Consequently ${0, 1}^{N}$ is uncountable: it is nonempty by [F5], so if it were at most countable, [F5] would produce a surjection $N \to {0, 1}^{N}$ , which step 3.1 forbids.

5.1step 3.1step 4.1∎

Therefore every list of binary sequences omits at least the complementary diagonal sequence $d$ constructed above, and the set of binary sequences is uncountable. The only set introduced is $D$ , separated from $N \times {0, 1}$ by a condition that determines each value uniquely; no element is selected from a nonempty family, so no choice principle is used.

Remarks

The construction complements the diagonal entry: at coordinate $n$ it looks at the $n$ -th value of the $n$ -th listed sequence and writes the other symbol. Every listed sequence is contradicted at its own index, so the resulting sequence cannot be on the list.
This is the literal diagonal argument that accompanies the characteristic-function bijection of The set of binary sequences is equinumerous with $P (N)$ , hence uncountable; there the uncountability was transferred from $P (N)$ , here it is produced directly from the diagonal sequence, with no appeal to decimal expansions.

Countability and the Uncountability of R: Examples and Counterexamples

1 · Prerequisites

2 · Summary

Examples and counterexamples

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

The integers are countably infinite: Z≈NZ≈N

Example

Facts & Assumptions

Verification

Remarks

Deleting one point of a countably infinite set leaves a set equinumerous with it

Example

Facts & Assumptions

Verification

Remarks

P(N)P(N) is uncountable

Example

Facts & Assumptions

Verification

Remarks

The set of binary sequences is equinumerous with P(N)P(N), hence uncountable

Example

Facts & Assumptions

Verification

Remarks

The rationals in an interval are countably infinite while the interval is uncountable

Example

Facts & Assumptions

Verification

Remarks

The complement of an at most countable set of reals is uncountable

Example

Facts & Assumptions

Verification

Remarks

A nonempty surjective image of NN need not be equinumerous with NN

Statement refuted

Facts & Assumptions

Counterexample

Remarks

The empty set is at most countable but no function from NN is onto it

Statement refuted

Facts & Assumptions

Counterexample

Remarks

An explicit enumeration of the rationals, with repetitions and then without them

Example

Facts & Assumptions

Verification

Remarks

A real coefficient list of degree d has at most d real roots

Statement

Facts & Assumptions

Proof

Remarks

Real algebraic numbers are countably infinite, without choice

Example

Facts & Assumptions

Verification

Remarks

Cantor diagonal construction misses every prescribed list of binary sequences

Example

Facts & Assumptions

Verification

Remarks

Sources

The integers are countably infinite: $Z \approx N$

$P (N)$ is uncountable

The set of binary sequences is equinumerous with $P (N)$ , hence uncountable

A nonempty surjective image of $N$ need not be equinumerous with $N$

The empty set is at most countable but no function from $N$ is onto it