4
$\begingroup$

It is a well known fact that any intersection of equivalence relations on a fix set is itself an equivalence relation. The same holds for a few other common relational theories, such as partial orders. I'm curious about a syntactic characterization of theories with this property. All of the examples I can think of are axiomatized by universal Horn sentences (i.e. sentences of the form $\forall \bar{x} \varphi_0 \wedge \dots \wedge \varphi_{n-1} \rightarrow \varphi_n$, with $\varphi_0,\dots,\varphi_n$ atomic formulas), but I'm not sure if this is a precise characterization.

Fix a language $\mathcal{L}$ with a single relational symbol $R$. We'll say that an $\mathcal{L}$-sentence or theory $\Sigma$ is preserved under relational intersections if whenever $(X,A)$ and $(X,B)$ are models of $\Sigma$ on the same underlying set $X$, then $(X,A\cap B) \models \Sigma$, and $(X,X^n) \models \Sigma$, where $n$ is the arity of $R$ (this being the empty intersection).

Question 1: Is there a syntactic characterization up to logical equivalence of sentences that are preserved under relational intersections?

All of the examples I know of also have the property that they are preserved under arbitrary relational intersections. In a similar situation--sentences that are preserved under intersections of substructures--preservation under finite intersection gives preservation under arbitrary intersections, but the idea of that proof doesn't really work in this context.

Question 2: If $\Sigma$ is preserved under relational intersections, does it follow that for any (possibly empty) family $(X,A_i)\models \Sigma$ indexed by $i \in I$, we have $(X,\bigcap_{i \in I} A_i)\models \Sigma$?

This feels like something that should be classical model theory, but I can't find any references.

$\endgroup$
  • 4
    $\begingroup$ It’s not just universal Horn sentences: all sentences that do not use $R$ at all, such as there exist at least $k$ objects, also trivially have this property, and in general are not equivalent to universal Horn sentences. $\endgroup$ – Emil Jeřábek Mar 13 '20 at 17:34
  • $\begingroup$ Very good point. $\endgroup$ – James Hanson Mar 13 '20 at 18:07
  • $\begingroup$ @EmilJeřábek3.0 Perhaps more intricately, "If $R$ holds of at most $n$ tuples then the universe has at least $k$ objects." $\endgroup$ – Noah Schweber Mar 14 '20 at 0:46
3
$\begingroup$

This is only a very partial answer, but it may be useful. I can characterize those theories which are preserved under substructure and arbitrary relational intersections.

Let's say a sentence is universal $(R,\neq)$-Horn if it has the following form: $$\forall x\, \left(\left(\bigwedge_{i=1}^n \varphi_i\right)\rightarrow \psi\right)$$ where $\psi$ is an instance of $R$ in context $x$, and each $\varphi$ is either an instance of $R$ in context $x$ or $x_i \neq x_j$, where $x_i$ and $x_j$ are distinct variables in $x$.

It is easy to see that any universal $(R,\neq)$-Horn theory is preserved under substructure and arbitrary relational intersections.

Let $\Sigma$ be a theory which is preserved under substructure and arbitrary relational intersections. Let $\Sigma'$ be the set of all universal $(R,\neq)$-Horn consequences of $\Sigma$. Then every model of $\Sigma$ is a model of $\Sigma'$, and we want to show the converse.

