XOR’s Hammer

July 19, 2009

Functions with Very Low Symmetry and the Continuum Hypothesis

A function from $\mathbb{R}$ to $\mathbb{R}$ is called even if for all $h\in\mathbb{R}$ , $f(-h) = f(h)$ . We might call it even about the point $x$ if, for all $h\in\mathbb{R}$ , $f(x-h) = f(x +h)$ .

Conversely, we can call a function strongly non-even if for all $x\in\mathbb{R}$ , $h>0$ , $f(x-h)\ne f(x+h)$ .

Finding strongly non-even functions is easy, as any injective function provides a trivial example. We can make things harder for ourselves by considering only functions from $\mathbb{R}$ to $\mathbb{N}$ . But now, it is just as easy to show that there are no strongly non-even functions.

Therefore, let’s make the following definition: Let a function $f\colon \mathbb{R}\to\mathbb{N}$ be non-even of order $n$ if, for all $x$ , $|\{h>0\mid f(x-h) = f(x + h)\}|\leq n$ . Thus, a strongly non-even function is non-even of order $0$ , and a function being non-even of order $n$ implies that it’s non-even of order $m$ for all $m\geq n$ .

In this paper, the set theorists Peter Komjáth and Saharon Shelah proved:

The existence of a non-even function of order 1 is equivalent to the Continuum Hypothesis (i.e., the statement that $2^{\aleph_0} = \aleph_1$ ).

Thus, if we assume that there is a non-even function of order 1, then we can conclude that $2^{\aleph_0} = \aleph_1$ . Can we weaken the hypothesis and still conclude something interesting? We can, as they also proved:

For any $n$ , if there is a non-even function of order $n$ , then $2^{\aleph_0}\leq \aleph_{\lceil\log_2{(n+1)}\rceil}$ .

Keep reading →

3 Comments

Filed under Uncategorized

May 14, 2009

A Suite of Cool Logic Programs

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 and Automated Reasoning, all three of these algorithms (and many more) are implemented. Furthermore, you can download and play with them for free. (However, I still recommend checking out the book: especially if you are looking for a good textbook for a course on logic with a concrete, computational bent.)

Below, I’ll describe how to install the programs and try them out. There are many more interesting functions in this suite that I haven’t described.

Keep reading →

2 Comments

Filed under Uncategorized

April 9, 2009

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: $\mathit{bal}$ , $\mathit{kat}$ , and $\mathit{lot}$ . So, you head down to the ancient language department of your local university.

The first professor you come across, $\hbox{Prof. Bal}$ , knows what $\mathit{bal}$ means, the second professor you come across, $\hbox{Prof. Kat}$ , knows what $\mathit{kat}$ means, and the third professor you come across, $\hbox{Prof. Lot}$ , knows what $\mathit{lot}$ means. So you have fortunately solved your problem.

But you’re now curious and decide to meet some other professors in the department. The next professor you come across is named $\hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat})$ . He doesn’t know what $\mathit{bal}$ means or what $\mathit{kat}$ means, but if you told him what $\mathit{bal}$ meant, he would be able to tell you what $\mathit{kat}$ means (for example, maybe he knows that $\mathit{kat}$ is the noun form of $\mathit{bal}$ ).

The next professor you meet is named $\hbox{Prof. }(\mathrm{Bal}\rightarrow(\mathrm{Kat}\rightarrow\mathrm{Lot}))$ . If you told him what $\mathit{bal}$ meant and what $\mathit{kat}$ meant, he would be able to tell you what $\mathit{lot}$ means.

The next professor you meet is named $\hbox{Prof. }((\mathrm{Bal}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Lot})$ . If you told him a method for finding out the meaning of $\mathit{kat}$ given the meaning of $\mathit{bal}$ , he would be able to tell you the meaning of $\mathit{lot}$ .

In general, for any two professors $\hbox{Prof. }P$ and $\hbox{Prof. }Q$ , there is a professor $\hbox{Prof. }P\rightarrow Q$ with the property that if you told him what $\hbox{Prof. }P$ knew, he would be able to tell you what $\hbox{Prof. }Q$ knows (but $\hbox{Prof. }P\rightarrow Q$ doesn’t know any more than that).

Notice that some professors have essentially the same state of knowledge. For example, $\hbox{Prof. Bal}$ and $\hbox{Prof. }((\mathrm{Kat}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})$ have essentially the same knowledge, since to get the meaning of $\mathit{bal}$ out of $\hbox{Prof. }((\mathrm{Kat}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})$ you only have to tell him a method for finding out the meaning of $\mathit{kat}$ given the meaning of $\mathit{kat}$ , which is something that you can do without any particular special knowledge concerning $\mathit{bal}$ , $\mathit{kat}$ and $\mathit{lot}$ .

A more nontrivial example is that $\hbox{Prof. }(((\mathrm{Bal}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})\rightarrow\mathrm{Kat})$ has the same state of knowledge as $\hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat})$ . This is because each can “simulate” the other. In one direction, suppose somebody told $\hbox{Prof. }(((\mathrm{Bal}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})\rightarrow\mathrm{Kat})$ the meaning of $\mathit{bal}$ . He therefore knows a trivial “method” for getting the meaning of $\mathit{bal}$ given any inputs, and so he knows the meaning of $\mathit{kat}$ . In the other direction, suppose we told $\hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat})$ a method for turning (methods for turning the meaning of $\mathit{bal}$ into the meaning of $\mathit{kat}$ ) into the meaning of $\mathit{bal}$ . Well, $\hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat})$ knows a method for turning the meaning of $\mathit{bal}$ into the meaning of $\mathit{kat}$ , so he can use that find the meaning of $\mathit{bal}$ . He can then use his method a second time to turn that into the meaning of $\mathit{kat}$ .

