One-to-One Correspondence of Infinite Sets

Date: 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/