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.

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search