The puzzle is then to prove that there are only finitely many professors with different states of knowledge.

This puzzle is equivalent to showing that intuitionistic implicational propositional logic over three variables has only finitely many logically inequivalent formulas. Another formulation is: Let $\mathbb{C}_n$ be the free cartesian closed category over $n$ objects. Given objects $A$ and $B\in \mathbb{C}_n$ , say that $A$ and $B$ are equivalent if there is an arrow from $A$ to $B$ and an arrow from $B$ to $A$ . Then there are only finitely many equivalence classes in $\mathbb{C}_3$ . (The corresponding statements are also true with $3$ replaced by $n$ .)

Keep reading →

Leave a Comment

Filed under Uncategorized

March 23, 2009

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

Let $\mathrm{PA}$ be Peano Arithmetic. Gödel’s Second Incompleteness Theorem says that no consistent theory $T$ extending $\mathrm{PA}$ can prove its own consistency. (I’ll write $\mathrm{Con}(T)$ for the statement asserting $T$ ’s consistency; more on this later.)

In particular, $\mathrm{PA} + \mathrm{Con}(\mathrm{PA})$ is stronger than $\mathrm{PA}$ . But certainly, given that we believe that everything $\mathrm{PA}$ proves is true, we believe that $\mathrm{PA}$ does not prove a contradiction, and hence is consistent. Thus, we believe that everything that $(\mathrm{PA} + \mathrm{Con}(\mathrm{PA}))$ proves is true. But by a similar argument, we believe that everything that $(\mathrm{PA} + \mathrm{Con}(\mathrm{PA} + \mathrm{Con}(\mathrm{PA})))$ proves is true. Where does this stop? Once we believe that everything $\mathrm{PA}$ proves is true, what, exactly, are we committed to believing?

Keep reading →

5 Comments

Filed under Uncategorized

December 20, 2008

Trigonometric Series and the Beginnings of Set Theory

Let $f\colon\mathbb{R}\to\mathbb{R}$ be a $2\pi$ -periodic function. It may or may not have a representation as a trigonometric series

$\displaystyle{a_0+\sum_{n=1}^\infty a_n\sin(nx) + b_n\cos(nx)}$

A natural question to ask is whether or not the representation of $f$ 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.

There is a nice writeup of this story in the first part of this article by Alexander Kechris. I’ll give part of the story below.

Keep reading →

Leave a Comment

Filed under Uncategorized

December 11, 2008

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.

Keep reading →

1 Comment

Filed under Uncategorized

November 14, 2008

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 $\mathbb{R}^*$ which contains the reals and also some infinitesimals, prove that some statement holds of $\mathbb{R}^*$ , and then use a general “transfer principle” to conclude that the same statement holds of $\mathbb{R}$ .

Implicit in this procedure is the idea that $\mathbb{R}$ is the real world, and therefore the goal is to prove things about it. We construct a field $\mathbb{R}^*$ with infinitesimals, but only as a method for eventually proving something about $\mathbb{R}$ .

We can do precisely the same thing with $\mathbb{Q}$ instead of with $\mathbb{R}$ . But, in Weak Theories of Nonstandard Arithmetic and Analysis, Jeremy Avigad observed that if we don’t care about transferring the results back down to $\mathbb{Q}$ , then we can get all the basic results of calculus and elementary real analysis just by working with $\mathbb{Q}^*$ , and without ever having to construct the reals.

Keep reading →

2 Comments

Filed under Uncategorized

November 9, 2008

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” $G$ to actually be a sequence of games $\{G_n\}$ for $n\in \mathbb{N}$ . For example, $\text{checkers}_n$ would be checkers played on an $n\times n$ board. The problem was then to analyze the computational complexity of the function which takes $n$ and tells you which player has a winning strategy and what the winning strategy is. I’ll call that function the analysis function of $G$ .

Are there any games which can actually be played in the real world with an undecidable analysis function? Robern Hearn, in the same thesis that I linked to last time, showed that the answer is yes.

Keep reading →

Leave a Comment

Filed under Uncategorized

November 3, 2008

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 number of other results showing that various popular games are complete for some complexity class.

But what if you come across a new game, which no computer scientist has heard of yet? Well, you’re in luck, as Robert Hearn, in his thesis, formulated a framework called Constraint Logic intended to make it easy to prove complexity results for games.

Keep reading →

1 Comment

Filed under Uncategorized

October 26, 2008

Another Puzzle in Recursion Theory: n-Enumerable Sets

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 that we relax the restrictions on the program, and we allow it to take a number out of the bag that it has put in (but once the program has done that, the number stays out forever). We call the set of numbers which are in the bag from some point on (i.e., the set of numbers which are put in the bag and never taken out) in a procedure of this sort a 2-c.e. set.

We can analogously let an $n$ -c.e. set be one given by a program which can, for each number, “toggle” that number’s status up to and including $n$ times if it likes.

The puzzle is then to find, for each $n$ , an example of a set which is $n$ -c.e. but not $n-1$ -c.e.

Keep reading →

Leave a Comment

Filed under Puzzles

October 16, 2008

Two Puzzles in Recursion Theory: Verbose Sets and Terse Sets

Let $K$ be the set of all $n$ such that the $n$ 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 $K$ is computably enumerable, but not decidable.

