Let $\mathcal L=\{\cdot,e\}$ be the language of monoids so that $\cdot$ represents an operation which is closed and associative, and $e$ represents an identity. Consider the structure of natural numbers on this language. I have proved that every singleton $\{n\}\subseteq \Bbb N$ is definable in this language.
I'm now trying to determine whether every subset of $\Bbb N$ is definable. At the very least it seems like every subset should be fixed by any automorphism. In fact, the only automorphism that I can think of is the identity automorphism. Clearly 0 cannot map to anything other than 0, and if 1 maps to anything other than 1, then in order for the map to be a bijection some other element must map to 1, and therefore these two numbers permute. If this is an automorphism then the singletons of these two numbers permute, which I've shown they can't since they're definable. I think the same argument should also hold for any two positive numbers.
On the other hand, (1) while we know that if a set is definable then it is fixed by every automorphism, the converse is not true. So we cannot infer that every set is definable from the above argument. (2) It kind of feels like a set which is neither finite nor cofinite should be undefinable. For instance, the evens seems like a good candidate for being undefinable. However, the main tool for proving that it is undefinable (finding an automorphism which does not fix it) does not seem to work. Or at least, I'm not seeing which automorphism one could use.
The set of formulas is countable. The powerset of $\Bbb N$ is not.