Saturday, 9 March 2013

What is Abstract Structure?

[This post continues the theme of "Eliminating Relata", and abstraction more generally, discussed in a couple of earlier posts:
"Eliminating Relata" 16 July 2012.
"Eliminating Relata, II", 16 July 2012
"Individuation for Structured Sets and Leibniz Abstraction" 27 July 2012.]

1. What is Abstract Structure?

The reader is familiar with the intuitive notion that all isomorphic copies of some particular model have the same "abstract structure". We should like to identify, for each model $\mathcal{A} = (A, R_1, \dots)$, some special entity, $\hat{\mathcal{A}}$, such that the following holds:
Abstraction Principle
$\hat{\mathcal{A}} = \hat{\mathcal{B}} \Leftrightarrow \mathcal{A} \cong \mathcal{B}$.
However it is very puzzling how one might do this. The crucial issue, it seems to me, is whether this special entity $\hat{\mathcal{A}}$ is itself a model, with a domain. Do abstract structures have domains?

2. What is an Abstract Graph?

For example, one wishes to think of the abstract graph associated with all isomorphic copies of some given graph $\mathcal{G}$. But, although the formal definition of a graph is that $\mathcal{G} = (V,E)$, for some domain $V$ of vertices and edge relation $E$, one does not wish to identify the abstract graph with any of these particular graphs.

For example, first fix the following graph:
$V = \{0,1,2\}$
$E = \{\{1,2\}\}$
$\mathcal{G} = (V,E)$
We may "picture" this graph $\mathcal{G}$ as follows:
$\circ \hspace{2cm} \circ -----\circ$
$ 0 \hspace{2.1cm} 1 \hspace{2.1cm} 2$
Now we may also "picture" the corresponding abstract graph as follows,
$\circ \hspace{2cm} \circ -----\circ$
by simply omitting the "labels". We are left with just three "nodes", two of which are edge-related.

Of course, you and I have no dfficulty understanding this intuitive idea. But, pictures aside, it remains terribly unclear.

What are these nodes? For the small circle token inscriptions in a token of such a picture are not the nodes! And neither are the circle types in a picture-type. Somehow, the circles "represent" the nodes.

Supposing that there is indeed an abstract graph corrresponding to $\mathcal{G}$, and it is unique, let us call it $\hat{\mathcal{G}}$. By stipulation, the domain of $\mathcal{G}$ is the set $\{0,1,2\}$. Now, what is the domain of the abstract graph, $\hat{\mathcal{G}}$? Not $0,1,2$, clearly. But what then? Doesn't $\hat{\mathcal{G}}$ have a domain of nodes, no matter how mysterious they seem?

3. Abstract Structure = Categorical Propositional Function

Let's propose that an abstract graph $\hat{\mathcal{G}}$ does not have a domain at all. An abstract graph is more like a propositional description of a particular model, than a model itself. In this particular case, consider the following second-order formula $\Phi_{\mathcal{G}}(X)$:
\begin{eqnarray*} \exists x_0 \exists x_1 \exists x_2(x_0 \neq x_1 \wedge x_0 \neq x_2 \wedge x_1 \neq x_2 \\ \wedge \neg Xx_0x_0 \wedge \neg Xx_0x_1 \wedge \neg Xx_0x_2 \wedge \neg Xx_1x_0 \\ \wedge  \neg Xx_1x_1 \wedge Xx_1x_2 \wedge \neg Xx_2x_0 \wedge Xx_2x_1 \wedge \neg Xx_2x_2 \\ \wedge \forall y(y = x_0 \vee y = x_1 \vee y = x_2)). \end{eqnarray*}
This formula $\Phi_{\mathcal{G}}(X)$ categorically axiomatizes the graph $\mathcal{G}$ in the sense that
if $\mathcal{G}^{\prime}$ satisfies $\Phi_{\mathcal{G}}(X)$, then $\mathcal{G}^{\prime} \cong \mathcal{G}$. 
We may think of the formula $\Phi_{\mathcal{G}}(X)$ as expressing the value $\hat{\Phi}_{\mathcal{G}}[X]$ of the corresponding second-order propositional function $\hat{\Phi}_{\mathcal{G}}$ at value $X$. And then we shall claim that this second-order propositional function $\hat{\Phi}_{\mathcal{G}}$ is the abstract structure $\hat{\mathcal{G}}$ of the graph $\mathcal{G}$ defined above.

