# Continuously selecting elements from unordered pairs

The symmetric square of a topological space $X$ is obtained from the usual square $X^2$ by identifying pairs of symmetric points $(x_1,x_2)$ and $(x_2,x_1)$. Thus, elements of the symmetric square can be identified with unordered pairs $\{x_1,x_2\}$ from $X$ (including the degenerate case $x_1 = x_2$). With this identification, the following question is very natural:

When is there a continuous selector from the symmetric square to the original space?

This is always possible if $X$ is a generalized ordered space (a subspace of a linear order with the order topology) since min and max are both continuous selectors. I don't think this is a necessary condition since I can construct continuous selectors (on Baire space, for example) that aren't equal to min or max for any ordering of the underlying space.

A necessary condition is that removing the diagonal disconnects $X^2$. More precisely, as Adam Bjorndahl pointed out in the comments, the complement of the diagonal should be the union of two disjoint open sets such that $(x_1,x_2)$ is in one iff $(x_2,x_1)$ is in the other. So, for example, there are no continuous selectors for the symmetric square of the plane nor the circle.

I'm mostly interested in the case when $X$ is Polish, so it's fine to assume that $X$ is very nice: Hausdorff, normal, perfect, etc.

-
After removing diagonal, any point $(x,y)$ should be in a component different from $(y,x)$. It seems that this should be necessary and sufficient condition. Did I miss something? – Anton Petrunin Sep 5 '11 at 23:53
Now that you put it in those terms, I think it's me that completely missed the full weight of the necessary condition. Please post your comment as an answer so I can accept it. Follow-up: Is this equivalent to the linear ordering condition? – François G. Dorais Sep 6 '11 at 0:50
Is it important what the connected components of $X^{2} - \Delta$ look like? I'm worried about an example like $X = \mathbb{Q}^{2}$. Maybe instead of components we want: there is a decomposition of $X^{2} - \Delta$ into disjoint opens $U$ and $V$ such that $(x,y) \in U$ iff $(y,x) \in V$? – Adam Bjorndahl Sep 6 '11 at 2:52
Well, it seems like I managed to both underestimate and overestimate the same argument in the span of a few hours. Anton's argument works fine when $X^2$ is locally connected, but I don't see the general case. Maybe Anton had a bit more in mind? Your decomposition into two symmetric open sets works, but I feel like it's more a restatement of the question than an answer. Then again, maybe there is no better answer than that. – François G. Dorais Sep 6 '11 at 3:53
The case of $\mathbb{Q}^2$ is actually pretty neat. If I'm not mistaken, it does have a continuous selector, as will any other countable metric space. – François G. Dorais Sep 6 '11 at 4:14

In this paper Van Mill and Wattel proved that the existence of a continuous selection characterizes orderability in the class of compact Hausdorff spaces.

-
Thanks! This takes care of a large chunk of the problem... – François G. Dorais Oct 19 '11 at 21:39

This should have been a comment, but it got a bit too long.

A possibly useful necessary condition, in regular spaces, for the existence of a continuous selector is that there should not exist three points $a,b,c\in X$ such that each two lie in a closed connected set that misses the third point. Proof: If we had three such points and closed connected sets, then we could argue as follows for any alleged selector $S$. Suppose, without loss of generality, that $S\{a,b\}=a$. Let $M$ be a closed connected set containing $b$ and $c$ but not $a$. By regularity of $X$, $a$ and $M$ have disjoint open neighborhoods. So if we let $m$ vary over $M$, the values of $S\{a,m\}$ form a connected subset of $M\cup\{a\}$ that contains $a$, which means none of these values can be in $M$ because of the disjoint neighborhoods. In particular, $S\{a,c\}=a$. Now hold $c$ fixed and consider $S\{n,c\}$, where $n$ varies over a closed connected set $N$ that contains $a$ and $b$ but not $c$. An argument like the preceding one shows that $S\{n,c\}$ must stay in $N$, so in particular $S\{b,c\}=b$. A third use of the same argument, holding $b$ fixed and moving $c$ to $a$ in a closed connected set that misses $b$ shows that $S\{b,a\}=b$, contrary to our initial assumption.

This implies in particular that, if $X$ is to have a continuous selector from pairs, then $X$ cannot contain a triod or a circle (homeomorphic copies of the letters F and D). If we were dealing with CW complexes, we could deduce that the dimension is at most 1 (so we have a graph), that the graph must be acyclic (so we have a forest), and that there must be no branching (so we have a disjoint union of real intervals). For not-so-nice spaces, the situation is unfortunately not so clear.

-
Thanks! So the CW complexes with continuous selectors are precisely those which are generalized ordered spaces. (By the way, I like your choice of triod and circle!) – François G. Dorais Sep 6 '11 at 13:16

Like the first answer, this is really a comment that has outgrown the comment box. No new results here, but a different way of looking at continuous selectors that may be helpful (somewhat analogous to the relationship between choice functions and preference relations in decision theory).

Call a relation $T$ on a topological space $X$ an open tournament on $X$ (thanks for the terminology!) if the following conditions hold:

(a) $T$ is total: for all $x,y \in X$, either $xTy$ or $yTx$;

(b) $T$ is antisymmetric: for all $x,y \in X$, if $xTy$ and $yTx$ then $x = y$;

(c) $T$ respects the topology on $X$: for all distinct $x,y \in X$ with $xTy$, there exist disjoint open neighbourhoods $U$ and $V$ about $x$ and $y$, respectively, such that for all $x' \in U$ and all $y' \in V$, $x'Ty'$.

Let's read $xTy$ and "$x$ trounces $y$" (yes, I am having some fun with this).

Lemma: The existence of a continuous selector for a Hausdorff space $X$ is equivalent to the existence of an open tournament on $X$.

Proof. Given an open tournament $T$ on $X$, define $s: [X]^{2} \to X$ by $$s(\{x,y\}) = x \iff xTy.$$ Conditions (a) and (b) ensure that $s$ is a well-defined selector function. Moreover, if $s(\{x,y\}) = x$ and $W$ is an open neighbourhood about $x$, then since $xTy$ we can find $U$ and $V$ as in condition (c), in which case the open sets $U \cap W$ and $V$ yield an open neighbourhood about $\{x,y\}$ contained in $s^{-1}(W)$, so $s$ is continuous. Note also that conditions (a) and (c) imply that $X$ is Hausdorff.

Conversely, suppose that $X$ is a Hausdorff space and $s$ is a continuous selector function. Define $T \subset X \times X$ by: $$xTy \iff s(\{x,y\}) = x.$$ It is clear that $T$ is total and antisymmetric. Suppose that $x \neq y$ and $xTy$, so we have $s(\{x,y\}) = x$. Let $W$ and $W'$ be disjoint neighbourhoods of $x$ and $y$, respectively, and let $U$ and $V$ be the open neighbourhoods of $x$ and $y$ corresponding to $s^{-1}(W)$. Then $W \cap U$ and $W' \cap V$ are as required in condition (c). $\blacksquare$

Given an open tournament $T$ on $X$, for each $x \in X$ define $$T_{x} := \{y \in X : x \neq y \textrm{ and } xTy\}$$ and $$T^{x} := \{y \in X : x \neq y \textrm{ and } yTx\}.$$ Then it is easy to see that for all $x \in X$, $T_{x}$ and $T^{x}$ are open, and moreover $$T_{x} \sqcup T^{x} = X - \{x\}.$$ This shows that a necessary condition for the existence of an open tournament on $X$ is that $X$ is disconnected whenever it is punctured. In particular, this provides another way of seeing that neither $\mathbb{R}^{2}$ nor $S^{1}$ admit continuous selectors. This condition is certainly not sufficient, however, since it is satisfied by the triod. In that case, something more subtle seems to be going on; loosely speaking, the problem seems to be that distinct punctures in a neighbourhood of the vertex create very different separations.

Edit: Let me try to make this last point a bit more precise. First some intuition. If $A$ and $B$ constitute a separation of a space $Y$, then $\chi_{A}: Y \to \{0,1\}$, the characteristic function of $A$, is both surjective (since $A \neq \emptyset$ and $A \neq Y$), and also continuous. Conversely, every continuous surjective characteristic function $\chi$ on $Y$ yields the separation $\chi^{-1}(1) \sqcup \chi^{-1}(0)$ of $Y$.

