Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck 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 sum rule: a finite disjoint union is finite with AB=A+B\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert and iIAi=iIAi\lvert\bigcup_{i \in I} A_i\rvert = \sum_{i \in I}\lvert A_i\rvert, and a sum over a finite index set splits along a partition

Statement

  1. Two blocks. If AA and BB are finite and disjoint, then ABA \cup B is finite and AB=A+B\lvert A \cup B\rvert = \lvert A\rvert + \lvert B\rvert (The cardinality A\lvert A\rvert of a finite set).
  2. A finite partition. If II is a finite set and (Ai)iI(A_i)_{i \in I} is a family of finite sets that are pairwise disjoint, then iIAi\bigcup_{i \in I} A_i is finite and iIAi=iIAi\big\lvert\bigcup_{i \in I} A_i\big\rvert = \sum_{i \in I}\lvert A_i\rvert, the sum being that of The sum iSai\sum_{i \in S} a_i over a finite index set, and its product form.
  3. Splitting a sum along a partition of its index set. Let SS be finite, let JJ be finite, and let (Sj)jJ(S_j)_{j \in J} be pairwise disjoint subsets of SS with jJSj=S\bigcup_{j \in J} S_j = S. Then for a:SRa : S \to \mathbb{R} or a:SNa : S \to \mathbb{N}, iSai=jJ(iSjai),iSai=jJ(iSjai).\sum_{i \in S} a_i = \sum_{j \in J}\Big(\sum_{i \in S_j} a_i\Big), \qquad \prod_{i \in S} a_i = \prod_{j \in J}\Big(\prod_{i \in S_j} a_i\Big). In particular iSTai=iSai+iTai\sum_{i \in S \cup T} a_i = \sum_{i \in S} a_i + \sum_{i \in T} a_i for disjoint finite SS and TT.

Disjointness is a hypothesis and not a formality. It is spent at exactly one step, the injectivity of the splice map, and dropping it makes clause 1 false; the companion page carries that false statement with its smallest witness.

