March 2017 – Point at Infinity

Today, we take a break from our recent philosophical musings to return to some good old-fashioned mathematics (indeed, the mathematics today could be seen as all being “old-fashioned,” as the theorem we will be considering dates back to the ancient Greeks).

I’m sure my readers have all been introduced to the prime numbers, but, to refresh any memories, let me remind you that a prime number is a natural number, at least 2, that has no divisors other than 1 and itself. The first few prime numbers are, therefore: 2, 3, 5, 7, 11, 13…

The prime numbers can be thought of as the building blocks of number theory, as the backbone of the natural numbers. They have occupied a central place in mathematics and offered endless fascination for millennia. They are a source of great mystery even today.

In this post, we look at a classic theorem, commonly attributed to Euclid. Euclid’s proof is one of the gems of mathematics, a proof that is taught to every mathematician at the beginning of their true mathematical career. The theorem, as we will state it, is simply this:

Euclid’s Theorem: There are infinitely many prime numbers.

Euclid himself did not state the theorem in exactly this form, perhaps because of the ancient Greeks’ general antipathy towards the existence of infinite sets. He instead put forward the equivalent statement, “For every finite set of prime numbers, there is a prime number not in that set.”

Euclid’s Theorem has collected a vast and varied array of delightful proofs throughout the years, and, in a proposed infinite series of blog posts, I plan to cover all of them. Today, we will look at three proofs, from three very different centuries, all using only elementary number-theoretic techniques. First, of course, is Euclid’s proof itself.

Proof One (Euclid): Suppose that $P = \{p_0, p_1, \ldots, p_n\}$ is a finite set of prime numbers. We will show that there is a prime number that is not in $P$ . To do this, let $q = p_0p_2\ldots p_n$ , and let $r = q+1$ . For all $i \leq n$ , $p_i$ divides $q$ with no remainder (as $q = p_i(p_0\ldots p_{i-1}p_{i+1}\ldots p_n)$ ), so, as $r = q+1$ and $p_i \geq 2$ , $p_i$ does not divide $r$ . Since $r > 1$ and every integer greater than 1 has prime divisors, there is at least one prime, $p^*$ , that divides $r$ . But we just saw that no element of $P$ divides $r$ , so $p^*$ is a prime that is not in $P$ .

The next proof we will consider is due to the eighteenth-century German mathematician Christian Goldbach, largely known today for the statement of the still unproven Goldbach’s Conjecture. This proof (like Goldbach’s Conjecture itself) appears in a letter from Goldbach to Leonhard Euler (whose analytic proof of Euclid’s Theorem we will visit in a future post).

Proof Two (Goldbach): For each natural number $n$ , let $F_n = 2^{2^n} + 1$ , so $F_0 = 3, F_1 = 5, F_2 = 17$ , etc. ( $F_n$ is known as the $n^{\mathrm{th}}$ Fermat number.)

Claim 1: For every natural number $n$ , $F_{n+1} = F_0F_1\ldots F_n + 2$ .

Proof of Claim 1: Suppose that the Claim is false, and let $n$ be the smallest natural number such that $F_{n+1} \neq F_0F_1 \ldots F_n + 2$ . Since the Claim can easily be verified by inspection for $n=0$ , we may assume $n > 0$ . But now we have the following sequence of calculations where, because we are assuming that $n$ is the smallest counterexample to the Claim, we can use the fact that $F_n = F_0F_1\ldots F_{n-1} + 2$ .

$\begin{array}{rcl}F_{n+1} & = & 2^{2^{n+1}}+1 \\ & = & 2^{2^n}\cdot 2^{2^n} + 1 \\ & = & (F_n-1)(F_n-1)+1 \\ & = & (F_n)(F_n) - 2F_n + 2 \\ & = & (F_n)(F_0F_1\ldots F_{n-1} + 2) -2F_n + 2 \\ & = & F_0F_1\ldots F_n + 2F_n - 2F_n + 2 \\ & = & F_0F_1\ldots F_n + 2 \end{array}$

But this calculation shows that $n$ is not a counterexample to our Claim, contradicting our assumption and finishing the proof of the Claim.

