On Infinity and Computability

Introduction

I’ve been thinking about the ability to model the Universe as a whole for about 10 years, and over the last few weeks, this thinking became rigorous, and today, I proved a formal result after reading my absolute favorite book on mathematics, Mathematical Problems and Proofs. Specifically, the text introduces Dedekind’s definition of an infinite set, which is that a set is infinite if it can be put into a one-to-one correspondence with one of its proper subsets. I then realized two things: (1) we can use Dedekind’s definition of infinity to ask whether a finite volume of space could contain a machine capable of predicting the behavior of the entire Universe and (2) that Dedekind’s definition of infinity is equivalent to an intuitive definition of infinity where a number is infinite if and only if it is greater than all natural numbers.

Predicting the Behavior of the Universe

Assume that we have a machine $M$ such that the output tape of $M(t)$ contains the state of the Universe at time $t+1$ . That is, if we look at the output tape of $M$ at time $t$ , we will see a complete and accurate representation of the entire Universe at time $t+1$ , essentially predicting the future. It turns out we get very different answers depending upon whether we assume $M$ is within the Universe, or outside the Universe. This is plainly a thought experiment, but the case where $M$ is within the Universe is not, and has clear physical meaning, and so it is a serious inquiry. The plain conclusion is that we cannot realistically predict the behavior of the Universe as a whole, completely and accurately, absent what are unintuitive consequences discussed below.

Case 1: $M$ is within the Universe. Because the machine is within the Universe, it must be the case that the output tape for $M(t)$ contains a complete and accurate representation of both the internal state of $M$ at time $t+1$ , and the output tape at time $t+1$ . We can represent this as $M(t) = \{U(t+1), M_{internal}(t+1), M_{tape}(t+1)\}$ , where $U$ is the state of the Universe excluding $M$ , $M_{internal}$ is the internal state of $M$ , and $M_{tape}$ is the output tape of $M$ .

However, $M_{tape}(t+1) = M(t+1) = \{U(t+2), M_{internal}(t+2), M_{tape}(t+2)\}$ , which means that the output tape at time $t$ given by $M(t)$ , must also contain the output tape for $M(t+1)$ . This recurrence relation does not end, and as a consequence, if we posit the existence of such a machine, the output tape will contain the entire future of the Universe. This implies the Universe is completely predetermined.

Case 2: $M_{internal}$ is within the Universe, though $M_{tape}$ is simply no longer required. Removing the requirement to represent the output tape is just to demonstrate that we still have a serious problem even in this case. Because we’re assuming the output tape does not need to contain a representation of its own output, this solves the recurrence problem, and so $M(t) = \{U(t+1), M_{internal}(t+1)\}$ .

However, it must be the case that the total information on the output tape equals the total information in the Universe, since the output tape contains a complete and accurate representation of the Universe excluding the machine, and a complete and accurate representation of the internal state of the machine, which together is the entire Universe. Therefore, it must be the case that the Universe, and the output tape, which is within the Universe, must contain the same amount of information. Using Dedekind’s definition of infinity, it must be the case that the Universe and the machine contain an infinite amount of information. Because UTMs contain a finite amount of information, we are still stuck with a non-computable Universe.

Case 3: $M$ is outside the Universe, or the entire output tape is outside the Universe. In this case we can have a computable Universe that is in essence modeled or represented, respectively, by a copy of the Universe, that is housed outside of the Universe. Note that because in this case the output tape is always outside the Universe, it does not need to contain a representation of itself, solving the recurrence problem in Case 1. Further, because the output tape is outside the Universe, it can hold the same finite amount of information as the Universe, solving the Dedekind-infinite issue in Case 2.

The point is not that any of these cases are realistic, and instead, the point is that none of these cases are realistic, yet these are the only possible cases. The conclusion is therefore, that there doesn’t seem to be any clear path to a perfect model of the Universe, even if we have perfect physics.

Intuitive Infinity

Once I had completed the result above, I started thinking about infinity again, and I realized you can prove that a number is Dedekind infinite if and only if it is greater than all integers, which I call “intuitively infinite”. Dedekind infinity is great, and forces you to think about sets, but you also want to be sure that the idea comports with intuition, especially if you’re going to use the notion to derive physically meaningful results like we did above. Now this could be a known result, but I don’t see it mentioned anywhere saliently, and you’d think it would be, so since I’m frankly not interested in doing any diligence, here’s the proof.

Let’s start by saying a number is intuitively infinite if it is greater than all natural numbers. Now assume that $A \subset B$ and there is a one-to-correspondence $f: A \rightarrow B$ . Further assume that the cardinality of $B$ , written $|B|$ , is not intuitively infinite, and as such, there is some $n \in \mathbb{N}$ , such that $n = |B|$ . Because $f$ is one-to-one, it must be the case that $|A| = |B| = n$ , but because $A \subset B$ , there must be some $b \in B$ such that $b \notin A$ . Because $b \notin A$ , it must be the case that $|A| + 1 \leq |B|$ , but this contradicts the assumption that $f$ is one-to-one. Therefore, if $A \subset B$ and there is a one-to-correspondence $f: A \rightarrow B$ , then $|B|$ is intuitively infinite.

Now assume that $|B|$ is intuitively infinite and further let $x \in B$ be some singleton. It would suffice to show that $|B| = |B - x|$ , since that would imply that there is a one-to-one correspondence from $B$ to one of its proper subsets, namely $B - x$ . Assume instead that $|B| > |B - x|$ . It must be the case that $|B| \geq \aleph_0$ , since you can show there is no smaller infinite cardinality. Because we have assumed that $|B| > |B - x|$ , then it must be the case that $|B| > \aleph_0$ , since removing a singleton from a countable set does not change its cardinality. Note we are allowing for infinite numbers that are capable of diminution by removal of a singleton arguendo for purposes of the proof. Analogously, it must be the case $|B - x| > \aleph_0$ , since assuming $|B - x| = \aleph_0$ would again imply that adding a singleton to a countable set would change its cardinality, which is not true. As such, because $|B - x| > \aleph_0$ , there must be some $\bar{X} \subset B - x$ such that $|B - \bar{X} - x| = \aleph_0$ . That is, we can remove a subset from $B - x$ and produce a countable set $S$ .

As such, because $x \notin \bar{X}$ , it must be the case that $B = (S \cup x) \cup \bar{X} = (S \cup \bar{X}) \cup x$ . However, on the lefthand side of the equation, the union over $x$ does not contribute anything to the total cardinality of $B$ , because $S$ is countable and $x$ is a singleton, whereas on the righthand side $x$ does contribute to the total cardinality because $S \cup \bar{X} = B - x$ , which we’ve assumed to have a cardinality of less than $|B|$ . This implies that the number of elements contributed to an aggregation by union is not determined by the number of elements in the operand sets, and instead by the order in which we apply the union operator, which makes no sense. Therefore, we have a contradiction, and so $|B - x| = |B|$ , which completes the proof.

Discover more from Information Overload

Subscribe to get the latest posts sent to your email.

Discover more from Information Overload

Share this:

Related

Leave a comment Cancel reply