Applying this to models in general, and this will guarantee that we have the required abstraction principle:
Abstraction Principle
$\hat{\mathcal{A}} = \hat{\mathcal{B}} \Leftrightarrow \mathcal{A} \cong \mathcal{B}$.
4. Skolemization: Labelled Structure

To continue this very brief introduction, suppose that we skolemize the formula $\Phi_{\mathcal{G}}(X)$ as follows, by introducing three distinct skolem constants $a,b$ and $c$:
\begin{eqnarray*} a \neq b \wedge a \neq c \wedge b \neq c \wedge \neg Xaa \wedge \neg Xab \wedge \neg Xac \wedge \neg Xba \wedge \\ \neg Xbb \wedge Xbc \wedge \neg Xca \wedge Xcb \wedge \neg Xcc \wedge \forall y(y = a \vee y = b \vee y = c). \end{eqnarray*}
This breaks into three formulas:
\begin{eqnarray*} a \neq b \wedge a \neq c \wedge b \neq c. \\ \neg Xaa \wedge \neg Xab \wedge \neg Xac \wedge \neg Xba \wedge \neg Xbb \wedge Xbc \wedge \neg Xca \wedge Xcb \wedge \neg Xcc. \\ \forall y(y = a \vee y = b \vee y = c). \end{eqnarray*}
If we now "picture" this, we would get,
$\circ \hspace{2cm} \circ -----\circ$
$ a \hspace{2.1cm} b \hspace{2.1cm} c$

The "labels" are skolem constants!

