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](https://arxiv.org/pdf/1501.04523.pdf). 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](https://math.okstate.edu/people/jayjs/survey-submit.pdf). 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$.



Do monotone functions on the interval have an "Alexander duality" property?
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$).




---


1[blog](https://gowers.wordpress.com/2008/08/16/just-do-it-proofs/), [tricki](http://www.tricki.org/article/Just-do-it_proofs)  

2See, for example, here: [What is the cardinality of a set of all monotonic functions on a segment $[0,1]$?](https://math.stackexchange.com/q/71163)  

3Notice that in this step we are using Axiom of Choice. (In the form of the well-ordering principle.)


