# One more proof

• Apr 19th 2009, 01:37 PM
zhupolongjoe
One more proof
Prove that for all natural numbers k,m, Nk X Nm is finite.

I know the lemma "for every k belong to N, every subset of Nk is finite", could we just say that Nk X Nm is a subset of Nk, so it is finite....?

The hint is "consider the function f: NkXNm--->Nkm given by f(a,b)=(a-1)m+b. Use the Division Algorithm to show f is a one-to-one correspondence. This is a formal version of the product rule that says the number of elements in NkXNm is km

This makes it more complicated than I thought.
• Apr 19th 2009, 02:02 PM
Plato
I suggest this mapping: $\Phi :N_k \times N_m \mapsto N_{\left( {2^k } \right)\left( {3^m } \right)} \,,\,\Phi (g,h) = \left( {2^g } \right)\left( {3^h } \right)$.
Of course $N_{\left( {2^k } \right)\left( {3^m } \right)} \,$ is finite.
It is easy to show that $\Phi$ is one to one.

Here are theorems that you need to do these sorts of cardinality problems.
T1 There is an injection from A to B if and only if there is a surjection from B to A.

T2 If there is an injection from A to B then the cardinality of A at most the cardinality of B.
i.e. $|A|\le |B|$.

T3 If there is an surjection from B to A then the cardinality of B at least the cardinality of A.
i.e. $|B|\ge |A|$.