Results 1 to 2 of 2

Math Help - One more proof

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    296

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,793
    Thanks
    1688
    Awards
    1
    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|.
    Last edited by Plato; April 19th 2009 at 03:28 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum