3
$\begingroup$

Let ${\cal E}$ denote the collection of open sets of $\mathbb{R}$ with respect to the Euclidean topology. It is well known that $|{\cal E}| = 2^{\aleph_0}$. Is there an injective map $f:{\cal E}\setminus \{\emptyset\} \to \mathbb{R}$ such that $f(U)\in U$ for all $U \in {\cal E}\setminus \{\emptyset\}$?

$\endgroup$
6
  • 5
    $\begingroup$ Indeed since the reals are separable (have a countable open basis, in this case open intervals with rational endpoints), it is enough to enumerate this basis, and define the map as (say) the average of the endpoints of the smallest numbered interval contained in the input set. For an injective map, well order the reals and the open sets and then pick the smallest ordered real in this basis interval not picked for any previous open set.Gerhard "But Don't Try Listing Them" Paseman, 2017.07.22. $\endgroup$ Jul 22, 2017 at 14:41
  • 1
    $\begingroup$ The interesting question here is whether choice is indeed needed. $\endgroup$ Jul 22, 2017 at 16:39
  • $\begingroup$ (And no, it is not needed, as addressed below.) $\endgroup$ Jul 22, 2017 at 16:51
  • 3
    $\begingroup$ @ChrisGerig For sufficiently concrete collections of sets, it is not unreasonable to expect that a sufficiently concrete choice function exists without having to appeal to the axiom of choice. The case at hand illustrates this. The problem is typically with "arbitrary" collections. Removing the requirement that the function is injective, the problem is trivial: You can easily describe a function that picks an element from each open subset of $\mathbb R$. The open sets are still simple enough that an explicit recipe can be given that makes the function injective. $\endgroup$ Jul 22, 2017 at 20:51
  • 1
    $\begingroup$ @ChrisGerig Many results in descriptive set theory deal with the same sort of problem: Rather than arbitrary sets, consider "simple" collections, and verify that choice functions for them can be constructed. Think of the collection of closed nonempty subsets of $\mathbb R$. Again, it is trivial to define a choice function. Now consider instead the collection of $F_\sigma$ sets. Then think of the collection of $G_\delta$ sets. With no choice (or just a small amount, such as countable choice) we can go much farther. $\endgroup$ Jul 22, 2017 at 20:57

4 Answers 4

6
$\begingroup$

Choose a well-ordering of $\cal{E}\backslash\{\emptyset\}$ with order type the initial ordinal of size $2^{\aleph_0}$. Consider injective functions $f$ from initial segments of $\cal{E}\backslash\{\emptyset\}$ to $\mathbb{R}$ satisfying $f(U)\in U$. The set of such functions is partially ordered by extension, and Zorn's lemma implies there is a maximal such function. The domain of the maximal function $f$ must by all of $\cal{E}\backslash\{\emptyset\}$, for if it weren't, there would be a smallest open set $U$ not in the domain. Now $U$ has cardinality $2^{\aleph_0}$ and the set $\{V\in\cal{E}:V\leq U\}$ has cardinality less than $2^{\aleph_0}$, so we can define $f(U)$ to be any element of $$ U\backslash\{f(V):V\leq U\}. $$

$\endgroup$
1
  • $\begingroup$ very good. For every family of sets $M$ such that $|X|\ge|M|$, the minimal (shortest) well-ordering of $M$ allows for an injection $\ f:M\to\cup M\ $ such that $\ \forall_{X\in M}\ f(X)\in X.\ $ (Frankly, this OP's question is on the level of an initial textbook on set theory, it's very far from any research question). $\endgroup$
    – Wlod AA
    May 14, 2020 at 2:08
6
$\begingroup$

Fix an injective map $h:\mathcal{E}\to\mathbf{R}/\mathbf{Q}$. Lift it to a map $g:\mathcal{E}\to\mathbf{R}$. Then for every $U\in\mathcal{E}$ there exists $r(U)\in\mathbf{Q}$ such that $f(U)=g(U)-r(U)\in U$. Then $f$ is injective, hence is a function as desired.


Addendum: this can be made without choice. To simplify I'll replace $\mathbf{Q}$ with $\mathbf{Z}[1/2]$. First, there is an explicit injection from $\mathcal{E}$ to $2^{\mathbf{Q}}$ [see edit below]. Then we use a bijection $\mathbf{Q}\to\mathbf{N}$ to get an injection $\mathcal{E}\to 2^{\mathbf{N}}$. Third, we find (below) an explicit map $g:2^{\mathbf{N}}\to\mathbf{R}$ such that the composite map $h:\mathcal{E}\to\mathbf{R}/(\mathbf{Z}[1/2])$ is injective. Then using an enumeration of $\mathbf{Z}[1/2]$, the map $f$ as above can be constructed explicitly.

Here is a construction of $g$ (using the ugly convention $\mathbf{N}=\{1,2,\dots\}$). Define $g(I)=\sum_{n\in I}3^{-n^2}$. Let us show that $h$ is injective. If $I\neq J$, then $t:=g(I)-g(J)=\sum_{n\ge 1}u_n3^{-n^2}$, where $(u_n)$ is not identically zero and takes values in $\{-1,0,1\}$. We have $0<|t|<1/2$. If $(u_n)$ is finitely supported then $t\in\mathbf{Z}[1/3]\smallsetminus\mathbf{Z}$ and hence $t\notin\mathbf{Z}[1/2]$. Otherwise, $t$ has a lacunary ternary expansion and hence is irrational. So in all cases $t\notin\mathbf{Z}[1/2]$ and hence $h$ is injective.


Edit (May '20): as user Arno told me, the map I proposed, mapping $U$ to $U\cap\mathbf{Q}$, is not injective (just take $U=\mathbf{R}$ vs the complement of an irrational singleton). Let me fix this: define $U_n=\{x\in U:d(x,U^c)> 1/n\}$. Define $\theta:\mathcal{E}\to (2^{\mathbf{Q}})^\mathbf{N}\simeq 2^{\mathbf{Q}\times\mathbf{N}}$ by $\theta(U)=(U_n\cap\mathbf{Q})_{n\in\mathbf{N}}$. I claim that $\theta$ is injective. Indeed, suppose that $U\neq V$, say there exists $x\in U\smallsetminus V$. There exists $n_0$ such that $[x-2/n_0,x+2/n_0]\subset U$. For $n\ge n_0$, there exists a rational $y$ such that $|y-x|< 1/n$. So $y\notin V_n$, while $y\in U_n$. Hence $(U_n)_{n\in\mathbf{N}}\neq (V_n)_{n\in\mathbf{N}}$.

$\endgroup$
7
  • 1
    $\begingroup$ You do not need choice when picking elements from a countable set. Instead, you are using choice when finding $g$. $\endgroup$ Jul 22, 2017 at 16:38
  • 1
    $\begingroup$ @AndrésE.Caicedo thanks, I removed reference to choice. Actually, $g$ can be consructed without choice. I'll edit. $\endgroup$
    – YCor
    Jul 22, 2017 at 16:39
  • 1
    $\begingroup$ You do not need choice to show that $|\mathbb R|\le|\mathbb R/\mathbb Q|$, which is the same as showing that such an $h$ exists. (You need choice to show that $\le$ is actually an equality.) $\endgroup$ Jul 22, 2017 at 16:41
  • 1
    $\begingroup$ Once you have an injection $\pi\!:\mathcal E\to(0,1)$, you can define $g$ as the map sending $x=\pi(U)$ to $0.(x\upharpoonright0)^\frown(x\upharpoonright1)^\frown(x\upharpoonright 2)^\frown\dots$. This doesn't use choice (and avoids the detour through $h$ and having to lift it). $\endgroup$ Jul 22, 2017 at 16:49
  • 3
    $\begingroup$ I think you have a mistake in this. You seem to claim that an open subset of $\mathbb{R}$ is determined by the rational numbers it contains. This is a tempting thought (which I fell for more than once myself), but not actually correct. One can easily built open sets containing all rational numbers of arbitrarily small positive measure. $\endgroup$
    – Arno
    May 13, 2020 at 19:35
5
$\begingroup$

We can get a rather simple such function $f$. If if we measure this in terms of descriptive set theory, we get a Baire class 1 function (we need DST for Quasi-Polish spaces here, as $\mathcal{E} = \mathcal{O}(\mathbb{R})$ is not metric). If we want to do this in a weak axiom system, then $\mathrm{ACA}_0$ would do.

Let us start by fixing some enumeration $(I_n)_{n \in \mathbb{N}}$ of the non-trivial closed intervals with rational endpoints. Now consider $\chi : \mathcal{O}(\mathbb{R}) \to 2^\mathbb{N}$ defined as $\chi(U) = \{n \in \mathbb{N} \mid I_n \subseteq U\}$.

The function $\chi$ is injective and Baire class 1 respectively definable in $\mathrm{ACA}_0$, and this is where all the complexity lies. If instead we would have chosen the type of $\chi$ as being $\chi : \mathcal{O}(\mathbb{R}) \to \mathcal{O}(\mathbb{N})$, then $\chi$ would even have been continuous.

For each interval $I_n$, we pick a finite prefix $w_n$ of a ternary expansion of a real number such that any extension of $w_n$ belongs to $I_n$. As the intervals are non-trivial, such thing always exists.

We can now built $f$ as $f(U) = (w_{\min \chi(U)}2\chi(U))_3$, ie by building the reals via their ternary expansions. This is well-defined whenever $U \neq \emptyset$. By construction of the $w_n$, we have that $f(U) \in U$. We can recover $\chi(U)$ from $f(U)$ ("look after the last 2 in the ternary expansion"), so $f$ inherits being injective from $\chi$. This part of the construction is continuous, so $f$ does not gain any complexity over $\chi$.

$\endgroup$
4
$\begingroup$

With the axiom of choice:
if $\kappa$ is an infinite cardinal, then any collection of (at most) $\kappa$ sets, each of cardinality (at least) $\kappa$, has an injective choice function. In this case $\kappa=2^{\aleph_0}$, and not only the collection of all nonempty open subsets of $\mathbb R$ but even the collection of all uncountable Borel subsets of $\mathbb R$ has an injective choice function.

Without the axiom of choice:
Construct a set $S\subset\mathbb R$ of cardinality $2^{\aleph_0}$ such that $x,y\in S,\ x\ne y\implies x-y\notin\mathbb Q$, and define an injection $h:\mathcal E\to S$. (This can all be done without choice.) Let $\mathbb Q=\{r_n:n\in\mathbb N\}$. Given $U\in\mathcal E\setminus\{\emptyset\}$, find the least $n$ such that $r_n+h(U)\in U$, and define $f(U)=r_n+h(U)$. Then $f(U)=f(V)\implies h(U)-h(V)\in\mathbb Q\implies h(U)=h(V)\implies U=V$.

P.S. Here is a simple way to construct such a set $S$. Enumerate the positive rational numbers as $\{d_n:n\in\mathbb N\}$. For $X\subseteq\mathbb R$ define $D(X)=\{x-y:x,y\in X,\ x\gt y\}$. The following construction can easily be made choice-free by using intervals with rational endpoints.

Construct a closed interval $I$ with $d_0\notin D(I)$; then construct disjoint closed intervals $I_0,I_1\subset I$ with $d_1\notin D(I_0\cup I_1)$; then construct disjoint closed intervals $I_{00},I_{01}\subset I_0$ and disjoint closed intervals $I_{10},I_{11}\subset I_1$ with $d_2\notin D(I_{00}\cup I_{01}\cup I_{10}\cup I_{11})$; and so on. The limiting set $$S=I\cap(I_0\cup I_1)\cap(I_{00}\cup I_{01}\cup I_{10}\cup I_{11})\cap\cdots$$

is a Cantor set with $D(S)\cap\mathbb Q=\emptyset$.

In a comment FrançoisG.Dorais pointed to a more general construction in an answer to the question explicit big linearly independent sets.

$\endgroup$
4
  • 1
    $\begingroup$ Such a construction is on MO: mathoverflow.net/questions/23202/… $\endgroup$ May 14, 2020 at 1:12
  • $\begingroup$ Thanks. However I wanted a less general and simpler construction, since my aim was to give a very simple answer to this question. $\endgroup$
    – bof
    May 14, 2020 at 2:03
  • $\begingroup$ @FrançoisG.Dorais Did I duplicate an existing answer? All the other answers are too complicated for me to read (very short attention span), but I wonder if one of them isn't the same as mine, just presented in the obfuscatory style people seem to like (to write, if not to read). If so, I will delete my answer. $\endgroup$
    – bof
    May 14, 2020 at 3:57
  • $\begingroup$ No problem, my comment was intended as an addition to your answer before you added your construction. Now it just gives more information for the readers. $\endgroup$ May 14, 2020 at 4:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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