What is classification? Classification is one of the most basic human activities. We wake up to a world of vibrant experience and immediately begin structuring it, organizing it into objects and actions, people and animals, edible and non-edible, friend and foe, and so on. Eventually our system of classifications becomes immense and interconnected, partitioning up … Continue reading How hard is…
A hat puzzle Infinitely many prisoners are assembled in a line as pictured. Each knows their place in the line. Each wears either a black or white hat, and each can only see the hats in front of them. Starting from the back of the line, each prisoner has to guess the color of their … Continue reading Choosing things is hard: infinite hats, definability, and topology
Credit to Joel David Hamkins, who I heard discussing this paradox on an episode of the podcast My Favorite Theorem. Define a finite game to be any two-player turn-based game such that every possible playthrough ends after finitely many turns. For example, tic-tac-toe is a finite game because every game ends in at most nine … Continue reading The Hypergame Paradox
Recently I told a friend that I thought ZFC was one of humankind’s greatest inventions. He pointed out that it was pretty bold to claim this about something that most of mankind has never heard of, which I thought was a fair objection. After thinking for a bit, I reflected that the sense of greatness … Continue reading ZFC as One of Humankind’s Great Inventions
I want to describe a hierarchy of infinitary logics, and show some properties of one of these logics in particular. First, a speedy review of first order logic. In the language of first order logic we have access to parentheses {(, )}, the propositional connectives {∧, ∨, ¬, →}, the equals sign {=}, quantifiers {∀, … Continue reading Hilbert-type Infinitary Logics
Part 1 here Part 2: How big is 𝒫(ω)? Now the pieces are all in place to start applying forcing to prove some big results. Everything that follows assumes the existence of a countable transitive model M of ZFC. First, a few notes on terminology. The language of ZFC is very minimalistic. All it has … Continue reading Forcing and the Independence of CH (Part 2)
Part 2 here. Part 1: What is Forcing? Forcing is a set-theoretic technique developed by Paul Cohen in the 1960s to prove the independence of the Continuum Hypothesis from ZFC. He won a Fields Medal as a result, and to this day it’s the only Fields Medal to be awarded for a work in logic. … Continue reading Forcing and the Independence of CH (Part 1)
Assumed background knowledge: basic set theory lingo (∅, singleton, subset, power set, cardinality), what is first order logic (structures, universes, and interpretations), what are ℕ and ℝ, what’s the difference between countable and uncountable infinities, and what “continuum many” means. 1 IntroductionHere I give a high-level description of what an ultraproduct is, and provide a … Continue…
Previous: All About Countable Saturation After I had finished writing up and illustrating the proof of countable saturation in the last post, I came up with a significantly simpler proof. Darn! I don’t want to erase all those pretty pictures I already made, so I’ll just include this proof as a separate little bonus. I’m … Continue reading Shorter Proof of Countable Saturation (Ultra 7.5)
Previous: Ultraproducts and Compactness What is Countable Saturation? I’ve spent a lot of time in the last posts gushing about how cool and powerful Łoś’s theorem is. But Łoś’s theorem is only the second most powerful property of ultraproducts that I know. The most powerful is what’s known as countable saturation. Countable saturation is a … Continue reading All About Countable Saturation (Ultra…