31
$\begingroup$

Recall that a partially ordered set (poset) $P$ has the fixed point property (FPP) if any order preserving function $f:P\longrightarrow P$ has a fixed point.

Theorem. Suppose $P$ and $Q$ are posets with the FPP and at least one of them is finite. Then $(P\times Q)$ has FPP.

Note: $(a,b)\le(c,d)$ if and only if $a\le c$ and $b\le d$.

Question. Suppose $P$ and $Q$ are two infinite posets with the FPP. Does $(P\times Q)$ have the FPP ?

Improve this question
$\endgroup$
1
  • 7
    $\begingroup$ Are you just after nasty counterexamples, or are you also interested in how to make the FPP property well behaved? If the later, see "Complete axioms for categorical fixed point operators" by Alex Simpson and Gordon Plotkin (homepages.inf.ed.ac.uk/als/Research/fixpoints.ps.gz) where they define suitable uniformity conditions for FPP property to behave well. $\endgroup$
    – Andrej Bauer
    Commented Aug 31, 2014 at 16:31

3 Answers 3

Reset to default
19
$\begingroup$

This an open problem, as far as I know. The finite case was solved by Roddy in 1994.

There were some more general results proved by other people later: see this paper by Bernd S. W. Schröder for a survey of history and recent results about FPP in posets.

Improve this answer
$\endgroup$
2
  • $\begingroup$ (All the other references here are behind a paywall but) the Schroder paper contains some interesting arguments that are similar to ones that have been used in domain theory. Unfortunately, the discussion on this page is an example of the way that pure mathematicians and computer scientists (by which I mean the inhabitants of university buildings so called - we are all mathematicians) talk past one another. I have given a similar theorem and its background from computer science - what it the background for these fixed point results for posets in pure mathematics (departments)? $\endgroup$
    – Paul Taylor
    Commented Sep 2, 2014 at 16:06
  • $\begingroup$ @PaulTaylor I am not sure what you are asking for, but perhaps you will be interested in another paper of Schroeder that is not behind a paywall: csi.uottawa.ca/ordal/papers/schroder/FINSURVE.html (I also recommend his book). A recent paper of Szymik (dx.doi.org/10.1007/s11083-014-9332-x or in preprint version arxiv.org/abs/1210.6496) gives some insight into the "meaning" of the "strong fixed point property" described in your answer, my answer and Schroeder's paper. $\endgroup$
    – Michał Kukieła
    Commented Sep 2, 2014 at 18:48
12
$\begingroup$

The question you asked is one of the main long-open problems in fixed point theory of posets.

Commenting on Paul Taylor's interesting answer: the property he describes is called strong fixed point property in order theory. In fact, if one of the posets $P,Q$ has the strong fixed point property and the other has usual fixed point property, then the product $P\times Q$ has the fixed point property. (If both of them have the strong fixed point property, then $P\times Q$ also has the strong fixed point property.) This was proved by Duffus and Sauer in 1980. Fixed point property is not equivalent to strong fixed point property even for finite posets (Pickering, Roddy 1992).

Some approaches that are not mentioned in Schröder's survey mentioned by Gejza Jenča have been presented by Josef Niederle here and here.

EDIT (made following one of Paul Taylor's comments): Unfortunately all of the papers cited above are behind a paywall. However, one can find free conference versions of Niederle's work: here and here.

Improve this answer
$\endgroup$
11
$\begingroup$

Strengthening the hypotheses on $P$ and $Q$ from a fixed point property (every endofunction has some fixed point) to the existence of a fixed point operator $\mathsf{fix}$ with $$ \text{for any } f:P\to P, \qquad f({\mathsf{fix}}(f)) = {\mathsf{fix}}(f), $$ there is a standard theorem in domain theory or lambda calculus (theoretical computer science) due to Hans Bekić.

We are given $h:P\times Q\to P\times Q$. Define $$ f = \lambda x.{\mathsf{fix}}_P(\lambda y.\pi_1(h(x,y))) : P\to Q $$ $$ g = \lambda y.{\mathsf{fix}}_Q(\lambda x.\pi_0(h(x,y))) : Q\to P $$ which have the properties that $$ f x = \pi_1(h(x,f x)) \quad\text{and}\quad g y = \pi_0(h(g y,y)). $$ Now let $x_0 = {\mathsf{fix}}_P(\lambda x.g(f x))$ and $y_0=f(x_0)$, so $x_0=g(y_0)$. Then $$ \pi_0(h(x_0,y_0)) = \pi_0(h(g y_0,y_0)) = g(y_0) = x_0 $$ $$ \pi_1(h(x_0,y_0)) = \pi_1(h(x_0,f x_0)) = f(x_0) = y_0 $$ so $(x_0,y_0)$ is a fixed point of $h$.

In fact $f$ and $g$ are variables in this, so the argument provides a fixed point operator for $P\times Q$.

Hans Bekić was a member of the IBM Vienna Laboratory but died in a mountain accident in 1982, leaving a lot of his work unpublished. It was edited and published by Cliff Jones and is available here. The result above is on pages 38-9 of Bekic2.pdf in this directory.

Google seems to think that this surname has an acute rather than a hachek.

Improve this answer
$\endgroup$
10
  • 5
    $\begingroup$ A remark, since some, like me, might not find this immediately obvious given the context of the question, $\mathsf{fix}_P:P^P \to P$ is assumed to be a homomorphism in the contextual category, otherwise there is no reason to believe that $f$ and $g$ are homomorphisms. In the context of the question, this means that $\mathsf{fix}_P:P^P \to P$ must be order preserving, where $P^P$ has the pointwise ordering; it cannot merely select an arbitrary fixed point for each $f:P \to P$. $\endgroup$
    – François G. Dorais
    Commented Sep 1, 2014 at 22:32
  • 4
    $\begingroup$ @Rahman.M: The bottom line for posets (as I tried to clarify above) is that if there are order-preserving fixpoint operators $\mathsf{fix}_P:P^P\to P$ and $\mathsf{fix}_Q:Q^Q\to Q$ then $P \times Q$ has the FPP. Here $P^P$ (similarly $Q^Q$) is the set of all order-preserving functions $P \to P$ with the pointwise ordering (i.e., $f \leq g \iff (\forall p \in P)(f(p) \leq g(p))$). $\endgroup$
    – François G. Dorais
    Commented Sep 2, 2014 at 4:04
  • 1
    $\begingroup$ As`Andrej said, whether you regard this as an "open" problem depends on whether you're looking for a theorem or a counterexample. In any area of mathematics, a random conjecture expressed in inappropriate generality is likely to be false, with unenlightening counterexamples. This result comes from the practical task of giving mathematical meaning to programming languages. As Francois explains, it requires a cartesian closed category with fixed point operators; domain theory provided many such categories. Yes, I agree that the argument is bizarre. $\endgroup$
    – Paul Taylor
    Commented Sep 2, 2014 at 8:50
  • 2
    $\begingroup$ In other words, mathematical questions often become simpler, when one makes simplifying assumptions. $\endgroup$
    – Joel David Hamkins
    Commented Sep 2, 2014 at 12:06
  • 4
    $\begingroup$ Paul, your repeated gibes about 'oligarchy', 'Thought Police', etc. are extremely tiresome. I do encourage you to have a chat with Joel David Hamkins; you can use an SE chat room for that purpose. In fact, go right ahead and exchange some comments here; just try to keep in mind that StackExchange sites are, by design, not congenial to extended open-ended discussions. $\endgroup$
    – Todd Trimble
    Commented Sep 2, 2014 at 13:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .