# Countable orthonormal basis for Hilbert space

If $D=\{x_n : n\in \mathbb{N}\}$ is a countable set dense in a Hilbert space $\mathcal{H}$, how can I show that Gram-Schmidt algorithm applied to $D$ (or a subset of $D$) produces an orthonormal numerable basis for $\mathcal{H}$?

So far I have been able to prove that every ortonormal basis of $\mathcal{H}$ has to be numerable.

Actually, we have a non-constructive proof.

Lemma : Let $\mathcal{H}$ be a Hilbert space. Then it is impossible that $\mathcal{H}$ has a countable dense subset $D$ and an uncountable orthonormal set $\{e_{i}\mid i\in I\}$.

Proof: Prove by contradiction. Suppose the contrary that $\mathcal{H}$ has a countable dense subset $D$ and an uncountable orthonormal set $\{e_{i}\mid i\in I\}.$ Let $r=\frac{1}{4}$ and for each $i\in I$, let $B_{i}=B(e_{i,}r)$, then open ball centered at $e_{i}$ with radius $r$. Note that $B_{i}\cap B_{j}=\emptyset$ whenever $i\neq j$. (For, if there exists $x\in B_{i}\cap B_{j}$, then $||e_{i}-e_{j}||\leq||e_{i}-x||+||x-e_{j}||<2r$. By orthonormality, $||e_{i}-e_{j}||=\sqrt{2}$, which is a contradiction.) For each $i\in I,$ further define $A_{i}=B_{i}\cap D$, which is non-empty because $D$ is dense. Now we obtain a non-empty collection of non-empty sets $\{A_{i}\mid i\in I\}$. By Axiom of Choice, there exists a function $\theta:I\rightarrow\cup_{i\in I}A_{i}$ such that $\theta(i)\in A_{i}$. Note that $\theta$ is injective because $A_{i}\cap A_{j}=\emptyset$ whenever $i\neq j$. Therefore $\mbox{Cardinality}(I)\leq\mbox{Cardinality}(\cup_{i\in I}A_{i})\leq\mbox{Cardinality}(D)$, which is a contradiction.

We are are ready to prove: Suppose that $\mathcal{H}$ is separable (i.e., $\mathcal{H}$ has a countable dense subset), then $\mathcal{H}$ has a countable orthonormal base (finite or countably infinite). By Zorn's lemma, we can find a maximal (with respect to the partial ordering $\subseteq$) orthonormal set $\{e_{i}\mid i\in I\}$. By the lemma, $I$ must be countable. Then for any $x\in\mathcal{H}$, we have $x=\sum_{i\in I}<x,e_{i}>e_{i}$, where the sum is independent of ordering. (I leave the proof to you).

/////////////////////////////////////////////////////////////

I expand the last line, state it as a theorem and give a self-contained proof. This is known as the Fourier expansion in Hilbert space.

////////////////////////////////////////////////////////////

Theorem: Let $\mathcal{H}$ be a Hilbert space (over $\mathbb{R}$ or $\mathbb{C}$) and let $\{e_{i}\mid i\in I\}$ be a maximal (with respect to $\subseteq$) orthonormal set (where the index $I$ may be uncountable). Then for each $x\in\mathcal{H}$, we have $x=\sum_{i\in I}\langle x,e_{i}\rangle e_{i}$, where the series converges in unorder sense (explained in Claim (4) below).

Proof:

Claim (1) (Bessel's inequality): For any finite subset $I_{1}\subseteq I$ and any $x\in\mathcal{H}$, $\sum_{i\in I_{1}}|\langle x,e_{i}\rangle|^{2}\leq||x||^{2}$.

Proof of Claim (1): Denote $Px=\sum_{i\in I_{1}}\langle x,e_{i}\rangle e_{i}$. Observe that $Px\bot x-Px$, so $||x||^{2}=||Px||^{2}+||x-Px||^{2}\geq||Px||^{2}=\sum_{i\in I_{1}}|\langle x,e_{i}\rangle|^{2}$.

Claim (2): For any $x\in\mathcal{H}$, $\{i\in I\mid\langle x,e_{i}\rangle\neq0\}$ is a countable set.

Proof of Claim (2): Let $I'=\{i\in I\mid\langle x,e_{i}\rangle\neq0\}$. Prove by contradiction. Suppose the contrary that $I'$ is uncountable. For each $n\in\mathbb{N}$, let $I_{n}=\{i\in I\mid|\langle x,e_{i}\rangle|\geq\frac{1}{n}\}$. Observe that $I'=\cup_{n}I_{n}$, so there exists $n$ such that $I_{n}$ is uncountable. Choose $k$ such that $\frac{k}{n^{2}}>||x||^{2}$. Choose a finite subset $I'_{n}\subseteq I_{n}$ that contains $k$ elements, then $\sum_{i\in I'_{n}}|\langle x,e_{i}\rangle|^{2}\geq\frac{k}{n^{2}}>||x||^{2}$, contradicting to claim (1).

Claim (3): Given $x\in\mathcal{H}$ and let $I_{x}=\{i\in I\mid\langle x,e_{i}\rangle\neq0\}$. Fix an enumeration for $I_{x}$, say $I_{x}=\{i_{1},i_{2},\ldots\}$ (finite or infinite), then the series $\sum_{k}\langle x,e_{i_{k}}\rangle e_{i_{k}}$ is convergent.

Proof of Claim (3): If $I_{x}$ is a finite set, we are done. Suppose that $I_{x}$ is a countably infinite set. Let $s_{n}=\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}}$. By Claim (1), for each $n$, $\sum_{k=1}^{n}|\langle x,e_{i_{k}}\rangle|^{2}\leq||x||^{2}$, so the series $\sum_{k=1}^{\infty}|\langle x,e_{i_{k}}\rangle|^{2}$ is convergent. We show that $\{s_{n}\}$ is a Cauchy sequence in $\mathcal{H}$. Let $\varepsilon>0$. Choose $N$ such that $\sum_{k=N}^{\infty}|\langle x,e_{i_{k}}\rangle|^{2}<\varepsilon^{2}$. For any $m,n\geq N$, we have (without loss of generality, assume that $m<n$): $||s_{n}-s_{m}||^{2}=||\sum_{k=m+1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}}||^{2}=\sum_{k=m+1}^{n}|\langle x,e_{i_{k}}\rangle|^{2}<\varepsilon^{2}$. That is, $||s_{m}-s_{n}||<\varepsilon$. Therefore $\sum_{k}\langle x,e_{i_{k}}\rangle e_{i_{k}}$ is convergent. We denote $y=\sum_{k}\langle x,e_{i_{k}}\rangle e_{i_{k}}$.

Claim (4): The series $\sum_{i\in I}\langle x,e_{i}\rangle e_{i}$ converges to $y$ in unorder sense, where $y$ is the element in Claim (3). More precisely, let $\mathcal{C}$ be the collection of all finite subsets of $I$. Define a binary relation $\preceq$ on $\mathcal{C}$: $I_{1}\preceq I_{2}$ iff $I_{1}\subseteq I_{2}$. Note that $\preceq$ has the properties: (i) For any $I_{0}\in\mathcal{C}$, $I_{0}\preceq I_{0}$ (reflexive), (ii) For any $I_{1},I_{2},I_{3}\in\mathcal{C}$, if $I_{1}\preceq I_{2}$ and $I_{2}\preceq I_{3}$, then $I_{1}\preceq I_{3}$ (transitive), (iii) For any $I_{1},I_{2}\in\mathcal{C}$, there exists $I_{3}\in\mathcal{C}$ such that $I_{1}\preceq I_{3}$ and $I_{2}\preceq I_{3}$. In short, $\left(\mathcal{C},\preceq\right)$ is a directed system. Define $\theta:\mathcal{C\rightarrow\mathcal{H}}$ by $\theta(I_{1})=\sum_{i\in I_{1}}\langle x,e_{i}\rangle e_{i}$, $I_{1}\in\mathcal{C}$. Then the triple $\left(\mathcal{C},\preceq,\theta\right)$ is a net in $\mathcal{H}$. We say that $\sum_{i\in I}\langle x,e_{i}\rangle e_{i}$ converges to $y$ in unorder sense iff the net $\left(\mathcal{C},\preceq,\theta\right)$ converges to $y$. That is, for each open neighborhood $U_{y}$ of $y$, there exists $I_{1}\in\mathcal{C}$ such that for any $I_{2}\in\mathcal{C}$, if $I_{1}\preceq I_{2}$, then $\theta(I_{2})\in U_{y}.$

Proof of Claim (4). Let $y$ be the element in Claim (3). Let $\varepsilon>0$ be arbitrary. Let $U_{y}=B(y,\varepsilon)$ be the open ball centered at $y$ with radius $\varepsilon$. Choose $N$ such that $||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-y||\leq\frac{\varepsilon}{4}$. (If $I_{x}$ in Claim (3) is a finite set, let $N$ be the number of elements in $I_{x}$.) We adopt the notation in Claim (3) and continue to work with the enumeration $I_{x}=\{i_{1},i_{2},\ldots\}$. Let $I_{1}=\{i_{1},i_{2},\ldots,i_{N}\}$. Clearly $I_{1}\in\mathcal{C}$. Consider the case that $I_{x}$ is an infinite set (the finite case is trivial). By continuity of norm (i.e., the continuity of the map $x\mapsto||x||$), we have $$\lim_{n}||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}}||=||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-y||\leq\frac{\varepsilon}{4}.$$ On the other hand, for any $n>N$, we have $||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}}||^{2}=\sum_{k=N+1}^{n}|\langle x,e_{i_{k}}\rangle|^{2}$. Hence $\sum_{k=N+1}^{\infty}|\langle x,e_{i_{k}}\rangle|^{2}\leq\left(\frac{\varepsilon}{4}\right)^{2}$. Let $I_{2}\in\mathcal{C}$ be arbitrary such that $I_{1}\preceq I_{2}$. Then $$||\theta(I_{2})-y||\leq||\sum_{k=1}^{N}\langle x,e_{i_{k}}\rangle e_{i_{k}}-y||+||\sum_{i\in I_{2}\setminus I_{1}}\langle x,e_{i}\rangle e_{i}||\leq\frac{\varepsilon}{4}+||\sum_{i\in I_{2}\setminus I_{1}}\langle x,e_{i}\rangle e_{i}||.$$ Observe that $$||\sum_{i\in I_{2}\setminus I_{1}}\langle x,e_{i}\rangle e_{i}||^{2}=\sum_{i\in I_{2}\setminus I_{1}}|\langle x,e_{i}\rangle|^{2}\leq\sum_{k=N+1}^{\infty}|\langle x,e_{i_{k}}\rangle|^{2}\leq\left(\frac{\varepsilon}{4}\right)^{2}$$ because for any $i\in I_{2}\setminus I_{1}$, if $i\notin\{i_{N+1},i_{N+2},\ldots\}$, then $\langle x,e_{i}\rangle=0$.

Now we have: $||\theta(I_{2})-y||\leq\frac{\varepsilon}{2}$. This shows that $\sum_{i\in I}\langle x,e_{i}\rangle e_{i}=y$ in unordered sense.

Claim (5): The $y$ defined in Claim (3) and Claim (4) is $x$. That is $x=\sum_{i\in I}\langle x,e_{i}\rangle e_{i}$.

Proof of Claim (5): Let $z=x-y$. Prove by contradiction. Suppose the contrary that $z\neq0$. We adopt the notation in Claim (3) and Claim (4). Recall that for each $a\in\mathcal{H}$, the map $x\mapsto\langle x,a\rangle$ is continuous. Let $i\in I$ be arbitrary. Conside the case that $I_{x}$ is infinite (The finite case is trivial.). We have $$\langle z,e_{i}\rangle=\lim_{n\rightarrow\infty}\langle x-\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}},e_{i}\rangle.$$ If $i\notin I_{x}$, we have $\langle x,e_{i}\rangle=0$ and $\langle e_{i_{k}},e_{i}\rangle=0$ for all $k$, and hence $\langle z,e_{i}\rangle=0$. Suppose that $i\in I_{0}$, say $i=i_{k'}$ for some $k'\in\mathbb{N}$. Then for any $n\geq k'$, we have $$\langle x-\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}},e_{i}\rangle=\langle x,e_{i}\rangle-\langle\sum_{k=1}^{n}\langle x,e_{i_{k}}\rangle e_{i_{k}},e_{i}\rangle=\langle x,e_{i_{k'}}\rangle-\langle x,e_{i_{k'}}\rangle=0.$$ Therefore $\langle z,e_{i}\rangle=0$ in all cases. Define $\tilde{z}=z/||z||$, then $\{e_{i}\mid i\in I\}\cup\{\tilde{z}\}$ is an orthonormal set, containing $\{e_{i}\mid i\in I\}$ as a proper subset. This contradicts to the maximality of $\{e_{i}\mid i\in I\}$.

We construct a sequence $\{e_{n}\}$ inductively as follows: Define $$e_{1}=\begin{cases} 0, & \mbox{ if }x_{1}=0\\ \frac{x_{1}}{||x_{1}||}, & \mbox{ if }x_{1}\neq0 \end{cases}.$$ Suppose that $e_{1},e_{2},\ldots,e_{n}$ have been defined. Define $$\tilde{e}_{n+1}=x_{n+1}-\sum_{i=1}^{n} < x_{n+1},e_{i} > e_{i}$$ and further let $$e_{n+1}=\begin{cases} 0, & \mbox{ if }\tilde{e}_{n+1}=0\\ \frac{\tilde{e}_{n+1}}{||\tilde{e}_{n+1}||}, & \mbox{ if }\tilde{e}_{n+1}\neq0 \end{cases}.$$

Claim 1: Prove by induction that $< e_{i},e_{j}>=0$ whenever $i\neq j$ and $||e_{i}||$ is either $0$ or $1$.

Claim 2: Linear span by $\{x_{n}\mid n\in\mathbb{N}\}$ is precisely linear span by $\{e_{n}\mid n\in\mathbb{N}\}$. Hence, taking closure on both sides, we conclude that the closed linear span by $\{e_{n}\mid n\in\mathbb{N}\}$ is $\mathcal{H}$.

Finally, The collection $\{e_{n}\mid e_{n}\neq0\}$ is an orthonormal base for $\mathcal{H}$.

I don't have time to write down the details of the proof. Please tell me if anything is wrong. Thank you.