CounterexampleConstruction: AI-adaptedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6.1-sol)

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.

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$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

33 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

John K. Hunter, An Introduction to Real Analysis (complete author-hosted lecture notes, 307 pp.) (standard reference, not scraped)
Jiri Lebl, Basic Analysis I: Introduction to Real Analysis, Volume I (author-hosted complete book PDF) (standard reference, not scraped)

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