Gödel’s Second Incompleteness Theorem for Programmers

In the previous blog post in this series, we looked at Gödel’s First Incompleteness Theorem, and came to the amazing conclusion that we can’t compute certain kinds of functions in formal systems (like Javascript). Specifically, we looked at a special function, , which turned out to be non-computable. In case we forgot, the first incompleteness … [Read more…]

Gödel’s First Incompleteness Theorem for Programmers

Gödel’s incompleteness theorems have been hailed as “the greatest mathematical discoveries of the 20th century” — indeed, the theorems apply not only to mathematics, but all formal systems and have deep implications for science, logic, computer science, philosophy, and so on. In this post, I’ll give a simple but rigorous sketch of Gödel’s First Incompleteness … [Read more…]

Confusing Math with Morality

This essay is in response to Counterintuitive problem: Everyone in a room keeps giving dollars to random others. You’ll never guess what happens next. Dan Goldstein attributes the problem to Uri Wilensky, of Northwestern, who formulates it thusly: Imagine a room full of 100 people with 100 dollars each. With every tick of the clock, … [Read more…]

How to prove there is no Universe

Years ago, when I first read Paul Halmos’ seminal Naive Set Theory, I was blown away by how easy it was to prove that there is no universe. In fact, not even three sections in, he drops this italicized bombshell: $$nothing\text{ }contains\text{ }everything$$ or, “more spectacularly,” he continues $$there\text{ }is\text{ }no\text{ }universe$$ Luckily, we only … [Read more…]