# Rigorous Proof of the Principle of Counting

Principle of Counting: If there are m ways of doing a task A and n ways of doing a task B, then there are mn ways of doing tasks A and B.

What would it take to prove this rigorously? All the proofs I have seen rely on our intuitive notion of counting. In the wikipedia article, it says that this principle is just the definition of the cardinality of the cartesian product of two finite sets. Does this mean that, if I wanted to prove this rigorously, I would have to pick a model of ZF, define cardinality, reformulate the statement in terms of my model and then prove it?

-
You could probably pull off an induction on $n$. I think such a proof would be more of an exercise in semantics rather than mathematics. Personally, I'm happy to take PoC as an axiom. :-) – Dimitrije Kostic Nov 19 '11 at 22:37
Well, induction is part of ZF too... You can't do anything without using some kind of axioms, and there's nothing wrong with that. Axioms are pretty just ways of formalizing our intuitive notion of what mathematics is. – Carl Nov 19 '11 at 23:26
What is the role of tasks in the formulation? They seem to me just to add potential confusion (for instance task B might be a subtask of A...). If you are asking to prove that that if sets $A$, $B$ have finite cardinalities $n$ and $m$ respectively, then $A\times B$ has cardinality $nm$, the product being described by Peano's axioms, then one should not have a hard time giving a formal proof. – Marc van Leeuwen Nov 20 '11 at 17:23

Let's say I want to build something. It can be done in two steps. For step $1$, I have $m$ choices. For step $2$, $n$ choices. Each possible construction then can be represented by an ordeded pair $(x,y)$, where $x\in [1,m]$ and $y\in [1,n]$.

The number of possible constructions is then the number of elements of the set $S$ with pairs $(x,y)$ as defined. I don't know if you want the answer of how the size of $S$ is proven, but I (or somebody else) can show you if you want.

-
Yes, I would like to know how the size of $S$ is computed from first principles, i.e. the axioms of ZF. – echoone Nov 20 '11 at 6:25
By induction. Let A and B be finite sets. We want to prove that AXB={(a,b) | $a\in A$ and $b\in B$} has size |A|*|B|. Base case: |B|=0. It follows AXB is the empty set and |A|*|B|=0 by definition. Induction step: |B| has size n+1. Let b an element of B. |B-b|=n. Thus, |AX(B-b)|=an. We also have that AXB=AX(B-b) U AX{b} so |AXB|=|AX(B-b)| + |AX{b}|=an+a=a(n+1), as needed. – anon Nov 20 '11 at 6:36
Regaring your comment "why have the principle of counting when the cartesian product captures the intuitive notion of "ways of doing a task". It seems silly to me." You can think of the "Principle of counting" as another name for |AXB|=|A|*|B| (what I proved above). It's just that the name is better in the context when you're counting things. – anon Nov 20 '11 at 6:53

You do need to rely on an intuitive notion somewhere, because "ways of doing a task" is not itself a formal mathematical concept until you explicitly equip it with a formal interpretation. You can then argue formally that the consequences of your interpretation are such-and-such, but the argument that the interpretation accurately captures your notion of "ways of doing a task" is necessarily informal.

-
I agree that you need a formal mathematical concept in order to argue formally. I believe the formal concept for the principle of counting is the cartesian product. It makes me wonder though: why have the principle of counting when the cartesian product captures the intuitive notion of "ways of doing a task". It seems silly to me. – echoone Nov 20 '11 at 6:20