# Is the compactness theorem for first-order logic equivalent to saying that an arbitrary intersection of 0-definable sets is 0-definable?

Is it true that:

1. The intersection of $$0$$-definable sets is $$0$$-definable?
2. The intersection of a family of $$0$$-definable sets is $$0$$-definable?

The motivation for this question was an attempted rephrase of the compactness theorem using a new meta-level operator in place of $$\models$$ (representing both definability and truth in a model).

The erroneous initial attempt is in Appendix B.

A corrected attempt, and the translation of the compactness theorem into this new setting, is in Appendix A.

### Appendix A

Suppose $$\varphi$$ is a sentence, we can define $$\text{e}(\varphi)$$ as follows:

$$\text{e}(\varphi) \;\;\text{is defined as}\;\; \{ M : M \models \varphi \}$$

Similarly, we could define $$M \models \varphi$$ as $$\varphi \in \text{e}(\varphi)$$.

For convenience, let $$\text{e}(\Gamma)$$ be equivalent to $$\bigcap_{\gamma \in \Gamma} \text{e}(\gamma)$$.

The entailment phrasing of the compactness theorem in the standard notation reads: for all sets of sentences $$\Gamma$$ and sentences $$\varphi$$ such that $$\Gamma \models \varphi$$, there exists a finite $$\Gamma_0 \subset \Gamma$$ such that $$\Gamma_0 \models \varphi$$.

$$\Delta \models \psi$$ if and only if for all models $$M$$, if $$M \models \Delta$$, then $$M \models \psi$$.

Thus $$\Delta \models \psi$$ if and only if $$\text{e}(\Delta)$$ is a subclass of $$\text{e}(\psi).$$

The compactness theorem is thus equivalent to, for all $$\Gamma$$ and $$\varphi$$ such that $$\text{e}(\Gamma) \subset \text{e}(\varphi)$$, then there exists a finite $$\Gamma_0 \subset \Gamma$$ such that $$\text{e}(\Gamma_0) \subset \text{e}(\varphi)$$.

$$\Gamma_0$$ can be rewritten as a sentence $$\gamma$$ by joining its elements with conjunction.

Note, however, that the specific $$\Gamma_0$$ can change depending on what the conclusion is.

The compactness theorem is NOT equivalent to:

for all sets of sentences $$\Gamma$$, there exists a sentence $$\sigma$$ such that $$\text{e}(\Gamma)$$ is equal to $$\text{e}(\sigma)$$.

For a counterexample, consider the set of sentences $$\bigwedge_{i \in \mathbb{N}} c_i = d_i$$. This group of sentences asserting the equality of two series of constant symbols is not equivalent to any single sentence.

### Appendix B

For a fixed structure $$M$$, let's define the map $$\text{compat}$$ as follows:

$$\text{compat}(\varphi) \;\;\text{is the set of all \vec{v} such that \text{FV}(\vec{v}) \supset \text{FV}(\varphi)}$$

And let's define $$\text{ev}$$ as follows:

$$\text{ev}(\varphi)\;\; \text{is the set of all \vec{v} in \text{compat}(\varphi) such that M, \vec{v} \models \varphi(\vec{v}) holds}$$

$$\text{ev}$$ is meant to be read as "evaluation".

We immediately get some trivial facts:

• $$\text{ev}(\varphi \land \psi) \;\;\text{is}\;\; \text{ev}(\varphi) \cap \text{ev}(\psi)$$
• $$\text{ev}(\varphi \lor \psi) \;\;\text{is}\;\; \text{ev}(\varphi) \cup \text{ev}(\psi)$$
• $$\text{ev}(\lnot\varphi) \;\;\text{is}\;\; \text{compat}(\varphi) \setminus \text{ev}(\varphi)$$

The statement of the compactness theorem that I'm most familiar with is:

• every contradictory set of sentences $$\Delta$$ contains a finite subset $$\Delta_0$$ that is contradictory.

Let's define $$\text{ev}(\Gamma)$$ as $$\bigcap_{\gamma \in \Gamma}\text{ev}(\gamma)$$.

The compactness theorem is straightforwardly equivalent to saying that if $$\text{ev}(\Delta) = \varnothing$$, there exists a finite subset of $$\Delta$$ called $$\Delta_0$$ such that $$\text{ev}(\Delta_0) = \varnothing$$.

