MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

Suppose that I have a partial order P and an increasing sequence $a_0< a_1<a_2<\cdots$ of elements of $P$. A pair of elements (b,c) from P is said to be an exact pair for this sequence, if

  • Both $b$ and $c$ are upper bounds for the sequence, so that $a_n<b$ and $a_n<c$ for every $n$, and
  • Whenever $d\leq b$ and $d\leq c$ then $d\leq a_n$ for some $n$.
           b     c

More generally, an ideal $I$ in $P$ admits an exact pair $(b,c)$, if $I=\{\ a \mid a< b\text{ and } a<c\ \}$.

Note that if a strictly increasing sequence has an exact pair, then the sequence cannot have a least upper bound, since such a bound would be below both b and c and therefore have to be below some $a_n$, and consequently not an upper bound of the sequence after all. Note also that if $b$ and $c$ form an exact pair for a strictly increasing sequence, then there can be no greatest lower bound for $\{b,c\}$, and so orders with such exact pairs are not lattices.

The exact pair property arises in computability theory, because in the hierarchy of Turing degrees, every increasing sequence admits an exact pair. This is one way of seeing that the set of Turing degrees is not a lattice. More generally, every countable ideal in the Turing degrees has an exact pair, and in the case of principal ideals, this implies that every Turing degree is the greatest lower bound of a pair of incomparable degrees. It also arises for certain hierarchies of complexity theory.

The exact pair property is so beautifully structural, serving as an alternative to completeness, and for this reason I have always wondered whether it could have applications in other contexts, but I have only ever heard of it in connection with the computability degrees. Therefore,

My question is: Does the exact pair phenomenon arise elsewhere in mathematics? Are there other natural orders studied outside logic that have the exact pair property?

Perhaps other natural hierarchies in mathematics exhibit the exact pair property? Or perhaps they do but this remains undiscovered...

share|cite|improve this question
I don't have much to say here, except that the poset $P = \mathbb{N} \cup \lbrace\infty_1,\infty_2\rbrace$ with the usual ordering on the natural numbers and the additional stipulations $n \leq \infty_1$, $n \leq \infty_2$ often serves as a counter-example in domain theory. – Andrej Bauer Apr 21 '10 at 4:40
I understand that the theorem is due to Spector (1956) On degrees of recursive unsolvability, Annals of Mathematics 64:581-592. It's a very nice theorem: Shore stresses its use in eliminating second-order quantification. – Charles Stewart Apr 21 '10 at 9:30
Thanks for the reference, Charles. – Joel David Hamkins Apr 21 '10 at 10:45

The projections $\mathcal{P}(\mathcal{C}(H))$ in the Calkin algebra have a similar property with the pair "on the other side", i.e. for every countable subset one can find a pair with exactly the same upper (or lower) bounds. This can be seen from the proof of Theorem 4.1 of my paper Filters in C*-algebras. Conversely, for any pair (or even countable subset) one can find an increasing sequence with exactly the same upper bounds, which applies more generally to the projections in any C*-algebra with real rank zero. As with Turing degrees, this can also be used to show that $\mathcal{P}(\mathcal{C}(H))$ is not a lattice. To see this first note that $\mathcal{P}(\mathcal{C}(H))$ has no $(\omega,1)$-gaps, by essentially the same argument used with $\mathscr{P}(\omega)/\mathrm{fin}$. Thus to show that $\mathcal{P}(\mathcal{C}(H))$ is not a lattice one simply needs to find a pair of projections that has a strictly increasing sequence with the same upper bounds, as done by Farah/Hadwin/Weaver (see this mathoverflow post)

share|cite|improve this answer
So this is kind of like the opposite of what was asked for, is that the idea? – Nik Weaver Feb 26 at 15:36
Sure, I guess you might call this the dual exact pair property. But it still serves as an alternative to (countable) completeness, with pairs replacing single least upper bounds. – Tristan Bice Feb 26 at 16:51
Yes, I see. It is kind of surprising, isn't it? – Nik Weaver Feb 26 at 17:03
Certainly is, although I guess you should always expect the unexpected with the Calkin algebra. – Tristan Bice Feb 26 at 17:09

The mathematicians' idiom for a wide class of situations resembling this one is "blow-up", inspired by the term from algebraic geometry. It is used both as noun (a blow up of ...) and verb (to blow up ...).

It means to start from one structure and blow up (inflate) part of it, forming a larger or more complicated structure, keeping other parts the same.

For this example of "exact pairs", one can construct the partial order $P$ by starting with linear order consisting of the chain $a_i$ and its least upper bound $L$, then blowing up $L$ into a pair of points $b,c$. Identifying $b$ and $c$ is a quotient of posets that reverses the blow up (ie, restores $L$ in its original state of being a least upper bound to the $a_i$) and this is equivalent to the definition of exact pair. It is also clear from this observation how to define exact triples, or splittings of several least upper bounds.

So outside of recursion theory, I think math people would commonly describe such a diagram as a (two-fold) splitting or blowup of a point in a poset. I don't know of any compelling examples where this construction occurs but certainly the idea would feel very familiar to many if phrased in the language of blow-ups.

EDIT: something close to what Joel is asking about is the theory of R-trees (R as in "real numbers"). The minimal example of a dense order where any chain has a least exact-pair of upper bounds is some sort of infinite trivalent R-tree.

share|cite|improve this answer
Thanks for your answer. In the Turing degrees, every increasing sequence has an exact pair, but they are never unique, and indeed I think that every upper bound $b$ forms an exact pair (b,c) with some c. Further, there are upper bounds below $b$, just not below both b and c. So if one were to identify all such pairs in the Turing degrees, the resulting partial order would not have the least-upper-bound property, and may very well continue to exhibit the exact pair property. So I don't really follow your proposal, unless you are just talking about one sequence and one exact pair for it. – Joel David Hamkins Jun 17 '10 at 12:23

Interesting property. You can create such a structure over the closure of the graph of $\sin(\frac{1}{x})$ for $x\in [-1,0)$. Partially order the points by the $x$ coordinate (of the graph). You then have a whole segment's worth of exact pairs over $0$.

One can probably generalize that construction to apply to landing rays (of the uniformizing map for the basin at infinity) of a non-locally connected polynomial Julia set for a ray which 'tries' to land on the critical orbit.

share|cite|improve this answer
Thanks for the example, Jacques. I think that one could make many similar examples. What I am looking for ideally are examples akin to the Turing degrees, that is, large intensely studied hierarchies that have the properrty that every increasing sequence admits an exact pair. – Joel David Hamkins Apr 23 '10 at 3:25

In trying to understand better a certain weak choice axiom, I once concocted an example in sheaf theory which involves an exact pair in the sense of this question, without knowing it was a "thing" elsewhere.

In constructive mathematics, one choice principle which has been found useful is called the Presentation Axiom, Pax for short, which says roughly that any object $A$ (of one's given category) can be covered by an object $P$ which is projective: any further covering $Q \twoheadrightarrow P$ must split. You can imagine this applying for example to certain categories of sheaves of modules where one might want to consider projective resolutions. Or you can imagine it applying to certain categories of Heyting-valued sets or other toposes where the full axiom of choice is out of the question.

In constructive mathematics, it is also known as "CoSHEP" (Category of Sets Has Enough Projectives); a more philosophical justification (quoting the nLab) is

every set $A$ should have a ‘completely presented’ set of ‘canonical’ elements, that is elements given directly as they are constructed without regard for the equality relation imposed upon them. For canonical elements, equality is identity, so the BHK interpretation of logic justifies the axiom of choice for a completely presented set. This set is $P$, and $A$ is obtained from it as a quotient by the relation of equality on $A$. This argument can be made precise in many forms of type theory (including those of Martin-Löf and Thierry Coquand), which thus justify CoSHEP, much as they are widely known to justify dependent choice.

Now, Pax as stated above (for let's say a topos $E$) was actually the external version: an object $P$ is externally projective if the external hom-functor $\hom(P, -): E \to Set$ takes epimorphisms to epimorphisms. There's also an internal version of Pax which is often more appropriate: if $(-)^P: E \to E$ denotes the internal hom-functor, then we say $P$ is internally projective if $(-)^P$ preserves epimorphisms, and internal Pax would say that every object $A$ is covered by an internally projective $P$. What I had wanted was an example of a topos which validates external Pax but not internal Pax.

Presheaf toposes $E = Set^{C^{op}}$ (the category of functors $C^{op} \to Set$, where $C$ is a small category and $Set$ is just a vanilla category of sets in a ZFC background) always validate external Pax. It's easy to show that representable functors $\hom_C(-, a)$ are externally projective, as are coproducts of representable functors, and any object $F: C^{op} \to Set$ is covered by such a coproduct via a canonical map $\sum_{A \in Ob(C)} \sum_{x \in F A} hom_C(-, A) \twoheadrightarrow F$. So I wanted a $C$ which would force internal Pax to fail for $Set^{C^{op}}$.

The example I came up with is where $C$ is a generic exact pair, i.e., the poset $\mathbb{N} \cup \{a, b\}$ where the natural numbers $\mathbb{N}$ is ordered as usual and $a, b$ are incomparable elements that dominate every element of $\mathbb{N}$. We consider $C$ as a 'thin' category as is customary for posets. I claim that $A = \hom_C(-, a)$, or indeed any object $P$ covering $A$, cannot be internally projective. Specifically, that such $(-)^P: E \to E$ cannot preserve an evident epimorphism $F \twoheadrightarrow G$ where $F(n) = \{m \in \mathbb{N}: m \geq n\}$ and $F(a), F(b)$ are empty, where the restriction maps are given by the inclusions $F(n+1) \hookrightarrow F(n)$, and where $G$ is the presheaf with $G(n) = \ast$ (a one-point set) and $G(a), G(b)$ are empty.

To show the induced natural transformation $F^P \to G^P$ isn't an epimorphism, it suffices to show that the component $F^P(b) \to G^P(b)$ isn't a surjection between sets; in fact one may calculate that $F^P(b)$ is empty and $G^P(b)$ has exactly one element. Such calculations aren't exactly a spectator sport, so I'll wrap it up by making a few observations:

  • For general $F$ one may identify $F^P(b)$ with $Nat(\hom_C(-, b) \times P, F)$, where the right side indicates a set of natural transformations.

  • In the case where $P = \hom_C(-, a)$, we have in fact $\hom_C(-, b) \times \hom_C(-, a) \cong G$, and a natural transformation $G \to F$ boils down to having an element that belongs to the intersection of all the $F(n)$. Of course no such element exists since the intersection is empty.

  • So $F^{\hom_C(-, a)}(b)$ is empty, and $G^{\hom_C(-, a)}(b)$ has an element (in fact just one).

  • For general $P$ covering $\hom_C(-, a)$, there is a section $s: \hom_C(-, a) \to P$ (Yoneda lemma), and this section induces a map $F^P \to F^{\hom_C(-, a)}$, and thence a function $F^P(b) \to F^{\hom_C(-, a)}(b)$. The domain $F^P(b)$ has to be empty since the codomain is. On the other hand, $G^P(b)$ is nonempty because there is a map $\hom_C(-, b) \times P \to \hom_C(-, b) \times \hom_C(-, a) \cong G$.

share|cite|improve this answer
Why the downvote?? – Todd Trimble Apr 13 at 11:33

Rather than an answer, a comment that is too long to go where it belongs.

I'm guessing that this phenomenon is rarely observed, because mathematicians neither want to nor have much reason to deal with such badly behaved partial orders, since you can construct better behaved order-theoretic structures over them that conserve your ability to reason about the original example.

In recursion theory, mass problems were proposed by Medvedev, a student of Kolmogorov, as a formalisation of Kolmogorov's idea of a "calculus of problems" as a foundation for intuitionistic logic. They are essentially sets of oracle Turing machines, and so generalise the usual theory of Turing degrees by admitting least upper bounds, and so lattice structure. Stephen Simpson has done nice work recently, motivated by the idea that there are natural intermediate degrees expressible as mass problems that are not Turing degrees, such as Martin-Löf randomness. Cf. Simpson (2008) Mass Problems and Intuitionism, Notre Dame Journal of Formal Logic 49(2):127-136.

Recursion theorists are, I think, logicians first and mathematicians second, and so they have a different attitude to formalisation: the structure of Turing degrees is most important to them because that is the basic structure, and that is important enough that they will tolerate the sharp edges that come with the first-order formalism.

So if I am not wrong about mathematical culture, I think examples will be hard to find, and may lie behind more widely known structures.

share|cite|improve this answer

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.