Existence of a subset of infinite model that's not definable I'm working on the following problem: Show that any infinite model $\mathcal{M}$ has a subset of its domain that's not definable in $\mathcal{M}$ using parameters.
I tried to follow a contradiction proof but didn't get far. Because the language is unknown, I ruled out Tarski Undefinability of Truth and Fixed Point Lemma. It doesn't seem to have anything to do with the $\Sigma_n$ hierarchy either. Any hint on where to start?
Edit: $\mathcal{M}$ is model of a countable language
 A: The result (Ed: as first stated) is not true in general.  But first of all, we give a result along the lines of the question which is true.  (Ed: Conveniently, it answers the revised question.)
Let $L$ be a language which has a finite or denumerably infinite number of non-logical symbols, and let $T$ be a theory over $L$.
Let $M$ be a model of $T$ of cardinality $\kappa$, where $\kappa$ is infinite.
Then $M$ has $2^\kappa>\kappa$ subsets.
But there are only $\kappa$ expressions of the form $F(a_1,a_2,\dots,a_n,y)$, where $F(x_1,x_2,\dots,x_n,y)$ is a formula of the language, and the $a_i$ are (names of) elements of $M$. 
Thus there are no more than $\kappa$  subsets of $M$ that are definable using parameters. There are in fact exactly $\kappa$. We use the formula $y=x$. If $a$ is (the name of) an element of $M$, then $\{a\}$ is definable by parameters.
The analysis can be extended to uncountable languages, by putting a suitable lower bound on the cardinality of the model $M$. 
Counterexample (Ed: for the original question):   Look at the language $L$ that has a predicate symbol for every subset of $\mathbb{N}$, and let $T$ be the theory over this language whose axioms are all sentences true in $\mathbb{N}$, with the natural interpretation for each predicate symbol.  Then every subset of $\mathbb{N}$ is definable, even without parameters.  For if $P_A$ is the predicate symbol corresponding to $A \subseteq \mathbb{N}$, then the formula $P_A(y)$ defines $A$.
Admittedly, $L$  is a rather large language.  But such languages can be useful in Model Theory, for example in constructing non-standard models of analysis in which every "normal" function and relation on $\mathbb{R}$ can be automatically extended to the non-standard model.
A: To sum up Andre's great answer. This is a standard cardinality play, using two facts:


*

*For every infinite cardinal $\kappa<2^\kappa$,

*if $A$ is an infinite set then $\{B\subseteq A\big||B|<\aleph_0\}=|A|$.


Suppose $L$ is a countable language, therefore the set of formulae is countable (since every formula corresponds to a finite string over $\aleph_0$)
Now suppose the model has universe of cardinality $\kappa\ge\aleph_0$, then we have $2^\kappa>\kappa$ many subsets of the universe, in contrast every definable set corresponds to a formula and a finite set of parameters.
Therefore we have $\aleph_0\cdot\kappa=\kappa$ many definable sets in the model.