Puzzle #1. Describe a winning strategy for the following game: You are given three numbers $x_1, x_2, x_3$ . You must correctly say for each number whether or not it is in $K$ . You are allowed to ask (and receive a truthful answer to) two questions of the form “Is $n$ in K?” for any $n$ .

Puzzle #2. Show that there is no winning strategy for the game which is the same as that in Puzzle #1 except you are given two numbers and may ask only one question. (Even stronger, show that if $S\subset \mathbb{N}$ is a set such that you can win that game, then $S$ must be decidable.)

Keep reading →

2 Comments

Filed under Puzzles

October 13, 2008

When are the Real Numbers Necessary?

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 rationals.

It’s pretty clear that spatial concepts having to do with distances and rotation require the real numbers. For example, if we took $\mathbb{Q}^2$ as our model of the plane, the distance from $(0,0)$ to $(1,1)$ would not be rational, and we would not be able to rotate the point $(1,0)$ about the point $(0,0)$ by most angles.

But I always implicitly thought that spatial notions not depending on distances or angles required only the rationals. It turns out that I was wrong: there are spatial notions not depending on distances or angles which differ depending on whether you take space to be $\mathbb{Q}^n$ or $\mathbb{R}^n$ . The fact that I was wrong follows from a theorem of Micha Perles which is very famous in combinatorics, but which I only found out about recently.

Keep reading →

5 Comments

Filed under Uncategorized

October 13, 2008

What Would the World Look Like if Everything was Computable?: An Introduction to Hyland’s Effective Topos

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 $\mathbb{N}$ into our universe: natural numbers are the most basic computational objects there are. (Notation: I’ll use $N$ to refer to $\mathbb{N}$ when we’re considering it as part of the universe we’ll building, and just $\mathbb{N}$ when we’re talking about the set of natural numbers in the “real” world.) What should we take as our set of functions $N^N$ from $N$ to $N$ ? Since we want to admit only computable things, we should let $N^N$ be the set of computable functions from $\mathbb{N}$ to $\mathbb{N}$ , which we can represent non-uniquely by their indices (i.e., by the programs which compute them).

(For clarity, I’ll use the following notation for computable functions: $\phi_e$ denotes the partial function from $\mathbb{N}$ to $\mathbb{N}$ computed by the $e$ th Turing machine. Given $n\in\mathbb{N}$ , it is possible that the computation $\phi_e(n)$ never halts; in that case, I’ll write $\phi_e(n){\uparrow}$ and say that $\phi_e(n)$ is undefined. If it does halt, I’ll write $\phi_e(n){\downarrow}$ and say that $\phi_e(n)$ is defined. If it halts, then it yields an output $m$ . To indicate what it is, I’ll write $\phi_e(n) = m$ or $\phi_e(n){\downarrow} = m$ .)

So, we’ve decided that $N^N$ should equal $\{e \mid \forall n\in\mathbb{N}\, \phi_e(n){\downarrow}\}$ . What should $N^{\left(N^N\right)}$ equal? At this point, there is a slight subtlety: It’s not simply the set of computable functions from $N^N$ (considered as a subset of $\mathbb{N}$ ) to $N$ (considered as $N$ ), because we would like to only admit those functions from $N^N$ to $N$ that return the same number when given inputs which represent the same element of $\mathbb{N}^\mathbb{N}$ .

Therefore, we’ll let $N^{(N^N)}$ be the set of $e\in\mathbb{N}$ such that, for all $n\in N^N$ , $\phi_e(n){\downarrow}$ , and whenever $n,m\in N^N$ are such that for all $x\in\mathbb{N}$ , $\phi_n(x) = \phi_m(x)$ , then $\phi_e(n) = \phi_e(m)$ .

We can similarly define $(N^N)^{(N^N)}$ , except that there are now two places where we should take into account that we consider $n,m\in N^N$ equivalent if for all $x\in\mathbb{N}$ , $\phi_n(x) = \phi_m(x)$ : We’ll let $(N^N)^{(N^N)}$ be the set of $e$ such that, whenever $n, m \in N^N$ are equivalent in the aforementioned sense, $\phi_e(n)$ and $\phi_e(m)$ are defined and equivalent in the aforementioned sense.

In a similar fashion, we can define $(N^{(N^N)})^{(N^N)}$ and so on; these sets are called the sets of hereditarily computable functions.

Can we generalize this construction to a category that incorporates all possible computable representations of real objects? More ambitiously, can we generalize to a category that is a genuine mathematical universe in the sense that questions like “Does the Riemann Hypothesis hold in this category?” are meaningful? The answer, due to Martin Hyland, is yes.

Keep reading →

2 Comments

Filed under Toposes

October 7, 2008

A language which does term inference

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 it to 3, the compiler will figure out that x is an int. (It couldn’t be a float, since it was added to 3 and not 3.0.)

But it often seems like the compiler should be able to infer not just the types of expressions, but the expressions themselves! For example, if the compiler infers that the type of some function f is (int -> int) -> (int list) -> int list (i.e., f is a higher-order function which takes a function from int to int, a list of ints, and produces a list of ints), then f is very probably the map function, defined informally by

map g [x_1;...;x_n] = [g x_1;...;g x_n].

Therefore, if the compiler determines that some expression has that type, and the user has somehow omitted the actual function definition, why not allow the compiler to infer what the expression is?

I made a stab at implementing this type of idea in a toy language I call TermInf (apologies for the weird hosting: I don’t have another hosting service at the moment). It’s a modification of the toy language Poly from Andrej Bauer’s Programming Language Zoo. You’ll need OCaml to compile it. Please feel free to alert me to any bugs or to tell me that my code is horrible.

