Category Archives: Uncategorized

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.

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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, … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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: … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

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 … Continue reading →

Why did the chicken cross the island on Lost?

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 … Continue reading →