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.
The set of functions between finite sets is finite, with
Statement
Let and be finite sets and write
Then is finite and , the power being the -valued exponentiation of Exponentiation of natural numbers, , and its agreement with the integer power in .
Both degenerate cases are covered and neither is a stipulation. If there is exactly one function , the empty function, so even when . If and there is no function at all, so with .
Statement references
Facts & Assumptions
Given: Finite sets and , and . Here is the SET of functions ; it carries no further structure.
Induction (The principle of mathematical induction).
Cardinality (The cardinality of a finite set): is the unique natural with ; ; exactly when ; and a bijection transports finiteness and cardinality.
The sum rule for two disjoint blocks: (The sum rule: a finite disjoint union is finite with and , and a sum over a finite index set splits along a partition, clause 1).
The product rule: for finite , (The product rule: , and , clause 1).
Maps (Injection, surjection, bijection, Equinumerous sets, and ): a map with a two-sided inverse is a bijection.
A subset of a finite set is finite (A subset of a finite set is finite, with , and equality holds if and only if , clause 1); cancellation in : implies (Addition is cancellative); and , (The natural numbers (von Neumann), On the order is membership: ).
Proof
Base case . Then by [L2], and a function is the empty function, of which there is exactly one whatever is; so , which is finite with cardinality because is a bijection of onto it. And by [L5].
Inductive hypothesis: fix and assume that for every finite and every finite with the set is finite with .
Inductive step. Let . Then by [L2], so fix and put , which is finite by [L7]. Since with and , [L3] gives , hence by cancellation. Define by ; its inverse is , which is a function on because , and the two composites are the identity, so is a bijection. By the hypothesis of step 1.2 and by [L4] the codomain is finite with cardinality , and transport carries this to .
By induction on the statement holds for every pair of finite sets , .
The two degenerate readings are instances of it: gives by step 1.1, valid for as well; and with gives , which is right because a function would have to supply a value in for some element of .
Remarks
-
Where the choice of sits. A single element is taken from a single nonempty set, which is an ordinary existential instantiation and not a choice principle. Nothing in the argument selects a point of every member of a family.
-
here is a bare set. The same set carries a vector space structure over a field in The vector space of all functions with pointwise operations, and as the case ↗, much later in the reading order; that structure is not used, and this theorem is a count and nothing more.
-
The exponent notation is not an accident. counts the functions , and is by clause (e) of Exponentiation of natural numbers, , and its agreement with the integer power in the product of copies of : one factor for each element of the domain, which is exactly what the inductive step does one point at a time.
Depends on
Exponentiation of natural numbers, , and its agreement with the integer power in
The product rule: , and
The sum rule: a finite disjoint union is finite with and , and a sum over a finite index set splits along a partition
The cardinality of a finite set
A subset of a finite set is finite, with , and equality holds if and only if
Injection, surjection, bijection
Equinumerous sets, and
The principle of mathematical induction
The natural numbers (von Neumann)
On the order is membership:
Addition is cancellative