3
$\begingroup$

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

  • 0
    There are more than countably many, if the model is large. But still not enough.2011-08-21

2 Answers 2

4

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.

2

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.