4
$\begingroup$

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?

  • 0
    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.2011-11-20

2 Answers 2

3

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.

  • 1
    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.2011-11-20
8

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.

  • 0
    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.2011-11-20