Equivalent Sets

Before proceeding to Main Questions, we denote the set of positive integers {1,2,3,4,5, ...} by N (the natural numbers).

Main Questions:

  1. What is the definition of equivalence of sets: A ~ B?
  2. What is an infinite set?
  3. What is a countable set?
  4. What is an essential property of an infinite set?
N.B. We shall work with subsets of the positive integers
N = {1,2,3,4,5, ...}

Same number of elements -- an approach via functions

One way of showing that two sets, A and B, have the same number of elements, is to constuct a "one to one" and "onto" mapping between them. E.g. with both sets have the same number of elements (3), since there is a "one to one" correspondence
2 <--> 8, 2 <--> 8, 2 <--> 8.
Most of us (including JL) probably used a third set and the one to one correspondence from C to A given by
1 <--> 2, 2 <-->4, 3 <--> 6.
and a similar correspondence from C to B to decide that each set had 3 elements.

Now the sets

have the same number of elements since there is a one to one correspondence from D to E:
1 <--> 2, 2 <--> 3, 3 <--> 4, 4 <-->5, ... .
(The formula is k --> k+1, k = 1,2,3,... .)

Some definitions:

A is equivalent to B (written A ~ B) if
there is a one to one correspondence f: A --> B. (Also called a one to one and onto function f: A --> B; or a bijection f: A --> B.)
The set A is finite if
A is empty or is equivalent to {1,...,n} for some n in N.
The set A is infinite if
A is not finite.
The set A is countable if
A is equivalent to N ( A ~ N).
The set A is uncountable if
A is infinite and not countable.
I quote Alberto Torchinsky (Real Analysis, Addison-Wesley, 1987) on the meaning of A ~ B:
Intuitively, the sets A and B are interchangeable provided we are interested in some property that concern the specific nature of the elements.

Questions:

  1. The set A = {1,2,3,4} is equivalent to B = {14, 85, 2, 9}. What is the bijection f: A --> B?
  2. The set N is equivalent to the set B = {12, 14, 16, 18, ...}. What is the bijection f: N --> B?
  3. The interval (0,1) = { x is a real number,0 < x < 1} is equivalent to the interval (0,2) = { x is a real number, 0 < x < 2}. What is the bijection f: (0,1) --> (0,2)?

Think about:

  1. The set N is equivalent to the set of all positive prime numbers P. Think about why this is so. Can you give the bijection f: N --> P?
  2. Show that N is equivalent to a proper subset of itself.
  3. Any countable set is equivalent to a proper subset of itself.
  4. What is a property of infinite sets which is not shared by finite sets?
  5. Is there an uncountable set of real numbers?

Next up:

Euler's proof that there are infinitely many prime numbers.

N.B. A positive integer p is a prime number if p is not 0 or 1 and if p is divisible only by 1 and p.

Back to Prof. Lewis's LAS 100 home page