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?

toocomplicated. $\endgroup$ – Emil Jeřábek 3.0 Dec 10 '19 at 17:15