# Characterizing relations by forbidden induced subsets

Working with relations in a purely set theoretic manner i.e. as just sets of ordered pairs, we see for any relation $$R$$ there exists unique inclusion minimal sets $$A$$ and $$B$$ such that $$R\subseteq A\times B$$ so that if we write $$\text{dom}(R)=A$$ and $$\text{rng}(R)=B$$ with $$\text{fld}(R)=A\cup B$$ then $$\text{fld}(R)$$ by definition is the unique inclusion minimal set $$X$$ such that $$R\subseteq X\times X$$. Now we say any relation $$L$$ is isomorphic to the relation $$R$$ and write $$R\cong L$$ if and only if there exists a bijection $$f:\text{fld}(R)\to \text{fld}(L)$$ such that $$\forall x,y\in\text{fld}(R)\left(xRy\iff f(x)Lf(y)\right)$$ further we say any relation $$J$$ is an induced subset of $$R$$ if and only if there exists a set $$S$$ such that we have $$J=R\cap S^2$$. With that said, note if we write:

$$R\text{ is reflexive}\iff \forall a\in\text{fld}(R)\left(aRa\right)$$ $$R\text{ is total}\iff \forall a,b\in\text{fld}(R)\left(aRb\lor bRa\right)$$ $$R\text{ is symmetric}\iff \forall a,b\in\text{fld}(R)\left(aRb\implies bRa\right)$$

Then if we let $$\small A_{1}=\{(1,1),(1,2),(2,2)\}$$, $$\small A_{2}=\{(1,2),(2,1),(1,1)\}$$, $$\small A_{3}=\{(1,1),(2,1)\}$$, as well as $$\small A_{4}=\{(1,2),(2,1)\}$$, $$\small A_{5}=\{(1,1),(2,2)\}$$, $$\small A_{6}=\{(1,1),(1,2)\}$$ and $$\small A_{7}=\{(1,2)\}$$ then we can prove:

$$\small R\text{ is reflexive}\iff \text{No induced subset of }R\text{ is isomorphic to a relation in }\{A_{2},A_{3},A_{4},A_{7},A_{6}\}$$ $$\small R\text{ is total}\iff \text{No induced subset of }R\text{ is isomorphic to a relation in }\{A_{2},A_{3},A_{4},A_{5},A_{6},A_{7}\}$$ $$\small R\text{ is symmetric}\iff \text{No induced subset of }R\text{ is isomorphic to a relation in }\{A_1,A_{3},A_{6},A_{7}\}$$

Further for many other relational properties such finite families of finite relations exist which act as "obstruction" sets, for example if we write $$\small R\text{ is transitive}\iff \forall a,b,c\in\text{fld}(R)\left(aRb\land bRc\to aRc\right)$$ then there is a finite family $$\mathcal{F}$$ of finite relations such that $$R$$ is transitive iff no induced subset of $$R$$ is isomorphic to a relation in $$\mathcal{F}$$ in fact the smallest such set $$\mathcal{F}$$ contains $$34$$ elements. Now it seems any relational property that can be characterized with a universal quantifier over its field of elements and any first order sentence identifying the elements among each other or as pairs in a relation, must always have some finite family of finite relations which act as an obstruction set as previously defined (and vice versa). Or more formally if we call any property $$\mathcal{P}$$ universal iff there exists $$n\in\mathbb{N}$$ such that there is a fixed formula $$\phi_R(x_1,\ldots x_n)$$ formed using only the conjugation, disjunction, or negation of those propositions of the form $$x_i=x_j$$ or $$x_iRx_j$$ for any relation $$R$$ and any integers $$1\leq i,j\leq n$$ such that for any relation $$A$$ we have: $$\small (A\text{ has property }\mathcal{P})\iff \forall a_1,\ldots a_n\in\text{fld}(A)\left[\phi_A(a_1,\ldots a_n)\right]$$ and if we also say any family of relations $$\mathcal{F}$$ obstructs $$\mathcal{P}$$ when any relation $$R$$ has property $$\mathcal{P}$$ iff no induced subset of $$R$$ is isomorphic to an element of $$\mathcal{F}$$, then I am claiming for any property $$\mathcal{P}$$ that:

$$\small\mathcal{P}\text{ is universal }\iff \text{There exists a finite family of finite relations which obstructs }\mathcal{P}$$

It seems like it should be relatively easy to prove and I have an argument in my mind, but I'm not able to write up anything that isn't horrible looking. I sense that I lack some pretty basic knowledge in logic/language theory which would allow me to write up a formal proof. What would one look like?

• This is quite trivial to prove if you work with binary relational structures $(A,R)$, $R\subseteq A\times A$ (or indeed, with structures over any finite relational language). Your setup where you are trying to infer the field from the relation itself makes it more messy, but it shouldn’t be too complicated. – Emil Jeřábek 3.0 Dec 10 '19 at 17:15
• I would just add that for someone coming from combinatorics and an interest in hereditary graph properties, and without a background in first order logic, this is a perfectly reasonable question with a satisfying answer (even if the answer is a standard application of compactness). – Gabe Conant Dec 10 '19 at 17:36
• @GabeConant Why would you need compactness? – Emil Jeřábek 3.0 Dec 10 '19 at 18:16
• One direction: for any finite structure $A$, you can write down explicitly a universal sentence that expresses omitting $A$. The other direction: $\forall x_1\dots\forall x_n\phi(x_1,\dots,x_n)$ with $\phi$ quantifier-free holds in a given structure iff it omits all structures with domains of the form $\{a_1,\dots,a_n\}$ (with the $a_i$ not necessarily distinct) that satisfy $\neg\phi(a_1,\dots,a_n)$. There are only finitely many such things (up to isomorphism). – Emil Jeřábek 3.0 Dec 10 '19 at 18:51
• @Emil Ah I see. I could get at most $2n$ elements by choosing for every integer $1\leq i\leq n$ an element $y_i\in\text{fld}(R)$ such that $(x_i,y_i)\in R$ or $(y_i,x_i)\in R$ then if $L=R\cap\{x_1,y_1,\ldots x_n,y_n\}^2$ we see $L$ is a non-empty induced subset of $R$ with $\text{fld}(L)=\{x_1,y_1,\ldots x_n,y_n\}$ i.e $2n$ field elements and $\phi_R\leftrightarrow\phi_L$ thus in particular the set $\mathcal{F}=\{R\subseteq \{1,\ldots ,2n\}^2:R\text{ does not have property }P\}$ would be an obstruction set of $\mathcal{P}$ if such a formula $\phi$ on $n$ elements distinguishes $\mathcal{P}$. – Ethan Dec 10 '19 at 21:02

I am going to rephrase the question in terms of first order relational structures. I believe the answer will be sufficiently close to what you are looking for.

Let $$L$$ be the first order language containing only a binary relation symbol $$R$$. Call a class $$\mathcal{P}$$ of $$L$$-structures universal if there is a collection $$T$$ of universal $$L$$-sentences such that $$M\in\mathcal{P}$$ if and only if $$M\models T$$. Call $$\mathcal{P}$$ strongly universal if, moreover, $$T$$ is finite--equivalently, there there is a single universal $$L$$-sentence $$\phi$$ such that $$M\in\mathcal{P}$$ if and only if $$M\models \phi$$. (So what I am calling strongly universal is the version of what you are calling universal.)

Theorem. Let $$\mathcal{P}$$ be a class of $$L$$-structures.
$$(a)$$ $$\mathcal{P}$$ is universal if and only if there is a class $$\mathcal{F}$$ of finite $$L$$-structures such that $$M\in\mathcal{P}$$ if and only if $$M$$ omits every element of $$\mathcal{F}$$ as a (induced) substructure.
$$(b)$$ $$\mathcal{P}$$ is strongly universal if and only if there is a finite class $$\mathcal{F}$$ of finite $$L$$-structures such that $$M\in\mathcal{P}$$ if and only if $$M$$ omits every element of $$\mathcal{F}$$ as a (induced) substructure.

