Countability and Computability

We have been counting finite objects and now we will move on to infinite objects. Notice that we rely a lot on the notion of bijections as a way to show that two sets have the same cardinality, i.e., if we can show a bijection $f: A \rightarrow B$ , then $|A| = |B|$ as a result. This concept in fact extends to infinite sets naturally.

Example 30

The set ${\mathbb N} = \{0,1,\ldots\}$ and $2 {\mathbb N} = \{0,2,4,\ldots \}$ have the same cardinality.

Proof:

Define the function $f(n) = 2n$ . Notice that this mapping is a bijection $f: {\mathbb N} \rightarrow 2 {\mathbb N}$ .

Notice that it might be tempting to say that ${\mathbb N}$ is clearly bigger than $2{\mathbb N}$ (since in particular is a superset!), but the behavior of infinite is not as obvious as the finite one. A bijection is a definite and undeniable proof that they have the same cardinality. The next example is a bit less obvious.

Example 31

The set ${\mathbb N}$ and ${\mathbb Z}$ have the same cardinality.

Proof:

Define

f(n) = \begin{cases} n/2, & \text{if $n$ is even }\ \\ -(n+1)/2, & \text{otherwise} \end{cases}

This is a mapping from ${\mathbb N}$ to ${\mathbb Z}$ . To prove that it is one-to-one, suppose $f(a) = f(b)$ (we will need to argue that this would imply $a=b$ ), there are three cases to analyze:

If $a$ and $b$ are even, then we have $a/2 = b/2$ and therefore $a=b$ .
If both $a$ and $b$ are odd, it is similar to the above case.
Finally, if $a$ and $b$ have different parities, let us consider the case when $a$ is even and $b$ is odd (the other case is symmetric). Then we have $a/2 = -(b+1)/2$ which implies that $a= -(b+1)$ . This means that $a$ is a negative integer, which is impossible.

To argue that $f$ is onto, consider an integer $m \in {\mathbb Z}$ . If $m$ is non-negative, then $f(2m) = m$ . If $m$ is negative, then we have $f(-2m-1) = m$ .

Countability and Computability

📄️ Countable sets

📄️ Diagonalization

📄️ Computability