## Sunday, 18 August 2013

### The Abstract Structure of a Binary Relational Model

Generalizing the previous M-Phi post on the abstract structure of an $\omega$-sequence, suppose that $\mathcal{A} = (A, R)$ is any (set-sized) binary relational model (i.e., $A$ is the domain/carrier set and $R \subseteq A^2$). Let $\kappa = |A|$. Let $L$ be a second-order, possibly infinitary, language, with $=$ (but no non-logical primitive symbols), which allows compounds over $\kappa$-many formulas and allows quantifier prefixes to be a set $V$ of variables of cardinality $\kappa$. For each $a \in A$, let $x_a$ be a unique variable that "labels" $a$. Let the second-order unary variable $X$ label the domain $A$ and let the second-order binary variable $Y$ label the relation $R$.

The (possibly infinitary) diagram formula $\Phi_{\mathcal{A}}(X,Y)$ is then:
$\exists V[\bigwedge_{a,b \in A; a \neq b} (x_a \neq x_b) \wedge \bigwedge_{a \in A} Xx_a \wedge \forall x(Xx \to \bigvee_{a \in A} (x = x_a))$ $\wedge \bigwedge_{a,b \in A} (\pm_{ab} Yx_a x_b) ]$
where $V = \{x_a \mid a \in A\}$ and $\pm_{ab}Yx_ax_b$ is $Yx_ax_b$ if $(a,b) \in R$ and $\neg Yx_ax_b$ otherwise.

On the Diagram Conception of Abstract Structure,
The abstract structure of $\mathcal{A}$ is the proposition $\hat{\Phi}_{\mathcal{A}}$ expressed by the formula $\Phi_{\mathcal{A}}(X,Y)$.
Categoricity ensures that, for any $\mathcal{B} = (B,S)$ (a relational model, with a single binary relation $S \subseteq B^2$), we have:
$\mathcal{B} \models \Phi_{\mathcal{A}}(X,Y)$ if and only if $\mathcal{B} \cong \mathcal{A}$.