Fundamental Counting Principle Proof (NOT via induction)

[Chicago_Boy1]

Hello all,

I am going through some sample problems exercises in Paul Sally's Tools of the Trade, and am being asked to prove the Fundamental Counting Principle. That is, If A has m elements and B has n elements, then A X B has mn elements.

Sally goes on to write that "this is simple to prove by drawing little trees or using some other artifice."

Basically, I am not really sure what he means by "drawing little trees." Can someone guide me through how I can actually prove this WITHOUT induction?

Thank you in advance.

P.S. I know that I am supposed to show that I've attempted to solve the problem, but honestly I have no idea where to even start.

 

[ystael]

What is your definition of "A has m elements" for a set A? It's probably something like "A is in bijective correspondence with the set [m] = \{0, 1, \dots, m - 1\}" (although knowing Sally, he probably starts counting with 1 instead). So you can rephrase the problem as: If f: A \to [m] is a bijection and g: B \to [n] is a bijection, find a bijection h: A \times B \to [mn]. Does that help?