Let $X,Y$ be two copies of the unit interval $[0,1]$. Consider functions $X\rightarrow Y$ and $Y\rightarrow X$ both as subsets of the cartesian product $X\times Y$. (More precisely: identify a function $f:X\rightarrow Y$ with its graph $\{(x,f(x)):x\in X\}$, and likewise a function $g:Y\rightarrow X$ with its graph $\{(g(y),y)\subset X\times Y:y\in Y\}$.)

One can convince oneself that:

(A) Any monotone nondecreasing function $f:X\rightarrow Y$ and any monotone nondecreasing function $g:Y\rightarrow X$ intersect nontrivially in $X\times Y$.

(Proof sketch below in the "appendix".) I am curious about the following "converse" statement:

Is the following true?

(B) If a subset $S\subset X\times Y$ has the property that it intersects nontrivially every monotone nondecreasing function $g:Y\rightarrow X$, then it contains a monotone nondecreasing function $f:X\rightarrow Y$.

If so, does this have a name? Do you know a proof or reference?


I'm calling (B) a "converse" to (A) because the latter is equivalent to the statement "if a subset $S\subset X\times Y$ contains a monotone $f:X\rightarrow Y$, then it meets every monotone $g:Y\rightarrow X$."

The motivation comes from combinatorial commutative algebra (!): I got curious about this question after hearing a talk yesterday on letterplace and co-letterplace ideals of posets. Let $P$ be a finite poset, and let $[n]$ be the $n$-chain. Fix a field $k$ and let $R$ be a polynomial ring over $k$ with indeterminates indexed by the elements of the cartesian product $[n]\times P$. The squarefree monomials in $R$ are thus in bijection with the subsets of $[n]\times P$. The letterplace ideal of $P$, denoted $L(n,P)$, is the ideal generated by squarefree monomials corresponding with the graphs of poset maps $[n]\rightarrow P$, and the co-letterplace ideal of $P$, written $L(P,n)$, is the ideal generated by squarefree monomials corresponding with graphs of poset maps $P\rightarrow [n]$.

In the talk I learned that it is a theorem that $L(n,P)$ and $L(P,n)$ are Alexander dual to each other, in the sense of Stanley-Reisner theory. This translate into the following pair of converse statements:

(A') Every poset map $[n]\rightarrow P$, regarded as a subset of $[n]\times P$, meets every poset map $P\rightarrow [n]$.

(B') If a subset $S\subset [n]\times P$ meets every poset map $P\rightarrow [n]$, then it contains a poset map $[n]\rightarrow P$. (And vice versa.)

Suppose that $P$ is a chain. Then the true statement (A') is a discrete analogue of the true statement (A). This made me want to know if the continuous analogue of (B') was also true.


Proof sketch of statement (A), that $f,g$ have a common point in $X\times Y$:

If they don't meet at $(0,0)$ or $(1,1)$, then we have strict inequalities $g(f(0))>0$ and $g(f(1))<1$. Then the function $g(f(x)) - x$ goes from pos. to neg. on $[0,1]$. Let $x^\star$ be the infimum of the $x$'s such that $g(f(x))-x$ is negative.

Since $g(f(x))$ is monotone nondecreasing, it is continuous except for an at-most-countable set of (upward) jump discontinuities; hence the same is true of $g(f(x))-x$. The point $x^\star$ cannot be one of these discontinuities because this would force $g(f(x))-x$ to be positive on an open interval to the right of $x^\star$. Thus $g(f(x))-x$ is continuous at $x^\star$. This implies it is not negative at $x^\star$ since this would force it to be negative on an open interval to the left of $x^\star$. Then $g(f(x))-x$ is positive at every point $x<x^\star$ and negative on a set of points $x>x^\star$ that have $x^\star$ as a limit point. Hence it is zero there, so $x^\star = g(f(x^\star))$, and

$$(x^\star,f(x^\star)) = (g(f(x^\star)),f(x^\star))\in X\times Y$$

is a point common to $f$ and $g$.

  • 1
    $\begingroup$ What does it mean that (graphs of) two functions intersect non-trivially. Is it just that their intersection is non-empty, or is something more required? $\endgroup$ – Martin Sleziak Jun 14 '17 at 16:30
  • 1
    $\begingroup$ @MartinSleziak - Yes, I meant that their intersection is not empty. $\endgroup$ – benblumsmith Jun 14 '17 at 17:07
  • 1
    $\begingroup$ @MartinSleziak, I agree that some interchange is needed, but it seems that @ benblumsmith has made two interchanges, first identifying $X \times Y$ with $Y \times X$, then graphing the converse of $g$ rather than $g$ itself. It seems to me that only the latter interchange is what is desired. $\endgroup$ – LSpice Jun 14 '17 at 17:08
  • 2
    $\begingroup$ @LSpice - I agree. The identification of $X\times Y$ with $Y\times X$ is technically unnecessary in light of the explicit formula for the graph of $g$. When I first wrote it down the sentence just ended with "likewise for $g$." Then I added the explicit $(g(y),y)$ just to make super-abundantly-explicit how the graph of $g$ was being made a subset of $X\times Y$. I guess I may have made things less clear instead of more. I'll make an edit. $\endgroup$ – benblumsmith Jun 14 '17 at 17:11
  • 2
    $\begingroup$ While this is tangential to the question, I note that the argument for (A) reduces to the assertion that $g\circ f$, a monotone self-mapping of $X$, has a fixpoint. Thus, it works even if $Y\ne X$ ($Y$ may be an arbitrary partially ordered set), and $X$ does not have to be $[0,1]$ either—e.g., it is enough if $X$ is a complete lattice, by the Knaster–Tarski theorem. (By symmetry, it is also enough if $Y$ is a complete lattice.) $\endgroup$ – Emil Jeřábek Jun 14 '17 at 17:47

Let us try to construct $S$ which is a counterexample to (B) by transfinite induction. (In the style of just-do-it1 proofs.)

We will use the fact2 that the set $\mathcal M$ of all monotone non-decreasing functions $[0,1]\to[0,1]$ has cardinality $\mathfrak c$. Let $\mathcal M=\{f_\alpha; \alpha<\mathfrak c\}=\{g_\alpha; \alpha<\mathfrak c\}$ be any two enumerations3 of $\mathcal M$.

By transfinite recursion we define points $P_\alpha,Q_\alpha \in [0,1]\times[0,1]$ for $\alpha<\mathfrak c$. The points $P_\alpha$ will help us avoid all $f_\alpha$'s (they will be forbidden points). The points $Q_\alpha$ will help us intersect all $g_\alpha$'s (they will be included in $S$.)

In the inductive step we simply choose any $P_\alpha\ne Q_\alpha$ such that

  • $P_\alpha,Q_\alpha\notin\{P_\beta,Q_\beta; \beta<\alpha\}$
  • $P_\alpha \in \{(x,f_\alpha(x)); x\in X\}$
  • $Q_\alpha \in \{(g_\alpha(y),y); y\in Y\}$

This is always possible since the set $\{P_\beta,Q_\beta; \beta<\alpha\}$ has cardinality less than $\mathfrak c$ and the graphs of $f$ and $g$ have cardinality $\mathfrak c$.

Now we simply put $$S=\{Q_\alpha; \alpha<\mathfrak c\}.$$

For any $\alpha$, we get that $S$ intersects $g_\alpha$ (since $Q_\alpha\in S$), but $S$ does not contain $f_\alpha$ (since $P_\alpha\notin S$).

1blog, tricki
2See, for example, here: What is the cardinality of a set of all monotonic functions on a segment $[0,1]$?
3Notice that in this step we are using Axiom of Choice. (In the form of the well-ordering principle.)

  • 2
    $\begingroup$ I hope I did not make some embarrassing mistake in the above answer. If it is indeed correct, it seems quite natural to ask what happens if we require $S$ to be "nice" (measurable, analytic, Borel, ...) or if we are not allowed to use AC. $\endgroup$ – Martin Sleziak Jun 14 '17 at 18:46
  • $\begingroup$ This seems right. It is amazing to me that the cardinality of the set of monotone functions is not greater than the cardinality of the continuum. I agree that your proposed restrictions on $S$ are natural. If one of them rescued the claim, that would be very cool but at this point it would surprise me. $\endgroup$ – benblumsmith Jun 15 '17 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.