Proving that unary predicates theory has no $T$-complete formulas

140 Views Asked by At

As a follow up to my previous question, as suggested in the comments, I would like to know a way how to prove that the theory of infinitely many unary predicates, is axiomatized by the sentences $\sigma_{F, G}$ (for $F, G$ disjoint finite subsets of $\mathbb{N}$) given by $\exists x\left(\bigwedge_{j \in F} U_{j}(x) \wedge \wedge_{j \in G} \neg U_{j}(x)\right)$ has no principal types. I know that the way to show it is through showing that no formula in $\mathcal{L}$ is $T$-complete.

To clarify, by theory of infinitely many unary predicates, I mean the language with unary predicate symbols $\left(U_{n}: n \geq 1\right)$. and $T$ a theory $\operatorname{Th}(\mathcal{M})$ where $\mathcal{M}$ is the following structure: take $\mathcal{M}=\mathcal{P}(\mathbb{N})$ and define the interpretation of each $U_{n}$ by taking $U_{n}^{\mathcal{M}}(\alpha) \leftrightarrow n \in \alpha$ for each $\alpha \subseteq \mathbb{N}$.

I am using defnitions as in thew original question:

Definitions

Take a satisfiable set of $L$-sentences $\Sigma$ and variables $x = x_1, \ldots, x_n$. Denote by $S_x(\Sigma)$ the set of all $\Sigma$-realizable $x$-types in $L$.

A type $p(x) \in S_x(\Sigma)$ is principal if it contains a $\Sigma$-complete formula. Equivalently, the singleton $\{p(x)\}$ is an open set in $S_x(\Sigma)$, or principal $x$-types are exactly the isolated points of $S_x(\Sigma)$.

The source of this example is lecture notes by Henson.

1

There are 1 best solutions below

0
On

Think about reducts. For each finite set $X\subseteq\mathbb{N}$ (really, every finite sublanguage of $L$) and each $a,b\in\mathcal{M}$, write $a\sim_Xb$ iff $$\{n\in X: U_n(a)\}=\{n\in X: U_n(b)\}.$$ Now you can show that the following holds:

Suppose $\varphi$ is an $L$-formula only using symbols $U_i$ for $i\in X$, and $a\sim_Xb$. Then $\mathcal{M}\models \varphi(a)\leftrightarrow\varphi(b)$.

This has nothing to do with unary predicates, it's a more general feature of arbitrary "filterings" of languages.


Now here's the key point about $\mathcal{M}$: for every finite $X\subseteq\mathbb{N}$ there are $a,b\in\mathcal{M}$ with $tp(a)\not=tp(b)$ but $a\sim_Xb$. For example, pick any $a$ whatsoever and let $b=a\Delta\{\max(X)+1\}.$ This lets us wrap things up as follows:

For each formula $\varphi$, let $a,b$ be elements of $\mathcal{M}$ with distinct types but which are $\sim_{X_\varphi}$-equivalent.