Let $(M,R)\models \Sigma'$, and let $$\mathcal{R} = \{R'\subseteq M^n\mid R\subseteq R' \text{ and } (M,R')\models \Sigma\}.$$ If we can show that $\bigcap_{R'\in \mathcal{R}} R' = R$, then we're done: $\Sigma$ is preserved under arbitrary relational intersections, so $(M,R)\models \Sigma$.

Clearly $R\subseteq \bigcap_{R'\in \mathcal{R}} R'$, so it suffices to show that for every tuple $b\in M^n$ such that $b\notin R$, there is some $R'\in \mathcal{R}$ such that $b\notin R'$.

So fix such a $b$ and consider the $L(M)$-theory $$\Sigma\cup \{a\neq a'\mid a\neq a'\in M\} \cup \{R(a)\mid a\in M^n\text{ and }M\models R(a)\}\cup \{\lnot R(b)\}.$$ This is consistent by compactness, using the fact that $M$ satisfies all universal $(R,\neq)$-Horn consequences of $\Sigma$. Let $N$ be a model, and let $(M',R')$ be the induced substructure of $N$ with domain the interpretation of the constant symbols in $L(M)$. We can identify $M'$ with $M$, since distinct constant symbols have distinct interpretations. Since $\Sigma$ is preserved under substructure, $(M,R')\models \Sigma$, and by construction $R\subseteq R'$ and $b\notin R'$, as desired.

It's now an easy application of compactness to show that a sentence is preserved under substructure and arbitrary relational intersections if and only if it is equivalent to a finite conjunction of universal $(R,\neq)$-Horn sentences.


A few comments:

There's a slight ambiguity in your question about whether "arbitrary intersection" includes the empty intersection. It seems to me to be more natural to include the empty intersection, i.e. if $\Sigma$ is preserved under arbitrary intersections, then $(M,R)\models \Sigma$ when $R = M^n$. The argument above uses this interpretation (since $\mathcal{R}$ might be empty!). But then when we talk about being closed under (finite) relational intersections, we should include the empty intersection in addition to binary intersections.

If you want to "arbitrary intersection" to mean "arbitrary nonempty intersection", you just need to adjust the definition of universal $(R,\neq)$-Horn to allow $\psi$ to be $\bot$. Then in the argument, you can show that $\mathcal{R}$ is non-empty, since $$\Sigma\cup \{a\neq a'\mid a\neq a'\in M\} \cup \{R(a)\mid a\in M^n\text{ and }M\models R(a)\}$$ is consistent.

To adjust this argument to remove the assumption of preservation under substructure seems tricky: in the compactness argument to find the model $N$, we'd need to ensure that the domain doesn't grow, which forces us to think about omitting the partial type $\{x\neq a\mid a\in M\}$. So the syntactic characterization has to be strong enough to ensure not just consistency but also that this partial type is omittable. It's not immediately clear to me how to do this.

Adjusting arbitrary intersections to binary intersections seems much harder. My guess is that there is no nice characterization unless your Question 2 has a positive answer.

$\endgroup$
  • 2
    $\begingroup$ I'm always for the empty intersection. Am I understanding correctly that we could in principle allow the $\varphi_i$'s to be of the form $x=y$, but this can be removed by renaming variables? $\endgroup$ – James Hanson Mar 14 '20 at 20:06
  • 2
    $\begingroup$ Also I believe you can get preservation under arbitrary intersections from preservation under binary intersections and passing to substructures by a proof analogous to the proof for intersections of substructures. $\endgroup$ – James Hanson Mar 14 '20 at 20:07
  • 2
    $\begingroup$ Given $(X,A_i)$, take an ultraproduct over the family of finite intersections of the $A_i$'s using an ultrafilter extending the filter generated by sets of the form $\{\bar{j} \in I : i \in \bar{j}\}$, where $A_{\bar{j}} = \bigcap_{i \in \bar{j}}A_i$, then pass to the substructure whose underlying set is the diagonal embedding of $X$. This structure will be $(X, \bigcap_{i \in I}A_i)$. $\endgroup$ – James Hanson Mar 14 '20 at 20:11
  • 1
    $\begingroup$ Can you think of an example of a theory that is preserved under relational intersections and only has infinite models but isn't equivalent to a universal $(R,\neq)$-Horn theory plus axioms asserting the existence of infinitely many elements? $\endgroup$ – James Hanson Mar 15 '20 at 6:29
  • 1
    $\begingroup$ Yes, I think this works: $(\forall x\forall y R(x,y))\lor (\exists x\forall y \lnot R(x,y))$, plus the axioms saying the domain is infinite. $\endgroup$ – Alex Kruckman Mar 15 '20 at 15:30

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.