# MathOverflow, the eternal fountain of mathematics: reflections on a hundred kiloreps

It seems to appear that I have somehow managed to pass  the 100,000 score milestone for reputation on MathOverflow.  A hundred kiloreps!  Does this qualify me for micro-celebrity status?  I have clearly been spending an inordinate amount of time on MO…  Truly, it has been a great time.

MathOverflow, an eternal fountain of mathematics, overflows with fascinating questions and answers on every imaginable mathematical topic, drawing unforeseen connections, seeking generalizations, clarification, or illustrative examples, questioning assumptions, or simply asking for an explanation of a subtle mathematical point.  The mathematics is sophisticated and compelling.  How could a mathematician not immediately plunge in?

I first joined MathOverflow in November 2009, when my colleague-down-the-hall Kevin O’Bryant dropped into my office and showed me the site.  He said that it was for “people like us,” research mathematicians who wanted to discuss mathematical issues with other professionals, and he was completely right.  Looking at the site, I found Greg Kuperberg’s answer to a question on the automorphism tower problem in group theory, which was one of the first extremely popular questions at that time, the top-rated question.  I was hooked immediately, and I told Kevin on that very first day that it was clear that MathOverflow was going to take a lot of time.

I was pleased to find right from the beginning that, although there were not yet many logicians participating on MO, there were nevertheless many logic questions, revealing an unexpectedly broad interest in math logic issues amongst the general mathematical community.  I found questions about definability, computability, undecidability, logical independence, about the continuum hypothesis and the axiom of choice and about large cardinals, asked by mathematicians in diverse research areas, who seemed earnestly to want to know the answer.  How pleased I was to find such a level of interest in the same issues that fascinated me; and how pleased I was also to find that I was often able to answer.

In the early days, I may have felt a little that I should be a kind of ambassador for logic, introducing the subject or aspects of it to those who might not know all about it yet; for example, in a few answers I explained and introduced the topic of cardinal characteristics of the continuum and the subject of Borel equivalence relation theory, since I had felt that mathematicians outside logic might not necessarily know much about it, even when it offered connections to things they did know about.  I probably wouldn’t necessarily answer the same way today, now that MO has many experts in those subjects and a robust logic community.  What a pleasure it has become.

A while back I wrote a post The use and value of MathOverflow in response to an inquiry of François Dorais, and I find the remarks I made then are as true for me today as ever.

I feel that mathoverflow has enlarged me as a mathematician.  I have learned a huge amount here in the past few years, particularly concerning how my subject relates to other parts of mathematics.  I’ve read some really great answers that opened up new perspectives for me.  But just as importantly, I’ve learned a lot when coming up with my own answers.  It often happens that someone asks a question in another part of mathematics that I can see at bottom has to do with how something I know about relates to their area, and so in order to answer, I must learn enough about this other subject in order to see the connection through.  How fulfilling it is when a question that is originally opaque to me, because I hadn’t known enough about this other topic, becomes clear enough for me to have an answer.  Meanwhile, mathoverflow has also helped me to solidify my knowledge of my own research area, often through the exercise of writing up a clear summary account of a familiar mathematical issue or by thinking about issues arising in a question concerning confusing or difficult aspects of a familiar tool or method.

Mathoverflow has also taught me a lot about good mathematical exposition, both by the example of other’s high quality writing and by the immediate feedback we all get on our posts.  This feedback reveals what kind of mathematical explanation is valued by the general mathematical community, in a direct way that one does not usually get so well when writing a paper or giving a conference talk.  This kind of knowledge has helped me to improve my mathematical writing in general.

Thanks very much again, MathOverflow!  I am grateful.

A few posts come to mind:

There have been so many more great questions and posts.  If you are inclined, feel free to post comments below linking to your favorite MO posts!

Concerning the MO reputation system, I suppose some might suspect me of harboring unnatural thoughts on reputation — after all, I once proposed (I can’t find the link now) that the sole basis of tenure and promotion decisions for mathematics faculty, as well as choice of premium office space, should be:  MO reputation, ha! — but in truth, I look upon it all as a good silly game.  One may take reputation as seriously as one takes any game seriously, and many mathematicians can indeed take a game seriously.  My honest opinion is that the reputation and badge system is an ingenious piece of social engineering.  The designers must have had a good grasp on human psychology, an understanding of the kinds of reasons that might motivate a person to participate in such a site; one thinks, for example, of the intermittent reward theory.  I find it really amazing what the stackexchange designers have created, and who doesn’t love a good game?

Announcement on History of MathOverflow

# The use and value of mathoverflow

François Dorais has created a discussion on the MathOverflow discussion site, How is mathoverflow useful for me? in which he is soliciting response from MO users.  Here is what I wrote there:

The principal draw of mathoverflow for me is the unending supply of extremely interesting mathematics, an eternal fountain of fascinating questions and answers. The mathematics here is simply compelling.

