This post is a set of notes from a talk I gave on December 5th for the discrete mathematics seminar at Marshall University. I want to argue that logical analysis can reveal the “internal combinatorics” of theorems, using some recent results of Dorais, Dzafarov, Hirst, Mileti, and Shafer [DDHMS 2012] as a particular example of the process.

Two examples

Let’s start by looking at two combinatorial theorems and some relationships between them. The first theorem is the infinitary version of Ramsey’s theorem. I am always interested in the infinitary version, so I will omit “infinitary” after this.

Ramsey’s Theorem. Suppose that the set of $n$-element subsets of $\mathbb{N}$ is colored with $k$ colors. Then there is an infinite subset $A$ of $\mathbb{N}$ such that every $n$-element subset of $A$ has the same color.

The set $A$ is called a homogeneous set for the coloring, and the number $n$ is called the exponent. We denote the special case of Ramsey’s theorem for exponent $n$ with $k$ colors as $\mathsf{RT}^n_k$.

In general, once we prove the instance of Ramsey’s theorem for a fixed exponent and $2$ colors, there is a straightforward inductive argument to prove the theorem for that same exponent with any finite number $k > 2$ of colors. Suppose we have a coloring with $k$ colors $\{1, 2, \ldots, k\}$. Replace all colors greater than $1$ with $2$. We now have a new coloring with $2$ colors, so by assumption there is a homogeneous set for the new coloring. If the color for this homogenous set is $1$, then the set is homogeneous for the original coloring. If not, then the original coloring induces a $(k-1)$ coloring of the homogeneous set. By induction, there is a subset of the homogeneous set that is homogeneous with respect to this new coloring (modulo a small argument that we can work with any infinite set in place of $\mathbb{N}$ in the theorem). That subset is then homogeneous for the original $k$-coloring.

The second of our two theorems generalizes Ramsey’s theorem by replacing the domain $\mathbb{N}$ with the complete binary tree $\mathbb{T}_2$. A subset of $\mathbb{T}_2$ is a chain if each pair of elements in the set is comparable: one of them is an extension of the other. A subset $A$ of $\mathbb{T}_2$ is perfect if for every $p \in A$ there are $q,r \in A$ that extend $p$ and such that $q$ and $r$ are incomparable with each other.

Tree Theorem (CHM 2009). Suppose that the set of $n$-element chains of $\mathbb{T}_2$ is colored with $k$ colors. Then there is an infinite subset $A$ of $\mathbb{T}_2$ which is perfect and such that every $n$-element chain from $A$ has the same color.

We denote the special case of the tree theorem with exponent $n$ with $k$ colors as $\mathsf{TT}^n_k$.

The tree theorem result has a combinatorial proof not too different from the proof of Ramsey’s theorem. But the tree theorem is stronger than Ramsey’s theorem, in the following sense.

Proposition 1. The Tree Theorem for exponent $n$ with $k$ colors implies Ramsey’s theorem for that exponenent and number of colors.

The proof is as follows. Given a $k$-coloring $f$ of $n$-element subsets of $\mathbb{N}$, create a coloring $g$ of $n$-element chains of $\mathbb{T}_2$ by ignoring the content of the nodes and just looking at their lengths: $g(\{\sigma_1, \ldots, \sigma_n\}) = f(\{|\sigma_1|, |\sigma_2|, \ldots, |\sigma_n|\})$. Apply the tree theorem to find a homogeneous subset of $\mathbb{T}_2$. Because the subset is perfect, we can pick an infinite path $\alpha$ through it (e.g. “always go left”). Then we can read off a subset of $\mathbb{N}$ by looking at the lengths of the nodes that appear in $\alpha$. This will be a homogeneous subset for the original instance of Ramsey’s theorem.

Internal combinatorics

The two examples above show that there are intricate relationships between fragments of Ramsey’s theorem and fragments of the tree theorem. Similar relationships are known between many combinatorial theorems, and in other instances the lack of established relationships is well known. But these relationships cannot even be described by talking about the theorems themselves.

Proposition 2. If $T_1$ and $T_2$ are statements and $T_2$ is true then “$T_1$ implies $T_2$” is true. If $T_2$ is provable then “$T_1$ implies $T_2$” is provable.

This makes it very difficult to state the combinatorial relationships described above in ordinary mathematical language. In fact Proposition 1 is trivially correct, because $\mathsf{RT}^n_k$ is true, and the proof we presented is redundant. The same thing happens if we try to expand the implication: “Assuming $\mathsf{TT}^n_k$, given any instance of $\mathsf{RT}^n_k$ we can find a homogeneous subset” is an immediate consequence of $\mathsf{RT}^n_k$ itself. The definition of the material conditional ignores the actual content of the theorems and just looks at their truth values; it is unable to capture the relationship between the theorems that is exposed in our proof.

