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?
Best Answer
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.