Justin Attempts to Understand Part of “The Fabric of Reality”, Part 3

Summary so far of my attempts to understand David Deutsch’s discussion of Godel’s Theorem in The Fabric of Reality:

So in Part 1 we considered a type of “diagonal argument” applied to DD’s discussion of Cantgotu enviroments. Basically, DD said that a program for a VR generator has to have a discrete, quantized set of values for any variables, expressible as a finite sequence of symbols, and that it can be executed in a sequence of steps. Suppose we have an infinite set of possible VR programs meeting this criteria that some VR generator can run. We could define a second infinite set of programs (the Cantgotu list) in relation to the first by saying that this second set consists of programs whose characteristic is that, in any given minute, the VR environment they produce behaves differently than a VR environment in the first set. So in the first minute, Cantgotu Environment 1 behaves differently than plain old Environment 1, and in the second minute, Cantogu Environment 1 behaves differently than plain old Environment 2, and so on. So ultimately the Cantgotu Environment varies from every environment in the first list, and so this shows we can only run a fraction of logically possible environments.

In Part 2 we talked about the problem situation Godel’s Theorem was facing. Basically, mathematicians liked to believe that their proofs were on absolutely certain foundations. And Godel made this impossible by showing that 1) any set of rules of inference that could validate arithmetic proofs couldn’t validate its own consistency, and 2) a consistent set of rules of inference will fail to show as valid methods of proof which are in fact valid. And DD tells us that Godel used something like the diagonal arg that Cantor used to show there’s bigger infinities than natural numbers and that DD uses when talking about Cantgotu environments.

Basically, with regards to point 2, Godel considered some set of rules for making inferences, then showed how to construct a proposition you couldn’t either prove or disprove under the rules of inference. Then he showed the proposition was in fact true.

I feel like I get the general point but am not sure I could apply explain or apply this idea very well without knowing more technical details.

BTW I watched this video on Cantor’s diagonalization argument which I thought was okay (I tried a few different vids out). I looked for additional material (besides The Fabric of Reality) directly on Godel’s Theorem but it all seemed like it would be above my level of mathematical understanding.

Justin Attempts to Understand Part of “The Fabric of Reality”, Part 2

This post is part 2 of my attempt to understand the discussion of Godel’s incompleteness theorem presented in The Fabric of Reality by David Deutsch (DD). See Part 1 here.

Below is a summary of what I thought the relevant parts of Chapter 10 were. I included a big chunk of the beginning of the chapter cuz it seemed like relevant context to understand the problem situation Godel was facing.

David looks back on his discussion of Cantgotu environments and asks:

I have said that there exist infinitely many [Cantgotu environments] for every environment that can be rendered. But what does it mean to say that such environments ‘exist’? If they do not exist in reality, or even in virtual reality, where do they exist?

DD asks whether abstract, non-physical entities like numbers & laws of physics exist. He wants to distinguish things that have an independent existence vs. things that are features of our culture, arbitrary, etc.

DD says if we want to know whether a given abstraction exists, we should ask whether it “kicks back” in a complex, autonomous way. He talks about natural numbers as an example. We came up with them as an abstract way of expressing “successive amounts of a discrete quantity.” But after we made them, it turns out they have all these properties we have to figure out (like characteristics of the distribution of prime numbers.)

Since we cannot understand them either as being part of ourselves or as being part of something else that we already understand, but we can understand them as independent entities, we must conclude that they are real, independent entities.

DD says abstract entities are intangible and don’t literally kick back. He says proofs play the role in maths experiment and observation plays in science, and says that mathematicians are big on thinking proofs are absolutely certain.

DD talks some about Pythagoras and Plato. Pythagoras thought regularities in nature were expressions of mathematical relationships in natural numbers. Plato thought the physical world wasn’t real and thought things we experience in our world were reflections from the world of Forms (the Forms including numbers like 1,2,3, mathematical operations etc.) DD also mentions Plato’s theory of in-born knowledge.

