Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.28

28.  Show that the union of two countable sets is countable.

Solution: We assume that A and B are two countable sets.
We will consider following cases.
Case 1:
If bothA and B are finite, then A\cup B is finite and hence countable.
Case 2:
We assume that one of A and B is finite and the other is countable infinite. We assume without loss of generality that A is finite.
Since B is countably infinite, there exists a function
f:B \rightarrow \mathbb{Z^+}
This is a one-to-one correspondence, that is,
f(b_i)=i
For b_i \epsilon B and i \epsilon \mathbb{Z^+}
Let us consider
C=A-B
Thus,
A \cup B = B\cup C
If C= Ø
Then A \cup B = B
This is countably infinite.
Therefore, we assume that C\neq Ø
Also we suppose that
C=\left \{ c_1,c_2,...,c_n \right \}
We consider the function
g:B \cup C \rightarrow \mathbb{Z^+}
Where g(c_j)=j
And g(b_i)=n+i
Clearly, g is one-to-one and onto.
Thus,B \cup C is countable.
But B \cup C = A \cup B
So, A \cup B is countable.
Case 3:
We suppose that both A and B are infinite and A\cap B= Ø
Since A and B are both countable, there exist functions
p:\mathbb{Z^+} \rightarrow A
q:\mathbb{Z^+} \rightarrow B
These are one-to-one correspondences.
We also consider the function
r:\mathbb{Z^+} \rightarrow A \cup B
Where r(n)=p\left ( \frac{n}{2} \right )
If n is even
And r(n)=q\left ( \frac{n+1}{2} \right )
If n is odd
Since p,q are one-to-one, so r is also one-to-one.
Similarly, since p,q are onto, so r is also onto.
Therefore, r is a one-to-one correspondence, and hence,r is countable.
Case 4:
We suppose that both A and B are infinite and A \cap B= Ø
We assume that C=B-A
Then,
A \cup B= A \cup C
And
A \cap C= Ø
If C is countably infinite, then
A \cup B= A \cup C
Is countable by the previous case
If C is finite, then
A \cup B= A \cup C
Is countable by case 2
Therefore, A \cup B is countable.

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.27

27. Show that the set of all numbers of the form a+b\sqrt{2} where a and b are integers, is countable.

Solution: We shall first prove a proposition.
We assume that A is a non-empty set. Then the following are equivalent.
(a) A is countable
(b) there exists a surjection f: \mathbb{Z^+} \rightarrow A
(c) there exists an injection g: A \rightarrow \mathbb{Z^+}