More details below.

Keep reading →

7 Comments

Filed under Functional Programming

September 29, 2008

Playing Games in the Transfinite: An Introduction to “Ordinal Chomp”

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 $n \times m$ 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 the square at the lower left-hand corner is poisonous, and the player who is forced to eat it loses.

This image from the Wikipedia article shows a typical sequence of moves for a $5\times 3$ chocolate bar:

At this point, Player A is forced to eat the poisoned square and hence loses the game.

Although the question of what the winning strategies are for this game is very much an open problem, the question of who has a winning strategy is not: On the $1\times 1$ board, Player B wins (since Player A must eat the poison piece on his first move). But for any other board, Player A has a winning strategy.

To see why, suppose not. Then if Player A’s first move is to eat just the one square in the top right-hand corner, Player B must have a winning response (since we are supposing that Player B has a winning response to any move that Player A makes). But if Player B’s response is winning, then Player A could have simply made that move to start with.

However, suppose we play Chomp not just on $n\times m$ boards, but on $\alpha\times\beta$ boards, where $\alpha$ and $\beta$ are arbitrary ordinals. The game still makes sense just as before, and will always end in finite time, but Player A no longer wins all of the time (there will no longer be a top right-hand corner square if either $\alpha$ or $\beta$ is a limit ordinal).

Scott Huddleston and Jerry Shurman investigated Ordinal Chomp in this paper, and showed that it has a number of interesting properties. I’ll describe a few of them below.

Keep reading →

4 Comments

Filed under Uncategorized

September 21, 2008

Avoiding Set-Theoretic Paradoxes using Symmetry

Intuitively, for any property $P(x)$ of sets, there should be a set $\{x \mid P(x)\}$ which has as its members all and only those sets $x$ such that $P(x)$ holds. But this can’t actually work, due to Russell’s Paradox: Let $b = \{x\mid x\notin x\}$ , and then you can derive a contradiction from both $b\in b$ and $b\notin b$ .

The standard solution to this is essentially to forbid the construction of any set which is too big. This solves the problem since you can prove that there are many sets which are not members of themselves, making $b$ too big to be a set. But you also end up throwing out many sets which you might want to have: for example, the set of all sets, the set of all groups, etc.

Randall Holmes recently published a paper espousing another solution: instead of forbidding the construction of sets which are too big, forbid the construction of sets which are too asymmetric. Details below.

Keep reading →

1 Comment

Filed under Uncategorized

September 14, 2008

The Undecidability of Identities Involving Sine, Exponentiation, and Absolute Value

In the book A=B, the authors point out that while the identity

$\displaystyle{\sin^2(|10 + \pi x|) + \cos^2(|10 + \pi x|) = 1}$

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 $\mathcal{R}$ denote the class of expressions generated by

The rational numbers, and $\pi$ .
The variable $x$
The operations of addition, multiplication, and composition.
The sine, exponential, and absolute value functions.

Then the problem of deciding whether or not an expression $E$ in $\mathcal{R}$ is identically zero is undecidable. This means as well that the problem of deciding whether or not two expressions $E_1, E_2\in \mathcal{R}$ are always equal is also undecidable, since this is equivalent to deciding if $E_1 - E_2 = E_1 + (-1)\cdot E_2$ is identically zero.

A summary of Richardson’s proof (mostly from Richardson’s paper itself) is below.

Keep reading →

1 Comment

Filed under Uncategorized

September 4, 2008

A Geometrically Natural Uncomputable Function

There are many functions from $\mathbb{N}$ to $\mathbb{N}$ that cannot be computed by any algorithm or computer program. For example, a famous one is the halting problem, defined by $f(n) = 0$ if the $n$ th Turing machine halts and $f(n) = 1$ if the $n$ th Turing machine does not halt. Another one in the same spirit is the busy beaver function.

We also know a priori that there must be uncomputable functions, since there are $2^{\aleph_0}$ functions from $\mathbb{N}$ to $\mathbb{N}$ but only $\aleph_0$ computer programs. But that is nonconstructive, and the two examples I gave above seem a bit like they’re cheating since their definitions refer to the concept of computability. Is there a natural example of an uncomputable function that does not refer to computability?

In this paper, Alex Nabutovsky found what I think is a great example of such a function from geometry. Details below.

Keep reading →

2 Comments

Filed under Uncategorized

September 4, 2008

Integrability Conditions (Guest Post!)

Please enjoy the following guest post on differential geometry by Tim Goldberg.

A symplectic structure on a manifold $M$ is a differential $2$ -form $\omega$ satisfying two conditions:

$\omega$ is non-degenerate, i.e. for each $p \in M$ and tangent vector $\vec{u}$ based at $p$ , if $\omega_p(\vec{u},\vec{v}) = 0$ for all tangent vectors $\vec{v}$ based at $p$ , then $\vec{u}$ is the zero vector;
$\omega$ is closed, i.e. the exterior derivative of $\omega$ is zero, i.e. $\mathrm{d} \omega = 0$ .

In trying to come up with answers to questions like “what do you do?” and “what is symplectic geometry?” that would be accessible to an advanced undergraduate or beginning graduate student, I’ve tried to come up with fairly intuitive descriptions of what the two symplectic structure conditions really mean.

