Question

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.

a) the integers greater than 10
b) the odd negative integers
c) the integers with absolute value less than 1,000,000
d) the real numbers between 0 and 2
e) the set A×Z+ where A={2,3}

Answer 1

a) Countably infinite

b) Countably infinite

c) Finite

d) Uncountable

e) Countably infinite

Explanation:

a) Let S the set of integers grater than 10.

Consider the following correspondence:

defined by for .

Let's see that the function is one-to-one.

Suppose that f(10+k)=f(10+j) for k≠j. Then k-1=j-1. Thus k-j=1-1=0. Then k=j. This implies that 10+k=10+j. Then the correspondence is injective.

b) Let S the set of odd negative integers

Consider the following correspondence:

defined by .

Let's see that the function is one-to-one.

Suppose that f(-(2k+1))=f(-(2j+1)) for k≠j. By definition, k=j. This implies that the correspondence is injective.

c) The integers with absolute value less than 1,000,000 are in the intervals A=(-1.000.000, 0) B=[0, 1.000.000). Then there is 998.000 integers in A that satisfies the condition and 999.000 integers in B that satifies the condition.

d) The set of real number between 0 and 2 is the interval (0,2) and you can prove that the interval (0,2) is equipotent to the reals. Then the set is uncountable.

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

Consider the following correspondence:

defined by

Let's see that the function is one-to-one.

Consider three cases:

1. , then 2k=2j, thus k=j.

2. , then 2k+1=2j+1, then 2k=2j, thus k=j.

3. , then 2k=2j+1. But this is impossible because 2k is an even number and 2j+1 is an odd number.

Then we conclude that the correspondence is one-to-one.

Niccherip5 and 1 more users found this answer helpful

THANKS

0

5.0

(1 vote)

Still have questions?

FIND MORE ANSWERS

ASK YOUR QUESTION

Explanation:

Answer 2

a) Countably infinite

b) Countably infinite

c) Finite

d) Uncountable

e) Countably infinite

Explanation:

a) Let S the set of integers grater than 10.

Consider the following correspondence:

`f: S\rightarrow \mathbb{Z}^+` defined by
`f(10+k)=k-1` for
`k\in\mathbb{Z}^+/\{0\}`.

Let's see that the function is one-to-one.

Suppose that f(10+k)=f(10+j) for k≠j. Then k-1=j-1. Thus k-j=1-1=0. Then k=j. This implies that 10+k=10+j. Then the correspondence is injective.

b) Let S the set of odd negative integers

Consider the following correspondence:

`f: S\rightarrow \mathbb{Z}^+` defined by
`f(-(2k+1))=k`.

Let's see that the function is one-to-one.

Suppose that f(-(2k+1))=f(-(2j+1)) for k≠j. By definition, k=j. This implies that the correspondence is injective.

c) The integers with absolute value less than 1,000,000 are in the intervals A=(-1.000.000, 0) B=[0, 1.000.000). Then there is 998.000 integers in A that satisfies the condition and 999.000 integers in B that satifies the condition.

d) The set of real number between 0 and 2 is the interval (0,2) and you can prove that the interval (0,2) is equipotent to the reals. Then the set is uncountable.

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

Consider the following correspondence:

`f: S\rightarrow \mathbb{Z}^+` defined by
`f(2,k)=2k, \;f(3,j)= 2j+1`

Let's see that the function is one-to-one.

Consider three cases:

1.
`f(2,k)=f(2,j)`, then 2k=2j, thus k=j.

2.
`f(3,k)=f(3,j)`, then 2k+1=2j+1, then 2k=2j, thus k=j.

3.
`f(2,k)=f(3,j)`, then 2k=2j+1. But this is impossible because 2k is an even number and 2j+1 is an odd number.

Then we conclude that the correspondence is one-to-one.