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.


1 Answer 1


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$.

  • $\begingroup$ Oh I see. I passed from sentences to sets of things with free variables completely unjustifiably without realizing it. Wow. :/ Thanks. $\endgroup$ Dec 4, 2022 at 21:30
  • 3
    $\begingroup$ @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!). $\endgroup$ Dec 6, 2022 at 2:29
  • $\begingroup$ 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. $\endgroup$ Dec 6, 2022 at 3:37
  • 1
    $\begingroup$ Why not modify the question to ask whether the two statements at issue are true? That would leave everything very understandable and clear. $\endgroup$ Dec 6, 2022 at 3:42
  • $\begingroup$ @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). $\endgroup$ Dec 7, 2022 at 2:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .