Basic counting principles

Mathematical statement

Counts of mutually exclusive choice classes are added. Counts of combinations across successive choice stages are multiplied when the options and conditions at every stage are explicit.

Representative formula (exact TeX)

N(A)

Assumptions

• The choice sets or choice sequences being counted are finite.
• For the addition principle, the classes are disjoint or their overlap is corrected separately.
• For the multiplication principle, every stage and its number of available options are explicitly described relative to prior choices.

Symbol scope

• N — finite cardinality function
• A — finite choice collection

Intuition, definition, and misconceptions

If a task can be completed in one of m mutually exclusive ways or one of n mutually exclusive ways, the total is m+n. Disjointness matters because otherwise the same outcome may be counted twice.

If a process has m first-stage choices and each has n subsequent choices, there are m×n ordered combinations. If the number of later options depends on the first choice, the branches must be counted separately.

N(A) denotes only the number of elements in a finite set A. Complete formulas and formal proofs for the addition and multiplication principles are handled separately by later compiler and Evidence work.

A common mistake is to add overlapping cases directly or multiply unconditionally when later option counts depend on earlier choices.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Natural number — Counts of finite objects are represented by natural numbers.
• Arithmetic operations — Basic counting principles use addition and multiplication to combine local counts.

Verification boundary

This object does not yet bind every condition of the addition and multiplication principles to formal Evidence; the representative expression N(A) is not a complete proof.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Align the principles with Fintype.card_sum and Fintype.card_prod, making the no-overlap condition explicit for addition.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.