ABp;q>0f(0)¢¢¢f(p¡1)g(0)¢¢¢g(q¡1)0¢¢¢p¡1p¢¢¢p+q¡1h(k)=f(k)h(p+j)=g(j)h:p+q¡!A[B

Facts & Assumptions

Given: Finite sets as in the statement, and the truncated difference and the two finite sums of Finite sums and finite products of natural numbers, k<nak\sum_{k<n} a_k and k<nak\prod_{k<n} a_k in N\mathbb{N}. Throughout, \ast denotes either ++ or \cdot on R\mathbb{R} or on N\mathbb{N}, ee the corresponding identity, and k<nck\bigstar_{k<n} c_k the associated iterated operation; the four cases are proved by one argument, as in A finite sum is unchanged by a permutation of its index range: k<naπ(k)=k<nak\sum_{k<n} a_{\pi(k)} = \sum_{k<n} a_k for every bijection π:nn\pi : n \to n.

[L2]

Cardinality (The cardinality A\lvert A\rvert of a finite set): A\lvert A\rvert is the unique natural with AAA \approx \lvert A\rvert; n=n\lvert n\rvert = n; =0\lvert\varnothing\rvert = 0; a bijection transports finiteness and cardinality.

[L3]

Sums over a finite index set (The sum iSai\sum_{i \in S} a_i over a finite index set, and its product form): iSai=k<naφ(k)\sum_{i \in S} a_i = \sum_{k<n} a_{\varphi(k)} for any bijection φ:SS\varphi : \lvert S\rvert \to S, the value being independent of φ\varphi; inai=k<nak\sum_{i \in n} a_i = \sum_{k<n} a_k; reindexing along a bijection TST \to S leaves the value unchanged; and iai=e\sum_{i \in \varnothing} a_i = e.

[L4]

Recursion clauses: k<0ck=e\bigstar_{k<0} c_k = e and k<σ(n)ck=(k<nck)cn\bigstar_{k<\sigma(n)} c_k = \big(\bigstar_{k<n} c_k\big) \ast c_n (Finite sums and finite products of natural numbers, k<nak\sum_{k<n} a_k and k<nak\prod_{k<n} a_k in N\mathbb{N}, Finite sums and finite products, by recursion).

[L5]

Splitting at an index: for pNp \le N and q=Npq = N - p, k<Nck=(k<pck)(j<qcp+j)\bigstar_{k<N} c_k = \big(\bigstar_{k<p} c_k\big) \ast \big(\bigstar_{j<q} c_{p+j}\big) (clause 3 of Laws of finite sums and products in N\mathbb{N}, and ι(k<nak)=k<nι(ak)\iota\big(\sum_{k<n} a_k\big) = \sum_{k<n} \iota(a_k), clause 3 of Laws of finite sums and finite products).

[L6]

Order and addition in N\mathbb{N}: pkp \le k gives a unique jj with p+j=kp + j = k; p+j<p+q    j<qp + j < p + q \iff j < q; addition is commutative; σ(m)=m+1\sigma(m) = m + 1 (Order on the natural numbers, Addition is cancellative, Order is compatible with addition, Addition is commutative, Addition of natural numbers, On N\mathbb{N} the order is membership: m<n    mnm < n \iff m \in n).

[L7]

Maps (Injection, surjection, bijection, Equinumerous sets, ABA \approx B and ABA \preceq B): composites and inverses of bijections are bijections, and an injective surjection is a bijection.

Proof

technique · induction
1.1

The splice map. Let AA, BB be finite and disjoint, put p:=Ap := \lvert A\rvert, q:=Bq := \lvert B\rvert, and fix bijections f:pAf : p \to A and g:qBg : q \to B. Define h:p+qABh : p + q \to A \cup B by h(k)=f(k)h(k) = f(k) when k<pk < p, and, when pkp \le k, by h(k)=g(j)h(k) = g(j) for the unique jj with p+j=kp + j = k; that jj satisfies j<qj < q because p+j=k<p+qp + j = k < p + q. The map hh is well defined by [L6], it is surjective because every element of ABA \cup B is some f(k)f(k) or some g(j)g(j), and it is injective: two indices below pp are separated by the injectivity of ff, two indices at least pp by the injectivity of gg together with the uniqueness of jj, and an index below pp from one at least pp because f(k)Af(k) \in A, g(j)Bg(j) \in B and AB=A \cap B = \varnothing. The last of these three cases is the only use of disjointness in the whole proof.

L6L7construct
1.2

Base cases of the two inductions below, at m=0m = 0. A family indexed by 0=0 = \varnothing has empty union, so k<0Bk==0=k<0Bk\big\lvert\bigcup_{k<0} B_k\big\rvert = \lvert\varnothing\rvert = 0 = \sum_{k<0}\lvert B_k\rvert; and a partition of SS indexed by 00 forces S=S = \varnothing, so both sides of clause 3 are ee.

baseL2L3L4
1.3

Inductive hypothesis for both inductions, at mm: for pairwise disjoint finite B0,,Bm1B_0, \dots, B_{m-1} the union k<mBk\bigcup_{k<m} B_k is finite with cardinality k<mBk\sum_{k<m}\lvert B_k\rvert; and for a partition of a finite set SS into pairwise disjoint S0,,Sm1S_0, \dots, S_{m-1} one has iSai=k<m(iSkai)\bigstar_{i \in S} a_i = \bigstar_{k<m}\big(\bigstar_{i \in S_k} a_i\big).

ih
2.1

Clause 1. By step 1.1 the map hh is a bijection p+qABp + q \to A \cup B, so ABp+qA \cup B \approx p+q; hence ABA \cup B is finite and AB=p+q=p+q=A+B\lvert A \cup B\rvert = \lvert p+q\rvert = p + q = \lvert A\rvert + \lvert B\rvert.

step 1.1L2L7
3.1

Clause 3 for two blocks. Let SS, TT be finite and disjoint and aa defined on STS \cup T. With p=Sp = \lvert S\rvert, q=Tq = \lvert T\rvert and the bijections f,g,hf, g, h of step 1.1 for the pair SS, TT, step 2.1 gives ST=p+q\lvert S \cup T\rvert = p+q, so hh may be used as the enumeration in [L3]. Then iSTai=k<p+qah(k)=(k<pah(k))(j<qah(p+j))=(k<paf(k))(j<qag(j))=(iSai)(iTai)\bigstar_{i \in S \cup T} a_i = \bigstar_{k<p+q} a_{h(k)} = \big(\bigstar_{k<p} a_{h(k)}\big) \ast \big(\bigstar_{j<q} a_{h(p+j)}\big) = \big(\bigstar_{k<p} a_{f(k)}\big) \ast \big(\bigstar_{j<q} a_{g(j)}\big) = \big(\bigstar_{i \in S} a_i\big) \ast \big(\bigstar_{i \in T} a_i\big), using [L5] at the second equality.

step 1.1step 2.1L3L5
3.2

Inductive step for clause 2, in the case of an index set σ(m)\sigma(m). Let B0,,BmB_0, \dots, B_{m} be pairwise disjoint and finite. Then k<σ(m)Bk=(k<mBk)Bm\bigcup_{k<\sigma(m)} B_k = \big(\bigcup_{k<m} B_k\big) \cup B_m, and these two sets are disjoint because each BkB_k with k<mk < m is disjoint from BmB_m. By the hypothesis of step 1.3 the first is finite with cardinality k<mBk\sum_{k<m}\lvert B_k\rvert, so clause 1 makes the union finite with cardinality k<mBk+Bm=k<σ(m)Bk\sum_{k<m}\lvert B_k\rvert + \lvert B_m\rvert = \sum_{k<\sigma(m)}\lvert B_k\rvert by [L4].

step 1.3step 2.1L4
4.1

Clause 2. By step 1.2, step 3.2 and induction, the statement holds for every family indexed by a natural number mm. For a general finite index set II take a bijection φ:mI\varphi : m \to I with m=Im = \lvert I\rvert; then iIAi=k<mAφ(k)\bigcup_{i \in I} A_i = \bigcup_{k<m} A_{\varphi(k)} and iIAi=k<mAφ(k)\sum_{i \in I}\lvert A_i\rvert = \sum_{k<m}\lvert A_{\varphi(k)}\rvert by the definition of the sum over a finite index set, so the two statements coincide.

step 1.2step 3.2L1L3
5.1

Inductive step for clause 3, index set σ(m)\sigma(m). Let SS be finite and partitioned into pairwise disjoint S0,,SmS_0, \dots, S_m, and put S:=k<mSkS' := \bigcup_{k<m} S_k, which is finite by [L8] and disjoint from SmS_m. The hypothesis of step 1.3 applies to the partition of SS' into S0,,Sm1S_0, \dots, S_{m-1}, and step 3.1 applies to the disjoint pair SS', SmS_m, giving iSai=(iSai)(iSmai)=(k<miSkai)(iSmai)=k<σ(m)(iSkai)\bigstar_{i \in S} a_i = \big(\bigstar_{i \in S'} a_i\big) \ast \big(\bigstar_{i \in S_m} a_i\big) = \big(\bigstar_{k<m}\bigstar_{i \in S_k} a_i\big) \ast \big(\bigstar_{i \in S_m} a_i\big) = \bigstar_{k<\sigma(m)}\big(\bigstar_{i \in S_k} a_i\big) by [L4].