Proof. Suppose first that there is a class $$\mathcal{F}$$ of finite $$L$$-structures such that $$M\in\mathcal{P}$$ if and only if $$M$$ omits every element of $$\mathcal{F}$$. Given $$A\in\mathcal{F}$$, let $$\psi_A$$ be a universal $$L$$-sentence that holds in an $$L$$-structure if and only if it omits $$A$$ (this is possible since $$A$$ is finite). Let $$T=\{\psi_A:A\in\mathcal{F}\}$$. Then $$M\in\mathcal{P}$$ if and only if $$M\models T$$. So this proves the right-to-left direction of both statements.

Now we prove the left-to-right direction of $$(a)$$. Suppose $$\mathcal{P}$$ is universal, witnessed by the $$L$$-theory $$T$$. Since every sentence in $$T$$ is universal, it follows that $$\mathcal{P}$$ is closed under substructures (i.e., if $$M\in\mathcal{P}$$ and $$N$$ is a substructure of $$M$$ then $$N\in\mathcal{P}$$). Now let $$\mathcal{F}$$ be the class of all finite $$L$$-structures not in $$\mathcal{P}$$. We claim that an $$L$$-structure $$M$$ is in $$\mathcal{P}$$ if and only if $$M$$ omits every element of $$\mathcal{F}$$. For one direction, if $$M$$ is in $$\mathcal{P}$$ then $$M$$ omits $$\mathcal{F}$$ by definition of $$\mathcal{F}^*$$ and the fact that $$\mathcal{P}$$ is closed under substructures. For the other direction, suppose $$M$$ is an $$L$$-structure not in $$\mathcal{P}$$. Then $$M\models\neg\phi$$ for some $$\phi\in T$$. Since $$\phi$$ is universal and $$L$$ is relational, there is some finite substructure $$A$$ of $$M$$ such that $$A\models\neg\phi$$. So $$A\not\in\mathcal{P}$$, which implies $$A\in\mathcal{F}$$. So $$M$$ does not omit $$\mathcal{F}$$.

Finally, for the left-to-right direction of $$(b)$$, suppose $$\mathcal{P}$$ is strongly universal, witnessed by the $$L$$-sentence $$\phi$$. Let $$\mathcal{F}$$ be given as in part $$(a)$$. We claim that there is some finite $$\mathcal{F}_0\subseteq\mathcal{F}$$ such that an $$L$$-structure $$M$$ omits $$\mathcal{F}$$ if and only if it omits $$\mathcal{F}_0$$. For each $$A\in\mathcal{F}$$, let $$\psi_A$$ be the same $$L$$-sentence as before. Let $$T=\{\psi_A:A\in\mathcal{F}\}$$. Then $$M\in\mathcal{P}$$ if and only if $$M\models T$$. So $$T\models \phi$$. By the compactness theorem, there is some finite $$T_0\subseteq T$$ such that $$T_0\models\phi$$. So if $$\mathcal{F}_0=\{A\in\mathcal{F}:\psi_A\in T_0\}$$, then $$\mathcal{F}_0$$ is as desired.

Remark 0. As Emil Jeřábek points out in the comments, the use of compactness is overkill in $$(b)$$. One can instead just list out the structures witnessing a failure of $$\phi$$.

Remark 1. In the setup of your question, it seems like you might have allowed the formula $$\phi_R$$ to depend on the concrete relation $$R$$ (depending on what you mean with the word "fixed"). But notice that in all of the examples (reflexive, symmetric, etc.) the formula is uniform in $$R$$. This is reflected in the notion of strongly universal by having the sentence $$\phi$$ depend only on the class $$\mathcal{P}$$. This is necessary. Otherwise you could form a class $$\mathcal{P}$$ such that $$\phi_R$$ is $$\forall x(x=x)$$ if $$\text{fld}(R)$$ is finite, and $$\phi_R$$ is $$\forall x(x\neq x)$$ if $$\text{fld}(R)$$ is infinite. So $$\mathcal{P}$$ consists just of the relations with finite universes, and thus cannot be characterized by omitting a class of finite structures (let alone a finite class).

• I know we aren't supposed to use the comment section for just "like" comments - but I am really impressed with your answer, Gabe! – Dominic van der Zypen Dec 14 '19 at 8:23