Roughly, an unlabelled graph is the abstract graph, understood as the second-order propositional function. And a labelled graph is a skolemized description of the abstract graph.


  1. Hi Sam,

    On the first point, then, for cardinalities, one can use that, yes. But, for the corresponding principle for isomorphism, I think (!), by a result of Harold Hodes, that it leads to an inconsistency. I.e., let (ISO) be the abstraction principle,

    (ISO) ^R1 = ^R2 iff R1 is isomorphic to R2

    Then adding (ISO) to ZF is inconsistent. (I don't know the proof.)

    The example you mention involves two acceptable, though arbitrary, skolemizations of the structure-formula (so, a and b are skolem terms). The structural description has no constants - only bound variables. That's how I account for "labelling". (In a sense, the nodes correspond to first-order variables; skolemization corresponds to arbirtarily picking some node of the structure and labelling it.)

    Hopefully, the arbitrariness is removed in two ways:
    i) M is first described categorically by the first-order ramsified description (no constants);
    ii) Then we pass to the abstract (second-order) propositional content, assuming that logically equivalent formulas express the same abstract proposition.

    For the case of M, we have the second-order propositional function,

    The proposition that there are exactly two things x,y such that Xxx & Xyy & Xyx & -Xxy.

    As applied to M, this yields a true proposition.

    So, the hope it to have something categorical in the required sense and implementation-independent too.



  2. Hi Jeff,

    Thanks for this! I deleted my post after searching for your previous posts on this (which I should have done before I posted!); sorry about that.


    ps I'm much less sure that this is pertinent now, but if R_1 and R_2 are set-sized, then (ISO) can surely be modeled in ZF (indeed, for any equivalence relation on sets). If R_1 and R_2 are arbitrary second-order relations, then can't we just use Burali-Forti reasoning to show that (ISO) is inconsistent?

  3. Hi Sam,

    Oh - they were good questions anyway! I linked in the previous posts now.

    Yes, I was thinking of the second-order form of (ISO), and I think the argument goes via Burali-Forti style reasoning. It's in a paper by Hodes from the 80s.



  4. Hi Jeff,

    Thanks, I'll look it up. My guess was that the second-order form of (ISO) is inconsistent independently of ZF. This assumes that the hat operator ^ is a type-lowering device. But I take it (?) your Fregean propositions are not objects, and so your version of (ISO) isn't susceptible to Burali-Forti.


  5. Hi Sam,

    Yes, I think that's right - Hodes's point is in the ball-park of neo-logicist approach, so doesn't require ZF at all.

    But I think to get this "abstract structure = propositional function" view to work, one would have to have the propositions either in a distinct sort, or make some sort of class/set style distinction.

    To take, the most extreme example, we try to get the abstract structure $\hat{V}$ of the cumulative hierarchy V. Because we proceed by infinitarily axiomatizing V, with a distinct variable for each set (along with the elementary diagram of V), then $\hat{V}$ is initially going to be expressed by a formula of class size, and so it cannot be an element of V.

    So, it looks like the abstract structure of a given model is, in some general sense, at a higher level.



  6. Hi Jeff,

    Right. And if propositional functions are supposed to exist for all formulas with one free second-order variable (as your descriptions are), then they'll have to be third-order entities. But then it looks like you might as well just have the abstract of a second-order structure be the third-order 'collection' of all isomorphic structures.

    All the best,

  7. Hi Sam,

    Yes, all that sounds right.

    But the isomorphism class (collection) approach is something I have a kind of dislike for. I like three things about the propositional function approach,

    1. The identification of the nodes with variables (in a sense, it explains the permutation invariance, or "lack of individuality" of the nodes);

    2. The connection between labelling and skolemization and specific implementations.

    3. I can apply this to get an account of possible worlds, by applying a second-order propositional function $\hat{\Phi}$ of this kind to a sequence of concretum relations.

    So, e.g., a possible world $w$ in which there are exactly six spacetime points, related in such-and-such a way, can be thought of as the image of a certain propositional function $\hat{\Phi}$ on the properties/relations Spacetime-Point and Between. (Worlds are then categorical propositions, "built up" from concretum relations.) I think that this then ensures that "isomorphic worlds" (worlds with no qualitative differences) are in fact identical. This is what Leibniz equivalence in physics (spacetime theory) amounts to.



  8. Hi Jeff,

    Thanks! So there are two proposals on the table (as I see it). On the first, we just go third-order in the usual way. Then we say that the abstract structure of X is {Y: Y is isomorphic to X}. On the second, we also ascend to a third-order language, but we add a theory of possibly non-set-sized formulas, and let the abstract structure of X be {Phi: \Phi is a categorical description of X}.

    In order to have a unique class of variables which can serve as nodes on the second approach, we'd need to associate each X with a class of variables in such a way that if X and Y are isomorphic, they are associated with the same class. Call this class of variables X*.

    If X* is available, then there's no reason why the advocate of the first approach can't avail themselves of it. They could then associate X with {Y: Y is isomorphic to X & the domain of Y is X*}. And the nodes of the abstract structure could be identified with X*. Permutation invariance is explained as it would be on the second approach - if you apply a permutation of the nodes to any model in the abstract structure you get another model in the same abstract structure.

    On the second point, I'm not seeing clearly what the desiderata are for labeling. If it's not too much hassle could you say where you think the approach I've outlined would be unsatisfactory re. labeling.

    I need to think more about the third point.

    Thanks for the discussion!


  9. Hi Sam,

    Great - thanks. So, I guess we have two approaches for identifying an abstract structure $\hat{X}$ for $X$:

    i. The isomorphism-class approach
    ii. The propositional-function approach.

    (Both will incur set/class issues, but let's pretend we can get round that!!)

    So, in going propositional, we don't identify $\hat{X}$ with the equivalence class, like {Phi: \Phi is a categorical description of X}. Rather, $\hat{X}$ is the second-order propositional content itself. Hopefully, this gets a unique thing to be $\hat{X}$. This is then expressed, linguistically, by one of these Phi in some sufficiently large language; and that can be skolemized, by introducing constants. So, properly speaking, nodes are not components of the abstract structure, but rather additional components (i.e., existentially bound first-order variables) of some (implementation-dependent) description of the structure (i.e., a formula Phi).

    On the isomorphism-class approach, one picks a class X* of variables, and yes, this can play a sort of role as a domain for $\hat{X}$. But I don't really want a domain! Rather I want to explain it away, by going propositional. For one can replace X* be any other set, Z, of the same cardinality, and that is the kind of implementation-dependence I want to avoid. On the prop-function approach, the domain of nodes is a kind of artifact of the labelled description of the structure. The structure is "domainless".

    I think you're right though that the isomorphism-class approach can introduce a labelling as you suggest. So, possibly, whatever I say is the advantage of the categorical prop function approach may be mimicked on the isomorphism class approach.

    The third point is, oddly enough, what is driving all this (in a paper I'm writing on "Leibniz equivalence"). I want to get an analysis of possible worlds in which worlds are *not* equivalence classes. So, it's a form of propositional "ersatzism". A possible world $w$ is $\hat{X}[\vec{R}]$, where $\hat{X}$ is a categorical second-order propositional function, and $R_i$ is a sequence of relations on concreta. So, e.g., an example of a possible world might be the proposition that there are exactly three concreta x,y,z and they bear relations ... blah ... blah. This world is the image of applying the corresponding second-order propositional function to the sequence of relations. (And this second-order propositional function is the "abstract structure" of that possible world, relative to those relations.)



  10. Hi Jeff,

    That's really helpful, thanks!

    So I'd initially thought that the propositional-function view was something like the following: the abstract structure of X is the propositional function F such that $F(Y) \leftrightarrow \Phi(Y)$, where $\Phi$ is a particular categorical description for X. More explicitly, we just get F from a single instance of third-order comprehension (on the possibly infinite formula $\Phi$). But then the view is not much different from the one I outlined. The reason is that $\Phi(Y)\leftrightarrow Y\cong X$. Since equivalence is the analogue of identity for higher-order entities, the abstract structure of X in this sense just is the abstract structure on the isomorphism-class view. The important difference is that the isomorphism-class view doesn't have to saddle itself with an unwieldily proper class sized object language, and attendant logic.

    That's why I explicated the propositional-function account in terms of an equivalence class of formulas. But I see now that the idea is to have something like a primitive 'content abstraction' operator which takes formulas, and delivers a function which maps classes to propositions. However, if we do this, it still seems very natural to lay down some axiom connecting this content to the formula abstracted on; something like:

    (*) the functional content of S applies to Y just in case S is true of Y.

    But then, again, the abstract structure on this view looks awfully similar to the isomorphism-class view (as far as I can see).

    Re. the domain. Strictly speaking the abstract structure on the isomorphism-class view doesn't have a domain, since it's not itself a structure. And the nodes on the propositional-function approach can also be changed - it seems just as arbitrary which variables we pick as the canonical ones as it is which domain we pick to be the domain of the structures in the abstract structure on the isomorphism-class approach. Are you thinking of the propositional function as coming equipped with some non-arbitrary class of variables? It's not clear to me yet how one would go about doing that.

    All the best,

  11. Hi Sam,

    Yes, right on both accounts.

    Given some (unary) prop function $\hat{\Phi}$ and relation $R$, the proposition $\hat{\Phi}[R]$ is true iff $\Phi$ is true of $R$. The propositional function here is meant to be language-independent (like an unsaturated sense, in Frege's terminology). There will be similarities with the isomorphism-class identification, as you point out.

    There no special domain on either approach, but one can add a "labelling" on both. The formula $\Phi$ expressing the propositional function itself has all its first-order variables "ramsified". $\exists y_0 \exists y_1 \dots \theta$. One can remove these, leaving just the subformula $\theta$ with the free first-order variables. This expresses an unsaturated propositional function, with N many argument places, where N is the cardinality of the original model. So, the nodes in some sense correspond to the saturated argument positions in the propositional function.