step 1.3step 3.1step 4.1L4L8
6.1

Clause 3. By step 1.2, step 5.1 and induction it holds for every index set that is a natural number, and the general finite JJ follows by reindexing along a bijection mJm \to J exactly as in step 4.1. The two-block form is step 3.1.

step 1.2step 3.1step 5.1L1L3
7.1

Clause 1 is step 2.1, clause 2 is step 4.1 and clause 3 is step 6.1; since \ast was an arbitrary one of the four operations, both the sum and the product forms of clause 3 are proved.

step 2.1step 4.1step 6.1discharge-induction

Remarks

  • Why the splice map is built once. The same bijection p+qABp + q \to A \cup B proves clause 1 and, used as an enumeration, proves the two-block case of clause 3. Building it twice, once for cardinalities and once for sums, would be two chances to get the index arithmetic wrong.

  • The subtraction in the splice is legitimate. Writing h(k)=g(kp)h(k) = g(k - p) for kpk \ge p means: the unique jj with p+j=kp + j = k, which exists by the definition of \le and is unique by cancellation. No negative number is formed anywhere.

  • Clause 3 is what the multinomial theorem needs. Its outer sum is indexed by the set of weak compositions of nn into mm parts, and the induction on mm partitions that index set by the value of the last part. Without clause 3 that step could not be taken.

Depends on

Used by

…and 9 more results.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 73 results over 22 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources