Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $X$ be a complete & separable metric space. Let $\{E_i\}_{i\in I}$ be a collection of closed and nonempty sets in $X$.

If $X$ is just a complete metric space, it seems not possible to construct a choice function $f$ such that $f(E_i)\in E_i$, without AC.

However, since $X$ is separable, it seems possible to construct a choice function.

How do I construct a choice function $f$ such that $f(E_i)\in E_i$ without AC$_\omega$?

EDIT; Since Hagen's argument doesn't require the condition 'boundedness of $E_i$, I removed it. Also $\{E_i\}$ doesn't need to be countable, so i changed it to $\{E_i\}_{i\in I}$ where $I$ is an arbitrary set.

share|improve this question
    
To be clear: by "complete" you mean "every Cauchy sequence converges"? There are other possible definitions which are equivalent given sufficient choice, but in ZF may be different. –  Nate Eldredge Oct 8 '12 at 18:32
    
@Nate Yes, i meant "every Cauchy sequence converges". I would like to know what equivalent statements are there (in ZFC). –  Katlus Oct 8 '12 at 18:41
    
For example, "any decreasing sequence of closed sets with diameters decreasing to 0 has nonempty intersection", which Hagen's answer used. Actually, if your claim holds in ZF then this statement will be equivalent after all. –  Nate Eldredge Oct 8 '12 at 18:59
add comment

1 Answer

up vote 8 down vote accepted

Let $(x_n)_{n\in \mathbb N}$ be a dense sequence.

Given a closed non-empty set $E$, define $f(E)$ as follows:

a) If $E\cap \{x_n\mid n\in \mathbb N\}$ is non-empty, let $f(E)=x_m$ where $m=\min\{n\in\mathbb N\mid x_n\in E\}$.

b) If on the other hand $E\cap \{x_n\mid n\in \mathbb N\}=\emptyset$, define $A_0=E$, $r_0=1$ and recursively $$\tag1m_n=\min\{k\in\mathbb N\mid d(x_k,A_n)<2^{-n}\},$$ $$\tag2r_{n+1} = d(x_{m_n}, A_n),$$ $$\tag3A_{n+1}=\{a\in A_n\mid d(x_{m_n},a)\le 2r_{n+1}\}.$$ Note that we will always have $2^{1-n}\ge r_n>0$ and $E=A_0\supseteq A_1\supseteq\ldots$ is a descending chain of closed sets. Let $A=\bigcap_{n\in \mathbb N} A_n$. By completeness, $A$ is not empty. And because the diameter of $A_n$ is at most $4r_{n}\to0$, there can be at most one element in $A$. Define $f(E)$ as the only element of $A$.

Remark: Note that it is possible that no point $a\in A$ exists with $d(x,A)=d(x,a)$, but at least we have that $d(x,A)=0$ implies $x\in A$ for closed sets $A$, an dthat special case is covered in part a) so that we indeed have $r_n>0$ in part b).


Edit (after commments by Nate et. al.): The above proof used as the following definition of completeness: Every decreasing sequence of nonempty closed sets withvanishing diameter has nonempty intersection. The same construction also works with the definition Every Cauchy sequence converges.

In fact, the sequence $(y_n)_{n\in\mathbb N}$ with $y_n:=x_{m_n}$ as constructed above is Cauchy: By $(1)$ there exists $a\in A_{n+1}$ such that $d(y_{n+1},a)<2^{-(n+1)}$. On the other hand, $(3)$ and $(2)$ imply $d(y_n,a)\le 2r_{n+1}=2d(y_n,A_n)<2\cdot2^{-n}$ for this $a$. Consequently, $d(y_n,y_{n+1})<\frac5{2^{n+1}}$, which leads to $d(y_n,y_m)< \frac5{2^n}$ for $m>n$. Hence $y=\lim_{n\to\infty}y_n$ exists and from $d(y_n,E)\le d(y_n,A_n)\to 0$ we conclude $d(y,E)=0$ and by closedness $y\in E$ as required.


Edit: After a night of good sleep, the construction can be simplified (no cases, work directly with Cauchy sequences): Let $(x_n)_{n\in \mathbb N}$ be a dense sequence. Given a closed non-empty set $E$, define $f(E)$ as follows: Let $m_0=\min\{n\in \mathbb N\mid d(x_n,E)<1\}$ and $y_0=x_{m_0}$. Extend this recursively to a sequence $(y_n)_{n\in\mathbb N}$ with the properties $$\tag4d(y_n,y_{n+1})<2^{1-n}$$ and $$\tag5d(y_n,E)<2^{-n}.$$ To achieve this note that $d(y_n,E)<2^{-n}$ implies that the set $C_n=\{a\in E\mid d(y_n,a)<2^{-n}\}$ is nonempty, hence the union of open balls $U_n=\bigcup_{a\in C_n} B(a,2^{-1-n}\}$ is a nonempty open set. Let $m_{n+1}=\min\{n\in\mathbb N\mid x_n \in U_n\}$ and set $y_{n+1}=x_{m_{n+1}}$. From $y_{n+1}\in U_n$ we conclude that there exists $a\in C_n$ with $d(y_{n+1},a)<2^{-(n+1)}$. But for any such $a$ we see from $a\in C_n\subseteq E$ that $d(y_{n+1},A)<2^{-(n+1)}$ and $d(y_n,y_{n+1})\le d(y_n,a)+d(y_{n+1},a)<2^{-n}+2^{-(n+1)}<2^{1-n}$. Hence we can construct our sequence $(y_n)$ recursively such that $(1)$ and $(2)$ hold. By $(4)$ and the triangle inequality, it is a Cauchy sequence, hence has a limit $y$. From $(5)$ we conclude that $d(y,E)=0$, hence $y\in E$ because $E is closed.

share|improve this answer
    
Nice. The construction does not require choice, we rely in the countability of the dense set. –  Asaf Karagila Oct 8 '12 at 18:09
    
In your construction, how do you know $A_{n+1}$ is nonempty? Even in a complete separable metric space, given a point $x$ and a closed set $A$, there need not be any $y \in A$ with $d(x,y) = d(x,A)$. For example, let $X$ be a separable Hilbert space with orthonormal basis $\{e_n\}$ and let $A = \{ (1 + \frac{1}{n}) e_n \}$. $A$ is closed, indeed discrete, and $d(0,A) = 1$, but $d(0,y) > 1$ for every $y \in A$. –  Nate Eldredge Oct 8 '12 at 18:16
    
The unmotivated $2^{-n}$ apparently can be relaxed - but I thought I might need something with nice convergence while I wrote this. One could replace it by any zero sequence - or (I think) ignore it completely and just take the nearmost points for all $x_n$ in sequence: If $a\ne b$, then some member $x_n$ will be closer to $a$ then $\frac12d(a,b)$, hence $a$ and $b$ cannot be both in $A$. –  Hagen von Eitzen Oct 8 '12 at 18:16
    
... I think you can fix this problem by taking $A_{n+1} = \{a \in A_n \mid d(x_{m_n}, a) \le r_{n+1} + 2^{-n}\}$ or something like that. But please check me here. –  Nate Eldredge Oct 8 '12 at 18:21
    
@NateEldredge: Thanks for the hint. I hope my last edit fixed that. –  Hagen von Eitzen Oct 8 '12 at 18:24
show 9 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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