まず, \(E\) が外延的で整礎的であることをいう. 自然数 \(m_0\) と \(m_1\) について \[ \forall n\big(\,nEm_0\,\leftrightarrow\,nEm_1\,\big) \] が成立しているなら, \(m_0\) と \(m_1\) の二進数展開が一致するから \(m_0=m_1\) である. これは関係 \(E\) が外延的であることを意味する. 次に, \(nEm\) のときは \(2^n\leq m\) であることから \(n < m\) となることに注意しよう. このことから, どの \(m\) についても \(\{\,n\,:\,nEm\,\}\) は有限集合であることがわかる. また, \(\omega\) の空でない部分集合 \(S\) が与えられたとき, 通常の大小関係の意味で \(S\) の最小要素をとれば, それが \(E\) の意味で \(S\) の極小要素であることもわかる. こうして, \(E\) は集合 \(\omega\) において整礎的である.
モストフスキの収縮定理(→定理5.14)により, 関係 \(E\) にかんして再帰的に定義された関数(→定理5.6) \[ G(m)=\big\{\,G(n)\,:\,nEm\,\big\}\qquad(m\in \omega) \] は, \(\langle \omega,{E}\rangle\) と \(\langle G{“}\omega,{\in}\rangle\) の間の同型写像である. そこで, あとは \(G\) が \(R(\omega)\) の上への写像であることを示せばよい.
いま, \(nEm\) となるすべての \(n\) について \(\mathrm{rank}(G(n))\leq n\) であったと仮定すれば, \[ \mathrm{rank}(G(m))=\sup\{\,\mathrm{rank}(G(n))+1\,:\,nEm\,\}\leq \max\{\,n+1\,:\,nEm\,\}\leq m \] となる. よって帰納法によりすべての \(m\) で \(\mathrm{rank}(G(m))\leq m<\omega\) であり, \(G{“}\omega\subset R(\omega)\) である.
今度は \(x\in R(\omega)\) で, \(x\) のどの要素も \(G\) の値域に属すると仮定する. つまり \(x\subset G{“}\omega\) だったと仮定する. このとき, \(x\) が有限集合であることから, \[ x = \{\,G(n_0),G(n_1),\ldots,G(n_{k-1})\,\},\quad n_0 < n_1 < \cdots < n_{k-1} < \omega \] となるように \(n_0\),\(n_1\),…,\(n_{k-1}\) をとることができる. そこで \(m=2^{n_0}+2^{n_1}+\cdots+2^{n_{k-1}}\) とおけば \(G(m)=x\) となり \(x\) もまた \(G\) の値域に属する. このことから, \(R(\omega)\) 上の整礎的関係 \(\in\) にかんする帰納法により, \(R(\omega)\subset G{“}\omega\) となる.