Existence of a certain subset of $\mathbb{R}$

Question

To every real $x$ assign a finite set $\mathcal{A}(x)\subset \mathbb{R}$ where $x\not\in \mathcal{A}(x)$. Does there exist $\mathcal{W}\subset \mathbb{R}$ such that:

$$1.\;\;\mathcal{W}\cap \mathcal{A}(\mathcal{W})=\varnothing\qquad 2.\;\;|\mathcal{W}|=|\mathbb{R}|$$

This interesting problem was given to me by a friend, but I can't do it. Any ideas?

Answer 1

Let $\mathcal{Q}=\{[p,q]:\;p,q\in\mathbb{Q},\;p<q\}$. $\mathbb{Q}$ dense in $\mathbb{R}$ and $\mathcal{A}$ finite $\Rightarrow$ we may choose $\phi:\;\mathbb{R}\to\mathcal{Q}:$ $$(\text{i}):\;\;x\in\phi(x)\qquad (\text{ii}):\;\;\phi(x)\cap\mathcal{A}(x)=\varnothing$$ Since $|\mathcal{Q}|=|\mathbb{N}|$ there exists $I\in\mathcal{Q}$ such that $\text{card}\,\{x\in\mathbb{R}:\;\phi(x)=I\}=\mathfrak{c}\;(\Leftarrow$ König's th.$)$. Let $\mathcal{W}=\{x\in\mathbb{R}:\;\phi(x)=I\}$ and check $\mathcal{W}\cap\mathcal{A}(\mathcal{W})=\varnothing\;(\Leftarrow\mathcal{W}\subset I$ and $I\cap \mathcal{A}(\mathcal{W})=\varnothing)$

Answer 2

The following approach uses not only the Axiom of Choice (in the fomr of Zorn's lemma), but also the OCntinuum Hypothesis - and I am somewhat shocked that I cannot get rid of the latter:

Call $W$ nice if $W\cap \mathcal A(W)=\emptyset$. The nice subsets are inductively ordered (cf. answer by Patrick da Silva). For any subset $T\subseteq \mathbb R$ with $T\approx \mathbb R$, define $$ \begin{align}\mathcal A_T(x)&=\mathcal A(x)\cap T\\ \mathcal B_T(x) &= \mathcal A_T(x)\cup\{\,y\in T\mid x\in\mathcal A_T(y)\,\}\\ S_T&= \{\,x\in T\mid \mathcal B_T(x)\text{ uncountable}\,\}. \end{align}$$ Clearly, a subset $W$ of $T$ is nice if and only if $W\cap \mathcal A_T(W)=\emptyset$. Note that $\mathcal B_T(x)$ is the set of elements that are "forbidden" to add to a nice subset of $T$ that already contains $x$, that is if $W$ is nice and $y\notin W$, then $W\cap \{y\}$ is nice iff $y\notin\bigcup_{x\in W}\mathcal B(x)$.

If $S_T\ne T$, Zorn's lemma implies that there exists a maximal nice subset $M_T$ of $T\setminus S_T$. If $M_T\approx \mathbb R$, we are done. So assume $|M_T|<|\mathbb R|$. Then $\bigcup_{x\in M_T} \mathcal B_T(x)$ is the union of $M_T$-many countable sets, hence has cardinality $<|\mathbb R|$. Any element of $T\setminus S_T\setminus M_T$ could be added to $M_T$ without harm, so by maximality $T\setminus S_T\subseteq \bigcup_{x\in M_T} \mathcal B_T(x)$, i.e. $S_T$ differs from $T$ only by a smaller set. So $S_T\approx T\approx \mathbb R$.

Result: We may assume wlog. that $S_T\approx\mathbb R$ for all $T\subseteq \mathbb R$ with $T\approx \mathbb R$.

Now since $$S_{\mathbb R}=\bigcup_{n\in\mathbb N}\{\,x\in S_{\mathbb R}\mid n\ge |\mathcal A(x)| \,\},$$ there must exist $n\in\mathbb N$ with $\{\,x\in S_{\mathbb R}\mid n\ge |\mathcal A(x)| \,\}\approx\mathbb R$. Thus we can let $N\in\mathbb N$ be minimal with the property that there exists $T\subseteq S_{\mathbb R}$ with $T\approx \mathbb R$ and $|\mathcal A_T(x)|\le N$ for all $x\in T$. By our result, $S_T\approx\mathbb R$. Pick $x\in S_T$ and let $U=\{\,y\in T\mid x\in \mathcal A_T(y)\,\}$. Then $U$ is an uncountable subset of $S_{\mathbb R}$ and $|\mathcal A_U(y)|\le N-1$ for all $y\in U$. By the Continuum Hypothesis, $U\approx \mathbb R$ and we obtain a contradiction to the minimality of $N$.

Answer 3

Define the "conflict range" of $x$ to be $d(x)=\min\{|x-y| : y\in \cal{A}(x)\}$. That is, $d(x)$ measures the distance from $x$ to its (finite) set of conflicts; note that $d(x)>0$ for each $x$. Choose a distance $\Delta>0$ such that there are uncountably many $x$ with $d(x) > \Delta$. For instance, since$$d^{-1}((1,\infty)) \cup \bigcup_{k=0}^{\infty}d^{-1}\left((2^{-(k+1)},2^{-k}]\right)= \mathbb{R},$$ at least one of the sets in the union is uncountable, and we can choose $\Delta$ to be the lower endpoint of its argument. Now let ${\cal{D}}=d^{-1}\left((\Delta,\infty)\right)$, and note that $$ \bigcup_{k=-\infty}^{\infty}{\cal{D}}\cap(k\Delta, (k+1)\Delta]={\cal D}. $$ Each of the sets ${\cal{D}}\cap(k\Delta,(k+1)\Delta]$ is conflict-free by construction (its diameter is less than any of its elements' conflict ranges), and at least one of them must be uncountable (since their union is uncountable). That set satisfies the conditions of the problem. $\square$