CorollaryStatement: AI-adaptedProof: 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.

$∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$

Statement

Let $A$ be a finite set and $n : = ∣ A ∣$ . Then the power set $P (A)$ is finite and

$∣ P (A) ∣ = 2^{n},$

the power being the $N$ -valued exponentiation of Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ . Moreover $n < 2^{n}$ .

The last inequality is the quantitative form, for finite $A$ , of Cantor's theorem $A ≺ P (A)$ (Cantor's theorem: $A ≺ P (A)$ ), which holds for every set whatsoever. The two statements are consistent and the proof below derives the inequality from Cantor's theorem rather than leaving them side by side.

Facts & Assumptions

Given: A finite set $A$ with $n : = ∣ A ∣$ , and $2 = {0, 1}$ as a von Neumann natural (The natural numbers $N$ (von Neumann)). Write $2^{A}$ for the set of functions $A \to 2$ .

[L1]

$∣ X^{Y} ∣ = ∣ X ∣^{∣ Y ∣}$ for finite $X$ , $Y$ , and $X^{Y}$ is finite (The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$ ).

[L2]

Cardinality (The cardinality $∣ A ∣$ of a finite set): $∣ m ∣ = m$ for a natural $m$ ; a bijection transports finiteness and cardinality; and for finite $X$ , $Y$ one has $∣ X ∣ = ∣ Y ∣$ if and only if $X \approx Y$ .

[L3]

Cantor's theorem: $A ≺ P (A)$ , that is, there is an injection $A \to P (A)$ and no bijection (Cantor's theorem: $A ≺ P (A)$ , Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[L4]

Pigeonhole, claim 2: if $q < p$ then there is no injection $p \to q$ (The pigeonhole principle on $N$ ).

[L5]

Trichotomy: exactly one of $p < q$ , $p = q$ , $q < p$ holds (Trichotomy of the order on $N$ , Order on the natural numbers).

[L6]

Maps (Injection, surjection, bijection): a map with a two-sided inverse is a bijection; a composite of injections is an injection; and $f^{- 1} [T] = {x : f (x) \in T}$ .

Proof

technique · direct

1.1L6construct

The characteristic function. For $S \subseteq A$ define $χ_{S} : A \to 2$ by $χ_{S} (x) = 1$ when $x \in S$ and $χ_{S} (x) = 0$ otherwise, and let $X : P (A) \to 2^{A}$ be $S \mapsto χ_{S}$ . Let $Y : 2^{A} \to P (A)$ be $f \mapsto f^{- 1} [{1}]$ . Both composites are the identity: $χ_{S}^{- 1} [{1}] = {x \in A : χ_{S} (x) = 1} = S$ ; and for $f : A \to 2$ and $x \in A$ the value $f (x)$ is $0$ or $1$ , so $χ_{f^{- 1} [{1}]} (x) = 1$ exactly when $f (x) = 1$ and $= 0$ otherwise, that is $χ_{f^{- 1} [{1}]} = f$ . Hence $X$ is a bijection and $P (A) \approx 2^{A}$ .

2.1step 1.1L1L2

Therefore $P (A)$ is finite and $∣ P (A) ∣ = ∣ 2^{A} ∣ = ∣ 2 ∣^{∣ A ∣} = 2^{n}$ , using [L1] and $∣ 2 ∣ = 2$ from [L2].

3.1step 2.1L2L3L4L5L6

The inequality. By [L3] there is an injection $A \to P (A)$ ; composing with bijections $n \to A$ and $P (A) \to 2^{n}$ , which exist by [L2] and step 2.1, gives an injection $n \to 2^{n}$ . So $2^{n} < n$ is impossible by [L4], and $n \leq 2^{n}$ by [L5]. Also $n \neq 2^{n}$ : otherwise $∣ A ∣ = ∣ P (A) ∣$ , hence $A \approx P (A)$ by [L2], contradicting [L3].

4.1step 2.1step 3.1∎

The two assertions are step 2.1 and step 3.1, so $∣ P (A) ∣ = 2^{n}$ and $n < 2^{n}$ .

Remarks

The finiteness of $P (A)$ is part of the statement, and it is what makes $[A]^{k}$ finite in the next definition: a set of $k$ -element subsets is a subset of $P (A)$ .
Cantor's theorem is not weakened here. $A ≺ P (A)$ holds for every set, finite or infinite, and needs no counting; what the finite case adds is the value of the gap, $2^{n}$ against $n$ . The inequality above is deduced from Cantor's theorem, so no independent argument can disagree with it.

$∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources

∣P(A)∣=2∣A∣∣P(A)∣=2∣A∣ for finite AA

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources

$∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$