False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-29

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.

FALSE: every injection of a set into itself is a bijection

Statement

FALSE. The statement

every injective function $f : A \to A$ from a set to itself is a bijection

for all sets $A$ .

The claim is plausible because it is true for finite $A$ : that is clause 4 of A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ . What is easy to miss is that the proof of that clause uses finiteness twice, at the transport $∣ f [A] ∣ = ∣ A ∣$ and at the step "a subset of the same cardinality as the whole is the whole", and neither survives without it.

Facts & Assumptions

Given: The von Neumann naturals $N$ with $0 = \emptyset$ and successor $σ$ (The natural numbers $N$ (von Neumann)), and $A : = N$ , $f : = σ$ .

[L1]

$(N, 0, σ)$ satisfies the Peano axioms: $σ (n) \neq 0$ for every $n$ , and $σ$ is injective (The von Neumann naturals form a Peano system).

[L2]

Every nonzero natural is a successor (Every nonzero natural number is a successor), so the image of $σ$ is exactly $N ∖ {0}$ .

[L3]

Injection, surjection, bijection (Injection, surjection, bijection): $f$ is surjective when its image is the whole codomain, and bijective when injective and surjective.

[L4]

For finite $A$ , every injection $A \to A$ is a bijection (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , clause 4), the proof going through $∣ f [A] ∣ = ∣ A ∣$ and clause 3 of the same theorem (The cardinality $∣ A ∣$ of a finite set).

[L5]

$N$ is not finite: $N \approx̸ n$ for every natural $n$ (The pigeonhole principle on $N$ , claim 4, Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

Refutation

technique · direct

1.1

The witness is the successor map $σ : N \to N$ . It is injective by [L1].

givenL1L3

2.1

It is not surjective: $0$ is not in its image, since $σ (n) \neq 0$ for every $n$ by [L1]. Equivalently, its image is $N ∖ {0}$ by [L2], a proper subset of $N$ .

step 1.1L1L2L3

3.1

So $σ$ is an injection of $N$ into itself that is not a bijection, and the displayed statement is false.

step 1.1step 2.1L3

4.1

Finiteness is exactly the missing hypothesis. By [L4] the statement is true whenever $A$ is finite, and $N$ is not finite by [L5]. In the proof of [L4] the hypothesis is spent at the transport of cardinality along the bijection $A \to f [A]$ , which presupposes $A$ finite, and then at the conclusion $f [A] = A$ from $∣ f [A] ∣ = ∣ A ∣$ , which is the clause of A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ that fails here: $σ [N]$ is a proper subset of $N$ equinumerous with it.

step 3.1L4L5∎

Remarks

A set for which the statement fails is called Dedekind-infinite, and the refutation above exhibits $N$ as one. Claim 5 of The pigeonhole principle on $N$ says that no natural number is Dedekind-infinite, which is the finite half of the same picture.
The relation between the two notions of infinity — "not finite" and "Dedekind-infinite" — is a genuine question of set theory without choice, and it is treated on the countability page rather than here.
The surjective half fails too. The map $N \to N$ sending $0$ and $1$ to $0$ and $n \geq 2$ to $n - 1$ is surjective and not injective, so neither half of clause 4 of A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ survives the loss of finiteness.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

26 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

Dedekind-infinite set (Wikipedia) (standard reference, not scraped)
Surjective function (Wikipedia) (standard reference, not scraped)
Pigeonhole principle (Wikipedia) (standard reference, not scraped)
Finite set (Wikipedia) (standard reference, not scraped)