One-to-One Correspondence of Infinite SetsDate: 03/26/2001 at 18:27:57 From: Nana Kwame Anokye Subject: Infinite sets and 1-1 correspondence I can pretty much figure out 1-1 correspondence, but I am stuck on tutoring my brother, a senior in college, on whether any two infinite sets of natural numbers can be put in a 1-1 correspondence and how that is possible. Thanks. Date: 03/27/2001 at 15:15:04 From: Doctor Rob Subject: Re: Infinite sets and 1-1 correspondence Thanks for writing to Ask Dr. Math, Nana. Yes, every two infinite sets of natural numbers can be put into one-to-one correspondence. Let the sets be S and T. Since both are infinite, they are nonempty, so each contains a smallest element, call them s1 and t1. Make the correspondence so that s1 corresponds to t1. Let S1 = S - {s1} and T1 = T - {t1}. S1 and T1 are still infinite sets. Repeat this process as often as necessary. Prove that every element n of S or T is included after at most n steps of the process. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/