Selected Papers Network

I just made my first contribution to the Selected Papers Network. It was fun and easy and I strongly recommend you use it too!

It’s too early for serious commentary on the experience but there are a few things I noted right away:

  • The front page does not yet support MathJax. (Neither does Google+ but that’s another problem.) Hopefully that will be fixed soon. Meanwhile, you can use the MathJax bookmarklet.
  • The hashtag syntax is fairly simple and intuitive but there is room for improvement. The main improvement would be to relax the ID rules to allow full urls which are easier to cut and paste. For example, for arXiv:1234.6789, for doi:10.1234/0987654321.
  • Comments do not seem to generate arXiv trackbacks. (Or they have not yet made it through the arXiv editorial process.)
  • I wish topic (hash)tags were allowed to have natural syntax. I can’t think of a good reason why this has to follow the Twitter standard. Should it be #cstarAlgebras or #CstarAlgebras or #CStarAlgebras… why not C*-algebras? It’s better to allow natural syntax and implement a tag synonym system.

You can track these and other issues here.


What is combinatorial set theory?

This is a very difficult question that I find myself pondering every so often. I once heard a story that Jim Baumgartner was asked this question at a major logic meeting where all areas — recursion theory, model theory, proof theory, etc. — were well represented and he responded that it was the only area of logic not represented there. Indeed, the best way to describe infinitary combinatorics is to describe what it isn’t, as in the introductory paragraph of Jim’s review of William’s book on the subject:

Combinatorial set theory is frequently distinguished from axiomatic set theory, although the distinction is becoming less and less clear all the time. If there is a difference, it is more one of method than substance. Axiomatic set theory uses the tools of mathematical logic, such as the method of ultrapowers and the theory of forcing and generic sets, while the methods of combinatorial set theory are purely “combinatorial” in nature. In practice, an argument of result is “combinatorial” if it is not overtly model-theoretic, topological, or measure-theoretic.1

I stumbled across the above review while seeking to find a reference for the anecdote about Jim at the meeting. I don’t remember where I got this story from, I may have read it somewhere or I may have heard it from somebody or Jim himself. I didn’t find a reference for the anecdote. However, I did find that Jim wrote some fantastic book reviews. One of the best is his review of Kunen’s classic set theory textbook, where he writes the following about Jech’s encyclopedic Set Theory:

Graduate students went without food to put a copy of this fat green book on their shelves.2

This was the first edition of Jech’s book, of course. The classic is now much fatter, yellow rather than green, and sufficiently affordable that graduate students can acquire a copy without excessive suffering.

  1. James E. Baumgartner, Review: Neil H. Williams, Combinatorial set theory. Bull. Amer. Math. Soc. (N.S.) 1 (1979), 217–219. [link]
  2. James E. Baumbarther, Review: Kenneth Kunen, Set theory. An introduction to independence proofs. J. Symb. Logic 51 (1986), 462–464. [link]

Arithmetical consequences of the set-theoretic multiverse

In [2], Joel David Hamkins proposed a set of axioms for the set-theoretic multiverse. Several of these axioms reflect the typical world many set theorists live in, namely that generic extensions, inner models and the like are all legitimate universes. Some set theorists prefer the universe perspective where one such universe is singled out as more legitimate than others and other set theorists prefer to think that any universe is as legitimate as any other. Hamkins is of the latter view and, in many ways, his view is even radically opposed to the universe perspective. Indeed, some of Hamkins’s axioms take the form of “mirages” that gradually eliminate the possibility of singling out a preferred universe. These can be formulated as follows.1

Uncountability Mirage
Every universe is countable from the perspective of a larger universe.
Undefinability Mirage
Every universe is constructible from the perspective of a larger universe.
Wellfoundedness Mirage
Every universe is not wellfounded from the perspective of a larger universe.
Finiteness Mirage
Every universe has a nonstandard $\omega$ from the perspective of a larger universe.

The Undefinability Mirage is a fascinating axiom that I hope to talk about in the near future but it does not directly contradict the universe perspective. The Uncountability Mirage is startling but it isn’t earth-shattering on its own. However, the last two mirages are fundamentally incompatible with the universe perspective. The Finiteness Mirage — which actually implies the Wellfoundedness Mirage — is especially striking since it asserts that no universe understands true finiteness. This is a chilling thought for most mathematicians, even those who do not espouse the classical universe view. After reading Hamkins’s account, I wondered what kind of arithmetical consequences the multiverse axioms have. This is an important question since an arithmetical disagreement between the multiverse view and the universe view would make the divide much more than a different perspective.



Towsner’s stable forcing

It is well known that a model $\newcommand{\MN}{\mathfrak{N}}\MN$ of $\newcommand{\RCA}[1]{\mathsf{RCA}_{#1}}\RCA0$ satisfies $\Sigma^0_n$-induction ($\newcommand{\Ind}[1]{\mathsf{I}{#1}}\Ind{\Sigma^0_n}$) if and only if it satisfies bounded $\Sigma^0_n$-comprehension: if $\phi(x)$ is a $\Sigma^0_n$-formula (with parameters) then the set $\set{x \lt b: \phi(x)}$ exists for every number $b$ in $\MN$. Thus, it follows that $\Pi^0_n$-induction also holds and indeed induction holds for all boolean combinations of $\Sigma^0_n$ formulas. However, $\Ind{\Sigma^0_n}$ offers no control over sets of higher complexity than that. In particular, $\Delta^0_{n+1}$-induction may fail very badly in a model of $\Ind{\Sigma^0_n}$. Indeed, by a result of Slaman [1] $\Delta^0_{n+1}$-induction is equivalent to $\Sigma^0_{n+1}$-bounding ($\newcommand{\Bnd}[1]{\mathsf{B}{#1}}\Bnd{\Sigma^0_{n+1}}$) and it is known that we have a strict hierarchy: $$\Ind{\Sigma^0_1} \quad\WHEN\quad \Bnd{\Sigma^0_2} \quad\WHEN\quad \Ind{\Sigma^0_2} \quad\WHEN\quad \Bnd{\Sigma^0_3} \quad\WHEN \cdots$$ The actual size of the gaps between $\Ind{\Sigma^0_n}$ and $\Bnd{\Sigma^0_{n+1}}$ has recently been quantified by Henry Towsner, who included a beautiful forcing argument in his preprint [2] that shows that $\Ind{\Sigma^0_n}$ gives absolutely no control whatsoever on $\Delta^0_{n+1}$-definable sets.



Back to Cantor?

Set Theory has a fantastic and legendary history. At the end, it left us with ZFC, which is currently recognized as the foundation of mathematics. This state of affairs is arguably one of the best possible outcomes for the foundational crisis that plagued mathematics in the early 20th century. However, the choice to adopt ZFC was by no means unanimous, dissent has always been present, often with good reason. Whether propelled by inertia or by sheer power, for better or for worse, ZFC is now approaching 100 years of reign as the foundation of mathematics.



Scheming schemes…

In everyday language, the word scheme often has a negative connotation: scheme is used as a synonym for devious plan. In mathematical language, the word has no negative aspect at all. In fact, I think that mathematical schemes of all kinds are wonderful things and it often takes me a moment to understand when someone uses scheme to imply wrongful intent. This can lead to awkward social situations, but what I want to talk about here is how axiom schemes can sometimes behave badly and may lead to awkward mathematical situations.



Diaconescu’s Theorem

In the 1970s, Radu Diaconescu [1] showed that the Axiom of Choice implies the Principle of Excluded Middle. More specifically, he showed that every topos that satisfies (a very mild form of) the Axiom of Choice is Boolean. Diaconescu’s argument applies in many other contexts too. In this post, I will present a variant of that argument. I will keep the context of the argument deliberately ambiguous to demonstrate its broad applicability.



SMBC on madness…

It’s very easy to imagine a mad scientist: combine a bad hair day with a lab coat, surround with vats, oscillators, and other instruments, throw the mix into a cave and voilà!

It’s much harder to imagine a mad mathematician: bad hair and … what? Fortunately, SMBC has figured it out!


Envelope forcing

In a recent paper [1], Jared Corduan and I considered various notions of combinatorial indecomposability for finite ordinal powers of \(\omega.\) In this process, we uncovered two weak forms of Ramsey’s theorem for pairs (\(\newcommand{\RT}[2]{\mathsf{RT}^{#1}_{#2}}\RT2k\)):

  • The Weak Ramsey Theorem (\(\newcommand{\Wk}{\mathsf{W}}\Wk\RT2k\)). For every coloring \(c:\N^2\to\set{0,\dots,k-1}\) there are a color \(d \lt k\) and an infinite set \(H\) such that \[\set{y \in \N : c(x,y) = d}\] is infinite for every \(x \in H.\)
  • The Hyper-Weak Ramsey Theorem (\(\newcommand{\HWk}{\mathsf{HW}}\HWk\RT2k\)). For every coloring \(c:\N^2\to\set{0,\dots,k-1}\) there are a color \(d \lt k\) and an increasing function \(h:\N\to\N\) such that \[\bigcup_{x=h(i-1)}^{h(i)-1} \set{y \in \N : c(x,y) = d}\] is infinite for every \(i \in \N.\)

The first is equivalent to what we called the game indecomposability of the ordinal \(\omega^2,\) and the second is related to the lexicographic indecomposability of \(\omega^2.\) You can find out more about these notions of indecomposability in our paper, what I want to write about here is the forcing technique that we used to show that \(\HWk\RT22\) is \(\Pi^1_1\)-conservative over \(\mathsf{RCA}_0\) with \(\Sigma^0_2\)-induction and to separate the two principles \(\Wk\RT22\) and \(\HWk\RT22.\) I’ve been calling the method envelope forcing since the basic idea is to force over a larger model that envelops the original one rather than forcing over the ground model itself. In the following, I will give a brief tour of this method, skipping all the gory details (that can be found in our paper).