Non-degeneracy is pretty easy, because my intended audience is certainly familiar with the dot product in Euclidean space, and probably familiar with more general machinery like inner products and bilinear forms. A bilinear form on a vector space over a field $\mathbb{F}$ is just an assignment of a number in $\mathbb{F}$ to each pair of vectors, in such a way that the assignment is linear in each vector in the pair. A bilinear form is called non-degenerate if the only thing that pairs to zero with every single vector is the zero vector. A $2$ -form on $M$ is a collection $\omega = \{ \omega_p \mid p \in M \}$ of skew-symmetric bilinear forms, one for each tangent space of $M$ . Saying that $\omega$ is non-degenerate is saying that each of these bilinear forms is non-degenerate.

It’s much less clear how to describe to the uninitiated what the closed condition means. It’s even a bit unclear why this condition is required in the first place. A pretty nice answer came up yesterday, in a reading group I attend that is trying to learn about generalized complex structure. We are going through the PhD thesis of Marco Gualtieri, titled “Generalized Complex Geometry”. It is available at the following websites:

http://front.math.ucdavis.edu/0401.5221

http://front.math.ucdavis.edu/0703.5298.

This was the first meeting, and Tomoo Matsumura was the speaker. He suggested that the requirement that $\mathrm{d} \omega = 0$ is an integrability condition. I had never thought of it this way, but I probably will from now on.
Keep reading →

Leave a Comment

Filed under Uncategorized

August 29, 2008

Lots of Fun Math Papers

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.

Leave a Comment

Filed under Uncategorized

August 29, 2008

Non-Rigorous Arguments 1: Two Formulas For e

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 equality of two expressions (both of which happen to define $e$ ):

$\displaystyle{\sum_{n=0}^\infty \frac{1}{n!} = \lim_{n\to\infty}\left(1 + \frac{1}{n}\right)^n}$

I’ll also sketch how this can be made rigorous in non-standard analysis.

Keep reading →

Leave a Comment

Filed under Uncategorized

August 25, 2008

A Curious Application of Ambiguity with Respect to the Possessive Form

Why did the chicken cross the island on Lost?

Keep reading →

Leave a Comment

Filed under Uncategorized

August 25, 2008

Almost a Number-Theoretic Miracle

An arithmetic statement is one made up of quantifiers “ $\forall n\in\mathbb{N}$ ,” “ $\exists n\in \mathbb{N}$ ,” the logical connectives “and,” “or,” “not”, function symbols $\times$ , $+$ , constants ${0}$ , $1$ , and variables $n$ 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 shouldn’t be surprising, since if there were such an algorithm, it would be able to automatically prove Fermat’s Last Theorem, settle Goldbach’s Conjecture and the Twin Prime Conjecture, etc.

However, if we call a quasi-arithmetic statement one which uses the quantifiers “for all but finitely many $n \in\mathbb{N}$ ” (denoted “ $\forall^\infty n\in\mathbb{N}$ ”) and “there exists infinitely many $n\in\mathbb{N}$ ” (denoted “ $\exists^\infty n\in\mathbb{N}$ ”) instead of “ $\forall n\in\mathbb{N}$ ” and “ $\exists n\in\mathbb{N}$ ”, then we do have an algorithm for deciding whether a quasi-arithmetic statement is true or not!

Keep reading →

1 Comment

Filed under Uncategorized

August 23, 2008

Set Theory and Weather Prediction

Here’s a puzzle:

You and Bob are going to play a game which has the following steps.

Bob thinks of some function $f\colon \mathbb{R}\to\mathbb{R}$ (it’s arbitrary: it doesn’t have to be continuous or anything).

You pick an $x \in \mathbb{R}$ .

Bob reveals to you the table of values $\{(x_0, f(x_0))\mid x_0\ne x\}$ of his function on every input except the one you specified

You guess the value $f(x)$ of Bob’s secret function on the number $x$ that you picked in step 2.

You win if you guess right, you lose if you guess wrong. What’s the best strategy you have?

This initially seems completely hopeless: the values of $f$ on inputs $x_0\ne x$ have nothing to do with the value of $f$ on input $x$ , so how could you do any better then just making a wild guess?

In fact, it turns out that if you, say, choose $x$ in Step 2 with uniform probability from $\lbrack 0,1\rbrack$ , the axiom of choice implies that you have a strategy such that, whatever $f$ Bob picked, you will win the game with probability 1!

Keep reading →

6 Comments

Filed under Puzzles, Set Theory

August 22, 2008

Making Money Disappear Through Infinite Iteration

In Joel David Hamkin’s paper Supertasks and Computation, he relates the following puzzle: Suppose that you have a countable infinity of dollar bills, and one day you meet the devil, who offers you the following bargain: In the first half minute from now, the devil will give you two dollar bills, and take one from you in return. In the quarter minute after that, the devil again gives you two dollar bills, and takes one from you in return. And so on, in the eighth of a minute after that, and the sixteenth of a minute after that, etc. After a minute, the whole transaction is complete. Should you take this bargain?

The answer is “no” and the reason is that the devil could do the following: Think of the bills you have at the start as being numbered 1, 3, 5, etc. and imagine that the devil has an initial pile of bills numbered 2, 4, 6, etc. Then on the nth transaction, the devil gives you the two lowest-numbered bills from his initial pile and takes bill n from you (one can easily show that you have bill n in your possession at this point). Since the devil takes bill n from you on the nth transaction, he gets all the bills in the end and you end up with nothing.

So, even though you start with infinitely many bills and each transaction produces a net gain of one bill for you, after all the transactions are done you have nothing.