DD says that mathematicians agree “mathematical intuition” is a source of absolute certainty, but then disagree about what mathematical intuition tells them, heh. He gives the example of imaginary numbers. There were proofs about real numbers that involved imaginary numbers, and some mathematicians objected because they said imaginary numbers weren’t real. Good example.

DD talks about a crisis in mathematics. Aristotle had figured out the laws of logic and syllogisms, and said that all valid proofs could be expressed as syllogisms. He hadn’t proved this though. And DD says the crisis was modern mathematical proofs weren’t expressed syllogistically and involved tools outside the classical logic rules. So this proved that Aristotle’s rules were inadequate. And people were worried that maybe the new stuff wasn’t absolutely certain.

DD talks about responses to this crisis. One was intuitionism, which tries to construct intuition in a super narrow way only based on supposedly unchallengeable, self-evident aspects. This leads to them denying infinite sets.

DD says intuitionism had some value (like inductivism) in that it dared to question some received certainties. But it ultimately involved retreating into an inner world/domain that actually makes explanation of even that inner domain harder. E.g. intuitionists deny infinities. So there must be finite natural numbers. How many? And then why can’t you form an intuition about the next natural number above that one? Intuitionists reply to this by denying logic, specifically the law of the excluded middle, which says there’s no third possibility between a given proposition and its negation.

DD says:

…by severing the link between their version of the abstract ‘natural numbers’ and the intuitions that those numbers were originally intended to formalize, intuitionists have also denied themselves the usual explanatory structure through which natural numbers are understood. This raises a problem for anyone who prefers explanations to unexplained complications. Instead of solving that problem by providing an alternative or deeper explanatory structure for the natural numbers, intuitionism does exactly what the Inquisition did, and what solipsists do: it retreats still further from explanation. It introduces further unexplained complications (in this case the denial of the law of the excluded middle) whose only purpose is to allow intuitionists to behave as if their opponents’ explanation were true, while drawing no conclusions about reality from this.

DD then turns to Godel:

Thirty-one years later, Kurt Godel revolutionized proof theory with a root-and- branch refutation from which the mathematical and philosophical worlds are still reeling: […] Godel proved first that any set of rules of inference that is capable of correctly validating even the proofs of ordinary arithmetic could never validate a proof of its own consistency. […] Second, Godel proved that if a set of rules of inference in some (sufficiently rich) branch of mathematics is consistent (whether provably so or not), then within that branch of mathematics there must exist valid methods of proof that those rules fail to designate as valid. This is called Godel’s incompleteness theorem. To prove his theorems, Godel used a remarkable extension of the Cantor ‘diagonal argument’ that I mentioned in Chapter 6. He began by considering any consistent set of rules of inference. Then he showed how to construct a proposition which could neither be proved nor disproved under those rules. Then he proved that that proposition would be true.

So basically Godel showed that we can have no fixed way of knowing if a mathematical proposition is true.

Skipping ahead some in the chapter…

DD says one of Godel’s assumptions was that a proof can have only a finite number of steps. DD says this is correct as far as we know according to quantum theory.

DD says Godel inherited Greek conception that a proof was a particular type of object (a sequence of statements that obey rules of inference.) But really it’s better thought of as a process. He says that with the “classical theory of proof or computation” this distinction isn’t hugely significant because you can just make a record of the process and therefore have a proof “object”. But with quantum computer calculations lots of stuff is happening in other universes so you can’t record all that stuff. And this shows that the old traditional mathematical method of trying to have totally certain stuff by stripping away every source of ambiguity and error isn’t viable.

In the next part I’ll try and sum up.

Justin Attempts to Understand Part of “The Fabric of Reality”, Part 1

This post is part of my attempt to understand the discussion of Godel’s incompleteness theorem presented in The Fabric of Reality by David Deutsch (DD).

See part 2 here

In Chapter 10 of The Fabric of Reality, DD says:

Godel proved that if a set of rules of inference in some (sufficiently rich) branch of mathematics is consistent (whether provably so or not), then within that branch of mathematics there must exist valid methods of proof that those rules fail to designate as valid. This is called Godel’s incompleteness theorem. To prove his theorems, Godel used a remarkable extension of the Cantor ‘diagonal argument’ that I mentioned in Chapter 6. He began by considering any consistent set of rules of inference. Then he showed how to construct a proposition which could neither be proved nor disproved under those rules. Then he proved that that proposition would be true.

So my attempt to understand DD’s discussion of Godel’s incompleteness theorem will begin with a review of the relevant portion of Chapter 6, presented below:

DD opens the chapter with the question of whether we will be able to build a fully universal virtual reality generator which can render any environment the human mind is capable of experiencing.

DD clarifies that he’s talking about a virtual reality generator which could be programmed to generate all logically possible environments, and not something that would already contain within itself the specific instructions for generating the environment.

DD says we can imagine a virtual reality generator as having an effectively unlimited memory capacity for storing a given VR environment by imagining that it can read any number of disks.

DD says we can’t imagine unlimited computation speed like we can unlimited memory capacity. So what happens if the VR generator can’t render stuff fast enough??

DD says the answer is basically the VR generator would need to be able to control the equivalent of the brain’s “CPU clock” to keep it in sync with what the VR generator can generate. DD notes that this slowing down would be invisible from the user’s perspective within the simulation, though if their brain needs to be slowed down a bunch to make complex environments, more time will elapse in reality.

DD asks if there is anything outside the repertoire of a VR generator.

Would its repertoire be the set of all logically possible environments? It would not. Even this futuristic machine’s repertoire is drastically circumscribed by the mere fact of its being a physical object. It does not even scratch the surface of what is logically possible, as I shall now show.

DD says the basic idea of the argument he will use, which is called the diagonal argument, has had various other applications, like proving that there are infinite quantities greater than the infinity of natural numbers, and to prove Godel’s Incompleteness Theorem.

DD says that each program for the VR generator has to have some particular, quantized set of values for any variables, and therefore “the set of possible programs must be discrete.”

Question: What’s the alternative here? Like what would a non-discrete set of possible programs mean?

DD says each program has to be expressible as a finite sequence of symbols in a computer language.

There are infinitely many such programs, but each one can contain only a finite number of symbols. That is because symbols are physical objects, made of matter in recognizable configurations, and one could not manufacture an infinite number of them.

Question: Is this similar to how there’s an infinite number of books that could be written but a finite length to any given book, cuz books are made up of sequences of letters represented in some physical objects (in ink on pages, or in a hard drive and then displayed on a screen) and you can’t have infinite actual letters?

DD says the requirements he’s been talking about — “that the programs must be quantized, and that each of them must consist of a finite number of symbols and can be executed in a sequence of steps” — are a big deal that “impose drastic restrictions on the repertoire of any physically possible machine.”

DD asks us to imagine the infinite possible programs in an infinitely long list, numbered Program 1, Program 2, etc. You could also list them by VR environment they generate, so it’d be like Environment 1, Environment 2, etc.

DD says programs could vary a lot in how long they run for but let’s “consider only programs that continue to run for ever” to keep his proof simple.

DD says we can call the class of logically possible environments Cantgotu environments. He defines Cantgotu environments in the following way:

For the first subjective minute, a Cantgotu environment behaves differently from Environment 1 (generated by Program 1 of our generator). It does not matter how it does behave, so long as it is, to the user, recognizably different from Environment i. During the second minute it behaves differently from Environment 2 (though it is now allowed to resemble Environment i again). During the third minute, it behaves differently from Environment 3, and so on.

The “and so on” means that it behaves differently than all the Environments on our infinite list of programs the VR generator can run at some point.

Questions: How can we reason about these Cantgotu environments at all? What makes them logically possible? Do they necessarily contradict one or more of the requirements DD mentioned about programs being quantized in a finite number of symbols, etc? So the idea is these are programs which are physically impossible but which we don’t have any criticism of on logical grounds?

DD says that there’s a ton of Cantgotu environments possible, because the only constraint is that during some minute they behave differently than something in the list of programs the VR Generator can run.

DD says his argument shows that we can only run an infinitesimal fraction of the set of all logically possible environments.