Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.