We now need a very simple number-theoretic Claim.

Claim 2: If $a$ and $b$ are natural numbers, $p$ is a prime, and $p$ divides both $a$ and $a+b$ , then $p$ divides $b$ .

Proof of Claim 2: Suppose $a = mp$ and $a+b = np$ , where $m$ and $n$ are natural numbers. Then $b = a+b-a = np - mp = (n-m)p$ , so $p$ divides $b$ .

Claim 3: If $m < n$ are natural numbers, then there is no prime number $p$ such that $p$ divides both $F_m$ and $F_n$ .

Proof of Claim 3: Suppose that the Claim is false and that there are natural numbers $m < n$ and a prime number $p$ such that $p$ divides both $F_m$ and $F_n$ . Note that $F_m$ is one of the factors in the product $F_0F_1\ldots F_{n-1}$ , so $p$ divides $F_0F_1\ldots F_{n-1}$ . Since $F_n = F_0F_1\ldots F_{n-1} + 2$ , we also conclude that $p$ divides $F_0F_1\ldots F_{n+1} + 2$ , so, by Claim 2, we know that $p$ divides $2$ . As $2$ is prime, this means that $p = 2$ . But $F_m$ and $F_n$ are both odd, so this is impossible.

We are now ready to finish the proof. For each natural number $n$ , choose a prime number $p_n$ that divides $F_n$ . By Claim 3, for all natural numbers $m < n$ , we have $p_m \neq p_n$ , so $\{p_n \mid n \in \mathbb{N}\}$ is an infinite set of prime numbers.

Remark: The Fermat numbers were introduced, unsurprisingly, by the seventeenth-century French mathematician Pierre de Fermat (of Fermat’s Last Theorem fame). Fermat conjectured that every Fermat number is in fact prime (this would obviously imply Claim 3 from the previous proof). The first four Fermat numbers (3, 5, 17, 257) are easily verified to be prime, and the next Fermat number, 65537, can be seen to be prime with a bit more work. However, Euler proved in 1732 that $F_5$ is not prime. Indeed, $F_5 = 2^{32}+1 = 4294967297 = 641 \times 6700417$ . Many mysteries remain regarding the Fermat numbers. For example, even the following two very basic questions remain unsolved to this day:

Are there infinitely many prime Fermat numbers?
Are there infinitely many non-prime Fermat numbers?

The Fermat numbers grow so quickly that, even with computers, it can be hard to analyze even “relatively small” Fermat numbers. For example, it is unknown whether $F_{20}$ or $F_{24}$ are prime. On the other hand, the truly gigantic number $F_{3329780}$ is known to be non-prime: one of its prime factors is $193 \times 2^{3329780} + 1$ .

Finally, a proof that combines ideas from Euclid’s and Goldbach’s proofs was given recently by Filip Saidak.

Proof Three: (Saidak) Note first that, for every natural number $n$ , we have that $n$ and $n+1$ do not have any shared prime divisors. Now define an infinite sequence of natural numbers, $\langle n_0, n_1, \ldots \rangle$ as follows. Let $n_0$ be any natural number that is at least 2. Let $n_1 = n_0(n_0+1)$ . Since $n_0$ and $n_0 + 1$ do not share any prime divisors, and since both $n_0$ and $n_0+1$ have at least one prime divisor, it follows that $n_1$ must have at least 2 distinct prime divisors.

Now let $n_2 = n_1(n_1+1)$ . Again, $n_1$ and $(n_1 + 1)$ do not have any shared prime divisors. We have shown that $n_1$ has at least 2 distinct prime divisors, and we know that $n_1 + 1$ has at least one prime divisor, so $n_2$ must have at least 3 distinct prime divisors. Continuing in this way, defining $n_{k+1} = n_k(n_k+1)$ for every natural number $k$ , one proves that, for each natural number $k$ , the number $n_k$ has at least $k+1$ distinct prime divisors. In particular, there are infinitely many prime numbers.

Stay tuned for a future post, in which we will provide proofs of Euclid’s Theorem from further flung areas of mathematics, including real analysis and topology.

