# Applying the axiom of choice in the open mapping theorem

I am studying the book by Brézis on functional analysis and I just read the open mapping theorem. The proof is split in two steps. Here is a copy of the step 2:

I understood the idea of the proof. My problem is formalizing it. I was trying to deduce the existence of the sequence $(z_n)$, and its properties, possibly using recursion, induction and choice. I just asked a similar question about the Baire theorem and it was suggested to me to apply the axiom of dependent choice (DC).

The theorems I have are

Thm. 1 (Recursion): Let $A$ be a set, $a \in A \$ and $\ f:A \to A \$ be a function. Then there exists an unique sequence $\ b = (b_n): \mathbb{N} \to A \$ such that $\ b_0=a \$ and $\ b_{n+1} = f(b_n)$, $\forall n \in \mathbb{N}$.

Thm. 2 (Induction): Let $\ K \subset \mathbb{N} \$ be such that $\ 0 \in K \$ and, $\forall n \in \mathbb{N}$, if $\ n \in K$, then $\ n+1 \in K$. Then $\ K= \mathbb{N}$.

Together with some version of the axiom of choice or DC. This time I am allowed to use DC.

I tryed to define a relation like that in the answer to my last question but I failed because the (n+1)-th choice depends not only on the n-th choice but on all the previous entries. I need hints to find this relation or to try another approach. Any help is appreciated. Thanks in advance.

• The other answer was erased. It was wrong? Do I really need CC, DC or AC to find this sequence? – Gustavo Oct 21 '16 at 19:07

If you want to formalize the application of $\sf DC$ in this proof, then you first need to truly understand what $\sf DC$ means, and more specifically, how it is different than just choosing from a countable family of non-empty sets (countable choice).

The main difference is hinted in the name. Dependent Choice. The idea is that each choice you make will be influenced by previous choices, for example, if you have two possible choices for $z_1$, and $\|z_1-z_1'\|>\frac14$, then this means that choosing $z_2$ depends on whether you chose $z_1$ or $z_1'$.

This, in contrast to countable choice, which just tells you to choose without any constraints from a countable family of non-empty sets.

So, back to your question. How do we formalize this? Note that the choice, when applying $\sf DC$, is of the following form: Given a "valid" finite sequence $\langle z_1,\ldots,z_n\rangle$, there is some $z$ such that $\langle z_1,\ldots,z_n,z\rangle$ is also "valid", then there is a function $f\colon\Bbb N\to Z$, such that for every $n$, $f\restriction\{1,\ldots,n\}$ is a "valid" sequence.

(Here "valid" is whatever type of object that you're looking for.)

So all you need to do is argue why when given a sequence of $z_1,\ldots,z_n$ which satisfy the conditions, you can find an extension by some arbitrary vector. Then you can apply $\sf DC$.

If you want to use the axiom of choice in full, which does make this slightly clearer (as it imbues the proof of $\sf DC$ from $\sf AC$), simply fix for every finite "valid" sequence of vectors the set of possible extensions by a single vector, then show these are non-empty, and then fix a choice function.

Now by recursion, choose using this choice function. But instead of considering a function $f\colon E\to E$, here you consider a $A$ to be the set of all finite "valid" sequences, and you consider this choice function as a function from $A$ to itself.

${\LARGE [1]} \quad$ Let $$X = \left\{ (u^1,...,u^n) \in \bigcup_{j=1}^{\infty} E^j \ \ : \ \ \Bigg\lVert y - T \left( \sum_{j=1}^n u^j \right) \Bigg\Vert_F < \frac{c}{2^n} \right\} \ .$$ By (12) we have that $\ z_1 \in X \ \Rightarrow \ X \neq \varnothing$.

${\LARGE [2]} \quad$ Define a relation $\ R \subset X \times X \$ such that $\ (u^1,...,u^n)R(v^1,...,v^m) \$ if, and only if, $$m=n+1 \ , \quad (u^1,...,u^n)=(v^1,...,v^n) \ , \quad \displaystyle \Vert v^m \Vert_E < \frac{1}{2^m}$$ and $$\Bigg\lVert y - T \left( \sum_{j=1}^n u^j \right) - T(v^m) \Bigg\Vert_F < \frac{c}{2^m} \ \ .$$ The construction above shows that $\ z_1Rz_2 \$.

${\LARGE [3]} \quad$ Let $\ u=(u^1,...,u^n) \in X \$ and $\ \displaystyle w = 2^{n+1} \cdot \left[ y - T \left( \sum_{j=1}^n u^j \right) \right]$. Then $$\lVert w \rVert_F = 2^{n+1} \cdot \Bigg\lVert y - T \left( \sum_{j=1}^n u^j \right) \Bigg\Vert_F < 2^{n+1} \cdot \frac{c}{2^n} = 2c \ \Rightarrow \ w \in B_F (0_F,2c) \subset \overline{T[B_E(0_E,1)]} \ .$$ Therefore $\ B_F \left( w, \frac{c}{2^{n+1}} \right) \cap T[B_E(0_E,1)] \neq \varnothing$. Thus there exists $\ z \in B_E(0_E,1) \$ such that $\ T(z) \in B_F \left( w, \frac{c}{2^{n+1}} \right)$. Hence $\ \lVert z \rVert_E <1 \$ and $\ \lVert w - T(z) \rVert_F < \frac{c}{2^{n+1}} \$. Let $$\xi = \frac{1}{2^{n+1}} \cdot z \ .$$ Then $\ \lVert \xi \rVert_E < \frac{1}{2^{n+1}} \$ and $$\Bigg\lVert y - T \left( \sum_{j=1}^n u^j \right) - T(\xi) \Bigg\rVert_F = \Bigg\lVert \left( \frac{1}{2^{n+1}} \cdot w \right) - T \left( \frac{1}{2^{n+1}} \cdot z \right) \Bigg\rVert_F =$$ $$= \frac{1}{2^{n+1}} \cdot \lVert w - T(z) \rVert_F < \frac{1}{2^{n+1}} \cdot \frac{c}{2^{n+1}} < \frac{c}{2^{n+1}} \ .$$ So, $(u^1,...,u^n,\xi) \in X \$ and $\ (u^1,...,u^n)R(u^1,...,u^n,\xi) \ \Rightarrow \ u=(u^1,...,u^n) \in dom(R)$. We conclude that $\ dom(R)=X$.

${\LARGE [4]} \quad$ By DC, there exists $\ (\alpha_n)_{n \in \mathbb{N}^*} \in X^{\mathbb{N}^*} \$ such that $\ \alpha_1 = z_1 \$ and $\ \alpha_n R \alpha_{n+1} \$, $\forall n \in \mathbb{N}^*$.

Let $\ K = \big\{ k \in \mathbb{N}^* : \alpha_k \in E^k \big\}$. Then $\ \alpha_1 = z_1 \in E = E^1 \ \Rightarrow \ 1 \in K$. Let $\ k \in K$. Then $\ \alpha_k \in E^k \$, say $\ \alpha_k = \big( \alpha_k^1 , ... , \alpha_k^k \big)$. We have $\ \alpha_k R \alpha_{k+1} \$, with $\ \displaystyle \alpha_{k+1} \in X \subset \bigcup_{j=1}^{\infty} E^j \$. So, there exists $\ j \in \mathbb{N}^* \$ such that $\ \alpha_{k+1} \in E^j \$, say $\ \alpha_{k+1} = \big( \alpha_{k+1}^1 , ... , \alpha_{k+1}^j \big)$. Therefore $\ \big( \alpha_k^1 , ... , \alpha_k^k \big) R \big( \alpha_{k+1}^1 , ... , \alpha_{k+1}^j \big) \ \Rightarrow \ j=k+1 \ \Rightarrow \alpha_{k+1} \in E^{k+1} \ \Rightarrow \ k+1 \in K$. By induction, $K= \mathbb{N}^*$, ie, $\alpha_n \in E^n \$, $\forall n \in \mathbb{N}^*$. We write $\ \alpha_n = \big( \alpha_n^1, \alpha_n^2,..., \alpha_n^{n-1},\alpha_n^n \big)$, $\forall n \in \mathbb{N}^*$.

${\LARGE [5]} \quad$ For each $\ n \in \mathbb{N}^* \$ and each $\ j \in \{ 1,...,n \}$, let $\ \pi_n^j : E^n \to E \$ be the projection onto the $j$-th coordinate of $E^n$, ie, $\pi_n^j (u^1,...,u^n) = u^j$, $\forall (u^1,...,u^n) \in E^n$. For each $\ n \in \mathbb{N^*}$, let $$z_n = \pi_n^n (\alpha_n) = \pi_n^n \big( \alpha_n^1 , ... , \alpha_n^n \big) = \alpha_n^n \ .$$ Note that this notation is coherent with $\ \alpha_1 = \alpha_1^1 = z_1 \$ chosen above. We will show that the sequence $\ (z_n)_{n \in \mathbb{N}^*} = (\alpha_n^n)_{n \in \mathbb{N}^*} \in E^{\mathbb{N}^*} \$ is the desired one.

${\LARGE [6]} \quad$ First let $\ L = \{ \ell \in \mathbb{N}^* : \alpha_{\ell} = (z_1 , ... , z_{\ell}) \}$. By the last paragraph, $1 \in L$. Let $\ \ell \in L$. Then $\ \alpha_{\ell} = (z_1 , ... , z_{\ell})$. We have $\ \alpha_{\ell +1} = \big( \alpha_{\ell +1}^1 , ... , \alpha_{\ell +1}^{\ell} , \alpha_{\ell +1}^{\ell +1} \big)$, with $\ \alpha_{\ell} R \alpha_{\ell +1} \$, that is, $(z_1 , ... , z_{\ell}) R \big( \alpha_{\ell +1}^1 , ... , \alpha_{\ell +1}^{\ell} , \alpha_{\ell +1}^{\ell +1} \big) \ \Rightarrow \ (z_1 , ... , z_{\ell}) = \big( \alpha_{\ell +1}^1 , ... , \alpha_{\ell +1}^{\ell} \big) \$ and, by definition, $z_{\ell +1} = \alpha_{\ell +1}^{\ell +1} \ .$ So, $\ \alpha_{\ell +1} = (z_1 , ... , z_{\ell} , z_{\ell +1}) \ \Rightarrow \ \ell +1 \in L$. By induction, $L = \mathbb{N}^*$, ie, $\alpha_n = (z_1 , ... , z_n)$, $\forall n \in \mathbb{N}^*$.

${\LARGE [7]} \quad$ Now let $$K = \left\{ k \in \mathbb{N}^* \ : \ \lVert z_k \rVert_E < \frac{1}{2^k} \ \text{ and } \ \Bigg\lVert y - T \left( \sum_{j = 1}^{k} z_j \right) \Bigg\rVert_F < \frac{c}{2^k} \right\} \ .$$ By Brézis above, we have that $\ \lVert z_1 \rVert_E < \frac{1}{2} = \frac{1}{2^1} \$ and $\ \Bigg\lVert y- T \left( \sum_{j=1}^{1} z_j \right) \Bigg\rVert_F = \lVert y - T(z_1) \rVert_F < \frac{c}{2} = \frac{c}{2^1} \$. Wich implies $\ 1 \in K$. Let $\ k \in K$. Then $\ \lVert z_k \rVert_E < \frac{1}{2^k} \$ and $\ \Bigg\lVert y - T \left( \sum_{j = 1}^{k} z_j \right) \Bigg\rVert_F < \frac{c}{2^k} \ .$ By $[4]$ and $[6]$ we have $\ \alpha_k R \alpha_{k+1} \$, $\alpha_k = (z_1 , ... , z_k) \$ and $\ \alpha_{k+1} = (z_1 , ... , z_k , z_{k+1})$. So, by $[2]$, $(z_1 , ... , z_k) R (z_1 , ... , z_k , z_{k+1}) \ \Rightarrow \ \lVert z_{k+1} \rVert_E < \frac{1}{2^{k+1}} \$ and $$\Bigg\lVert y - T \left( \sum_{j = 1}^{k+1} z_j \right) \Bigg\rVert_F = \Bigg\lVert y - T \left( \sum_{j = 1}^{k} z_j \right) - T(z_{k+1}) \Bigg\rVert_F < \frac{c}{2^{k+1}} \ .$$ Hence $\ k+1 \in K$. By induction, $K = \mathbb{N}^*$, ie, the sequence $\ (z_n)_{n \in \mathbb{N}^*} \in E^{\mathbb{N}^*} \$ is such that $$\lVert z_{n} \rVert_E < \frac{1}{2^{n}} \qquad \text{ and } \qquad \Bigg\lVert y - T \left( \sum_{j = 1}^{n} z_j \right) \Bigg\rVert_F < \frac{c}{2^{n}} \ ,$$ forall $\ n \in \mathbb{N}^*$.

• @Asaf Karagila, is my proof correct? – Gustavo Oct 24 '16 at 0:51
• I didn't check the functional theoretic part, but the appeal to DC seems okay after a cursory glance. (I'm sorry, I don't have time to read through the details right now...) – Asaf Karagila Oct 24 '16 at 15:07