The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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.


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   
Associated Topics:
College Discrete Math
College Logic
High School Discrete Mathematics
High School Logic
High School Sequences, Series

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.