Gödel’s Second Incompleteness Theorem Explained

This is a followup to an earlier post where I talked about Gödel’s First Incompleteness Theorem. Here, I discuss the Second Incompleteness Theorem, and further implications.

Could you remind me what the theorem was?

The theorem states that a consistent formal system cannot prove its own consistency.

As previously discussed, there are a couple qualifiers. The formal system must include some amount of arithmetic, and must have a computable set of axioms.

What does consistency mean?

A system is consistent if it cannot prove any contradictions. A system is inconsistent if it can prove a contradiction.

Contradictions sound bad. Are they bad?

Yes. The Explosion Principle states that if you can prove a direct contradiction, then you can prove absolutely any statement.

Here’s how the Explosion Principle works. Suppose A and not-A are both provable. Now consider statement B. “(A implies B) or (not-A implies B)” is a tautology. Since both A and not-A, that means we can prove B. Following the same procedure we can also prove not-B.

[Read more…]

Gödel’s First Incompleteness Theorem explained

Once upon a time, mathematicians thought they would be able to prove everything. The endeavor was known as Hilbert’s Program. They would find a complete and consistent set of axioms, and on this foundation build all of mathematics. (Although to be fair, much of mathematics was already built and was to be placed upon on those foundations retroactively.) And then, if everything went well, they would generate an algorithm that could prove every statement either true or false.

To some extent, Hilbert’s Program was successful. We now have Zermelo-Fraenkel set theory, which is a solid foundation for the vast majority of mathematics. But there are two problems. First, set theory isn’t complete. Second, we can’t prove it’s consistent. And Gödel showed that these problems have no solutions.

Gödel’s First Incompleteness Theorem: No consistent formal system is complete.
Gödel’s Second Incompleteness Theorem: No consistent formal system can prove its own consistency.
(Both of these theorems have additional qualifiers that I’ll get to later.)

Here I will explain the proof for the First Incompleteness Theorem, and a few of its implications. In a later post, I will talk about the Second Incompleteness Theorem.
[Read more…]

Kochen-Specker Theorem explained

I previously explained Bell’s Theorem, which is a “no go” theorem of quantum mechanics. In brief, Bell’s Theorem proved in 1964 that any hidden variable interpretation of quantum mechanics must be nonlocal.

Of course, you may be thinking, maybe the world just is nonlocal, and that hidden information is being passed around faster than light. Unfortunately, there’s another major theorem which makes hidden variable theories even more unpalatable. In 1966-1967, the Kochen-Specker Theorem proved that any hidden variable interpretation must be contextual.

To understand the meaning of “contextual”, suppose we have a quantum cat, and the cat has many possible states. It could be awake or asleep. It could be happy or unhappy. Or the cat could be none of those things because it is dead. Now suppose there are two possible measurements, which answer the following questions:

(1) Is the cat awake, asleep, or dead?
(2) Is the cat happy, unhappy, or dead?

This is a quantum cat, so you can only choose one of the two measurements. However, even if you can’t make both measurements experimentally, you might reasonably expect that the outcomes of the two measurements are related to each other.  Specifically, if measurement (1) would find a dead cat, then so would measurement (2), and vice versa. This assumption is called non-contextuality. This cannot be true of hidden variable interpretations of quantum mechanics! Such theories must be contextual.

Figure 1: ambiguous catFig. 1: Cat of ambiguous state.  Credit: Visentico / Sento

[Read more…]

Bell’s Theorem explained

In 2009, I wrote an explanation of Bell’s Theorem that could be understood by popular audiences. I wanted to repost it, but ended up rewriting it completely.

Although the predictions of quantum theory are well-understood, its interpretation is famously difficult. Because quantum mechanics only makes probabilistic predictions, many people have desired a “hidden variable” interpretation, where quantum objects have definite states, despite appearances to the contrary. But hidden variable interpretations are generally not accepted.

It is certainly possible to create a hidden variable interpretation that agrees with the all the predictions of quantum theory, and de Broglie-Bohm theory is an example of such a interpretation. However, de Broglie-Bohm has a number of unsatisfying properties. Indeed there are a few theorems that prove that any hidden variable interpretation must have unsatisfying properties.

The most important of these is Bell’s Theorem, formulated in 1964. What follows is an explanation of the thought experiment, the mathematical proof, and its implications.

The setup

Bell’s Theorem considers a particular thought experiment, in which two electrons are emitted simultaneously from a single source in opposite directions. This source emits electrons that are “entangled”, meaning that their quantum states are correlated with one another. If you perform the same measurement on both electrons, both measurements will always produce the same result.1
[Read more…]

Data feels

cn: rape, sexual violence, & CSA juxtaposed with cold data. This is being crossposted to my other blog.

Some of my most important activist work is in volunteering technical skills for the Asexual Census, a survey of English online ace communities. This past week, I’ve been on a roll analyzing our 2015 survey. No numbers will be reported here, this is just a personal account.

Unsurprisingly, as soon as I was done with prep work, my attention was drawn to the statistics on sexual violence. As a programmer, I’ve been trained to always use descriptive variable names. Now I’m looking at variables named “rape” and “rapeCombined”.
[Read more…]

Paper: The Chaos within Sudoku

The Chaos within Sudoku” is a paper about solving Sudoku puzzles with physics. They simulate an imaginary physical system, let it run, and when it stops the puzzle is solved. See the video below:

The thing about Sudoku is that Sudoku is hard. More specifically, when Sudoku is generalized to grids of arbitrary size, it’s NP-complete. What happens when you translate an NP-complete problem to a physical simulation? The authors find chaotic dynamics.  And in the process, they identify the hardest Sudoku puzzle…
[Read more…]