Logical snippets

For about eighteen months now, I’ve been a regular visitor to the useful question-and-answer site, math.stackexchange.com — this is a student-orientated forum, not to be confused with the truly wonderful mathoverflow.net which is its research-level counterpart. OK, you can think of these visits as (hopefully) constructive procrastination on my part …

Of course, many of the questions on the site, including many I’ve found myself answering, are very ephemeral or very localized or based on very specific confusions. But a small proportion of the exchanges to which I’ve contributed might, for one reason or another, be of some interest/use to other students — or at least, to beginners and near beginners in logic.

So I’ve put together a page of links to these logical scraps, morsels, excerpts, … snippets, shall we say. I’ve grouped the links by level and/or topic.

This entry was posted in Logic. Bookmark the permalink.

3 Responses to Logical snippets

  1. David Auerbach says:

    Your help is needed elsewhere as well. You might want to head over to the NYTimes book review where I just read these choice paragraphs:
    A bigger problem is that M.U.H. appears to contradict Gödel’s incompleteness theorem, which states that in any sufficiently sophisticated, consistent mathematical theory there will be true statements that cannot be decided within that theory. Conceding this point, Tegmark replaces Mathematical Universe Hypothesis with Computable Universe Hypothesis: Only “computable” mathematical structures should be allowed. But this rules out all structures that contain infinity! In fact, he admits that “our current standard model (and virtually all historically successful theories) violate the C.U.H.,” which does not bode well for the whole idea, to say the least.

    Ironically, Mr. Tegmark has no qualms about telling us that there are infinitely many parallel universes out there. Actually, he believes that any mathematical structure spawns its own universe, and that all of these universes exist in parallel and on equal footing (further, he claims that if you accept M.U.H. or C.U.H., you are forced to also accept this proposal). According to him, a simple square, for example, should be viewed as just as legitimate a universe as the world around us. Tegmark’s “Level IV Multiverse” is therefore much like Borges’s Library of Babel, containing all possible books that can be written with a given alphabet. Any question is answered in one of them, but no one knows which one. In what sense is having all these books (or universes) different from nothing at all?

    • Mark says:

      According to Tegmark a physical consequence of Godel’s theorems is that “the MUH makes no sense because our universe would be somehow inconsistent or undefined. If one accepts David Hilbert’s dictum that mathematical existence is merely freedom from contradiction, then an inconsistent structure would not exist mathematically, let alone physically as in the MUH. According to the CUH, the mathematical structure that is our universe is computable and hence well-defined in the strong sense that all its relations can be computed.” Someone could say that the realm of physical reality might include infinite structures that are semicomputable but uncomputable, and that despite this might be described as computable as to an infinite intelligence which is able to inspect infinitely many totalities through infinitely many mental passages not accessible to us. There is a similar observation made by Kripke in his Naming and Necessity. This point is clear when Tegmark considers the first of these two possibilities:

      (1) Structures with relations defined by computations that are not guaranteed to halt (i.e., may require infinitely many steps). Based on a Godel-undecidable statement, one can even define a function which is guaranteed to be uncomputable, yet would be computable if infinitely many computational steps were allowed. (2) Still more general structures. For example, mathematical structures with uncountably many set elements (like the continuous space examples in Section III B and virtually all current models of physics) are all uncomputable: one cannot even input the function arguments into the computation, since even a single generic real number requires infinitely many bits to describe.

      Nevertheless, such an alternative is excluded by Tegmark, since he says that: “By drastically limiting the number of mathematical structures to be considered, the CUH also removes potential paradoxes related to the Level IV multiverse. A computable mathematical structure can by definition be specified by a finite number of bits. For example, each of the finitely many generating relations can be specified as a finite number of characters in some programming language supporting arbitrarily large integers (along the lines of the Mathematica, Maple and Matlab packages). Since each finite bit string can be interpreted as an integer in binary, there are thus only countably many computable mathematical structures. The full Level IV multiverse (the union of all these countably infinitely many computable mathematical structures) is then not itself a computable mathematical structure, since it has infinitely many generating relations. The Level IV multiverse is therefore not a member of itself, precluding Russell-style paradoxes.”

      Tegmark upholds the so called TOE (Theory of Everything), personally I am sympathetic with Freeman Dyson’s point of view: “It is my hope that we may be able to prove the world of physics as inexhaustible as the world of mathematics. Some of our colleagues in particle physics think that they are coming close to a complete understanding of the basic laws of nature. They have indeed made wonderful progress in the last ten years. But I hope that the notion of a final statement of the laws of physics will prove as illusory as the notion of a formal decision process for all of mathematics. If it should turn out that the whole of physical reality can be described by a finite set of equations, I would be disappointed. I would feel that the Creator had been uncharacteristically lacking in imagination. I would have to say, as Einstein once said in a similar context, “Da konnt’ mir halt der liebe Gott leid tun” (“Then I would have been sorry for the dear
      Lord”).”

    • Rowsety Moid says:

      That review of Our Mathematical Universe also says this:

      We read in the book that it is a “set of abstract elements with relations between them,” like the set of whole numbers with operations of addition and multiplication. However, there is a lot more to math than such mathematical structures. Objects other than sets are necessary, and they have now become widespread. Moreover, there is an effort underway to overhaul the foundations of math in which set theory is no longer central. So mathematical structures constitute but a small island of modern mathematics. Why would someone who believes that math is at the core of reality try to reduce all of reality to just this island?

      That looks like a pretty standard definition of ‘mathematical structure’ to me. I think it’s a bit much for an author to be taken to task for that in what is after all a book intended for a popular audience, especially since the reviewer doesn’t give any clue as to what the “widespread” objects that aren’t mathematical structures are meant to be or what the “effort underway to overhaul the foundations of math” is meant to be about. (Anyone know?)

Leave a Reply

Your email address will not be published. Required fields are marked *