4
$\begingroup$

I am trying to solve my friend's homework assignment, I got stuck at this part:

Let $\mathcal{L} = \{P^1, P^2, P^3, \cdots\}$ be language with equality, where $P^i$'s are unary predicates (relation symbols) for all $i>0$. Further, let $\mathcal{M}$ denote a $\mathcal{L}$-structure. Prove there isn't a theory $T$ satisfying $$\mathcal{M}\models T \iff \bigcap P^i_{\mathcal{M}}\ \mathrm{consists\ of\ infinitely\ many\ individuals},$$

where the subscript$_\mathcal{M}$ means interpretation of $P^i$'s.

It's been quite a while since I took logic lessons, but if I understand it correctly, we are trying to prove, in other words, that the property on RHS isn't FO expressible. I believe the right approach would be through the compactness theorem, but frakly, I don't know how to use it. (On this spot I've tried to formulate my thoughts, but in the process, I've realized they are complete rubbish)

I'm not asking for the solution right away - a good hint will do.

(BTW, this is my first SE post. I would much appreciate any suggestions and remarks concerning math, english, style, etc. This all is new for me. Sorry for molesting the english language, especially its punctuation.)

$\endgroup$
5
$\begingroup$

Hint: Pick a structure $\mathcal M$ that satisfies

  • $M = P^1_{\mathcal M} \supset P^2_{\mathcal M} \supset ...$,
  • $P^i_{\mathcal M} \setminus P^{i+1}_{\mathcal M}$ is infinite,
  • $\bigcap P^i_{\mathcal M}$ is infinite.

Let $\mathcal N$ be the substructure of $\mathcal M$ with the universe $M \setminus \bigcap P^i_{\mathcal M}$. Use Tarski-Vaught test to conclude that $N \prec M$ (for that use the fact that any formula may only mention finitely many predicate symbols). Now if the theory $T$ in question exists, then $\mathcal M \models T$ and $\mathcal N \not \models T$.

$\endgroup$
2
  • $\begingroup$ Very clever! +1 $\endgroup$ – Asaf Karagila Dec 15 '13 at 17:22
  • $\begingroup$ Thank you, Levon! It took me a while because I wasn't familiar with these notions; not even with elementary substructures. I've learned a bit. I will learn some more model theory though, as it turns out to be useful outside of its own field. $\endgroup$ – liczman Dec 16 '13 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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