Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is my proof correct?

  1. Sep 12, 2011 #1
    Suppose that f is a one-to-one correspondence between two sets X and Y. Prove that if X is finite, then Y is finite too.

    my proof: I've already proved that if X is infinite, then Y is infinite too. since f is a one-to-one correspondence, f-1: Y->X exists and by applying the same theorem it can be shown that if f:X->Y and Y is infinite, then X is infinite as well.so, I can claim that if f is a one-to-one correspondence, then X is infinite if and only if Y is infinite. hence, It's possible to say that if f is a one-to-one correspondence between the two sets X and Y, then X is finite if and only if Y is finite.
    Is my proof correct?
     
  2. jcsd
  3. Sep 12, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, your proof is correct (once you know that infinite = not-finite). Though, it might not be the shortest proof available. That is, that you proved it by making use of infinite sets is suprising.
     
  4. Sep 12, 2011 #3
    Actually It's because the book I'm studying from uses Dedekind's definition of an infinite set that a set is infinite iff there is a one-to-one correspondence between the set and a subset of the set. and then it defines a finite set as a set that is not infinite.so, I tried to stay faithful to the definitions that my book suggests. surely there is a shorter way of proving this using the other definition that says a set A is finite iff it's in one-to-one correspondence with Nk. then I can say X~Nk and X~Y, hence Y~Nk. I guess you meant I could use the second approach and It would be shorter. Is that you what you mean?
     
  5. Sep 12, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Aah, that explains things!! Yes, when working with Dedekind-finite things then you need to do it the way you do it.
    Also remark that Dedekind-finite is not the same as finite in the other definition. You need the axiom of choice for that. So it's best to stay close to the definitions!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook