Does the exact pair phenomenon for partial orders occur in your area of mathematics? - MathOverflow

Does the exact pair phenomenon for partial orders occur in your area of mathematics?

2010-04-20T18:23:37Z

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$.

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...

Answer by Jacques Carette for Does the exact pair phenomenon for partial orders occur in your area of mathematics?

2010-04-23T02:54:28Z

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.

Answer by Charles Stewart for Does the exact pair phenomenon for partial orders occur in your area of mathematics?

2010-04-23T07:35:08Z

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.

Answer by T. for Does the exact pair phenomenon for partial orders occur in your area of mathematics?

2010-06-17T08:43:28Z

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.