レーヴェンハイム・スコーレムの定理(下方)

$M$ の可算部分集合からなる可算増加列の合併として $N$ を構成する。タルスキ・ヴォート判定法を用いる:部分集合 $N \subseteq M$(部分構造として)が初等的であるのは、すべての $\mathcal{L}$-論理式 $\psi(x, \bar{y})$ と $N$ からのすべてのタプル $\bar{a}$ について、ある $b \in M$ が $\mathcal{M} \models \psi(b, \bar{a})$ を満たすならば、すでにそのような証拠 $b \in N$ が存在するとき、かつそのときに限る。

$\mathcal{L}$ は可算なので、論理式 $\psi(x,\bar y)$ は可算個しかない。$M$ が無限なので可能な、任意の可算無限な $X_0 \subseteq M$ から始める。可算な $X_n$ が与えられたとき、各論理式 $\psi(x,\bar y)$ と $X_n$ からの各タプル $\bar a$(依然として可算個のペアのみ、$X_n$ が可算で $\mathcal{L}$ が可算だから)について、$\exists b \in M\, \mathcal{M} \models \psi(b,\bar a)$ ならば、(選択公理を用いて)そのような証拠 $b$ を一つ選び、$X_{n+1}$ を作るために追加する。これは可算個の新しい元しか追加しないので、$X_{n+1}$ は可算のままである。

$N = \bigcup_{n<\omega} X_n$ とする。可算集合の可算合併なので $N$ は可算である(また $X_0 \subseteq N$ なので無限でもある)。$N$ についてタルスキ・ヴォート判定法を確認する:$N$ からの $\psi(x,\bar y)$ と $\bar a$ が与えられたとき、$\bar a$ は有限タプルなのである一つの $X_n$ に完全に含まれる(列は増加列である)。$\psi(b, \bar a)$ を満たす証拠 $b \in M$ が存在するならば、$X_{n+1}$ の構成により、すでに証拠が選ばれ $X_{n+1} \subseteq N$ に入れられている。

タルスキ・ヴォート判定法により、$N$(誘導された $\mathcal{L}$-構造 $\mathcal{N}$ を伴う)は $\mathcal{N} \preceq \mathcal{M}$ を満たす。初等部分構造は周囲の構造とまったく同じ文を満たすので、$\mathcal{N}$ は定理を証拠立てる可算無限モデルである。