# Do monotone functions on the interval have an “Alexander duality” property?

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?

Remarks

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.

Appendix

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

• 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? – Martin Sleziak Jun 14 '17 at 16:30
• @MartinSleziak - Yes, I meant that their intersection is not empty. – benblumsmith Jun 14 '17 at 17:07
• @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. – LSpice Jun 14 '17 at 17:08
• @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. – benblumsmith Jun 14 '17 at 17:11
• 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.) – 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.)

• 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. – Martin Sleziak Jun 14 '17 at 18:46
• 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. – benblumsmith Jun 15 '17 at 18:47