Let $G: \mathbb{R} \rightrightarrows \mathbb{R}$ be a correspondence such that $G(x) \neq \emptyset$ for all $x \in \mathbb{R}$. Is the set:
\begin{equation} S(x_{0}) := \{(x_{1},...) \in \mathbb{R}^{\mathbb{N}}: x_{1} \in G(x_{0}) ~and~ x_{n+1} \in G(x_{n}) ~for ~all~ n \in \mathbb{N}\} \end{equation}
nonempty for all $x_{0} \in \mathbb{R}$? It's 'obvious' that it is but I have not been able to come up with a proof which I would like to have. Any suggestions?
On
Perhaps the simplest proof uses the axiom of choice in the form "Every relation has a subset that is (the graph of) a function with the same domain as the relation." Apply this to the relation $G$ in the question to get a function $F:\mathbb R\to\mathbb R$. Then define the desired sequence inductively, starting with the prescribed $x_0$ and continuing with $x_{n+1}=F(x_n)$ for all $n$.
$1.$ We can get a proof of your statement by Zorn's Lemma. Suppose that $x_0 \in \mathbb{R}$. Consider the following set: $$X:=\{x_{ - } \colon A \to \mathbb{R} : A=\mathbb{N} \text{ or } A = \{1,...n \} \text{ for some } n \in \mathbb{N} \text{ such that } n\geq 1 \text{ and it is the case that } x_1 \in G(x_0), x_2 \in G(x_1), ... \} $$ with the inclusion of maps (i.e. $g \subset f$ if and only if $f$ extends $g$). With $x_i$ we mean the image of $i \in \mathbb{N}$ such that $i \geq 1$ through the map $x_{-}$. Then $X$ is a poset and of course it is not the empty set: we can pick $x_1 \in G(x_0)\neq \emptyset$ and consider the only map $\{1\} \to \{x_1\}$: this is an element of $X$.
Now we need to prove that every chain of $X$ has an upper bound: let $Y \subset X$ be a chain (i.e. $Y$ is totally ordered by the inclusion of maps). Then the union $y_{-}$ of the elements of $Y$ is still a map and its domain is $\mathbb{N}$ or $\{1,...n\}$ for some $n \in \mathbb{N}$ such that $n \geq 1$. It is the case that $y_1 \in G(x_0)$, $y_2 \in G(y_1)$, ... since the elements of $Y$ satisfy that property. Then $y_{-} \in X$ and, since every element of $Y$ is contained in $y_{-}$, we conclude that $y_{-}$ is an upper bound of $Y$.
We are in the hypothesis of Zorn's Lemma. Then there exists $x_{-} \in X$ such that $x_{-}$ is a maximal element (i.e. an element of $X$ that contains $x_{-}$ and that is different from $x_{-}$ does not exist). Of course the domain of $x_{-}$ is $\mathbb{N}$. In fact, if it were not $\mathbb{N}$, then it would be $\{1,...,n\}$ for some $n \in \mathbb{N}$ such that $n \geq 1$. Then, being $G(x_n) \neq \emptyset$, we could pick $x_{n+1} \in G(x_n)$ and extend $x_{-}$ to a map whose domain would be $\{1,...,n+1 \}$. That new map would be an element of $X$ that extends $x_{-}$ and that is different from $x_{-}$: it cannot exist, since $x_{-}$ is maximal!
Then the domain of $x_{-}$ must be $\mathbb{N}$, as we said. Since $x_{-} \in X$, it is the case that $x_1 \in G(x_0)$, $x_2 \in G(x_1)$,... . Then $(x_1,x_2,...) \in S(x_0)$.
$2.$ Another proof is the following (we will use the symbol $\mathbb{N}$ meaning the set $\mathbb{N} \diagdown \{ 0 \}$):
Fixed $x_0 \in \mathbb{R}$, suppose that there is a family $ \{ x_{-}^n \colon \{1,...,n \} \to \mathbb{R} \}_{n \in \mathbb{N}}$ such that the following property holds: for every $n \in \mathbb{N}$, it is the case that:
for every $i \in \{1,...,n\}$, it is the case that $x_i^n \in G(x_{i-1}^n)$ (where $x_0^n:=x_0$ for every $n \in \mathbb{N}$);
for every $k \in \{1,...,n-1\}$, it is the case that $x_{-}^n \supset x_{-}^{k}$.
Then define $x_{-}:=\cup \{ x_{-}^n \}_{n \in \mathbb{N}}$. Notice that $x_{-}$ is still a map, because of 2, and its domain is $\cup\{ \{1,...,n\} \}_{n \in \mathbb{N}} =\mathbb{N}$. Since 1 holds it is the case that $x_i \in G(x_{i-1})$, for every $i \in \mathbb{N}$. Then $(x_1,x_2,...) \in S(x_0)$.
We are done if such a family exists: to define it we only need the Principle of Mathematical Induction. At first we define $x_{-}^1$ by choosing an element of $G(x_0)$. Then, supposing that $x_{-}^n$ exists for $n \in \mathbb{N}$, we define $x_{-}^{n+1}$ by choosing an element of $G(x_n^n)$ and extending $x_{-}^n$ with that element.