In our previous post, we took a detour to consider the shape of space. Today, we return to time, both external and personal, and the question, “What does it mean to be immortal?”

The distinction between external time and personal time was introduced by Lewis in his 1976 paper, “The Paradoxes of Time Travel.” The term “external time” refers to time itself. “Personal time,” applied to a particular person, is, as Lewis puts it, “roughly, that which is measured by his wristwatch.” It might be more precise to think of personal time as the time measured by one’s internal processes: if, in a period of external time, I go through the physical processes that a typical person would go through in an hour, then, during that period of external time, one hour of personal time has elapsed for me.

In the common view of time, it is shaped like a straight line, stretching infinitely far in front of us. (We will be agnostic here about whether or not infinitely much time has already elapsed.) In this view, the years lying ahead of us form an $\omega$ -sequence, i.e., a sequence ordered like the natural numbers. This year could be called Year 0, next year Year 1, and so on. One natural number for each future year, and one future year for each natural number. Also, in human experience thus far, external time and personal time have pretty much lined up. With this simple view of time and of the relationship between external and personal time, it is also pretty simple to see what it means to be immortal: a person is immortal if they live for all of the years after they are born.

This simple view of immortality probably suffices for practical discussions about its feasibility and desirability. Right now, though, we’re going to indulge ourselves in a bit of conceptual analysis, contemplating improbable thought experiments with the aim of gaining a fuller understanding of immortality or, at the very least, having some fun trying. Today: transfinite life.

In a delightful 1985 paper, entitled “On Living Forever,” Phillip Bricker argues that he wants not just to live for an infinite number of years, but to live for a transfinite number of years, i.e., more than one $\omega$ -sequence of years. Even if our universe happens to only have an $\omega$ -sequence of years in the future, Bricker argues, it is conceivable that there are universes with more than an $\omega$ -sequence of years, and it would be desirable to live in such a universe and live for a transfinite number of years.

There are a number of points to be considered here. For simplicity, let’s say there is a universe with two $\omega$ -sequences of years, one after the other, and that we are currently considering the beginning of the first of these two $\omega$ -sequences. Let us call this year Year 0A, next year Year 1A, the following year Year 2A, and so on, defining Year NA for every natural number N. After this $\omega$ -sequence of years, there will be the start of the second $\omega$ -sequence. Let us call the first year of this sequence Year 0B, the next year Year 1B, and so on.

The first and most fundamental question is perhaps, “Is this possible? Does this make sense?” More precisely, can the universe of the second $\omega$ -sequence of years really be considered the “same” universe as that of the first $\omega$ -sequence of years? Can a universe extend across multiple $\omega$ -sequences of years? Bricker answers this question affirmatively with a process that might be called “decompression.” He asks the reader to consider the events between 11 PM and midnight on December 31, 1999. There is a possible world, he says, in which the events between 11 and 11:30 take one year to occur, the events between 11:30 and 11:45 take one year to occur, and so on, so that the events of this hour in our world take an entire $\omega$ -sequence of years in this other world. After midnight, the two worlds proceed at the same rate. Thus, if our world has one $\omega$ -sequence of years, this other world has two. Moreover, whatever relations hold between our world pre-midnight and our world post-midnight hold between the first $\omega$ -sequence of the other world and the second $\omega$ -sequence of the other world. So, Bricker argues, the extension of a possible universe across multiple $\omega$ -sequences of years is no more mysterious than the extension of our universe across multiple days.

I admit that this is a somewhat convincing argument, but I find it only convincing of the possibility of a transfinite universe of a very particular sort, namely of a sort that respects some continuity conditions. In the world in which the events of an hour in our world take an entire $\omega$ -sequence of years, things that proceed at a steady pace in our world proceed increasingly slowly. The world undergoes less and less change as this $\omega$ -sequence progresses. In a very precise sense, as these infinitely many years go on, this alternate world converges to a fixed limit. This limit, of course, is the state of our world at midnight, which is the state of the alternate world at the start of the second $\omega$ -sequence. Such a world, though, is a rather uninteresting example of a transfinite universe and would not be particularly appealing for somebody looking for true transfinite immortality. For suppose that such a person lived in this world for both $\omega$ -sequences of years. As the first $\omega$ -sequence went on, everything would slow down, including the person’s movements, internal processes, thoughts. At the end of the first $\omega$ -sequence, even if infinitely many years of external time had occurred, the person’s experiences would only be equivalent to a finite amount of personal time in our world. So this person, living for two $\omega$ -sequences of years, would have the same experience as someone living for one $\omega$ -sequene of years in our world, defeating the purpose of wanting a transfinite existence in the first place.

