Let $\mathcal{M}$ be an infinite L structure, where $L$ is countable language. I want to show that there are $\aleph_0$ many 0-definable sets in $\mathcal{M}$.
Attempt:
Proceed by induction on the formula $\phi$:
Define $\mathcal{D}= \{ A \subseteq M^n : \mathcal{M} \models \phi(a), \forall a \in A\}$
Base case :
$\phi$ is an atomic formula.
Suppose $\phi$ is $(t_2=t_2)$ for some $L$-terms $t_1(x), t_2(x)$.
Then $\mathcal{M} \models \phi(a)$ iff $t_1^{\mathcal{M}}(a)=t_2^{\mathcal{M}}(a)$ for $a=(a_1, \cdots, a_n) \in M^n$.
Suppose $t_1$ is the coordinate projection.
Then $t_1^{\mathcal{M}}(a)=a_i=t_2^{\mathcal{M}}(a)$ for $i=1, \cdots, n$.
So $A=\{$ a countable set in $M^n \}$.
$\mathcal{D}= \{$ the set of all countable sets $\}$...
But this is not what we wanted to show, since we want to show $|\mathcal{D}|= \aleph_0$.
Suppose $t_1$ is a constant symbol. Then since $L$ is countable by assumption, we have that $|\mathcal{D}|$ is countable.
But in the case of having finitely many constants symbols, we could also have $\mathcal{D}=$ finite..
So I'm not sure what I did wrong here.
Similarly, we also have the case $t_1$ is a function symbol, which we could also get $\mathcal{D}=$ finite.
And for the atomic formula base case, we also have that $\phi$ being a m-ary relation symbol, which I have the same problems.
Could someone please let me know what I did wrong, and how should I fix the proof?
Any ideas or hints will be appreciated!
Thanks!