The different sizes of infinity

Fri 02 September 2016 by TWal

What is infinity? Well, for example, there is an infinite number of integers \(\mathbb{N}^* = \{1,2,3,4,\dots\}\). So, we can say that \(|\mathbb{N}^*| = \infty\) (with \(|A|\) the cardinality of the set \(A\), for example \(|\{2,4,8\}| = 3\)). Is there a set that is bigger than \(\mathbb{N}^*\)? For example, is \(\mathbb{N} = \{0,1,2,3,4,\dots\}\) such a set? It has one more element, so \(|\mathbb{N}| = 1+|\mathbb{N}^*| = 1+\infty\)?

Here, we see that we need a way to say that a set is bigger than another without looking at its cardinal.

Injection, surjection and bijection

Let’s say you are a child and you don’t know how to count. In front of you, you have the digits \(1, 2, 3\) and the letters \(a, b, c, d, e\), and you want to know: do you have more letters than digits?

One way to do it is: for each digit, try to associate it with a letter such that two different digits are associated with two different letters.

1 -> d
2 -> a
3 -> c
     b
     e

It works! This means that the number of digits \(\leq\) the number of letters. Try to do it the other way: you can’t because you have more letters.

What we made here is what we call an injection from the set of our digits to the set of our letters. More formally, an injection from the set \(A\) to the set \(B\) is a function \(f\) such that if \(f(a) = f(b)\) then \(a=b\) (or equivalently, if \(a \neq b\) then \(f(a) \neq f(b)\)).

We note \(A \hookrightarrow B\) if there exists an injection from the set \(A\) to the set \(B\). This means that the set \(A\) is at most as big as the set \(B\).

Another way to do it is: for each letter, try to associate it with a digit such that in the end, each digit was associated with a letter.

a --> 1
c -´
b --> 3
d --> 2
e -´

It works! This also means that the number of letters \(\geq\) the number of digits. Try to do it the other way: again, you can’t.

Here, we made what we call a surjection. A function from set \(A\) to set \(B\) is surjective when for each \(b\) in the set \(B\), there exists \(a\) in the set \(A\) such that \(f(a) = b\) (in other words, each element of \(B\) is “reached” by \(f\))

We note \(A \twoheadrightarrow B\) when there exists a surjection from \(A\) to \(B\). This means that the set \(A\) is at least as big as the set \(B\).

Here, a natural question is: is \(A \hookrightarrow B\) the same as \(B \twoheadrightarrow A\)?

The answer is yes. Let’s take our injection from our digits to our letters and transform it to a surjection from our letters to our digits. Well, reverse the arrows and send the letters not associated with a digit to a random digit, for example \(3\)

1 -> d           1 <--- d
2 -> a           2 <--- a
3 -> c  becomes  3 <--- c
     b              `-- b
     e               `- e

Now, let’s take our surjection from our letters to our digits and transform it to an injection from our digits to our letters. Again, we can reverse the arrows, but there is a problem: we can’t send \(2\) to \(d\) and to \(e\). Well, in this case, simply choose one of those letters.

a --> 1           a <-- 1
c -´c
b --> 3  becomes  b <-- 3
d --> 2           d <-- 2
e -´e

Now, let’s talk about bijections. A bijection is a function that is both an injection and a surjection. An example of a bijection from \(\{1,2,3,4,5\}\) to \(\{a,b,c,d,e\}\):

1 -> c
2 -> e
3 -> b
4 -> a
5 -> d

We note \(A \sim B\) if there exists a bijection from the set \(A\) to the set \(B\). This means that \(A\) is as big as \(B\): they have the same size.

A natural question is: if \(A \hookrightarrow B\) and \(A \twoheadrightarrow B\), can we say that \(A \sim B\)? The problem is that the injective function and the surjective function might not be equal, so it’s not trivial why a bijection would exist. It finally turns out that it’s true: it’s the Cantor–Schröder–Bernstein theorem

Let’s try to find a set bigger than \(\mathbb{N}\)

It’s quite simple to make a bijection from \(\mathbb{N}\) to \(\mathbb{N}^*\), with \(f(n) = n+1\)

0 -> 1
1 -> 2
2 -> 3
...

So \(\mathbb{N}^* \sim \mathbb{N}\)

We tried to add 1 element to an infinite set, and it doesn’t work… What if we add an infinite number of elements to \(\mathbb{N}\)? Is \(\mathbb{Z} = \{\dots,-3,-2,-1,0,1,2,3,\dots\}\) bigger than \(\mathbb{N}\)?

Still, it doesn’t work. One bijection is:

$$f(n) = \begin{cases} 0 &\mbox{if } n=0\\ 2n &\mbox{if } n > 0\\ 2(-n)-1 &\mbox{if } n < 0\end{cases}$$
 0 -> 0
