Return to Answer

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.

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.

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.

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.

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$. In the argument below, I use this interpretation. But then when we talk about being closed under (finite) relational intersections, we should include the empty intersection in addition to binary 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.

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.

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.

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.

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.

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 - I suspect this is not possible except by giving a positive answer to your Question 2. Note that when you talk about being closed under (finite) relational intersections, you should include the empty intersection in addition to binary intersections, i.e. $(M,R)$ should always be a model when $R = M^n$.

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.

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$. In the argument below, I use this interpretation. But then when we talk about being closed under (finite) relational intersections, we should include the empty intersection in addition to binary 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.

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.