Is Maybe Int More Expressive Than Int in Set Thoery?

This question seems intuitively and undoubtedly correct as long as you have used Maybe Int in your code. The first brief glance brings us that Maybe Int has 1 additional case more than Int as the former could present Nothing but the latter cannot. Hence, the Maybe Int is more expressive than Int.

In this blog, I will try to figure out the anwser with set theory knowledge. However, I should acknowledge the set theory could not solve this question, which might lead you a bit more confusing after reading this blog. It's wrote down to reflect how I thought the problem.

What does the Expressive Mean?

When we talks about 'expressive', what are we talking about? The degree of 'expreesive' is evalueated accroding the number of whole set. If a set(A) is larger than another(B), we are talking about the total number of A is more than B's.

As a result, from the set theory view, the number refers to cardinality.

Simple Explaination on Maybe Int

Propose sets $I$, $N$, and $M$: $$\begin{align*} &I = \text{Int} \\ &None = \{\text{Nothing}\} \\ &M = I \cup None \end{align*}$$ It satisfies the definition of Maybe Int in haskell:

Maybe Int = Nothing | Just Int

Propose that Int is a finite set in Haskell, as it indeed in most system $\lvert I \rvert = 2^{32}-1$ according to the gmp library ref.

The result of $\lvert M \rvert - \lvert I \rvert$ could be simply calculated as $\lvert I \cap N \rvert = 0$. $$\begin{align*} & \lvert M \rvert - \lvert I \rvert \\ &= \lvert I \rvert + \lvert None \rvert - \lvert I \rvert \\ &= 1 \end{align*}$$

Hence, we could say because the cardinality of Maybe Int is larger than Int, we conclude the former is more expressive because it could express the case that the latter cannot. In other word, there is no Nothing case in a finite Int set.

The Underlying Weakness of Deduction

Everything is happy since now, but if we entend the premise a lot, we could see a huge problem emgerges from it. Here I'd like to quote the prodigious physicalist Richard Feynman:

Tip

Mathematicians are only dealing with the structure of reasoning, and they do not really care what they're talking about. They just want to know if it's true. They want to know if you can prove there is some structure of reasoning that will apply to the n-dimensional case.

Now propose the $I$ is no longer a finite set, it were a infinite set as $N = { ..., -1, 0, 1, ...}$. Even though the computer couldn't express the infinite types, it's still reasonable to take this assumption.

With the premise of infinite $I$, is the preceding conclusion true here? The anwser is no, there is no differences between an infinite set and the set with another additional element.

More precisely, let $I$ is an infinite integer set $N$: $$\begin{align*} & I = \text{N} \\ & None = \{ \text{Nothing} \} \\ & M = I \cup N \end{align*}$$ The result of $\lvert M \rvert - \lvert I \rvert$ is 0 now and it breaks our conclusion when $I$ is finite. The calculation might be anti-intuisive, so let's learn some infinite sets firstly.

Infinite Sets

I have learned some here which reveals some basic concepts about infinite sets.

Finite sets have exact cardinality, however, infinite sets don't. Hence, we use aleph numbers, represented by the Hebrew letter $\aleph$, to represent the cardinality (or size) of infinite sets that can be well-ordered. The $\aleph_0$ is defined to represent to be the cardinality of the natural numbers, which is a certain infinite "number". Note that $\aleph_0$ is infinite, so it's rather a infinite quantity than inifinite number.

We can tell whether two finite sets have same size easily because we simply compare the total number of whole elements.

But the whole elements number of an infinite set could not be listed, how could we compare the sizes when the $\aleph$ are infinite quantities which couldn't be compared.

How to Compare Cardinalities of Infinite Sets

We choose to construct bijection between two sets, if we could establish such kind of ONE-TO-ONE CORRESPONDANCE, essentially we pair up every element in the first set with an element in the second set so that every number in each set is paired with one and only one other number in the other set.

If we can establish a one-to-one correspondence between two sets, then we have proved that the two sets have the same cardinality.

Then, I put some conclusions for the common infinite sets. i

$$\begin{align*} & \lvert N \rvert = \lvert \mathbb{Z}^* \rvert = \lvert Z \rvert = \lvert Q \rvert = \aleph_0 \\\ & \lvert R \rvert = \aleph_1 \end{align*}$$

The Weakness Inside Conclusion in Finite Integer Set

After learning how to compare cardinalities of infinite sets, let's go back to check the cardinalities of $M$(Maybe Int) and $I$ when $\lvert I \rvert = \aleph_0$. You could quickly found that it's same question to compare $\lvert \mathbb{Z} \rvert$ and $\lvert \mathbb{Z}^* \rvert$.

have the same cardinality since there exists a bijection between them, a possible one is:

$$f(x) = \begin{cases} \frac{n-1}{2} & \text{when } n \text{ is odd}, \\\ -\frac{n}{2} & \text{when } n \text{ is even}. \end{cases}$$

Then we suddenly find that: the cardinalies of $M$ and $I$ are same! Hence, there is no such concepts of expressive if we see Maybe Int from the set theory. Now there is a big problem waiting for us!

Even though our assumption of $\lvert I \rvert = \aleph_0$ is wrong in computer worlds, the $String$ set still makes sense. The failure of explaination denotes we need more powerful math tool to understand and explain it.

Conclusion

The Maybe could not only be treated as a simple set of $None$ and $I$, but also owns more features. It implies even though set theory could not solve the question, there could be a new math tool to help.

The next passage will introduce the new math tools and try to give a persuasive anwser.