A property of a set of formulas that implies that every formula is equivalent to a Boolean combination of formulas of this set.

Question

Let $A \subset M \vDash T$ and let $\Phi$ be a set of formulas in n variables with parameters in $A$. Suppose that for $p \neq q$ in $S_{n}(A)$ there is $\phi(\overline{x})$ such that $p \vdash \phi$ iff $q \vdash \neg \phi$. Then every formula $\psi$ over $A$ in $x_{1}, \ldots, x_{n}$ is equivalent to a Boolean combination of formulas in $\Phi$.

I know I have to solve this with compactness and it really should not be that hard, but I struggle to compose a satisfying solution. My ansatz was to use that the $\phi$ isolate the corresponding type, because elsewise the solution of $\phi$ that is not a solution of the type would give us a different type that implies $\phi$, which contradicts the assumption. Then I just wanted to look at all the types $q \in S_{n}(A)$ with $\psi \in q$, which are all implied by some formula in $\Phi$ and conclude with compactness, but I am not quite satisfied with the last step. Do you have any suggestions?

Answer 1

Let $\Phi'=\Phi\cup\{\neg\phi\colon\phi\in\Phi\}$. For $p\in[\psi]$ and $q\in[\neg \psi]$, by the assumption we can find $\phi_{p,q}\in\Phi'$ such that $\phi_{p,q}\in p\smallsetminus q$. For fixed $p\in[\psi]$, $\neg\psi\vdash\bigvee_{q\in[\neg\psi]}\neg\phi_{p,q}$, so by compactness among $\{\phi_{p,q}\colon q\in[\neg \psi]\}$ you can find finitely many $\{\phi_{p,i}\colon 1\leq i\leq n_p\}$ such that $\neg\psi\vdash\bigvee_{i=1}^{n_p}\neg\phi_{p,i}$. By contraposition, $\bigwedge_{i=1}^{n_p}\phi_{p,i}\vdash \psi$ and note that $\bigwedge_{i=1}^{n_p}\phi_{p,i}\in p$. Denote $\theta_p:=\bigwedge_{i=1}^{n_p}\phi_{p,i}$.

Now $\psi\vdash\bigvee_{p\in[\psi]}\theta_p$. Again by compactness we can find $p_1,\ldots,p_k\in[\psi]$ such that $\psi\vdash\bigvee_{j=1}^k\theta_{p_j}$. On the other hand, as we have seen, each $\theta_{p_j}$ implies $\psi$, hence their disjunction implies $\psi$ as well, so $\psi$ is actually equivalent to $\bigvee_{j=1}^k\theta_{p_j}$. Now recall that each $\theta_{p_j}$ is a conjunction of elements of $\Phi'$, and each element from $\Phi'$ is either itself from $\Phi$ or it is negation of an element from $\Phi$.

Answer 2

I like to think about this fact from the point of view of the topology on the type space. Recall that a basis for the usual topology on $S_n(A)$ is given by $[\psi(x)] = \{p\in S_n(A)\mid \psi(x)\in p\}$.

Let $\Phi'$ be the closure of $\Phi$ under complements. Define a topology $\tau_{\Phi'}$ on $S_n(A)$ by taking the family $\{[\varphi(x)]\mid \varphi(x)\in \Phi'\}$ as a subbasis. This is weaker than (or equal to) the standard topology, and all the subbasic open sets are clopen. Since any two distinct points $p\neq q$ are separated by a clopen set, $\tau_{\Phi'}$ is Hausdorff. Now we use a general topology fact:

If $(X,\tau_1)$ is Hausdorff, $(X,\tau_2)$ is compact, and $\tau_1\subseteq \tau_2$, then actually $\tau_1 = \tau_2$. See here for a proof (take the bijection to be the identity map $(X,\tau_2)\to (X,\tau_1)$).

Thus $\tau_{\Phi'}$ is actually equal to the standard topology. So for any formula $\psi(x)$, we can express $[\psi(x)]$ as an arbitrary union of finite intersections of subbasic clopen sets. Since $[\psi(x)]$ is compact, we can make do with a finite union of finite intersections. So $\psi(x)$ is equivalent to $\bigvee_{i=1}^n \bigwedge_{j=1}^m \varphi_{i,j}(x)$, where each $\varphi_{i,j}(x)$ is in $\Phi$ or is the negation of a formula in $\Phi$.

Of course, SMM's answer is exactly what you get when you translate the compactness argument in the proof of the general topology fact into a compactness argument in terms of formulas.

In addition to being aesthetically pleasing, this more abstract view can be useful, in that it can help you more easily find proofs of similar facts. For example, suppose you have a stronger separation condition: for any types $p\neq q$, there is a finite conjunction $\varphi_p(x)$ of formulas in $\Phi$ and a finite conjunction $\varphi_q(x)$ of formulas in $\Phi$ such that $\varphi_p(x)\in p$, $\varphi_q(x)\in q$, and $\varphi_p(x)\land \varphi_q(x)$ is inconsistent. Then you don't need to pass to $\Phi'$ by closing under complements: the condition exactly says that $\tau_\Phi$ is Hausdorff. And you can conclude that every formula is equivalent to a positive Boolean combination (no negation) of formulas in $\Phi$.