Löwenheim–Skolem Theorem (downward)

We build $N$ as the union of a countable increasing chain of countable subsets of $M$, using the Tarski–Vaught test: a subset $N \subseteq M$ (as a substructure) is elementary iff for every $\mathcal{L}$-formula $\psi(x, \bar{y})$ and every tuple $\bar{a}$ from $N$, if there is some $b \in M$ with $\mathcal{M} \models \psi(b, \bar{a})$, then there is already such a witness $b \in N$.

Since $\mathcal{L}$ is countable, there are only countably many formulas $\psi(x,\bar y)$. Start with any countably infinite $X_0 \subseteq M$ (possible since $M$ is infinite). Given a countable $X_n$, for each formula $\psi(x,\bar y)$ and each tuple $\bar a$ from $X_n$ (still only countably many pairs, since $X_n$ is countable and $\mathcal{L}$ is countable), if $\exists b \in M\, \mathcal{M} \models \psi(b,\bar a)$, choose one such witness $b$ (using the Axiom of Choice) and add it to form $X_{n+1}$; this adds only countably many new elements, so $X_{n+1}$ stays countable.

Let $N = \bigcup_{n<\omega} X_n$; a countable union of countable sets, so $N$ is countable (and infinite, since $X_0 \subseteq N$). We check the Tarski–Vaught test for $N$: given $\psi(x,\bar y)$ and $\bar a$ from $N$, since $\bar a$ is a finite tuple it lies entirely in some single $X_n$ (the chain is increasing); if a witness $b \in M$ exists for $\psi(b, \bar a)$, then by construction of $X_{n+1}$, a witness was already chosen and placed into $X_{n+1} \subseteq N$.

By the Tarski–Vaught test, $N$ (with the induced $\mathcal{L}$-structure $\mathcal{N}$) satisfies $\mathcal{N} \preceq \mathcal{M}$. Elementary substructures satisfy exactly the same sentences as the ambient structure, so $\mathcal{N}$ is a countably infinite model witnessing the theorem.