2
$\begingroup$

Let $X_1, X_2$ be non-empty sets and let $R\subseteq X_1\times X_2$ such that for all $x\in X_1$ there is $y\in X_2$ such that $(x,y)\in R$.

Are there topologies $\tau_i$ on $X_i$ for $i=1,2$ and a continuous function $f:X_1\to X_2$ such that $R$ is the topological closure of $\text{graph}(f)$, where $\text{graph}(f) = \bigl\{\bigl(x,f(x)\bigr) \, : \, x\in X_1\bigr\}$?

$\endgroup$
8
$\begingroup$

Take $X_1=X_2=\{1,2,3\}$ and $R=\{(x,y):x\neq y\}$. Then the diagonal is open as a complement of the closed subset $R$. As an open subset, the diagonal is a union of products $A_i\times B_i$ of some open subsets $A_i\subseteq X_1$ and $B_i\subseteq X_2$. But these must be singletons so both $X_i$'s are discrete. Therefore any graph of a function is closed - a contradiction since $R$ is not a graph.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

According to https://mathoverflow.net/a/8994/4600, $\log_2$ of the number of topologies on $n$ elements is $\sim n^2/4$. So let's say there are $2^{n^2/4}$ topologies. Then the number of topologies on $X_1=[n]=\{0,\dots,n-1\}$ and $X_2=[n]$ is $$ 2^{n^2/4}\cdot 2^{n^2/4} = 2^{n^2/2}. $$ Consider now sets $R$ which contain $(k,0)$ for each $k<n$. There are $$ 2^{n(n-1)} $$ such sets. But there are only $$n^n = 2^{n\log_2 n}$$ functions, so the total number of $(\tau_1,\tau_2,f)$ is only $$ 2^{n^2/2}2^{n\log_2 n} < 2^{n(n-1)} $$ for large $n$. So there are just too many sets $R$.


Edit: This is rather complicated compared to Adam Przeździecki's solution, but it does have the virtue of showing that "closure of" could be replaced by any other method of uniquely obtaining $R$ from $f$, $\tau_1$, and $\tau_2$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Two answers 16 seconds apart :) $\endgroup$ – Adam Przeździecki May 26 '15 at 9:12
  • $\begingroup$ @AdamPrzeździecki well I had the unfounded worry that your solution would be the same as mine. $\endgroup$ – Bjørn Kjos-Hanssen May 26 '15 at 9:21

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.