Proof
(a) \Rightarrow (b)
If A is countably infinite, then there exists a bijection
f: \mathbb{Z^+} \rightarrow A
And then (b) follows
If A is finite, then there is a bijection
h:\left \{ 1,...,n \right \} \rightarrow A
For some n
Then the function f: \mathbb{Z^+} \rightarrow A defined by
f\left (i \right )=\left\{\begin{matrix} h\left (i \right ) & 1\leq i \leq n\\ h\left (n \right ) & i> n \end{matrix}\right.
Is a surjection
(b) \Rightarrow (c)
We assume that f: \mathbb{Z^+} \rightarrow A is a surjection. We claim that there is an injection g: A \rightarrow \mathbb{Z^+}
To define g we note that if
a\epsilon A
Then
f^{-1}(\left \{a \right \})\neq \phi
Hence, we set
g(a)=min f^{-1}(\left \{a \right \})
Now we note that if
a \neq a'
Then
f^{-1}(\left \{ a \right \})\bigcap f^{-1}(\left \{ a' \right \})=\phi
Implies
min f^{-1}(\left \{ a \right \})\neq min f^{-1}(\left \{ a' \right \})
Hence
g(a)\neq g(a')
And g: A \rightarrow \mathbb{Z^+} is an injection
(c) \Rightarrow (a)
We assume that g: A \rightarrow \mathbb{Z^+} is an injection. We want to show that A is countable.
Since
g:A \rightarrow g(A)
Is a bijection and
g(A)\subset \mathbb{Z^+}
That is, the subset of a countable set is countable.
So, A is countable.
This ends the proposition.
We now show that the set of all numbers of the form a+b\sqrt{2} where a,b are integers, is countable.
By the above proposition it suffices to construct an injective function
f:\mathbb{Z^+}\times \mathbb{Z^+} \rightarrow \mathbb{Z^+}
We define it as
f(a,b)=2^a3^b
We assume that
2^a3^b=2^c3^d
If
a<c
Then
3^b=2^{c-a}3^d
The left side of this equality is an odd number where as the right side is an even number implying
a=c
And
3^b=3^d
Then also
b=d
Hence, f is injective and so set of all numbers of the form a+b\sqrt{2} where a,b are integers, is countable.

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.26

26. Show that the set of all rational numbers of the form n/5, where n is an integer, is countable.

Solution:

We have to show that the set of all rational numbers of the form n/5 where n is an integer, is countable.
We shall first prove a proposition.
We assume that A is a non-empty set. Then the following are equivalent.
(a) A is countable
(b) there exists a surjection f: \mathbb{Z^+} \rightarrow A
(c) there exists an injection g: A \rightarrow \mathbb{Z^+}

Proof
(a) \Rightarrow (b)
If A is countably infinite, then there exists a bijection
f: \mathbb{Z^+} \rightarrow A
And then (b) follows
If A is finite, then there is a bijection
h:\left \{ 1,...,n \right \} \rightarrow A
For some n
Then the function f: \mathbb{Z^+} \rightarrow A defined by
f\left (i \right )=\left\{\begin{matrix} h\left (i \right ) & 1\leq i \leq n\\ h\left (n \right ) & i> n \end{matrix}\right.
Is a surjection
(b) \Rightarrow (c)
We assume that f: \mathbb{Z^+} \rightarrow A is a surjection. We claim that there is an injection g: A \rightarrow \mathbb{Z^+}
To define g we note that if
a\epsilon A
Then
f^{-1}(\left \{a \right \})\neq \phi
Hence, we set
g(a)=min f^{-1}(\left \{a \right \})
Now we note that if
a \neq a'
Then
f^{-1}(\left \{ a \right \})\bigcap f^{-1}(\left \{ a' \right \})=\phi
Implies
min f^{-1}(\left \{ a \right \})\neq min f^{-1}(\left \{ a' \right \})
Hence
g(a)\neq g(a')
And g: A \rightarrow \mathbb{Z^+} is an injection
(c) \Rightarrow (a)
We assume that g: A \rightarrow \mathbb{Z^+} is an injection. We want to show that A is countable.
Since
g:A \rightarrow g(A)
Is a bijection and
g(A)\subset \mathbb{Z^+}
That is, the subset of a countable set is countable.
So, A is countable.
This ends the proposition.
We define the function
f:\mathbb{Z} \times \mathbb{Z^+}\rightarrow \mathbb{Q}
As
f(n,5)=n/5
Since each rational number is of the form n/5 for some n \epsilon \mathbb{Z}, it follows that f is surjective.
Since \mathbb{Z} \times \mathbb{Z^+} is countably infinite, that is, the Cartesian product of countable sets is countable, it follows from part (b) of the above proposition and replacing \mathbb{Z^+} by an arbitrary countably infinite set (using composition of functions), that rational numbers of the form n/5 is countable.

 

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.25

25. Show that the set of all integers greater than -100 is countable.

Solution: In order to prove that the set of all integers greater than -100 is countable, it suffices to prove that the set of integers \mathbb{Z} is countable. This follows from the fact that the subset of a countable set is countable.

We can the list the integers in a sequence
0,1,-1,2,-2,3,-3,…
We define a function
f:\mathbb{N} \rightarrow \mathbb{Z}

This is defined as
f(n)=\left\{\begin{matrix} \frac{n}{2}&\text{n is even} \\ \frac{-(n-1)}{2}& \text{n is odd}\end{matrix}\right.

We now show that f is a bijection.
First we show that it is injective by case analysis on the parity of \mathbb{N}
Case 1
If m,n are two even natural numbers
Then
f(m)=\frac{m}{2}
f(n)=\frac{n}{2}
It follows that
f(m)=f(n)
Implies that
m=n
Case 2
If m,n are two odd natural numbers
Then
f(m)=-\frac{m-1}{2}
f(n)=-\frac{n-1}{2}
It follows that
f(m)=f(n)
Implies that
m=n
Therefore f is injective.
We now show that f is surjective by case analysis on the sign of some integer t in \mathbb{Z}
Case 1
If t is positive, then t will appear in an even position in the sequence.
Thus,
f(2k)=\frac{2k}{2}
=t
With
t=k
This implies that for every positive value t in \mathbb{Z} there is a natural number 2k
Case 2
If t is negative, then t will appear in an odd position in the sequence.
Thus,
f(2k-1)=-\frac{(2k-1)-1}{2}
=t
With
t=-k
This implies that for every negative value t in \mathbb{Z} there is a natural number 2k-1
Therefore, f is surjective
Hence, \mathbb{Z} is countable set.
Now we define the sequence
a_n=n-100
>-100
For n \in \mathbb{N}
This is clearly a subset of \mathbb{Z} and so is countable.