Answer to Question #263432 in Discrete Mathematics for Mao

Question

Determine the cardinality of each of the sets, A, B, and C defined below, and prove the cardinality of any set that you claim is countably infinite.

A is the set of negative odd integers

B is the set of positive integers less than 1000

C is the set of positive rational numbers with numerator equal to 1

Answer 1

Let us determine the cardinality of each of the sets, $A, B,$ and $C$ defined below, and prove the cardinality of any set that we claim is countably infinite.

Recall that the set $X$ is called countably infinite if it has the same cardinality as the set $\N=\{1,2,3,\ldots\}$ of positive integer numbers, that is there is a bijection $f:\N\to X.$

Let $A$ be the set of negative odd integers, that is $A=\{1-2k:k\in\N\}.$ Let us show that the map $f:\N\to A,\ f(n)=1-2n,$ is bijection. If $f(a)=f(b),$ then $1-2a=1-2b.$ It follows that $2a=2b,$ and hence $a=b.$ We conclude that the map $f$ is injection. For any $1-2n\in A$ we have that $f(n)=1-2n,$ and thus the map is surjection. Consequently, $f:\N\to A,\ f(n)=1-2n,$

is bijection, and we conclude that the set $A$ is countably infinite.

Let $B$ is the set of positive integers less than 1000. It follows that the set $A$ contains $999$ elements, and hence $|B|=999.$

Let $C$  is the set of positive rational numbers with numerator equal to 1, that is $C=\{\frac{1}{n}:n\in\N\}.$

Let us show that the map $f:\N\to C,\ f(n)=\frac{1}n,$ is bijection. If $f(a)=f(b),$ then $\frac{1}a=\frac{1}b.$ It follows that $a=b,$ and hence the map $f$ is injection. For any $\frac{1}n\in C$ we have that $f(n)=\frac{1}n,$ and thus the map is surjection. Consequently, $f:\N\to C$ is bijection, and we conclude that the set $C$ is countably infinite.