I feel that mathoverflow has enlarged me as a mathematician. I have learned a huge amount here in the past few years, particularly concerning how my subject relates to other parts of mathematics. I’ve read some really great answers that opened up new perspectives for me. But just as importantly, I’ve learned a lot when coming up with my own answers. It often happens that someone asks a question in another part of mathematics that I can see at bottom has to do with how something I know about relates to their area, and so in order to answer, I must learn enough about this other subject in order to see the connection through. How fulfilling it is when a question that is originally opaque to me, because I hadn’t known enough about this other topic, becomes clear enough for me to have an answer. Meanwhile, mathoverflow has also helped me to solidify my knowledge of my own research area, often through the exercise of writing up a clear summary account of a familiar mathematical issue or by thinking about issues arising in a question concerning confusing or difficult aspects of a familiar tool or method.

Mathoverflow has also taught me a lot about good mathematical exposition, both by the example of other’s high quality writing and by the immediate feedback we all get on our posts. This feedback reveals what kind of mathematical explanation is valued by the general mathematical community, in a direct way that one does not usually get so well when writing a paper or giving a conference talk. This kind of knowledge has helped me to improve my mathematical writing in general.

So, thanks very much mathoverflow! I am grateful.

# The differential operator $\frac{d}{dx}$ binds variables

Recently the question If $\frac{d}{dx}$ is an operator, on what does it operate? was asked on mathoverflow.  It seems that some users there objected to the question, apparently interpreting it as an elementary inquiry about what kind of thing is a differential operator, and on this interpretation, I would agree that the question would not be right for mathoverflow. And so the question was closed down (and then reopened, and then closed again….sigh). (Update 12/6/12: it was opened again,and so I’ve now posted my answer over there.)

Meanwhile, I find the question to be more interesting than that, and I believe that the OP intends the question in the way I am interpreting it, namely, as a logic question, a question about the nature of mathematical reference, about the connection between our mathematical symbols and the abstract mathematical objects to which we take them to refer.  And specifically, about the curious form of variable binding that expressions involving $dx$ seem to involve.  So let me write here the answer that I had intended to post on mathoverflow:

————————-

To my way of thinking, this is a serious question, and I am not really satisfied by the other answers and comments, which seem to answer a different question than the one that I find interesting here.

The problem is this. We want to regard $\frac{d}{dx}$ as an operator in the abstract senses mentioned by several of the other comments and answers. In the most elementary situation, it operates on a functions of a single real variable, returning another such function, the derivative. And the same for $\frac{d}{dt}$.

The problem is that, described this way, the operators $\frac{d}{dx}$ and $\frac{d}{dt}$ seem to be the same operator, namely, the operator that takes a function to its derivative, but nevertheless we cannot seem freely to substitute these symbols for
one another in formal expressions. For example, if an instructor were to write $\frac{d}{dt}x^3=3x^2$, a student might object, “don’t you mean $\frac{d}{dx}$?” and the instructor would likely reply, “Oh, yes, excuse me, I meant $\frac{d}{dx}x^3=3x^2$. The other expression would have a different meaning.”

But if they are the same operator, why don’t the two expressions have the same meaning? Why can’t we freely substitute different names for this operator and get the same result? What is going on with the logic of reference here?

The situation is that the operator $\frac{d}{dx}$ seems to make sense only when applied to functions whose independent variable is described by the symbol “x”. But this collides with the idea that what the function is at bottom has nothing to do with the way we represent it, with the particular symbols that we might use to express which function is meant.  That is, the function is the abstract object (whether interpreted in set theory or category theory or whatever foundational theory), and is not connected in any intimate way with the symbol “$x$”.  Surely the functions $x\mapsto x^3$ and $t\mapsto t^3$, with the same domain and codomain, are simply different ways of  describing exactly the same function. So why can’t we seem to substitute them for one another in the formal expressions?

The answer is that the syntactic use of $\frac{d}{dx}$ in a formal expression involves a kind of binding of the variable $x$.

Consider the issue of collision of bound variables in first order logic: if $\varphi(x)$ is  the assertion that $x$ is not maximal with respect to $\lt$, expressed by $\exists y\ x\lt y$, then $\varphi(y)$, the assertion that $y$ is not maximal, is not correctly described as the assertion $\exists y\ y\lt y$, which is what would be obtained by simply replacing the occurrence of $x$ in $\varphi(x)$ with the symbol $y$. For the intended meaning, we cannot simply syntactically replace the occurrence of $x$ with the symbol $y$, if that occurrence of $x$ falls under the scope of a quantifier.

Similarly, although the functions $x\mapsto x^3$ and $t\mapsto t^3$ are equal as functions of a real variable, we cannot simply syntactically substitute the expression $x^3$ for $t^3$ in $\frac{d}{dt}t^3$ to get $\frac{d}{dt}x^3$. One might even take the latter as a kind of ill-formed expression, without further explanation of how $x^3$ is to be taken as a function of $t$.

