MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Coding is obviously a fundamental tool in reverse mathematics, and practitioners take care to both demonstrate the correctness of their coding mechanisms and point out their limitations. Harvey Friedman posted on the FOM mailing list in 2004 (see [1] and [2]), prefacing the mathematical part of his first posting with the following.

For a wide variety of mathematical statements, the "correctness" or "appropriateness" of the coding used is completely unpoblematic, and goes virtually unnoticed. Part of the reason why it goes virtually unnoticed is that such coding mechanisms - in such unproblematic cases - are essentially the same as those that occur in virtually all aspects of recursion theory, in proof theory, and at least the finite part of set theory.

For other mathematical statements, the "correctness" or "appropriateness" of certain coding mechanisms is, in varying degrees, controversial. The main reason for this controversy is the presence of alternatives that seem equally reasonable, but are "substantially different".

The judging of the "correctness" or "appropriateness" of coding mechanisms has largely been of an informal, even sometimes polemical, nature. Here we wish to present some formal criteria that should go far in clarifying the issues, and open up new research programs.

I'm curious to know whether such new research programmes have indeed opened up, or whether there has been any further work in this area at all. I couldn't find anything by Googling "Coding in Reverse Mathematics" except an abstract for a talk by Friedman in October 2004.

[1] Friedman, H. Coding in Reverse Mathematics 1. FOM mailing list, 2004.

[2] Friedman, H. Coding in Reverse Mathematics 2. FOM mailing list, 2004.

share|cite|improve this question
This very issue came up at Keita Yokoyama's talk for the CUNY Logic Workshop last Friday, and I'm very interested to see the answers here. – Joel David Hamkins Mar 11 '13 at 13:35
up vote 8 down vote accepted

I can offer a computational perspective. In computable mathematics we are interested in "computing with mathematical objects" such as integers, finite sets, real numbers, infinite-dimensional Banach spaces, compact subsets of $\mathbb{R}^n$, and many other "infinite" things. Some of these are pretty complicated, so the question arises how to represent them as a data structures, in other words, we face a coding problem, just like in Reverse Mathematics.

In computability theory we normally code everything with natural numbers. Another possibility is to code things with "reals", by which computability theorists mean infinite binary sequences. In actual implementations we code by elements of datatypes available to us in a programming language. But we always face the same question, namely what does it mean to correctly encode a given mathematical object.

To properly answer such a question we have to take a very important step: we must turn encodings themselves into honest mathematical objects and collect them all (even the allegedly sensless ones) into a manageable mathematical structure, say a category. We should be able to use the structure of the resulting category to bring some order and sense to the black art of "choosing appropriate codings".

When this is done in computable mathematics, the result is a realizability topos. This is great, as we can interpret higher-order (intuitionistic) logic in it, and that suffices to develop mathematics. To see how this works, consider an easy example, the natural numbers. Nobody ever questions encodings of natural numbers, but nevertheless it is possible to come up with some bad ones. Encodings are objects of a realizability topos. Thus, a candidate encoding for natural numbers lives inside the topos as an object $N$. If in the topos the object $N$ satisfies Peano axioms, then it correctly encodes natural numbers, otherwise it does not.

Our correctness criterion then is this: an encoding is correct when, seen as an object of the realizability topos, it corresponds to the expected mathematical object. Other examples are easy to come by:

  • An encoding of real numbers is correct if the corresponding object in the topos is a Cauchy-complete archimedean ordered field.
  • An encoding of c.e. sets is correct if in the corresponding object in the topos is the object of countable subsets of $\mathbb{N}$.
  • An encoding of functions $X \to Y$ is correct if in the topos it is the exponential object of $X$ and $Y$.
  • An encoding of a group is correct if in the topos it corresponds to a group.
  • etc.

As toposes and intuitionistic mathematics make snaicititamehtam queasy, and reverse mathematics happens in the context of classical logic anyway, realizaiblity toposes are not going to be the right answer for Reverse Mathematics. Nevertheless, we have a plan: what category, or (non-standard) model of (weak) set-theory captures the idea of coding in Recursive Mathematics? If you can find it, and it has good enough properties, it should give some answers. This sounds like somebody's PhD.

share|cite|improve this answer
Hi Andrej, I left this open for a few months in the hopes that someone could answer my original question, but given the silence I take it that the answer is in fact "No, no one's looked at this since." So I'm going to accept your excellent answer. As you say, this sounds like a nice little research project. – Benedict Eastaugh Jul 26 '13 at 14:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.