-1 -> 1
 1 -> 2
-2 -> 3
 2 -> 4
...

Let’s try something more brutal: \(\mathbb{N}^2 = \{(n, m) \mbox{ with } n \mbox{ and } m \mbox{ in } \mathbb{N}\}\). We can still make a bijection!

Like this:

\ m  0 1 2 3
n

0    0 2-3 9 ...
     |/ / /  
1    1 4 8
      / /
2    5 7
     |/
3    6

We move along diagonals. Another way to make a bijection from \(\mathbb{N}^2\) to \(\mathbb{N}^*\) like this: \(f(n, m) = 2^n(2m+1)\). It’s injective and surjective because of the prime decomposition of natural numbers. Then we have \(\mathbb{N}^2 \sim \mathbb{N}^* \sim \mathbb{N}\) so \(\mathbb{N}^2 \sim \mathbb{N}\).

So, what about \(\mathbb{N}^m\) with \(m\) an integer? An example with \(m=3\): we can use a bijection from \(\mathbb{N}^2\) to \(\mathbb{N}\) to construct a bijection from \(\mathbb{N}^3\) to \(\mathbb{N}\): \(g(a, b, c) = f(f(a,b), c)\)

What about the set of rational numbers, \(\mathbb{Q}\)? Well, we have \(\mathbb{N} \twoheadrightarrow \mathbb{Z} \times \mathbb{N}^* \twoheadrightarrow \mathbb{Q}\) with \(\mathbb{Z} \times \mathbb{N}^* = \{(n, m) \mbox{ with } n \mbox{ in } \mathbb{Z} \mbox{ and } m \mbox{ in } \mathbb{N}^*\}\), with the surjection from \(\mathbb{Z} \times \mathbb{N}^*\) to \(\mathbb{Q}\): \(f(n, m) = n/m\). And we have \(\mathbb{N} \hookrightarrow \mathbb{Q}\) with \(f(n) = n\), so the Cantor-Schröder-Bernstein theorem shows that \(\mathbb{N} \sim \mathbb{Q}\)

Bigger sets

I will use the notation \(B^A\) for the set of functions from \(A\) to \(B\). It’s a really smart notation in several ways, for example \(|B^A| = |B|^{|A|}\).

The set \(\{0,1\}^{\mathbb{N}}\) is bigger than \(\mathbb{N}\) because there are no surjection from \(\mathbb{N}\) to \(\{0,1\}^{\mathbb{N}}\).

Let f be a function from \(\mathbb{N}\) to \(\{0,1\}^{\mathbb{N}}\), for example:

\(f(0) = \mathbf{1}, 0, 1, 1, 1, 0, \dots\)

\(f(1) = 1, \mathbf{0}, 0, 1, 1, 1, \dots\)

\(f(2) = 0, 1, \mathbf{1}, 0, 1, 1, \dots\)

\(f(3) = 1, 0, 0, \mathbf{1}, 1, 1, \dots\)

\(f(4) = 0, 1, 1, 0, \mathbf{0}, 1, \dots\)

\(\phantom{f()}u = 0, 1, 0, 0, 1, \dots\)

We can show that there is an element of \(\{0,1\}^{\mathbb{N}}\) that is not reached by \(f\). We define \(u \in \{0,1\}^{\mathbb{N}}\) with \(u(0) = 0, u(1) = 1, u(2) = 0, u(3) = 0, u(4) = 1\) (because the numbers on the diagonal are 1, 0, 1, 1, 0), or in general \(u(n) = 1 - f(n)(n)\).

This \(u\) is not reached by \(f\) because if there is an \(m\) such that \(f(m) = u\), we have a contradiction because this implies that \(f(m)(m) = u(m) = 1-f(m)(m)\)! Therefore \(f\) is not a surjection.

This proof is known an Cantor’s diagonal argument. So, we now know that \(\{0,1\}^{\mathbb{N}}\) is bigger than \(\mathbb{N}\). Using the same trick, we can show that \(\mathbb{R}\) is bigger than \(\mathbb{N}\). In fact, \(\mathbb{R} \sim \{0,1\}^{\mathbb{N}}\).

Is there a set bigger than \(\{0,1\}^{\mathbb{N}}\)?

Let’s have a look at the power set: \(\mathcal{P}(A)\) is the set of all subsets of \(A\). For example, \(\mathcal{P}(\{0,1,2\}) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}\). A nice property is: \(|\mathcal{P}(A)| = 2^{|A|}\).

\(\mathcal{P}(A)\) is always bigger than \(A\) because there are no surjection from \(A\) to \(\mathcal{P}(A)\).