So the expression $\frac{d}{dx}$ causes a binding of the variable $x$, much like a quantifier might, and this prevents free substitution in just the way that collision does. But the case here is not quite the same as the way $x$ is a bound variable in $\int_0^1 x^3\ dx$, since $x$ remains free in $\frac{d}{dx}x^3$, but we would say that $\int_0^1 x^3\ dx$ has the same meaning as $\int_0^1 y^3\ dy$.

Of course, the issue evaporates if one uses a notation, such as the $\lambda$-calculus, which insists that one be completely explicit about which syntactic variables are to be regarded as the independent variables of a functional term, as in $\lambda x.x^3$, which means the function of the variable $x$ with value $x^3$.  And this is how I take several of the other answers to the question, namely, that the use of the operator $\frac{d}{dx}$ indicates that one has previously indicated which of the arguments of the given function is to be regarded as $x$, and it is with respect to this argument that one is differentiating.  In practice, this is almost always clear without much remark.  For example, our use of $\frac{\partial}{\partial x}$ and $\frac{\partial}{\partial y}$ seems to manage very well in complex situations, sometimes with dozens of variables running around, without adopting the onerous formalism of the $\lambda$-calculus, even if that formalism is what these solutions are essentially really about.

Meanwhile, it is easy to make examples where one must be very specific about which variables are the independent variable and which are not, as Todd mentions in his comment to David’s answer. For example, cases like

$$\frac{d}{dx}\int_0^x(t^2+x^3)dt\qquad \frac{d}{dt}\int_t^x(t^2+x^3)dt$$

are surely clarified for students by a discussion of the usage of variables in formal expressions and more specifically the issue of bound and free variables.

# The mate-in-n problem of infinite chess is decidable

• D. Brumleve, J. D. Hamkins, and P. Schlicht, “The Mate-in-$n$ Problem of Infinite Chess Is Decidable,” in How the World Computes, S. Cooper, A. Dawar, and B. Löwe, Eds., Springer, 2012, vol. 7318, pp. 78-88.
@incollection{BrumleveHamkinsSchlicht2012:TheMateInNProblemOfInfiniteChessIsDecidable,
year= {2012},
isbn= {978-3-642-30869-7},
booktitle= {How the World Computes},
volume= {7318},
series= {Lecture Notes in Computer Science},
editor= {Cooper, S.~Barry and Dawar, Anuj and Löwe, Benedikt},
doi= {10.1007/978-3-642-30870-3_9},
title= {The Mate-in-$n$ Problem of Infinite Chess Is Decidable},
url= {http://wp.me/p5M0LV-f8},
publisher= {Springer},
author= {Brumleve, Dan and Hamkins, Joel David and Schlicht, Philipp},
pages= {78-88},
eprint = {1201.5597},
archivePrefix = {arXiv},
primaryClass = {math.LO},
}

Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The mate-in-$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most $n$ moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiers—*there is a move for white, such that for every black reply, there is a countermove for white*, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth.

Nevertheless, the main theorem of this article, confirming a conjecture of the first author and C. D. A. Evans, establishes that the mate-in-$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Unfortunately, this resolution of the mate-in-$n$ problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\frak{Ch}}$ is not known.

Richard Stanley’s question on mathoverflow: Decidability of chess on infinite board?

# The rigid relation principle, a new weak choice principle

• J. D. Hamkins and J. Palumbo, “The rigid relation principle, a new weak choice principle,” Math.~Logic Q., vol. 58, iss. 6, pp. 394-398, 2012.
@ARTICLE{HamkinsPalumbo2012:TheRigidRelationPrincipleANewWeakACPrinciple,
AUTHOR = {Joel David Hamkins and Justin Palumbo},
TITLE = {The rigid relation principle, a new weak choice principle},
JOURNAL = {Math.~Logic Q.},
YEAR = {2012},
volume = {58},
number = {6},
pages = {394--398},
ISSN = {0942-5616},
month = {},
note = {},
url = {http://jdh.hamkins.org/therigidrelationprincipleanewweakacprinciple/},
eprint = {1106.4635},
archivePrefix = {arXiv},
primaryClass = {math.LO},
doi = {10.1002/malq.201100081},
MRNUMBER = {2997028},
MRREVIEWER = {Eleftherios C.~Tachtsis},
abstract = {},
keywords = {},
source = {},
}

The rigid relation principle, introduced in this article, asserts that every set admits a rigid binary relation. This follows from the axiom of choice, because well-orders are rigid, but we prove that it is neither equivalent to the axiom of choice nor provable in Zermelo-Fraenkel set theory without the axiom of choice. Thus, it is a new weak choice principle. Nevertheless, the restriction of the principle to sets of reals (among other general instances) is provable without the axiom of choice.

This paper arose out of my related mathoverflow question:  Does every set admit a rigid binary relation (and how is this related to the axiom of choice)?