The product topology on the set $2^{Y}$ tells us that $\chi$ and $\chi'$ are "$F$-close" if they agree on the finite set $F \subset Y$ (these are the basic opens). This in turn provides a notion of closeness on the set $$\mathcal{S}_{Y} := \{(A,B) : \textrm{A and B constitute a separation of Y}\}$$ of all (ordered) separations of $Y$: $(A,B)$ and $(A',B')$ are "$F$-close" if $A \cap F = A' \cap F$ (so also $B \cap F = B' \cap F$).

More generally, given a fixed Hausdorff space $X$, let $$\mathcal{D} = \mathcal{D}_{X} := \{(A,B) : \textrm{A and B are open and disjoint}\},$$ and topologize this set using the notion of "$F$-closeness" as above: given a finite set $F \subset A \cup B$, say that $(A,B)$ and $(A',B')$ are "$F$-close" if $A \cap F = A' \cap F$ and also $B \cap F = B' \cap F$.

To connect this reasoning to the question at hand, observe that an open tournament $T$ on $X$ yields a function $f: X \to \mathcal{D}$ by setting $f_{T}(x) = (T_{x}, T^{x})$.

Lemma: $f_{T}$ is continuous.

Proof. Consider the basic open neighbourhood of $f_{T}(x) = (T_{x}, T^{x})$ corresponding to the finite set $F \subset T_{x} \cup T^{x} = X - \{x\}$. If $z \in T_{x} \cap F$, then in particular $xTz$ so there are open sets $U_{z}$ and $V_{z}$ about $x$ and $z$ respectively as in condition (c). Similarly, if $z \in T^{x} \cap F$ then $zTx$ so there are open sets $U_{z}$ and $V_{z}$ about $z$ and $x$ respectively as in condition (c). Set $$W := \bigcap_{z \in T_{x} \cap F} U_{z} \cap \bigcap_{z \in T^{x} \cap F} V_{z}.$$ Then $W$ is an open neighbourhood of $x$ and for any $y \in W$ we have $$T_{y} \cap F = T_{x} \cap F \textrm{ and } T^{y} \cap F = T^{x} \cap F,$$ which shows that $f$ is continuous. $\blacksquare$

Now we can see (from another perspective) why the triod admits no open tournament $T$: if it did and $v$ is the vertex point of the triod, then either $T_{z}$ consists of two of the prongs and $T^{z}$ consists of the third, or vice versa. However, in either case, $f_{T}$ cannot be continuous, since by choosing a point $w$ very close to $v$ (but distinct from $v$), we can always ensure that any two prongs lie in the same connected component, so we can always "ruin" whatever arbitrary choice was made at the vertex by $T$.

Here is a quick attempt at a converse. Let $f: X \to \mathcal{D}$ satisfy:

• $f$ is continuous;
• for each $x \in X$, $f(x) \in \mathcal{S}_{X - \{x\}}$;
• for all $x,y \in X$, $y \in (\pi_{0} \circ f)(x)$ iff $x \notin (\pi_{0} \circ f)(y)$.

Call such an $f$ (provisionally) "nice". One can check that when $T$ is an open tournament, $f_{T}$ is "nice". Define a binary relation $T_{f}$ on $X$ by: $$xT_{f}y \iff y \in (\pi_{0} \circ f)(x).$$ Then I believe/hope that $T_{f}$ is an open tournament (though I still need to check this carefully).

A converse like this would be appealing because it provides a nice picture of when there exists a continuous selector. For example, $\mathbb{R}$ would have one due to the "nice" function $$f(x) = (\{y : y < x\}, \{y : y > x\}).$$ Perhaps of more interest, the space $\mathbb{Q}^{2}$ would admit a continuous selector based on the existence of the following "nice" function: for each $p \in \mathbb{Q}^{2}$, let $L_{p}$ denote the subset of $\mathbb{Q}^{2}$ to the left of the line through $p$ of slope $\pi$, let $R_{p}$ denote the subset of $\mathbb{Q}^{2}$ to the right of the line through $p$ of slope $\pi$, and set $f(p) = (L_{p}, R_{p})$.

-
I'm happy you decided to use my terminology! Just to nitpik, I think it would be slightly better if tournaments were asymmetric ($x \mathrel{T} y$ implies $y \not\mathrel{T} x$), as they usually are in combinatorics. This also makes the openness requirement (c) a little cleaner. However, since it's obvious how to go back and forth between "strict" tournaments (like mine) and "loose" tournaments (like yours), there is really no significant difference between the two... – François G. Dorais Sep 7 '11 at 3:42
Good point -- it makes the translation back and forth between selectors a bit more cumbersome, but I think you're right that overall it's cleaner. – Adam Bjorndahl Sep 7 '11 at 4:00
The addendum is really neat! I like the argument in favor for $\mathbb{Q}^2$. I plan on posting the construction later today... The map $p \mapsto (T_p,T^p)$ for my construction is not nearly as nice as your $p \mapsto (L_p,R_p)$. It would be interesting to know if some construction for $\mathbb{Q}^2$ does give your $L_p$ and $R_p$. – François G. Dorais Sep 7 '11 at 18:20

This is an expansion on the comment I made to the effect that the symmetric square of $\mathbb{Q}^2$ has a continuous selector, which is surprising since the symmetric square of $\mathbb{R}^2$ does not have a continuous selector.

In fact, a much more general statement is true:

The symmetric square of a countable metric space always has a continuous selector.

Let $X$ be a countable metric space. I will show that $X^2$ minus the diagonal can be split into two open sets $U$ and $V$ such that $(x,y) \in U$ iff $(y,x) \in V$. This is sufficient since $T = X^2 - U$ is then an open tournament in the sense of Adam Bjorndahl.

Let $d$ be a metric on $X^2$ such that $(x,y) \mapsto (y,x)$ is an isometry (e.g., let $$d((x_1,y_1),(x_2,y_2)) = d_0(x_1,x_2) + d_0(y_1,y_2)$$ where $d_0$ is a metric on $X$). Since $X$ is countable, the set $D$ of all possible values of $d$ is also countable, which means that the set $E = (0,\infty) - D$ of non-values of $d$ contains arbitrarily small positive numbers.

Fix an enumeration $(x_0,y_0),(x_1,y_1),\ldots$  of $X^2$ minus the diagonal. We will define $U$ and $V$ by stages.

To start things off, let $\varepsilon_0 \in E$ be sufficiently small that the open ball $B_{\varepsilon_0}(x_0,y_0)$ does not intersect the symmetric ball $B_{\varepsilon_0}(y_0,x_0)$. (In particular, neither ball intersects the diagonal of $X^2$.) Put all points of $B_{\varepsilon_0}(x_0,y_0)$ in $U$ and all points of $B_{\varepsilon_0}(y_0,x_0)$ in $V$.

Next, we consider the point $(x_1,y_1)$. If $(x_1,y_1)$ was already put in $U$ or $V$, then skip to the next stage. Otherwise, let $\varepsilon_1 \in E$ be sufficiently small that the open ball $B_{\varepsilon_1}(x_1,y_1)$ does not intersect symmetric ball $B_{\varepsilon_1}(y_1,x_1)$, nor does either ball contain any points that were already put in $U$ or $V$. This is always possible since $\varepsilon_0$ is not a possible value of $d$, which means that $$\min\{d((x_0,y_0),(x_1,y_1)), d((y_0,x_0),(x_1,y_1))\} > \varepsilon_0.$$ So making sure that $$\varepsilon_1 < \min\{d((x_0,y_0),(x_1,y_1)),d((y_0,x_0),(x_1,y_1))\} - \varepsilon_0$$ will do for the second requrement. Finally, put all points of $B_{\varepsilon_1}(x_1,y_1)$ in $U$ and all points of $B_{\varepsilon_1}(y_1,x_1)$ in $V$.

Continue in the same manner for all the remaining points $(x_2,y_2),(x_3,y_3),\ldots$  Since all points of $X^2$ minus the diagonal will eventually be considered, in the end we will have a partition of $X^2$ minus the diagonal into two disjoint open sets $U$ and $V$ such that $(x,y) \in U$ iff $(y,x) \in V$.

-
That's a nice argument; I especially like the use of countability to ensure that $(x_{n}, y_{n})$ never lies on the boundary of any $B_{\varepsilon_{k}}(x_{k}, y_{k})$, $k < n$. I'd have to think about whether this process can ever correspond to a "linear" division of $\mathbb{Q}^{2}$ as in my construction. Your construction is clearly much more general, of course; both show, though, that $\mathbb{Q}^{2}$ admits very many distinct continuous selectors (in contrast to $\mathbb{R}$), which was not obvious to me before. Just curious -- how did this question originally come up? – Adam Bjorndahl Sep 9 '11 at 2:51
I was analyzing some results in intuitionistic analysis. Some were perplexing: I could prove the existence of the finite set of all solutions but I couldn't always prove the existence of a single solution. It turns out the problem boils down to the existence or non-existence of continuous selectors for finite sets... – François G. Dorais Sep 9 '11 at 13:52