In that puzzle, the devil was able to use a tricky strategy to give you more than he took at each stage and still end up with everything. In the following puzzle, which made the rounds when I was a graduate student, no matter what the devil does, he takes everything from you!

You and the devil are taking a train ride together. The train stops at each ordinal. At stop 0, you have countably infinitely many dollar bills. At each stop, the devil does the following two things (in order):

If you have nonzero number of dollar bills, the devil takes one and destroys it.

The devil gives you countably infinitely many dollar bills.

Prove that no matter what the devil does, when the train reaches stop $\omega_1$ (the first uncountable ordinal), you will have no money.

Solution below.

Keep reading →

2 Comments

Filed under Ordinals, Puzzles, Set Theory

August 21, 2008

What do We Have to Know About a Function in Order to Compute its Definite Integral?

Suppose that $f$ is a continuous function from $\lbrack 0,1\rbrack$ to $\lbrack 0,1\rbrack$ and that we have a program which computes it. (Ignore for now exactly what it means to “compute” a real-valued function of the reals. Suffice it to say that almost every natural continuous function you come across is computable). If we want to compute $\int_{0}^1 f(x)\,dx$ , say to within an accuracy of $0.001$ , how would we do it, and would we need any further information about $f$ in order to do it?

The obvious thing to do is to compute a Riemann sum $R(f,n)=\sum_{i=0}^{n-1} (1/n)\cdot f(i/n)$ for some large $n$ . However, this could be arbitrarily far from the true value of $\int_0^1 f(x)\,dx$ . For example, $f(i/n)$ might be 0 for all $0 \leq i \leq n-1$ , but $f$ might curve sharply up in between each $i/n$ and $(i+1)/n$ so that its definite integral is arbitrarily close to 1.

However, since $f$ is continuous on $\lbrack 0,1\rbrack$ , it is uniformly continuous. This means that for all $\epsilon > 0$ there is a $\delta > 0$ such that whenever $|x - y| < \delta$ , $|f(x) - f(y)| < \epsilon$ . If we could compute a function $\delta(\epsilon)$ such for all $\epsilon > 0$ , whenever $|x - y| < \delta(\epsilon)$ , $|f(x) - f(y)| < \epsilon$ , then we could compute the definite integral of $f$ with arbitrary accuracy: If we want to know $\int_0^1 f(x)\, dx$ to within 0.001, then choose $n$ so that $1/n < \delta(0.001)$ and we can take $R(f,n)$ , since $|R(f,n) - \int_0^1 f(x)\,dx| < 0.001$ .

So, one answer to the question “What extra information do we need in order to compute $\int_0^1 f(x)\,dx$ ?” is: a function $\delta(\epsilon)$ witnessing $f$ ’s uniform continuity.

In 1998, Alex Simpson showed, building on ideas of Ulrich Berger and others, that another answer is: Nothing!
Keep reading →

5 Comments

Filed under Programming

August 19, 2008

Rosser’s Clever Improvement to Gödel’s Original First Incompleteness Theorem

Sometimes it’s the case that in a first-order system T in which you can do number theory there is a property P(n) of natural numbers such that the following two seemingly contradictory statements hold:

For every n, T proves P(n)

and

T does not prove that for all n, P(n)

To see that these statements are not actually contradictory, replace T with a person Bob and observe that it’s certainly possible that

For every a, b, c > 1, and n > 2, Bob can verify that aⁿ + bⁿ ≠ cⁿ.

is true but that

Bob can verify that for every a, b, c > 1, and n > 2, aⁿ + bⁿ ≠ cⁿ.

is false, since for the first statement it suffices for Bob to be able to remember grade school arithmetic, whereas for the second statement to be true Bob must be able to prove Fermat’s Last Theorem.

If it’s the case that there is a property P(n) such that for all n, T proves P(n) but it is not the case that T proves for all n, P(n), then we could actually add “There exists an n such that ~P(n)” to T and still have a consistent theory. Thus, we might be in the even stranger situation where

For every n, T proves P(n).

but

T proves that there exists an n such that ~P(n)

even though T is consistent. Such a T is called ω-inconsistent. (T is called ω-consistent if it is not ω-inconsistent.)

On the other hand, note that it’s not really possible that

Bob cannot verify that there exists a, b, c > 1 such that a² + b² = c².

given that there are such a, b, and c, since we could just tell Bob an example and have him use his knowledge of grade-school arithmetic to verify it.

Similarly, for all the theories T we will consider, if there exists an n such that T proves P(n), then T proves that there exists an n such that P(n).

Now consider the following argument, which is a rough version of Gödel’s original argument for the first incompleteness theorem:

Suppose that T is a complete theory (meaning that for every sentence S, either T proves S or T proves ~S.) Let G be the sentence “G is not provable in T” which it turns out we can interpret in the language of number theory. Suppose that G is provable in T. Then there exists a proof of G in T, so T can prove “There exists a proof of G in T.” But this is the same as ~G. So, since T can prove both G and ~G, it is inconsistent.

Now suppose that G is not provable in T. If T was ω-consistent, then since T is also complete, we would know that T proved “There is no proof of G in T.” But this is equivalent to G. So, since T can prove both G and ~G, it is inconsistent.

So, what we have proven is that if T is ω-consistent, then it is incomplete. But Gödel’s First Incompleteness Theorem is usually stated as: If T is consistent, then T is incomplete. This is a stronger and cleaner statement. (Note that in both statements we are assuming that number theory can be expressed in T.)

J. Barkley Rosser was able to prove this stronger statement with a very clever change in the self-referential statement G.