Let \(f\) be a function from \(A\) to \(\mathcal{P}(A)\), and consider the set \(L = \{a \mbox{ in } A \mbox{ such that } a \mbox{ is not in } f(a)\}\). \(L\) is a subset of \(A\), and cannot be reached by \(f\) because if we have \(f(a) = L\), then \(a \mbox{ is in } f(a)\) is the same as \(a \mbox{ is in } L\) is the same as \(a \mbox{ is not in } f(a)\): it’s impossible!

For example, with \(A = \mathbb{N}\):

\(f(0) = \{\mathbf{0}, \phantom{1, }2, 3, 4, \phantom{5, }\dots\}\)

\(f(1) = \{0, \phantom{1, 2, }3, 4, 5, \dots\}\)

\(f(2) = \{\phantom{0, }1, \mathbf{2}, \phantom{3, }4, 5, \dots\}\)

\(f(3) = \{0, \phantom{1, 2, }\mathbf{3}, 4, 5, \dots\}\)

\(f(4) = \{\phantom{0, }1, 2, \phantom{3, 4, }5, \dots\}\)

\(\phantom{an}L = \{\phantom{0, }\mathbf{1}, \phantom{2, 3, } \mathbf{4}, \phantom{5, }\dots\}\)

So \(\mathbb{N}\) is smaller than \(\mathcal{P}(\mathbb{N})\) which is smaller than \(\mathcal{P}(\mathcal{P}(\mathbb{N}))\) and so on.

Another way to look at the above proof is by noticing that \(\mathcal{P}(A)\) is very similar to \(\{0,1\}^A\): there is a natural bijection from \(\mathcal{P}(A)\) to \(\{0,1\}^A\):

$$p(S)(x) = \begin{cases} 1 &\mbox{if } x \mbox{ is in } S\\ 0 &\mbox{if } x \mbox{ is not in } S \end{cases}$$

For example, if \(A = \{0, 1, 2, 3, 4\}\) then:

             0  1  2  3  4
{1, 3, 4} -> 0, 1, 0, 1, 1
{0, 3}    -> 1, 0, 0, 1, 0

And like above, we can prove that there is no surjection from \(A\) to \(\{0,1\}^A\), with the same \(u(x) = 1-f(x)(x)\). What does \(u\) represent? What is the set \(p^{-1}(u)\)? Well, \(a \mbox{ is in } p^{-1}(u)\) is the same as \(p(p^{-1}(u))(a) = u(a) = 1\) is the same as \(f(a)(a) = 0\) is the same as \(a \mbox{ is not in } p(f(a))\), so we can say that \(p^{-1}(u)\) is like our previous \(L\).

Aleph and Beth numbers: a new way to talk about infinity

We notice that there is a problem with the symbol \(\infty\): if \(|\mathbb{N}| = \infty\) and \(|\mathcal{P}(\mathbb{N})| = \infty\) then \(|\mathbb{N}| = |\mathcal{P}(\mathbb{N})|\)? This is false since we saw in the previous section that \(\mathcal{P}(\mathbb{N})\) is bigger than \(\mathbb{N}\)!

Beth numbers are defined like this: \(\beth_0 = |\mathbb{N}|\), \(\beth_1 = |\mathcal{P}(\mathbb{N})|\), \(\beth_2 = |\mathcal{P}(\mathcal{P}(\mathbb{N}))|\), and so on. Since \(|\mathcal{P}(A)| = 2^{|A|}\), we have \(\beth_{n+1} = 2^{\beth_n}\).

Aleph numbers are defined like this: \(\aleph_0 = |\mathbb{N}|\), \(\aleph_1\) is the size of the smallest set strictly bigger than \(\mathbb{N}\), \(\aleph_2\) is the size of the smallest set strictly bigger than a set of size \(\aleph_1\), and so on (see here for more information)

We can notice that \(\aleph_0 = \beth_0\) and \(\aleph_1 \leq \beth_1\)

When we proved that \(\mathbb{N} \sim \mathbb{Z} \sim \mathbb{N}^m\), we know that \(\aleph_0 = \aleph_0 + m = m\aleph_0 = \aleph_0^m\) if \(m\) is an integer.

A relation between Aleph and Beth numbers ? About the continuum hypothesis

One question that Cantor asked is: is there a set \(A\) such that \(\mathbb{N} \hookrightarrow A \hookrightarrow \mathbb{R}\) but \(A \not\sim \mathbb{R}\) and \(\mathbb{N} \not\sim A\), in other word: is there an infinity between the one of integers and the one of real numbers? In other words again: do we have \(\aleph_1 = \beth_1\) or \(\aleph_1 < \beth_1\)?

The continuum hypothesis says that no such set exists, in other words \(\aleph_1 = \beth_1\), but Cantor didn’t know if it was true or false.

Gödel showed in 1940 that it is not false, and Cohen showed in 1963 that it is not true. “What does this mean? Either something is true or is false!” you may ask. Let me explain: in mathematics, there are axioms, which are the ground truth, and we prove theorems using these axioms. The sets of axioms used are usually ZFC, and Gödel showed that ZFC cannot show that the continuum hypothesis is false, and Cohen showed that ZFC cannot show that the continuum hypothesis is true.

We can generalize the continuum hypothesis, by saying “There is no infinity between \(\mathbb{N}\) and \(\mathcal{P}(\mathbb{N})\), neither between \(\mathcal{P}(\mathbb{N})\) and \(\mathcal{P}(\mathcal{P}(\mathbb{N}))\) and so on. In other words: \(\mbox{for every integer }n, \aleph_n = \beth_n\) (to be correct, for every ordinals). Again, ZFC cannot prove whether this is true or false.

Fun results

We have \(\mathbb{R}^{\mathbb{N}} \sim \mathbb{R}\) because \(\mathbb{R}^{\mathbb{N}} \sim (\{0,1\}^{\mathbb{N}})^{\mathbb{N}} \sim \{0,1\}^{\mathbb{N} \times \mathbb{N}} \sim \{0,1\}^{\mathbb{N}} \sim \mathbb{R}\) (we use the fact that \(\{0,1\}^{\mathbb{N}} \sim \mathbb{R}\) and \(\mathbb{N} \sim \mathbb{N}^2 = \mathbb{N} \times \mathbb{N}\)). Each \(\sim\) requires a regular proof, but this shows the power of the notation \(B^A\)

This means that \(\beth_1^{\beth_0} = \beth_1\). We can also find it like this: \(\beth_1^{\beth_0} = (2^{\beth_0})^{\beth_0} = 2^{\beth_0^2} = 2^{\beth_0} = \beth_1\) (remember that \(\aleph_0 = \beth_0\))

If we note \(\mathcal{C}^0(\mathbb{R}, \mathbb{R})\) the set of continuous functions from \(\mathbb{R}\) to \(\mathbb{R}\), we have a more surprising result: \(\mathcal{C}^0(\mathbb{R}, \mathbb{R}) \hookrightarrow \mathbb{R}^{\mathbb{Q}} \sim \mathbb{R}^{\mathbb{N}} \sim \mathbb{R}\) and obviously \(\mathbb{R} \hookrightarrow \mathcal{C}^0(\mathbb{R}, \mathbb{R})\) (using constant functions), so \(\mathcal{C}^0(\mathbb{R}, \mathbb{R}) \sim \mathbb{R}\)!


Quine and narcissist: how does it work?

Sat 30 July 2016 by TWal

Quines and narcissists are quite useless, but I find them quite interesting. A quine is a program that prints its own source code, and a narcissist is a program that recognizes its own source code.

Quine

With Python

Let’s see how we can write a quine in Python with ...

read more

Programming in Brainfuck: Part 3 — Using a preprocessor

Thu 30 June 2016 by TWal

Here are the corrections for the exercises of part 2:

Compute the sum of an array:

[Tape: zero data1 flag1 ... datan flagn sum zero]
>+++>+>+++++>+>++++>+>++++++>+>> initialize array
<< [  loop on the array
    - clear the current flag
    < [ 
        > >>[>>]< go to sum
        + add 1
        <[<<]< go back to the current data
        - remove 1
    ]
    >+ set the current ...
read more

Programming in Brainfuck: Part 2 — Arrays

Sat 28 May 2016 by TWal

Here are the corrections for the exercises of part 1:

Test if all characters are the same:

Tape: nb char otherchar temp flag
>+++++++[-<+++++++>] initialise nb to 49 ("1")
>> , [<+<+>>-] read in temp and  move to char and otherchar
< [ while otherchar
    >>+ set else flag
    <<< [->->+<<] check equality and keep the value in temp ...
read more

Programming in Brainfuck: Part 1 — Common patterns & conditions

Sun 24 August 2014 by TWal

Here are the corrections for the exercises of part 0:

To print “Brainfuck” followed by a new line, here is a solution:

The ASCII codes are: 66 114 97 105 110 102 117 99 107 10
++++++++++[>+++++++>+++++++++++>++++++++++>++++++++++>+<<<<<-]   setup the memory like this: 0 70 110 100 100 10
>----.>++++.>---.>+++++.<<----.>>---.<<+++++++.>++.++++++++.>>.  print "Brainfuck"

To ...

read more

Programming in Brainfuck: Part 0 — Introduction

Wed 20 August 2014 by TWal

I love brainfuck. I’m amazed by what we can do with only eight instructions. I learned almost everything I know on this language by myself because I didn’t find any tutorial that teach in-depth how to program in brainfuck.

I decided to change this and to make my ...

read more