Some things in mathematical logic that I find interesting
My four-year-old has recently started asking me questions about infinity (“is there a biggest number?”, “what’s infinity plus one”, etc.) and he and my three-year-old often get into competitions to name the biggest number. The correct answers to these questions depend on how you interpret “number” and “infinity”; I’ve decided it’s best to pick one interpretation […]
The Axiom of Choice is usually introduced as a non-constructive axiom that mathematicians used to care about but don’t really pay much attention to anymore. It’s true that mainstream mathematicians often don’t pay much attention to it, but it turns out that AC isn’t inherently non-constructive: it depends on what the base system it’s being […]
Like most people, I don’t really know anything about quantum field theory. But the other day I stumbled across this paper by Stefano Gogioso, Maria E. Stasinou, and Bob Coecke that provides a very nice framework for what sort of thing a “quantum field theory” (or really, any “field theory”) is. It certainly doesn’t mean […]
We think of a proof as being non-constructive if it proves “There exists an such that without ever actually exhibiting such an . If you want to form a system of mathematics where all proofs are constructive, one thing you can do is remove the principle of proof by contradiction: the principle that you can […]
In an interesting paper called Extending the Manipulability of Differentials, the authors Jonathan Bartlett and Asatur Zh. Khurshudyan describe an interesting proposal for representing higher-order derivatives. The argument is basically this: As is well-known, the chain rule for first derivatives seems to follow algebraically if you use Leibniz notation for the derivatives: However, there’s a […]
Two lanes of a four lane highway are closed and you’re stuck in a traffic jam. If there are no on- or off-ramps, what should you hope to see on the road ahead of you: the other two lanes re-open or one of the two open lanes close? I think you should hope to see […]
If you do a google search for how to derive the facts that and , most of the derivations you’ll find rely on knowing something like the double angle formula and go through a direct, non-trivial evaluation of . It’s actually possible to compute these derivatives this without really remembering any specific facts about trigonometry […]
You can often get the gist of a mathematical subject via an informal explanation involving infinitesimals. But I often find that questions arise from that informal explanation that I’d like resolved, but I don’t want to jump all the way to the full definitions. Without a rigorous basis for reasoning about infinitesimals, it can be […]
Until this morning, I didn’t really understand how it was possible for a sailboat to sail into the wind: popular descriptions like Wikipedia’s talk about keels and lift and the Bernoulli effect and so forth, but this feels like a leap beyond my understanding: I wanted an account of how it is even possible in […]
A while ago, I wrote a blog post called Making Money Disappear Through Infinite Iteration, and I just put out a video version of this post on youtube. Note: it’s very rough and unpolished, but I hope to make more videos and get better at their production as time goes on. I’d been interested in […]
CGP Grey is a youtuber with a variety of interesting videos, often about the quirks of geography and political boundaries. In this video, he asks the question “How many continents are there?”, discusses a variety of subtleties in the notion of “continent”, and concludes that it is not well-defined enough to provide an answer. Let’s […]
Actually, thermodynamics is hard and I don’t understand it. But even without totally understanding thermodynamics, it turns out its possible to do a surprising number of useful calculations with just a couple of simple rules about entropy. The setup is as follows: Imagine that there is some set of states of the world, called the […]
I’m not a physicist, and I’d always supposed that, while the Earth has a significant gravitational pull because it’s so massive, the gravitational pull between everyday objects must be completely undetectable, or maybe only detectable with modern laboratory equipment. But I only thought that because I never bothered to actually plug in any numbers. Using […]
Mathematical logic has a categorization of sentences in terms of increasing complexity called the Arithmetic Hierarchy. This hierarchy defines sets of sentences and for all nonnegative integers . The definition is as follows: and are both equal to the set of sentences such that a computer can determine the truth or falsity of in finite […]
Popular explanations of physical phenomena like gyroscopes or magnetic fields often end up having to explain the right-hand rule to explain how rotational quantities add (say, by using the right-hand rule to convert angular momenta into vectors, then adding the vectors). This is bad, not just because the right-hand rule is confusing, but because it […]
The Strong Law of Small Numbers (see also Wikipedia) says that “There aren’t enough small numbers to meet the many demands made of them.” It means that when you look at small numbers, it’s easy to see compelling patterns that turn out to be false when you look at larger numbers. Using complexity theory, we […]
Take a real number, . Write out its continued fraction: It’s an intriguing fact that if you look at the sequence of geometric means this approaches a single constant, called Khinchin’s constant, which is approximately , for almost every . This means that if you were to pick (for convenience, say it’s between 0 and 1) […]
Most mathy people have a pretty good mental model of what a random process is (for example, generating a sequence of 20 independent bits). I think most mathy people also have the intuition that there’s a sense in which an individual string like 10101001110000100101 is more “random” than 0000000000000000000 even though both strings are equally […]
A generating function is a formal power series where the sequence of coefficients is the object of interest. Usually the point of using them is that operations on the power series (like addition, multiplication, and differentiation) correspond to meaningful operations on your sequence of coefficients. I’ve known about the gist of generating functions for a […]
Generalizing a problem can make the solution simpler or more complicated, and it’s often hard to predict which beforehand. Here’s a mini-example of a puzzle and four generalizations which alternately make it simpler or more complicated. Warning: The solutions are given right after the puzzles. If you want to think about them, cover the screen. […]
There is a class of all cardinalities , and it has elements , and operations , , and so forth defined on it. Furthermore, there is a map which takes sets to cardinalities such that (and so on). Ordinary generating functions can be thought of entirely analogously with set maps replacing sets: There is a […]
In 1931, Alfred Tarski proved that the real ordered field allows quantifier elimination: i.e., every first-order formula is equivalent to one with no quantifiers. This is implemented in Mathematica’s “Resolve” function. The Resolve function is called like Resolve[formula,domain] where domain gives the domain for the quantifiers in formula. Since we’ll always be working over in […]
Edit: These ideas are also discussed here and here (thanks to Qiaochu Yuan: I found out about those links by him linking back to this post). Although topology is usually motivated as a study of spatial structures, you can interpret topological spaces as being a particular type of logic, and give a purely logical, non-spatial […]
Let be the set of propositions considered by some rational logician (call her Sue). Further, suppose that is closed under the propositional connectives , , . Here are two related but different preorders on : if logically entails . if Sue considers at least as likely to be true as is. Let be the equivalence […]
The normal square root function can be considered to be multi-valued. Let’s momentarily accept the heresy of saying that the square root of a negative number is , so that our function will be total. How can we represent the situation of this branching “function” topologically? One thing we could do is just take the […]
By “voting”, I mean the following general problem: Suppose there are candidates and voters. Each voter produces a total ordering of all candidates. A voting procedure is a function which takes as input all orderings, and produces an output ranking of all candidates. Arrow’s impossibility theorem states that there is really no satisfactory voting procedure […]
In the book Good and Real, author Gary Drescher, who received his PhD from MIT’s AI lab, defends the view that determinism is a consistent and coherent view of the world. In doing so, he enters many different arenas: ethics, decision theory, and physics. In his chapter on quantum mechanics, he defends the “many-worlds” interpretation […]
A function from to is called even if for all , . We might call it even about the point if, for all , . Conversely, we can call a function strongly non-even if for all , , . Finding strongly non-even functions is easy, as any injective function provides a trivial example. We can […]
You may have heard about the Tarski-Seidenberg theorem, which says that the first-order theory of the reals is decidable, that the first-order theory of the complex numbers is similarly decidable, or that the first order theory of the integers without multiplication is decidable. In the course of John Harrison‘s logic textbook Handbook of Practical 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, […]
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. My […]
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 […]
We can think of a computably enumerable (or c.e.) set as a bag which some computer program puts more and more numbers into over time. The set then consists of all numbers which are in the bag from some point on (i.e., the numbers which are eventually put in the bag by the program). Suppose […]
Let be the set of all such that the th Turing machine halts. (For these puzzles, we will assume that Turing machines are always run on a blank initial state, i.e., they take no input.) Recall that is computably enumerable, but not decidable. Puzzle #1. Describe a winning strategy for the following game: You are […]
The natural numbers can all be finitely represented, as can the rational numbers. The real numbers, however, cannot be so represented and require some notion of “infinity” to define. This makes it both computationally and philosophically interesting to determine for what purposes you need the real numbers, and for what purposes you need only the […]
Suppose that we wanted to construct a mathematical universe where all objects were computable in some sense. How would we do it? Well, we could certainly allow the set into our universe: natural numbers are the most basic computational objects there are. (Notation: I’ll use to refer to when we’re considering it as part of […]
Many strongly typed languages like OCaml do type inference. That is, even though they’re strongly typed, you don’t have to explicitly say what the type of everything is since a lot of the time the compiler can figure it out by itself. For example, if you define a function which takes an x and adds […]
Chomp is a two-player game which is played as follows: The two players, A and B, start with a “board” which is a chocolate bar divided into small squares. With Player A starting, they take turns choosing a square and eating it together with all squares above and to the right. The catch is that […]
Intuitively, for any property of sets, there should be a set which has as its members all and only those sets such that holds. But this can’t actually work, due to Russell’s Paradox: Let , and then you can derive a contradiction from both and . The standard solution to this is essentially to forbid […]
In the book A=B, the authors point out that while the identity is provable (by a very simple proof!), it’s not possible to prove the truth or falsity of all such identities. This is because Daniel Richardson proved the following: Let denote the class of expressions generated by The rational numbers, and . The variable […]
There are many functions from to that cannot be computed by any algorithm or computer program. For example, a famous one is the halting problem, defined by if the th Turing machine halts and if the th Turing machine does not halt. Another one in the same spirit is the busy beaver function. We also […]
Please enjoy the following guest post on differential geometry by Tim Goldberg. A symplectic structure on a manifold is a differential -form satisfying two conditions: is non-degenerate, i.e. for each and tangent vector based at , if for all tangent vectors based at , then is the zero vector; is closed, i.e. the exterior derivative […]
In the course of looking up a link for my last blog entry, I discovered the MAA Writing Awards site, which collects many pdfs of articles that have won MAA writing awards. From browsing it a bit, it seems to be a goldmine of fun math articles.
I’m a big fan of non-rigorous arguments, especially in calculus and analysis. I think there should be a book cataloging all the beautiful, morally-true-but-not-actually-true proofs that mathematicians have advanced, but until that time I’ll try to at least catalog a few of them on my blog. This first one is Euler’s original argument for the […]
Why did the chicken cross the island on Lost? To get to the Others’ side. (Composed by Tim Goldberg.)
An arithmetic statement is one made up of quantifiers “,” “,” the logical connectives “and,” “or,” “not”, function symbols , , constants , , and variables which are bound by the aforementioned quantifiers. It is known that there is no algorithm which will decide whether or not an arithmetic statement is true or not. This […]