To illustrate the difficulty, let’s consider a universe, called Universe T, with two $\omega$ -sequences of years, that definitely does not converge, using a classic thought experiment known as Thomson’s Lamp, which we briefly visited in an earlier post in connection with Zeno’s paradoxes. Let’s suppose that you are living in this world, in the first $\omega$ -sequence. Let’s suppose moreover that you live for the entire first $\omega$ -sequence, spending all of the years living in the same house. On your bedside table is a lamp that, miraculously, never breaks and never needs a replacement bulb. Every morning, when you wake, you turn the lamp on, and every night, when you go to bed, you turn the lamp off. Now: at the first moment of the second $\omega$ -sequence of years, is the lamp on or off? (Does the lamp even exist?) It seems impossible to answer this question, or even to make sense of it. If it were the case that, from a certain point onward in the first $\omega$ -sequence of years, the lamp were off, then it would be natural to answer that the lamp is off at the start of second $\omega$ -sequence, and similarly if the lamp were on from a certain point. In this case, though, the lamp does not converge to any single state, so it is hard to see what will happen to it in the second $\omega$ -sequence.

In order to use Bricker’s argument to argue for the plausibility of this world, we would want to apply the opposite of “decompression,” something a person might reasonably call “compression.” To do this, we would want to consider a world, called Universe S, in which the first year’s events in Universe T take half an hour, the second year’s events in Universe T take a quarter of an hour, and so on, so that the events of the first $\omega$ -sequence of years in Universe T take one hour in Universe S. Now, one wants to say, there is no problem with Universe S lasting for more than one hour, so, to figure out what happened to your lamp at the start of the second $\omega$ -sequence in Universe T, just look at its state at the start of the second hour in Universe S. There is an issue here, though. In compressing the events of the first $\omega$ -sequence of Universe T into one hour, certain things, such as the turning on and off of the lamp, happen at faster and faster speeds, indeed at speeds approaching infinity. This would of course be a problem in our universe, in which nothing can travel faster than the speed of light. It might be a problem in every universe. Are there possible universes in which objects can travel arbitrarily fast? If so, what would these universes be like? Are these thought experiments entirely misguided in the first place and driven by inaccurate conceptions of time? These questions certainly lie beyond the scope of this post. For now, let’s just leave them here as possible difficulties in justifying the possibility of interesting transfinite universes.

Let’s put aside any objections, though, and suppose that there can in fact be a world spanning multiple $\omega$ -sequences of years and that a person could exist across these multiple $\omega$ -sequences in such a way that their personal time would coincide with the external time. Would this in fact be better than simply living for one $\omega$ -sequence? Bricker’s primary reason for answering affirmatively is simply that he wants the pleasures of life (for example, eating Thai food) to be experienced as many times as possible. Eating Thai food provides pleasure; why limit oneself to just an $\omega$ -sequence of Thai meals? Why not two $\omega$ -sequences of Thai meals? Why not uncountably many Thai meals? Inaccessibly many Thai meals? A supercompact number of Thai meals? The more the better!

Another intriguing reason offered by Bricker involves the pursuit of mathematical knowledge. There are unsolved problems in number theory, for example, which could easily be solved in an infinite amount of time simply by checking every number. For example, the Goldbach conjecture, unproven to this day, asserts that every even number greater than 2 can be expressed as the sum of two prime numbers. The conjecture has resisted many attempts at proof by some of the great mathematicians of the world, but, if someone were able to live for more than an $\omega$ -sequence of years, they could prove or refute it very easily: during the first $\omega$ -sequence of years, they could systematically check every even number. If they find one that cannot be expressed as the sum of two prime numbers, they write it down as a counterexample, disproving the conjecture. If, after the first $\omega$ -sequence of years, they have not written down a counterexample, they will know that there is none, and the conjecture is true.

