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, […]
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 […]
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. […]
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.
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 […]
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 […]
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 […]