CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)

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.

Two sets of the same finite cardinality between which the bijection is not unique

Statement refuted

Refuted claim: two equinumerous finite sets admit exactly one bijection between them.

The witness is $A : = 2 = {\emptyset, {\emptyset}} = {0, 1}$ and $B : = [2]^{1} = {{0}, {1}}$ , the set of one-element subsets of $2$ . Both have cardinality $2$ , and there are exactly two bijections between them.

Facts & Assumptions

Given: $A = 2 = {0, 1}$ with $0 = \emptyset$ and $1 = {0}$ (The natural numbers $N$ (von Neumann)), and $B = [2]^{1}$ , the set of $1$ -element subsets of $2$ .

[L1]

$∣ n ∣ = n$ for a natural $n$ , and $∣ A ∣$ is the unique natural equinumerous with $A$ (The cardinality $∣ A ∣$ of a finite set).

[L2]

$∣ [X]^{k} ∣ = (\binom{∣ X ∣}{k})$ and $(\binom{n}{1}) = n$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

[L3]

The set of bijections between two finite sets of common cardinality $n$ has exactly $n!$ elements (A finite set $A$ with $∣ A ∣ = n$ has exactly $n!$ bijections onto itself, and $n!$ bijections onto any set of the same cardinality), and $2! = 2$ (The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ ).

[L4]

A bijection is an injective surjection (Injection, surjection, bijection, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[L5]

Claim 3 of The pigeonhole principle on $N$ : a finite set is equinumerous with exactly one natural number.

Counterexample

technique · direct

1.1

The two sets and their cardinalities. $A = 2$ has $∣ A ∣ = 2$ by [L1]. The elements of $B = [2]^{1}$ are the one-element subsets of ${0, 1}$ , namely ${0}$ and ${1}$ , so $∣ B ∣ = (\binom{2}{1}) = 2$ by [L2]. Hence $∣ A ∣ = ∣ B ∣$ .

givenL1L2

2.1

Two distinct bijections. Let $f : A \to B$ be $f (0) = {0}$ , $f (1) = {1}$ , and let $g : A \to B$ be $g (0) = {1}$ , $g (1) = {0}$ . Each is injective, its two values being distinct, and each is surjective, its image being all of $B$ ; so both are bijections by [L4]. They are distinct, since $f (0) = {0} \neq {1} = g (0)$ .

step 1.1L4construct

3.1

There are exactly two. By [L3] the set of bijections $A \to B$ has $2! = 2$ elements, so $f$ and $g$ of step 2.1 are all of them.

step 1.1L3

4.1

The refuted claim fails: $∣ A ∣ = ∣ B ∣$ holds, and there are two bijections $A \to B$ , not one. The cardinality $∣ A ∣$ of a finite set asserts only that some bijection $A \to ∣ A ∣$ exists; [L5] makes the resulting natural number unique, not the witnessing map.

step 2.1step 3.1L1L5∎

Remarks

What is unique and what is not. Cardinality is a well-defined function of the set, but a bijection witnessing an equality of cardinalities need not be unique. Whenever a construction is made "along a bijection", one has to check, as The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form does, that the result does not depend on which bijection was used.
The count grows fast. For $∣ A ∣ = n$ there are $n!$ bijections onto any set of the same cardinality (A finite set $A$ with $∣ A ∣ = n$ has exactly $n!$ bijections onto itself, and $n!$ bijections onto any set of the same cardinality), so the bijection is unique only for $n \leq 1$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

36 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

Cardinality (Wikipedia) (standard reference, not scraped)
Bijective proof (Wikipedia) (standard reference, not scraped)
P. Halmos, Naive Set Theory, §13 (standard reference, not scraped)