29 - More examples of countable sets

!Screenshot 2023-11-16 at 3.21.25 PM.png
!Screenshot 2023-11-16 at 3.39.14 PM.png!Screenshot 2023-11-16 at 3.39.23 PM.png

HW 29

Ben Finch

E 29.1

Case 1: Both $A$ and $B^{\prime }$ are finite

If both $A$ and $B^{\prime }$ are finite, then there exist natural numbers $n$ and $m$ such that $A=\{a_1,a_2,\dots ,a_n\}$ and $B^{\prime }=\{b_1,b_2,\dots ,b_m\}$. The union $A\cup B^{\prime }$ will then be the set of all these elements, which is a finite set of size at most $n+m$. A finite set is by definition countable, so $A\cup B$ (which is equal to $A\cup B^{\prime }$) is countable.

Case 2: One of $A$ and $B^{\prime }$ is finite and the other is countably infinite.

Without loss of generality, assume that $A$ is finite and $B^{\prime }$ is infinite. Then we can list the elements of $A$ as $A=\{a_1,a_2,\dots ,a_n\}$ and the elements of $B^{\prime }$ can be listed as $B^{\prime }=\{b_1,b_2,b_3,\dots \}$. The union $A\cup B^{\prime }$ will be the set of all these elements. Since $B^{\prime }$ is already countably infinite, we can create a new list that includes all elements of $A$ followed by all elements of $B^{\prime }$. In other words, we can create the list $a_1,a_2,\dots ,a_n,b_1,b_2,b_3,\dots$.

Thus if $A$ and $B$ are countable sets, then $A\cup B$ is countable. $◻$

E 29.2
We construct a bijective function $f:\mathbb{N}\to \{0,1\}\times \mathbb{N}$. Define it by:

This function assigns every even natural number to an element in the set with the first component 0, and every odd natural number to an element in the set with the first component 1. This function is bijective, so $|\mathbb{N}|=\{0,1\}\times \mathbb{N}|$. Thus $\{0,1\}\times \mathbb{N}$ is countably infinite.

E 29.3
In 29.3, it was proved that if $A$ and $B$ are countably infinite sets, then $A\times B$ is also countably infinite. We now prove that if $A$ and $B$ are countable sets, then $A\times B$ is as well. There are two remaining cases

One of $A$ or $B$ is finite and the other is countably infinite. Without loss of generality, assume $A$ is finite and $B$ is countably infinite. If $A$ has $m$ elements and $B$ is countably infinite, then each element of $A$ can be paired with all elements of $B$, resulting in $m$ separate listings of a countably infinite set. This can be visualized as $m$ rows, each corresponding to an element of $A$, and columns corresponding to elements of $B$. Since a finite union of countable sets is countable, $A\times B$ is countable.

Both $A$ and $B$ are finite. If both sets are finite, with $A$ having $m$ elements and $B$ having $n$ elements, then their Cartesian product will have $m\times n$ elements, which is a finite number. Hence, $A\times B$ is countable.

Thus if $A$ and $B$ are countable sets, then $A\times B$ is as well.

E 29.4

a) Let $A_1,A_2$, . . . be arbitrary sets. Let $B_1=A_1$, and for each $n\ge 1$ let $B_{n+1}=B_n\times A_{n+1}$. Assume that all of the $A_i$ are countable. We work by induction

Base Case: For $n=1$, $B_1=A_1$ which is given to be countable.

Inductive Step: Assume for some $k\ge 1$ that $B_k$ is countable. We aim to show $B_{k+1}$ is countable. We know $B_{k+1}=B_k\times A_{k+1}$. Since $B_k$ is countable by the inductive hypothesis, and $A_{k+1}$ is countable by assumption, by Theorem 29.3, the Cartesian product of two countable sets is also countable. We can show this by constructing a bijection from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$, like Cantor's grid, and then using this bijection to pair elements from $B_k$ and $A_{k+1}$ to the natural numbers.

Hence, by induction, $B_n$ is countable for each $n\in \mathbb{N}$.

b) Describe a bijective function $f:A_1\times A_2\times A_3\to (A_1\times A_2)\times A_3=B_3$, and prove its bijectivity.

Consider the function $f(a_1,a_2,a_3)=((a_1,a_2),a_3)$.

To show injectivity, assume $f(a_1,a_2,a_3)=f(a_1^{\prime },a_2^{\prime },a_3^{\prime })$. Then $((a_1,a_2),a_3)=((a_1^{\prime },a_2^{\prime }),a_3^{\prime })$. By definition of ordered pairs, this means $a_1=a_1^{\prime }$, $a_2=a_2^{\prime }$, and $a_3=a_3^{\prime }$, so $(a_1,a_2,a_3)=(a_1^{\prime },a_2^{\prime },a_3^{\prime })$.

To show surjectivity, for any element $((a_1,a_2),a_3)\in B_3$, there exists an element $(a_1,a_2,a_3)\in A_1\times A_2\times A_3$ such that $f(a_1,a_2,a_3)=((a_1,a_2),a_3)$.

Hence, $f$ is bijective. $◻$

(c) Prove that if $A_1,A_2,A_3$ are countable, then the set $A_1\times A_2\times A_3$ is countable.

We already proved in exercise 29.3 that if $A$ and $B$ are countable sets, then $A\times B$ is as well. Thus, by extension, we can consider the Cartesian product of $A_1$ and $A_2$, denoted $A_1\times A_2$, which is countable by this previous result.

Now, since $A_1\times A_2$ is countable and $A_3$ is countable, we can apply the same reasoning to $(A_1\times A_2)\times A_3$. This set is the Cartesian product of two countable sets, and by the result from exercise 29.3, it is also countable.

Hence, $A_1\times A_2\times A_3$ is countable. $◻$

E 29.5
By Corollary 29.7, $\mathbb{Q}$ is countably infinite. By Theorem 29.3, $\mathbb{Z}\times \mathbb{N}$ is countably infinite, since both $\mathbb{Z}$ and $\mathbb{N}$ are countably infinite. Therefore, $|\mathbb{Z}\times \mathbb{N}|=|\mathbb{Q}|$. $◻$

E 29.6

Review the diagram above. We see that there is a systematic way to list the items in the union with no repeats in a specific order. Thus ${\cup }_{i=1}^{\mathrm{\infty }}{A}_i$ is countably infinite.

E 29.7
To prove that the set containing all finite sets of $\mathbb{N}$ is countably infinite, we will form a bijection between $\mathbb{N}$ and this set.

First, list all finite subsets of $\mathbb{N}$, first based on size and then by their least element. For example, start with the empty set, then all single-element subsets, then all two-element subsets, and so on.

We can now represent each element in this set with a natural number using binary form such that the $i$-th digit is 1 if i is in the subset and 0 otherwise. For example, the set {1, 3} can be represented by the binary number 101. Then we can convert that binary number (base 2) to a natural number in base 10 (the example of 101 being 5).

So, we have mapped each finite subset with a unique natural number and vice versa. This establishes a bijection between the set of all finite subsets of $\mathbb{N}$ and $\mathbb{N}$ itself. Therefore, this set and $\mathbb{N}$ have the same cardinality.

Hence, the set containing all finite sets of $\mathbb{N}$ is countably infinite. $◻$