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?