[proofplan]
We count definable subsets by counting the data that define them: a first-order formula with one distinguished object variable and finitely many parameter variables, together with a finite tuple of parameters from $M$. The language $\{\in\}$ is countable, so there are only countably many such formulas. For each fixed finite arity, the possible parameter tuples have cardinality at most $|M|$, and a countable union of sets of cardinality at most $|M|$ still has cardinality at most $|M|$ because $M$ is infinite. Since each formula-parameter pair defines at most one subset of $M$, the same bound holds for $\operatorname{Def}(\mathcal M)$.
[/proofplan]
[step:Encode every definable subset by a formula and a finite parameter tuple]
Let $\mathbb{N}_0 := \mathbb{N} \cup \{0\}$ denote the set of non-negative integers, let $\mathcal P(M) := \{A : A \subset M\}$ denote the power set of $M$, and let $\aleph_0 := |\mathbb{N}|$ denote the cardinality of the natural numbers. For a sequence of sets $(A_n)_{n \in \mathbb{N}_0}$, the notation $\bigcup_{n=0}^{\infty} A_n$ denotes the union indexed by all $n \in \mathbb{N}_0$.
For each integer $n \geq 0$, let $\Phi_n$ denote the set of [first-order formulas](/page/First-Order%20Formula) $\varphi(x,y_1,\dots,y_n)$ in the language $\{\in\}$ whose free variables are among $x,y_1,\dots,y_n$. Define the coding set
\begin{align*}
C := \bigcup_{n=0}^{\infty} \left(\Phi_n \times M^n\right),
\end{align*}
where $M^0 := \{()\}$ is the singleton set consisting of the empty tuple.
Define the map
\begin{align*}
F: C &\to \mathcal P(M) \\
(\varphi,a_1,\dots,a_n) &\mapsto \{x \in M : \mathcal M \models \varphi(x,a_1,\dots,a_n)\}.
\end{align*}
By the definition of $\operatorname{Def}(\mathcal M)$, every parameter-definable subset of $M$ is in the image of $F$. Hence
\begin{align*}
|\operatorname{Def}(\mathcal M)| \leq |C|.
\end{align*}
[guided]
Let $\mathbb{N}_0 := \mathbb{N} \cup \{0\}$ denote the set of non-negative integers, let $\mathcal P(M) := \{A : A \subset M\}$ denote the power set of $M$, and let $\aleph_0 := |\mathbb{N}|$ denote the cardinality of the natural numbers. For a sequence of sets $(A_n)_{n \in \mathbb{N}_0}$, the notation $\bigcup_{n=0}^{\infty} A_n$ denotes the union indexed by all $n \in \mathbb{N}_0$.
The definition of $\operatorname{Def}(\mathcal M)$ says that a definable subset is produced by three pieces of finite data: a natural number $n$, a [first-order formula](/page/First-Order%20Formula) with one variable $x$ reserved for the element being tested, and an $n$-tuple of parameters from $M$. We package all such data into one set.
For each $n \geq 0$, let $\Phi_n$ be the set of formulas $\varphi(x,y_1,\dots,y_n)$ in the language $\{\in\}$ whose free variables are among $x,y_1,\dots,y_n$. The parameter choices for such a formula form $M^n$. In the case $n=0$, there are no parameters, and we use the convention $M^0=\{()\}$.
Thus the full set of possible defining data is
\begin{align*}
C := \bigcup_{n=0}^{\infty} \left(\Phi_n \times M^n\right).
\end{align*}
Now define
\begin{align*}
F: C &\to \mathcal P(M) \\
(\varphi,a_1,\dots,a_n) &\mapsto \{x \in M : \mathcal M \models \varphi(x,a_1,\dots,a_n)\}.
\end{align*}
This map sends each formula together with its parameters to the subset of $M$ that it defines. Different elements of $C$ may define the same subset, so $F$ need not be injective. We only need surjectivity onto $\operatorname{Def}(\mathcal M)$: by definition, every member of $\operatorname{Def}(\mathcal M)$ arises from some formula and some finite tuple of parameters. Therefore
\begin{align*}
\operatorname{Def}(\mathcal M) \subseteq F(C),
\end{align*}
and consequently
\begin{align*}
|\operatorname{Def}(\mathcal M)| \leq |C|.
\end{align*}
[/guided]
[/step]
[step:Count formulas and parameter tuples]
The language $\{\in\}$ has finitely many non-logical symbols and countably many variables, so the set of all finite strings over its formal alphabet is countable. Every first-order formula is such a finite string; hence each $\Phi_n$ is countable. Therefore
\begin{align*}
|\Phi_n| \leq \aleph_0
\end{align*}
for every $n \geq 0$.
Let $\kappa := |M|$. Since $M$ is infinite, $\kappa \geq \aleph_0$. For each finite $n \geq 0$, the standard finite-product cardinal identity for infinite cardinals gives
\begin{align*}
|M^n| = \kappa^n \leq \kappa.
\end{align*}
Thus, for every $n \geq 0$,
\begin{align*}
|\Phi_n \times M^n|
\leq \aleph_0 \cdot \kappa
= \kappa.
\end{align*}
[guided]
We now estimate the size of each layer $\Phi_n \times M^n$.
First, the formulas are countable. The formal language $\{\in\}$ contains one non-logical binary relation symbol, the usual logical symbols, parentheses, connectives, quantifiers, and countably many variables. Thus its formal alphabet is countable. A formula is a finite string over this alphabet satisfying the recursive formation rules for first-order formulas. Since the set of all finite strings over a countable alphabet is countable, every subset of that set is countable. Hence
\begin{align*}
|\Phi_n| \leq \aleph_0
\end{align*}
for each integer $n \geq 0$.
Next, let
\begin{align*}
\kappa := |M|.
\end{align*}
The hypothesis says that $M$ is infinite, so $\kappa \geq \aleph_0$. For a fixed finite $n$, the set $M^n$ consists of finite parameter tuples $(a_1,\dots,a_n)$ from $M$. The standard cardinal arithmetic identity for infinite cardinals gives
\begin{align*}
|M^n| = \kappa^n \leq \kappa.
\end{align*}
For $n=0$, this says $|M^0|=1\leq \kappa$; for $n\geq 1$, it says that a finite tuple of elements of an infinite set carries no more cardinal information than one element of a set of the same cardinality.
Combining the count of formulas with the count of parameter tuples and using the standard [cardinal arithmetic](/page/Cardinal%20Arithmetic) identities for products of infinite cardinals gives
\begin{align*}
|\Phi_n \times M^n|
\leq |\Phi_n|\,|M^n|
\leq \aleph_0 \cdot \kappa
= \kappa.
\end{align*}
Thus each fixed-arity layer of possible defining data has cardinality at most $|M|$.
[/guided]
[/step]
[step:Take the countable union over all finite arities]
Since
\begin{align*}
C = \bigcup_{n=0}^{\infty} \left(\Phi_n \times M^n\right)
\end{align*}
and each set $\Phi_n \times M^n$ has cardinality at most $\kappa$, the countable-union estimate from [cardinal arithmetic](/page/Cardinal%20Arithmetic) for infinite cardinals gives
\begin{align*}
|C|
\leq \aleph_0 \cdot \kappa
= \kappa.
\end{align*}
Together with $|\operatorname{Def}(\mathcal M)| \leq |C|$, this yields
\begin{align*}
|\operatorname{Def}(\mathcal M)| \leq |M|.
\end{align*}
This proves the theorem.
[guided]
The coding set $C$ is the union of the fixed-arity coding sets:
\begin{align*}
C = \bigcup_{n=0}^{\infty} \left(\Phi_n \times M^n\right).
\end{align*}
We have already shown that for every $n \geq 0$,
\begin{align*}
|\Phi_n \times M^n| \leq \kappa,
\end{align*}
where $\kappa = |M|$ is infinite. The countable-union estimate from [cardinal arithmetic](/page/Cardinal%20Arithmetic) says that a countable union of sets of size at most an infinite cardinal $\kappa$ has size at most $\aleph_0 \cdot \kappa$, and cardinal arithmetic for infinite cardinals gives
\begin{align*}
\aleph_0 \cdot \kappa = \kappa.
\end{align*}
Therefore
\begin{align*}
|C|
\leq \aleph_0 \cdot \kappa
= \kappa.
\end{align*}
Finally, the previous encoding step showed that every definable subset of $M$ is obtained from some element of $C$. Thus
\begin{align*}
|\operatorname{Def}(\mathcal M)| \leq |C| \leq \kappa = |M|.
\end{align*}
This is exactly the desired bound.
[/guided]
[/step]
