Determine whether each of these sets is finite, countably infinite, or uncountable. For those that are countably infinite, exhibit a one-to-one correspondence between the set of positive integers and that set

As usual, let’s review the definitions before starting to solve the exercise.

Definition: “The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.”

Definition: “A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable. When an infinite set S is countable, we denote the cardinality of S by א0 (where א is aleph, the first letter of the Hebrew alphabet). We write |S| = א0 and say that S has cardinality “aleph null.”

Both definitions were taken from the textbook Discrete Mathematics and its Applications by Rosen.

Now, using the definitions above, let’s solve the exercise.

Table of Contents

a) the integers greater than 10

This set is countably infinite.

The one-to-one correspondence can be specified as follow:

f(x) = x – 10

You can easily prove that the above function is a one-to-one correspondence. First, you prove that the function is one-to-one (see an example here). Secondly, you show that the function is onto (see an example here).

Another way to show the correspondence is by listing the set in a sequence as follows:

11, 12, 13, 14, 15, …

b) the odd negative integers

The set is countably infinite.

-1, -3, -5, -7, …

c) the integers with absolute value less than 1,000,000

The set is finite.

Notice that because the elements of the set are the ones with absolute values less than 1 million, it is the same that the set of integers from 0 to 1 million. Therefore, it is a finite set.

d) the real numbers between 0 and 2

Uncountable.

e) the set A×Z+ where A={2,3}

Countably infinite.

If A=(2,3), then AxZ+={(a,b)| a∈{2,3} ^ b ∈Z+}.

The one-to-one correspondence can be specified as follows:

(2,1) —- 1

(3,1) —- 2

(2,2) —- 3

(3,2) —– 4

….

f) the integers that are multiples of 10

Countable infinite.

You can list the elements of the set as follow:

10, -10, 20, -20, 30, -30, 40, -40, …

Related posts: