[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*}[/step]

[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: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*}[/step]

[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: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.[/step]

[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]