Fundamental Counting Principle

[ElderBirk]

Hey Guys,

So, I am trying to prove the Fundamental Counting Principle using induction. I have no clue where to start or even how to use induction to prove it. I would appreciate some help.

The Question in a mathematical form: Let $^\sharp (A) = m$ and $^\sharp (B) = n$. Proove by induction that $^\sharp (A \times B) = mn$

 

[jedishrfu]

well induction proofs have two parts:
1) select an m and n and proof its true like #A=m=0 and #B=n=0
2) assume there's an n and m that is true
and add an element to the B set which then adds m elements to AxB set right?

 

[ElderBirk]

well induction proofs have two parts:
1) select an m and n and proof its true like #A=m=0 and #B=n=0
2) assume there's an n and m that is true
and add an element to the B set which then adds m elements to AxB set right?

Well, that doesn't really sound right, if $^\sharp (A) = 0$, it means $A = \emptyset$. As far as I understand induction, it has to do with adding our initial assumption to the second assumption and getting to the third assumption. Adding an emptyset doesn't make that much sense.

If I initially start with sets with 1 elements, then assume $^\sharp (A) = m$ and $^\sharp (B) = n$, How can I show if $^\sharp (A) = m +1$ then $^\sharp (A \times B) = mn + n$ without using the fundamental counting principle, which is what I am trying to prove.

 

[jedishrfu]

if you cross the empty set with the empty you get? drum roll please the empty set right?

hence #A is zero and #B is zero and the empty set is zero right?

suppose the A set is the set of vowels and the B set is the consonants and neither set has Y.

#A=5 and #B=20 so #(AxB) = 100 now adding Y to A (its the hidden vowel of english) changes #A to 6

and since AxB means pairing Y with each element of B how many new elements are added to AxB?

Read up on induction there are two parts to the proof:

http://en.wikipedia.org/wiki/Induction_proof

 

[ElderBirk]

if you cross the empty set with the empty you get? drum roll please the empty set right?

hence #A is zero and #B is zero and the empty set is zero right?

suppose the A set is the set of vowels and the B set is the consonants and neither set has Y.

#A=4 and #B=20 so #(AxB) = 80 now adding Y to A (its the hidden vowel of english) changes #A to 5

and since AxB means pairing Y with each element of B how many new elements are added to AxB?

Haha, thanks for the explanation. I love the drum roll part. Anyhow let's get back to the question:

I obviously know and understand what's going on. The problem is showing whatever is happening mathematically. Remember, Duh or an example is not a proof.

So I know that $\emptyset \times \emptyset = \emptyset$. Let's look at the structure of an induction outside of this context.

Let $A = \left\{n \in A | P(n) \right\}$. I want to show if $1 \in A$ and $k \in A$ and $k+1 \in A$ then $A = \mathbb{Z}^+$, where $p(n)$ is the condition for A.

The theory of induction stands on the fact that it starts with one. Showing that $^\sharp (\emptyset \times \emptyset) = 0$ serves no purpose. Other than that, I understand that if I add 1 to m and make it 1+m the total number will be n+nm. But what is the mathematical justification for that, how can I show this without using the fundamental counting principle, since it is what I am trying to prove?