Keep reading →

1 Comment

Filed under Provability Logic, Self-Reference

August 19, 2008

Great Intro to Intuitionistic Logic

At Mathematics and Computation, there’s a really good accessible introduction to intuitionistic logic called Intuitionistic Logic for Physics. It also includes some nice accessible remarks on smooth infinitesimal analysis.

Leave a Comment

Filed under Intuitionistic Logic, Smooth Infinitesimal Analysis, Toposes

August 18, 2008

Is the “Hardest Logic Puzzle Ever” too Easy?

In 1992, the philosopher George Boolos gave what he called the “Hardest Logic Puzzle Ever”, which he attributed to Raymond Smullyan. In 2008, a clever paper by two graduate students, Brian Rabern and Landon Rabern, appeared in the philosophical journal “Analysis” which gave a simpler solution to the puzzle than Boolos gave—and furthermore claimed that a solution to a stronger puzzle was possible!

As its name implies, the “Hardest Logic Puzzle Ever” has a number of complicating factors which will be irrelevant for this discussion. Instead, consider the following much simpler puzzle which will do just as well.

You are on an island populated by knights and knaves. Knights always tell the truth; knaves always lie. You meet a inhabitant of the island who you know is holding up either 1, 2, or 3 fingers behind his back. You don’t know if this inhabitant is a knight or a knave. By asking two yes-or-no questions, determine how many fingers the inhabitant has behind his back.

There are a number of ways to solve this. One solution follows from the observation that, for any question Q, if you ask a inhabitant of the island

If I asked you question Q, would you say “yes”?

then you will get a truthful response to question Q. A knight will tell the truth about his truthful response to Q, whereas a knave would lie about his false response to Q.

So one solution would be to ask

If I asked you if you were holding 1 finger up, would you say “yes”?

If the inhabitant says “yes”, then you know he is holding 1 finger up. On the other hand, if the inhabitant says “no”, then you ask “If I asked you if you were holding 2 fingers up, would you say `yes’?” If the inhabitant says “yes”, then he is holding 2 fingers up, otherwise he is holding 3 fingers up.

This works, and it seems like you can’t do any better: There are three possibilities for how many fingers the inhabitant could be holding up, and since you can only ask yes-or-no questions, you couldn’t determine which of the three possibilities holds with only one question. But this is exactly what Rabern and Rabern claim you can do.

Keep reading →

7 Comments

Filed under Puzzles, Self-Reference

August 16, 2008

One Puzzle with Two Totally Different Solutions

Peter Winkler’s excellent book Mathematical Puzzles: A Connoisseur’s Collection has in it the problem of finding a partition of $\mathbb{R}^3$ into disjoint non-trivial circles. (Here “non-trivial” means “not a point.”) Winkler gives a very clever solution which is purely geometric.

Later, I read the same problem in Krzysztof Ciesielski’s excellent book Set Theory for the Working Mathematician. In that book Ciesielski gives an almost purely set-theoretic solution.

I’ll discuss both solutions below. 　(Don’t read on yet if you want to think about the puzzle first.)
Keep reading →

3 Comments

Filed under Ordinals, Puzzles, Set Theory

August 16, 2008

Multivariable Calculus with Nilpotent Infinitesimals: More Smooth Infinitesimal Analysis

This is a continuation of my earlier post on smooth infinitesimal analysis. In this installment, I’ll show how the definition of a “stationary point” in Smooth Infinitesimal Analysis leads directly to a nice substitute for the Lagrange multipliers method. Then I’ll show how you can define differential forms as objects which assign a “signed volume” to genuinely infinitesimal objects, and how you can get Stokes’s Theorem (and the divergence theorem, etc.) in SIA.

Keep reading →

Leave a Comment

Filed under Intuitionistic Logic, Smooth Infinitesimal Analysis, Toposes

August 15, 2008

Ax’s Theorem: An Application of Logic to Ordinary Mathematics

There are a number of applications of logic to ordinary mathematics, with the most coming from (I believe) model theory. One of the easiest and most striking that I know is called Ax’s Theorem.

Ax’s Theorem: For all polynomial functions $f\colon \mathbb{C}^n\to \mathbb{C}^n$ , if $f$ is injective, then $f$ is surjective.

Very rough proof sketch: The field $\mathbb{C}$ has characteristic 0, so each of the axioms $\psi_p \equiv \overbrace{1 + 1 + \cdots + 1}^{p\text{ 1's}} \ne 0$ (where $p$ is a prime) is true in $\mathbb{C}$ . Suppose that some polynomial is injective but not surjective. Then there is a proof of that fact from the axioms of algebraically closed fields, together with the axioms $\psi_p$ . But a proof can only use finitely many axioms. Therefore, there must be some $\psi_p$ that is not used in the proof. One can then show that there would be a polynomial function which is injective but not surjective from $F^n$ to $F^n$ , where $F$ is a finite field of characteristic $p$ . But this is impossible, because $F$ is a finite set.

More details below.

Keep reading →

2 Comments

Filed under Model Theory

August 13, 2008

Did we learn all there is to know about exponentiation in sixth grade?

By sixth grade (I think), you’ve learned some basic facts about addition, multiplication, and exponentiation over the natural numbers: you’ve learned that addition and multiplication are commutative and associative, that multiplication distributes over addition, that 0 is an identity for addition and 1 is an identity for multiplication, and the following simplification rules for exponents:

1^x = 1

x¹ = x

x^{y + z} = x^y ⋅ x^z

(x ⋅ y)^z = x^z ⋅ y^z

(x^y)^z = x^{y ⋅ z}

Tarski called these the High School Identities (but I think we learn them before high school) and asked if every identity true in the natural numbers that just used addition, multiplication, and exponentiation followed from them.

The answer turned out to be “no.”

Keep reading →

Leave a Comment

Filed under Universal Algebra

August 13, 2008

Löb’s Theorem: Santa Claus and Provability

Consider the following argument for the existence of Santa Claus (which is called Curry’s paradox):

Let S be the sentence

If S is true, then Santa Claus exists.

Lemma: S is true.

Proof. S is of the form “If P, then Q.” so to show S we just have to assume P and show Q. So, assume that S is true (with the goal of showing that Santa Claus exists). Since we’ve assumed that S is true, it follows that if S is true, then Santa Claus exists (since that’s exactly what S says). Then, since S is true, Santa Claus exists. $\square$

Corollary: Santa Claus exists.

Proof. Since S is true, it is the case that if S is true, then Santa Claus exists (since that’s exactly what S says). Therefore, since S is true, Santa Claus exists. $\square$

Since Santa Claus doesn’t exist, this argument seems to just prove that informal reasoning combined with self-reference can often lead you astray. Can we extract any interesting theorems out of this argument? It turns out that we can.

Keep reading →

Leave a Comment

Filed under Provability Logic

August 13, 2008

Kreisel’s No-Counterexample Interpretation: How can we turn proofs in elementary number theory into programs?

For every true number-theoretic statement of the form “For all n there is an m such that P(n, m)” there is a witnessing function f such that for all n, P(n, f(n)) is true.

For example, a witnessing function for the statement “For all n there is an m such that m > n and m is prime” is any function which takes a number and returns a prime higher than that number, which certainly exists.

In general, if the statement “For all n₀ there is an m₀ such that for all n₁ there is an m₁ such that … for all n_r there is an m_r such that P(n₀, m₀, …, n_r, m_r)” is true then there are witnessing functions f₀(n₀), …, f_r(n₀, …, n_r) such that for all n₀, …, n_r, P(n₀, f₀(n₀), …, n_r, f_r(n₀, …, n_r)) is true.

Because it’s the case that if a number-theoretic statement is true, then its witnessing functions exist, we might hope that it woud be the case that if a number-theoretic statement is provable, then its witnessing functions are computable, that is, that we could extract a computer program for the witnessing functions from the proof.

For example, a computable witnessing function for the statement “For all n there is an m such that m > n and m is prime” can be easily extracted from Euclid’s proof that there are infinitely any primes.

Can this always be done? Unfortunately the answer is no, but Georg Kreisel’s No-Counterexample Interpretation gives an elegant piece of computational data that can be extracted from any provable number-theoretic statement.

Keep reading →

2 Comments

Filed under Proof Theory

August 11, 2008

How can one do calculus with (nilpotent) infinitesimals?: An Introduction to Smooth Infinitesimal Analysis

Many mathematicians, from Archimedes to Leibniz to Euler and beyond, made use of infinitesimals in their arguments. These were later replaced rigorously with limits, but many people still find it useful to think and derive with infinitesimals.

Unfortunately, in most informal setups the existence of infinitesimals is technically contradictory, so it can be difficult to grasp the means by which one fruitfully manipulates them. It would be useful to have an axiomatic framework with the following properties:

1. It is consistent.

2. The system acts as a good “intuition pump” for the real world. In particular, this entails that if you prove something in the system, then while it won’t necessarily be true in the real world, there should be a high probability that it’s morally true in the real world, i.e., with some extra assumptions it becomes true. It should also ideally entail that many of the proofs of Archimedes, et al., involving infinitesimals can be formulated as is (or close to “as is”).

“Smooth infinitesimal analysis” is one attempt to satisfy these conditions.
Keep reading →

7 Comments

Filed under Intuitionistic Logic, Smooth Infinitesimal Analysis, Toposes

	Mathematical Embarra… on Ax’s Theorem: An Applica…
	rjlipton on Ax’s Theorem: An Applica…
	steviefaulkner on The Undecidability of Identiti…
	Srivatsan on About
	Kenny on Functions with Very Low Symmet…
	mkoconnor on Functions with Very Low Symmet…
	mkoconnor on A Suite of Cool Logic Pro…
	Kenny on Functions with Very Low Symmet…
	Todd Trimble on A Suite of Cool Logic Pro…
	none on When are the Real Numbers…
	Sequential compactne… on Kreisel’s No-Counterexam…
	About decidability… on Rosser’s Clever Improvem…
	Todd Trimble on What Would the World Look Like…
	mkoconnor on What Happens When You Iterate …
	mkoconnor on What Would the World Look Like…

July 19, 2009

May 14, 2009

April 9, 2009

March 23, 2009

December 20, 2008

December 11, 2008

November 14, 2008

November 9, 2008

November 3, 2008

October 26, 2008

October 16, 2008

October 13, 2008

October 13, 2008

October 7, 2008

September 29, 2008

September 21, 2008

September 14, 2008

September 4, 2008

September 4, 2008

August 29, 2008

August 29, 2008

August 25, 2008

August 25, 2008

August 23, 2008

August 22, 2008

August 21, 2008

August 19, 2008

August 19, 2008

August 18, 2008

August 16, 2008

August 16, 2008

August 15, 2008

August 13, 2008

August 13, 2008

August 13, 2008

August 11, 2008

Recent Comments

Recent Posts

Archives

Blogroll

Top Posts