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?