TheoremStatement: Literature-sourcedProof: 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.

The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$

Statement

Let $A$ and $B$ be finite sets and write

$A^{B} : = {f : f is a function B \to A} .$

Then $A^{B}$ is finite and $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$ , the power being the $N$ -valued exponentiation of Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ .

Both degenerate cases are covered and neither is a stipulation. If $B = \emptyset$ there is exactly one function $B \to A$ , the empty function, so $∣ A^{\emptyset} ∣ = 1 = ∣ A ∣^{0}$ even when $A = \emptyset$ . If $A = \emptyset$ and $B \neq \emptyset$ there is no function at all, so $∣ A^{B} ∣ = 0 = 0^{∣ B ∣}$ with $∣ B ∣ \geq 1$ .

Facts & Assumptions

Given: Finite sets $A$ and $B$ , and $n : = ∣ B ∣$ . Here $A^{B}$ is the SET of functions $B \to A$ ; it carries no further structure.

[L1]

Induction (The principle of mathematical induction).

[L2]

Cardinality (The cardinality $∣ A ∣$ of a finite set): $∣ A ∣$ is the unique natural with $A \approx ∣ A ∣$ ; $∣ n ∣ = n$ ; $∣ A ∣ = 0$ exactly when $A = \emptyset$ ; and a bijection transports finiteness and cardinality.

[L3]

The sum rule for two disjoint blocks: $∣ S \cup T ∣ = ∣ S ∣ + ∣ T ∣$ (The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition, clause 1).

[L4]

The product rule: $∣ X \times Y ∣ = ∣ X ∣ \cdot ∣ Y ∣$ for finite $X$ , $Y$ (The product rule: $∣ A \times B ∣ = ∣ A ∣ ∣ B ∣$ , and $∣ \prod_{i < m} A_{i} ∣ = \prod_{i < m} ∣ A_{i} ∣$ , clause 1).

[L5]

Powers (Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ ): $m^{0} = 1$ and $m^{σ (n)} = m^{n} \cdot m$ .

[L6]

Maps (Injection, surjection, bijection, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ): a map with a two-sided inverse is a bijection.

[L7]

A subset of a finite set is finite (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , clause 1); cancellation in $N$ : $x + 1 = y + 1$ implies $x = y$ (Addition is cancellative); and $σ (n) = n + 1$ , $n = {i : i < n}$ (The natural numbers $N$ (von Neumann), On $N$ the order is membership: $m < n ⟺ m \in n$ ).

Proof

technique · induction

1.1

Base case $∣ B ∣ = 0$ . Then $B = \emptyset$ by [L2], and a function $\emptyset \to A$ is the empty function, of which there is exactly one whatever $A$ is; so $A^{B} = {\emptyset}$ , which is finite with cardinality $1$ because $0 \mapsto \emptyset$ is a bijection of $1 = {0}$ onto it. And $∣ A ∣^{0} = 1$ by [L5].

baseL2L5L6

1.2

Inductive hypothesis: fix $n \in N$ and assume that for every finite $A$ and every finite $B^{'}$ with $∣ B^{'} ∣ = n$ the set $A^{B^{'}}$ is finite with $∣ A^{B^{'}} ∣ = ∣ A ∣^{n}$ .

2.1

Inductive step. Let $∣ B ∣ = σ (n)$ . Then $B \neq \emptyset$ by [L2], so fix $b \in B$ and put $B^{'} : = B ∖ {b}$ , which is finite by [L7]. Since $B = B^{'} \cup {b}$ with $B^{'} \cap {b} = \emptyset$ and $∣ {b} ∣ = 1$ , [L3] gives $σ (n) = ∣ B^{'} ∣ + 1$ , hence $∣ B^{'} ∣ = n$ by cancellation. Define $Ψ : A^{B} \to A^{B^{'}} \times A$ by $Ψ (f) = (f ↾ B^{'}, f (b))$ ; its inverse is $(g, a) \mapsto g \cup {(b, a)}$ , which is a function on $B^{'} \cup {b} = B$ because $b \notin B^{'}$ , 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 $∣ A ∣^{n} \cdot ∣ A ∣ = ∣ A ∣^{σ (n)}$ , and transport carries this to $A^{B}$ .

step 1.2L2L3L4L5L6L7construct

3.1

By induction on $∣ B ∣$ the statement holds for every pair of finite sets $A$ , $B$ .

step 1.1step 2.1L1

4.1

The two degenerate readings are instances of it: $B = \emptyset$ gives $1 = ∣ A ∣^{0}$ by step 1.1, valid for $A = \emptyset$ as well; and $A = \emptyset$ with $∣ B ∣ \geq 1$ gives $∣ A^{B} ∣ = 0^{∣ B ∣} = 0$ , which is right because a function $B \to \emptyset$ would have to supply a value in $\emptyset$ for some element of $B$ .

step 1.1step 3.1L2L5discharge-induction∎

Remarks

Where the choice of $b$ 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.
$A^{B}$ here is a bare set. The same set carries a vector space structure over a field in The vector space $F^{X}$ of all functions $X \to F$ with pointwise operations, and $F^{n}$ as the case $X = n = {0, 1, \dots, n - 1}$ ↗, 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. $∣ A ∣^{∣ B ∣}$ counts the functions $B \to A$ , and $∣ A ∣^{n}$ is by clause (e) of Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ the product of $n$ copies of $∣ A ∣$ : one factor for each element of the domain, which is exactly what the inductive step does one point at a time.

Depends on

Used by

Dependency tree · two levels

45 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

Exponentiation (Wikipedia) (standard reference, not scraped)
Function (mathematics) (Wikipedia) (standard reference, not scraped)
R. Stanley, Enumerative Combinatorics, Vol. 1, Ch. 1 (standard reference, not scraped)
Twelvefold way (Wikipedia) (standard reference, not scraped)
Power set (Wikipedia) (standard reference, not scraped)

The set ABAB of functions B→AB→A between finite sets is finite, with ∣AB∣=∣A∣∣B∣∣AB∣=∣A∣∣B∣