This is equivalent to saying that every $$\text{ev}(\Gamma)$$ is equal to $$\text{ev}(\Gamma_0)$$ for some finite $$\Gamma_0 \subset \Gamma$$.

Since $$\Gamma_0$$ is finite, it can be rephrased into a single formula $$\Gamma_1 \land \cdots \land \Gamma_n$$.

This leads me to the following question. The statement below is certainly implied by the compactness theorem. Is it equivalent to the compactness theorem though?

for all $$\Gamma$$ there exists a well-formed formula $$\varphi$$ such that $$\text{ev}(\Gamma)$$ is equal to $$\text{ev}(\varphi)$$?

In the above statement there is no requirement that $$\varphi$$ be constructed out of bits and pieces of $$\Gamma$$ $$\land$$-ed together. It just needs to be a well-formed formula.

Furthermore, is it okay to weaken the statement further and only talk about 0-definable sets rather than grouping them all together into a $$\text{ev}(\varphi)$$ thing.

This question is based on a misunderstanding. There are two substantive claims made:

1. The intersection of $$\emptyset$$-definable sets is $$\emptyset$$-definable.

2. The intersection of a family of $$\emptyset$$-definable sets with the finite intersection property is nonempty.

Both of these claims are false, and counterexamples to each can be gotten from the structure $$M=(\mathbb{R};+,\times)$$:

• For a counterexample to $$1$$, note that every rational is $$\emptyset$$-definable and so every singleton is the intersection of $$\emptyset$$-definable sets, but clearly not every singleton is $$\emptyset$$-definable.

• For a counterexample to $$2$$, just take the set of formulas $$\Delta$$ which together say that $$x>q$$ for every rational $$q$$.

Now claim $$2$$ is true for reasonably saturated structures. Claim $$1$$, however, is very broadly false: it will fail for any structure with infinitely many $$\emptyset$$-definable elements, and so for example will fail in any model of the real-closed-field axioms. This is a bit fun, so I've spoilered it:

Suppose $$M$$ has infinitely many $$\emptyset$$-definable elements. Let $$(\varphi_i)_{i\in\mathbb{N}}$$ be a sequence of formulas defining distinct elements (more precisely, singleton subsets, but meh) of $$M$$, and let $$(\eta_j)_{j\in\mathbb{N}}$$ enumerate all the one-free-variable formulas in the language of $$M$$. Let $$\psi_i=\top$$ if $$\varphi_i^M\not\in\eta_i^M$$ and let $$\psi_i=\neg\varphi_i$$ if $$\varphi_i^M\in\eta_i^M$$. Then in $$M$$, the intersection $$\bigcap_{i\in\mathbb{N}}\psi_i$$ disagrees with $$\eta_i$$ about whether or not it contains the element defined by $$\varphi_i$$.

• Oh I see. I passed from sentences to sets of things with free variables completely unjustifiably without realizing it. Wow. :/ Thanks. Dec 4, 2022 at 21:30
• @GregNisbet I think there's more going wrong in your question than just passing from sentences to formulas. The step from "If $\mathrm{ev}(\Delta) = \varnothing$, then there is a finite $\Delta_0\subseteq \Delta$ such that $\mathrm{ev}(\Delta_0) = \varnothing$" to "for all $\Gamma$, there is a finite $\Gamma_0\subseteq \Gamma$ such that $\mathrm{ev}(\Gamma) = \mathrm{ev}(\Gamma_0)$ is just not justified (in any context!). Dec 6, 2022 at 2:29
• True. I made a number of mistakes trying to recast familiar stuff in terms of $\text{ev}$. I kinda want to delete or rewrite this question to be less bad, but Noah’s answer is good and that would remove the context. I might add a second attempt and move the first one to an appendix section. Dec 6, 2022 at 3:37
• Why not modify the question to ask whether the two statements at issue are true? That would leave everything very understandable and clear. Dec 6, 2022 at 3:42
• @AlexKruckman I modified the question to contain just the two questions that Noah answered in the main section. I also added a section outlining what I was originally trying to do in appendix A ... and ended up answering my original question (which has to do with definable classes of first-order structures not definable sets within a structure). Dec 7, 2022 at 2:03