I call these deeper relationships between combinatorial theorems, which go beyond the truth values and can only be discerned by looking at proofs, the internal combinatorics of the theorems. For example, the proof that $\mathsf{TT}^n_k$ implies $\mathsf{RT}^n_k$ reveals that the internal combinatorial structure of the former is strictly more complicated than that of the latter, because we can view $\mathsf{RT}^n_k$ as a special case of $\mathsf{TT}^n_k$. On the other hand, it does not seem as if $\mathsf{RT}^{20}_{100}$ is a special case of $\mathsf{RT}^{20}_2$, even though $\mathsf{RT}^{20}_2$ implies $\mathsf{RT}^{20}_{100}$.

This kind of internal combinatorial structure is what many mathematicians are interested in when comparing combinatorial results. Proposition 1 is not interesting because of its statement, which trivially follows from Proposition 2; it’s interesting because its proof reveals something about the nature of the principles involved.

We can study the relationships between the theorems – rather than just the truth values of the theorems – by studying manifestations of the theorems in restricted systems. This is a process that is well known in the study of foundations of mathematics:

• We first select a restricted environment in which to work. The restrictions typically include a restriction on the things we can express and on the methods of proof we can use. Three very different restricted envionments are ZF set theory; second-order arithmetic; and informal Bishop-style constructive mathematics.
• We express our natural-language theorems as statements $\mathsf{P}$ and $\mathsf{Q}$ in our restricted system. These statements are manifestations of the original, natural-language theorems within our restricted environment. Of course the same theorem may have several manifestations that we can compare.
• In many interesting cases, $\mathsf{Q}$ is not provable in the restricted environment (and is also not disprovable). Thus “$\mathsf{P}$ implies $\mathsf{Q}$” is no longer trivial.

A well known phenomenon is that many mathematical theorems are in the form “for every $X$ with a certain property, there exists a $Y$ in a particular relationship with $X$.” Both Ramsey’s theorem and the tree theorem can be phrased in this way. A set $X$ with the property is known as an instance of the theorem, and any corresponding $Y$ is a solution. In the case of combinatorial theorems such as Ramsey’s theorem and the tree theorem, we can represent the instances and solutions as subsets of $\mathbb{N}$, and the properties can be express by quantifying over $\mathbb{N}$. Theorems of this sort are called $\Pi^1_2$ in the literature.

I want to emphasize the perspective that the statements $\mathsf{P}$ and $\mathsf{Q}$ are only manifestations – avatars, so to speak – of the original, natural-language theorems. Like all manifestations, they omit some attributes of the original theorems, and simultaneously gain other attributes from the form of the manifestation.

Computable reducibility and Uniform reducibility

One common framework for carrying out the steps in the previous section is second-order arithmetic. In this framework, our only objects are natural numbers and sets of natural numbers. This causes the manifestations we study to be limited in that they usually restrict combinatorial theorems to countable sets, even if the theorems could apply to larger sets (cf. the Erdős–Rado theorem).

A central benefit of the restriction to sets of natural numbers is that we can talk meaningfully about computation. There is a formal definition of when one set of natural numbers $A$ is computable from another set of natural numbers $B$, and when one function $f \colon \mathbb{N} \to \mathbb{N}$ is computable from another function $g \colon \mathbb{N} \to \mathbb{N}$. The set or function being computed is called relatively computable from the set or function that is used to compute it. We can use computability to make formal sense of the relationships we saw above.

Suppose that we begin with a collection $M$ of subsets of $\mathbb{N}$. We will assume that the set is closed under relative computability: if $A \in M$ and $B$ is computable from $A$ then $B \in M$. If $\mathsf{Q}$ is a $\Pi^1_2$ principle, we say that $M$ is closed under finding solutions to $\mathsf{Q}$ if for every instance of $\mathsf{Q}$ in $M$ there is a solution to that instance also in $M$. If we want to study how a principle $\mathsf{Q}$ is computationally related to a principle $\mathsf{P}$, it is natural to ask the following question: if $M$ is closed under relative computability and under finding solutions to $\mathsf{Q}$, must it also be closed under finding solutions to $\mathsf{P}$?

Definition. A $\Pi^1_2$ theorem $\mathsf{P}$ is computably reducible to a $\Pi^1_2$ theorem $\mathsf{Q}$ if every collection $M$ of sets that is closed under relative computablility and under finding solutions to $\mathsf{Q}$ is also closed under finding solutions to $\mathsf{P}$. I will abbreviate this relationship as $\mathsf{Q} \to_\omega \mathsf{P}$.

In the literature, the relationship $\mathsf{Q} \to_\omega \mathsf{P}$ is called “$\mathsf{Q}$ implies $\mathsf{P}$ over $\omega$ models”. By analyzing the proof above that Ramsey’s theorem for exponent $n$ in $2$ colors implies Ramsey’s theorem in that exponent for $k$ colors, we can show that $\mathsf{RT}^n_2 \to_\omega \mathsf{RT}^n_k$ for each $k > 2$.

Dorais, Dzafarov, Hirst, Mileti, and Shafer [DDHMS 2012] have proposed a refinement of this reducibility. Looking at the proof above that $\mathsf{RT}^n_2 \to_\omega \mathsf{RT}^n_k$ for $k > 2$, we see that it asks for solutions of up to $(k-1)$ instances of $\mathsf{RT}^n_2$ to find a solution to a single instance of $\mathsf{RT}^n_k$. The following reducibility allows only one access to a solution of $\mathsf{Q}$ in the process of finding a solution of $\mathsf{P}$.

Definition (DDHMS 2012). A $\Pi^1_2$ theorem $\mathsf{P}$ is uniformly reducible to a $\Pi^1_2$ theorem $\mathsf{Q}$ if there are computable functions $\Phi, \Psi$ such that for any instance $A$ of $\mathsf{P}$, $\Phi(A)$ is an instance of $\mathsf{Q}$, and then for any solution $B$ to $\Phi(A)$ in $\mathsf{Q}$, $\Psi(B)$ is a solution to $A$ in $\mathsf{P}$. I will abbreviate this relationship as $\mathsf{Q} \to_u \mathsf{P}$.

For example, the proof above that $\mathsf{TT}^n_k$ implies $\mathsf{RT}^n_k$ can be analyzed to see that $\mathsf{TT}^n_k \to_u \mathsf{RT}^n_k$. Uniform reducibility is a special case of Weihrauch reducibility [GM 2009] [BGM 2012], although not quite equivalent, as I will explain in a future blog post.

What is the difference between $\to_\omega$ and $\to_u$? In each case we start with an instance of $\mathsf{P}$ that we want to solve, and we are able to obtain solutions to any instance of $\mathsf{Q}$ we can compute. In the case of computable reducibility, we may repeatedly generate instances of $\mathsf{Q}$ and obtain solutions from them, and later instances may even be generated using previous instances as inputs. In the case of uniform reducibility, we may only generate one instance of $\mathsf{Q}$, and then we must have a uniform way (the function $\Psi$) to turn any solution to that instance of $\mathsf{Q}$ into a solution of our original instance of $\mathsf{P}$. The natural question is whether the two are equivalent, and the answer is that they are not.

Theorem (DDHMS 2012). For $2 \leq j < k$, we have $\mathsf{RT}^n_j \not \to_u \mathsf{RT}^n_k$.

This theorem reveals something in natural-language mathematics about the combinatorial structure of Ramsey’s theorem. While we can reduce Ramsey’s theorem to the tree theorem in a very direct way, as above, no proof of that sort is going to exist to reduce Ramsey’s theorem in many colors to Ramsey’s theorem for the same exponent in fewer colors. This sort of realization about the internal combinatorics of the theorem would not be possible if we merely looked at truth values rather than at proofs.

References

• [BGM 2012] Vasco Brattka, Guido Gherhardi, and Alberto Marcone (2012), :The Bolzano-Wierstrass theorem is the jump of weak Kőnig’s lemma”, Annals of Pure and Applied Logic 163, 623-635. doi:10.1016/j.apal.2011.10.006 arXiv:1101.0792
• [CHM 2009] Jennifer Chubb, Jeffry L. Hirst and Timothy H. McNicholl (2009), “Reverse mathematics, computability, and partitions of trees”, Journal of Symbolic Logic 74:1, 201-215. doi:10.2178/jsl/1231082309, Preprint
• [DDHMS 2012] François G. Dorais, Damir D. Dzafarov, Jeffry L. Hirst, Joseph R. Mileti and Paul Shafer (2012), “On uniform relationships between combinatorial problems”, arXiv:1212.0157v1
• [GM 2009] Guido Gherardi and Alberto Marcone (2009), ” How Incomputable Is the Separable Hahn-Banach Theorem?”, Notre Dame J. Formal Logic 50:4, 393-425. doi:10.1215/00294527-2009-018 arXiv:0808.1663