ExampleConstruction: AI-generatedVerification: AI-generatedprecheck 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.

All $8$ functions $3 \to 2$ , the $0$ injections $3 \to 2$ , and the $8$ subsets of a $3$ -element set

Example

Every count here is small enough to list in full, so nothing is asserted by inspection. Take $3 = {0, 1, 2}$ and $2 = {0, 1}$ .

There are $2^{3} = 8$ functions $3 \to 2$ , and all eight are listed below as triples $(f (0), f (1), f (2))$ .
None of them is injective, and the predicted count is $2^{\underline{3}} = 2 \cdot 1 \cdot 0 = 0$ .
There are $2^{3} = 8$ subsets of a three-element set, and grouping them by size gives $1 + 3 + 3 + 1 = 8$ .

Facts & Assumptions

Given: The sets $3 = {0, 1, 2}$ and $2 = {0, 1}$ , and $A : = 3$ .

[L1]

$∣ X^{Y} ∣ = ∣ X ∣^{∣ Y ∣}$ (The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$ , Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ , The cardinality $∣ A ∣$ of a finite set).

[L2]

The number of injections of a $k$ -element set into an $n$ -element set is $n^{\underline{k}}$ , with $n^{\underline{0}} = 1$ and $n^{\underline{σ (k)}} = n^{\underline{k}} (n - k)$ (The number of injections from a $k$ -element set into an $n$ -element set is $n^{\underline{k}}$ , The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ ).

[L3]

Pigeonhole: there is no injection $σ (n) \to n$ , and none $p \to q$ when $q < p$ (The pigeonhole principle on $N$ , claims 1 and 2).

[L4]

$∣ P (A) ∣ = 2^{∣ A ∣}$ ( $∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$ ), $∣ [A]^{k} ∣ = (\binom{∣ A ∣}{k})$ (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ), and $\sum_{k < n + 1} (\binom{n}{k}) = 2^{n}$ ( $\sum_{k < n + 1} (\binom{n}{k}) = 2^{n}$ , and $\sum_{k < n + 1} (- 1)^{k} ι ⁣ (\binom{n}{k}) = 0$ for $n \geq 1$ , clause 1).

[L5]

Pascal's rule and the boundary values $(\binom{n}{0}) = (\binom{n}{n}) = 1$ (Pascal's rule $(\binom{n + 1}{k + 1}) = (\binom{n}{k}) + (\binom{n}{k + 1})$ , and the hockey-stick identity $\sum_{i \leq n} (\binom{i}{k}) = (\binom{n + 1}{k + 1})$ , The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

Verification

technique · direct

1.1

The eight functions $3 \to 2$ , written as the triples of their values: $(0, 0, 0)$ , $(0, 0, 1)$ , $(0, 1, 0)$ , $(0, 1, 1)$ , $(1, 0, 0)$ , $(1, 0, 1)$ , $(1, 1, 0)$ , $(1, 1, 1)$ . The list is exhaustive because a function is determined by its three values and each value is $0$ or $1$ , and it has no repetitions. There are eight, and [L1] predicts $∣ 2 ∣^{∣ 3 ∣} = 2^{3} = 2 \cdot 2 \cdot 2 = 8$ .

givenL1

2.1

None of the eight is injective: in every triple above two of the three entries are equal, so two distinct elements of $3$ receive the same value. This agrees with [L2], which predicts $2^{\underline{3}} = 2^{\underline{2}} \cdot (2 - 2) = 2^{\underline{2}} \cdot 0 = 0$ injections, and with [L3], which forbids an injection $3 \to 2$ outright since $2 < 3$ .

step 1.1L2L3

2.2

The eight subsets of $A = 3$ , grouped by cardinality: $\emptyset$ ; then ${0}$ , ${1}$ , ${2}$ ; then ${0, 1}$ , ${0, 2}$ , ${1, 2}$ ; then ${0, 1, 2}$ . So $∣ [A]^{0} ∣ = 1$ , $∣ [A]^{1} ∣ = 3$ , $∣ [A]^{2} ∣ = 3$ , $∣ [A]^{3} ∣ = 1$ , that is $(\binom{3}{0}) = 1$ , $(\binom{3}{1}) = 3$ , $(\binom{3}{2}) = 3$ , $(\binom{3}{3}) = 1$ , which is row $3$ of Pascal's triangle as [L5] gives it.

step 1.1L4L5

3.1

The two ways of counting $P (A)$ agree: directly, the list in step 2.2 has $1 + 3 + 3 + 1 = 8$ entries; by [L4], $∣ P (A) ∣ = 2^{3} = 8$ and $\sum_{k < 4} (\binom{3}{k}) = 2^{3}$ . This is clause 1 of [L4] in its smallest interesting case.

step 2.1step 2.2L4∎

Remarks

The zero count is the interesting one. $2^{\underline{3}} = 0$ because the falling factorial acquires the factor $2 - 2 = 0$ at the third step, which is the arithmetic shadow of the pigeonhole principle. Both routes are checked above against the same explicit list.
The three subsets of size $2$ and the three of size $1$ are matched by the complementation bijection of $(\binom{n}{k}) k! (n - k)! = n!$ for $k \leq n$ ; hence $(\binom{n}{k}) k! = n^{\underline{k}}$ , the quotient $n! / (k! (n - k)!)$ is a natural number, and $(\binom{n}{k}) = (\binom{n}{n - k})$ : ${0} \leftrightarrow {1, 2}$ , ${1} \leftrightarrow {0, 2}$ , ${2} \leftrightarrow {0, 1}$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

43 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

Power set (Wikipedia) (standard reference, not scraped)
Pigeonhole principle (Wikipedia) (standard reference, not scraped)
Binomial coefficient (Wikipedia) (standard reference, not scraped)
Twelvefold way (Wikipedia) (standard reference, not scraped)

All 88 functions 3→23→2, the 00 injections 3→23→2, and the 88 subsets of a 33-element set