Let’s note a couple of potential issues here. First, humans have finite brains. So, suppose that someone lives for longer than one $\omega$ -sequence of years. When they wake up in Year 0B, the first year of the second $\omega$ -sequence, they will only be able to remember finitely many things from the first $\omega$ -sequence. Thus, as far as their memory is concerned, they will essentially only have lived for a finite number of years. This brings up two questions. First, will they be able to tell that it is Year 0B? If they cannot remember anything past Year 100A, then, as far as they are concerned, it might as well be Year 101A. There are obvious external remedies for this. For example, perhaps they could fashion a clock that moves from 12 to 6 during one year, 6 to 9 during the next, 9 to 10:30 during the next, and so on, so that the clock returning to 12 will mark the end of the first $\omega$ -sequence of years.

Secondly, and perhaps more seriously, suppose that this person engaged themselves in solving Goldbach’s Conjecture by checking all of the numbers. Suppose that, in Year 0B, they find that they have not written down a counterexample. This indicates that the conjecture is true. However, due to their finite memory, they will only remember checking finitely many of the numbers. Can they assure themselves that they did in fact complete all of the calculations and didn’t give up partway through and sink into a decadent life of leisure? Again, there are possible remedies to this. They could set a computer on the task, putting precautions in place to make sure that the computer is not disturbed throughout the first $\omega$ -sequence of years. This would be better but would run into similar objections. How could the person be sure that the computer’s integrity was maintained throughout its calculations, that it didn’t lose power partway through, that a rival mathematician didn’t hack into it, that it didn’t obtain consciousness and sink into a decadent life of leisure? Verifying that an infinite sequence of calculations was carried out correctly could take another infinity of years, in which case we are back to where we started. Such a proof of Goldbach’s Conjecture would be fundamentally different from any proofs done today, and it seems likely that its veracity would always be subject to some amount of doubt.

We will turn to some other esoteric thought experiments in our next post. Until then, here are some questions, essentially taken from Cody Gilmore’s “The Metaphysics of Mortals: Death, Immortality, and Personal Time,” to ponder in order to test your intuition. We’ll consider possible answers next time; feel free to post thoughts in the comment section.

Alfred’s life has an external length of 100 years. However, his personal time passes very differently. The first 50 external years of his life correspond to his first personal year, the next 25 external years correspond to his second personal year, the next 12.5 external years to his third personal year, the next 6.25 to his fourth personal year, and so on. Is Alfred immortal?
Betty’s life lasts for an entire $\omega$ -sequence of years of external time (in a world in which there is only one $\omega$ -sequence). The first external year corresponds to one year of personal time, the second external year to half a year of personal time, the third external year to a quarter year of personal time, the fourth external year to an eighth of a year of personal time, and so on. Is Betty immortal?
Carmen lives in a world with two $\omega$ -sequences of years. She is born during the first $\omega$ -sequence of years, and her life lasts precisely until the end of the first $\omega$ -sequence of years. Her personal time matches external time. Is Carmen immortal?
David lives in the same world as Carmen and is also born during the first $\omega$ -sequence of years, at the same time as Carmen. David lives through the end of the first $\omega$ -sequence of years and then five years into the second $\omega$ -sequence of years before dying. His personal time matches external time. Is David immortal?

Cover image: Salvador Dali, “The Persistence of Memory”

	September (1): How D… on Dante, Einstein, and the Shape…
	વિરોધાભાસોમાંના સર્વ… on Circles 1: Circular Defin…
	Comparisons –… on Pythagoras’ Table of…
	Greifswald and the M… on Ultrafilters VII: Large C…
	John Gabriel on Cantor v. Crank

Point at Infinity

Updated at finite intervals

Point at Infinity

Month: March 2017

An Infinitude of Proofs, Part 0

Infinite Life III: Transfinite Life

Point at Infinity

Updated at finite intervals

Share this:

Share this: