# 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

-
Depends on the language. But if language is "small" there are too many subsets. –  André Nicolas Aug 21 '11 at 7:06
Sorry, I should have mentioned that it's a countable language. What do you mean by "small"? –  nullgraph Aug 21 '11 at 7:18
Countable qualifies as small. If $\mathscr{L}$ is countable, how many formulas are there over $\mathscr{L}$, even allowing parameters? And $M$ has at least how many subsets? –  Brian M. Scott Aug 21 '11 at 7:22
Ah I get it! There are only countably many formulas over $\mathcal{L}$, even allowing parameters and $M$ has uncountably many subsets, so some of them must not be definable. –  nullgraph Aug 21 '11 at 7:29
There are more than countably many, if the model is large. But still not enough. –  André Nicolas Aug 21 '11 at 7:49

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.

-

To sum up Andre's great answer. This is a standard cardinality play, using two facts:

1. For every infinite cardinal $\kappa<2^\kappa$,
2. 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.

-