# An Interesting Puzzle in Propositional Logic

Suppose that you’re translating an ancient text, and in this text you come across three words whose meaning you are unsure of: , , and .  So, you head down to the ancient language department of your local university. The first professor you come across, , knows what means, the second professor you come across, […]

# What Happens When You Iterate Gödel’s Theorem?

Let be Peano Arithmetic.  Gödel’s Second Incompleteness Theorem says that no consistent theory extending can prove its own consistency. (I’ll write for the statement asserting ‘s consistency; more on this later.) In particular, is stronger than .  But certainly, given that we believe that everything proves is true, we believe that does not prove a […]

# Trigonometric Series and the Beginnings of Set Theory

Let be a -periodic function. It may or may not have a representation as a trigonometric series A natural question to ask is whether or not the representation of as a trigonometric series is unique, if it has one. It was the consideration of this question that led Cantor to the invention of set theory. […]

# A Simple Introduction to Quantum Groups

In the course of reading some background material for an article by James Worthington on using bialgebraic structures in automata theory, I was led to finally reading up on what a Hopf algebra (sometimes called a “quantum group“) is. Although it is not strictly related to logic, I’ll write up what I learned here.

# Doing Calculus on the Rationals (with the help of Nonstandard Analysis)

Nonstandard Analysis is usually used to introduce infinitesimals into the real numbers in an attempt to make arguments in analysis more intuitive. The idea is that you construct a superset which contains the reals and also some infinitesimals, prove that some statement holds of , and then use a general “transfer principle” to conclude that […]

# Games Which are Impossible to Analyze

In the last post, I mentioned the computational complexity of various games. To be explicit, we consider each “game” to actually be a sequence of games for . For example, would be checkers played on an board. The problem was then to analyze the computational complexity of the function which takes and tells you which […]

# How to Show that Games are Hard

Peg Solitaire is a pretty popular game, often found in restaurants (including Cracker Barrel, if I remember correctly). It’s also NP-complete (by which I mean determining a winning strategy given the initial set-up is an NP-complete problem). You may have also heard of computational complexity results for Minesweeper (see here, for example). There are a […]