Saturday, 13 July 2013

Five Approaches to the Problem of Abstract Structure

Structuralism in the foundations of mathematics is the view that the topic of mathematical statements concerns structures (or patterns). For example, consider
2 + 2 = 4
According to eliminative structuralism, "$2 + 2 = 4$" is a statement about all mathematical structures that are models of $PA_2$.

According to ante rem structuralism, "$2 + 2 = 4$" is a statement about the ante rem abstract structure, usually called $\mathbb{N}$, that all models of $PA_2$ have in common.

I am more sympathetic to "sui-generis-ism" about mathematical objects. I think "$2 + 2 = 4$" is a statement about 2 and 4. The slogan of sui-generis-ism, from Bishop Butler, is:
Every thing is what it is and not another thing.
But sui-generis-ism is closely related to ante rem structuralism, though.

Whether or not one is a structuralist, one will be interested in making sense of the notion of what it is that isomorphic copies of mathematical structures "have in common".

The classic example (see Benacerraf 1965, "What Numbers Could Not Be") concerns particular "implementations" for $\mathbb{N}$ (I call these "gauges": they are analogous to gauge choices of isomorphic (Leibniz equivalent) spacetime models in general relativity). Following Benacerraf's example, let  $\omega$ be the set of finite von Neuman ordinals, and let $^{+}$ be the usual ordinal successor mapping $: x \mapsto x^{+} = x \cup \{x\}$. Let $S_u$ be the the unit set operation. Let $Z$ be the smallest set containing $\varnothing$ and closed under $S_{u}$. Then let us define two models:
$\mathbf{VN} := (\omega, \varnothing, ^{+})$: the von Neuman gauge for $\mathbb{N}$
$\mathbf{Zerm} := (Z, \varnothing, S_{u})$: the Zermelo gauge for $\mathbb{N}$.
As Benacerraf pointed out, there are three crucial facts:
(DIST) $\mathbf{VN} \neq \mathbf{Zerm}$
(ISO) $\mathbf{VN} \cong \mathbf{Zerm}$
(EQ) There's no mathematical reason to prefer $\mathbf{VN}$ over $\mathbf{Zerm}$, or vice versa, as the "correct" reduction of the numbers.
Now $\mathbf{VN}$ and $\mathbf{Zerm}$ are set-theoretic models of arithmetic, or "implementations". They are isomorphic but extensionally distinct. And neither seems preferable to the other. Consequently, Bencarraf concluded:
Numbers are not sets.
And went on to suggest a structuralist "way out".

The eliminativist "way out" gives up on identifying the numbers with anything, and sticks with the isomorphism class of models (the elements of these models needn't be sets: they could be spacetime points). The ante rem "way out" postulates a new kind of mathematical object, the ante rem abstract structure. For any specific model $\mathcal{A}$, there is to be an ante rem abstract structure, which for reasons I'll explain I'll denote $\hat{\Phi}_{\mathcal{A}}$, that all isomorphic copies have in common. So, for Benacerraf's example, we would have:
$\hat{\Phi}_{\mathbf{VN}} = \hat{\Phi}_{\mathbf{Zerm}}$
And arithmetic is, on Shapiro's view, about $\hat{\Phi}_{\mathbf{VN}}$.

More generally, we want to have, for models $\mathcal{A}, \mathcal{B}$,
Leibniz Abstraction
$\hat{\Phi}_{\mathcal{A}} = \hat{\Phi}_{\mathcal{B}}$ iff $\mathcal{A} \cong \mathcal{B}$
(I call this "Leibniz Abstraction" because it abstracts from isomorphic copies, and this identification of isomorphic indiscernibles is what lies behind Leibniz's relationist disagreement with Newton's substantivalist theory of space.)

But what is this mysterious entity, $\hat{\Phi}_{\mathcal{A}}$?

Let me explain why this is conceptually hard (though it might not be technically hard). It is conceptually hard, because on our usual account of models, models always have a carrier set (or domain). And then the structural parts of the model are relations and functions over the carrier set. So, for example, the relations are sets of $n$-tuples drawn from the carrier set. But if we look at the models $\mathbf{VN}$ and $\mathbf{Zerm}$, their carrier sets are distinct. We want to find something that is the same for both, and this means that we have to, somehow, "throw away" the carrier sets. But the carrier set, by definition, contains the relata of the relations, and therefore when we "throw away" the carrier set, we throw away the relations as well! We want, somehow, to keep the relations, but "throw away" the relata.

How do we do this?

I know of five prior approaches to this problem:
  1. The Skolemization Approach (Pettigrew, Burgess)
  2. The Isomorphism Type Approach (folklore)
  3. The Structure Identity/Univalence Approach (Category Theory)
  4. The Axiomatic Approach (Axiomatic Theory of Graphs) (Leitgeb)
  5. The Diagram Approach (me)
I've explained before what the diagram approach involves. Given a model $\mathcal{A}$, we define a certain (possibly infinitary) language $\mathcal{L}(\mathcal{A})$ and then define a certain diagram formula $\Phi_{\mathcal{A}}(\vec{X})$, which itself categorically defines the isomorphism type of $\mathcal{A}$. The abstract structure of $\mathcal{A}$ is then taken to be the propositional content of this formula, and this propositional content is denoted $\hat{\Phi}_{\mathcal{A}}$. This yields Leibniz Abstraction; it has eliminated any special carrier set/domain. As a simple example, suppose $G_1 = (V_1,E_1)$ and $G_2 = (V_2, E_2)$ are isomorphic graphs. Then the abstract, "unlabelled" graph, is $\hat{\Phi}_{G_1}$, which $= \hat{\Phi}_{G_2}$; and "labelling" corresponds precisely to skolemization of the diagram formula; distinct logically equivalent skolemizations correspond to automorphisms of $G_1$.

The Skolemization Approach is a "way out" consistent with eliminativist structuralism and set-theoretic reductionism. All mathematical objects are still sets. However, we should like to be able to talk as if we have the natural numbers $\mathbb{N}$ and not be committed to some particular reduction. How might we do this? Well, as soon as we have proved
There is a model $\mathcal{A} \models PA_2$
then we can skolemize this existence claim and use the skolem constant "$\mathbb{N}$" to refer (indeterminately, of course) to any isomorphic model for $PA_2$. (This skolem constant is just like a Hilbert $\epsilon$-term.) We do not have to worry ourselves about the question---a pseudo-question--- of which particular model $\mathbb{N}$ is, and what its domain is. That is now a pseudo-question, because it misunderstands the manner in which the term "$\mathbb{N}$" was introduced, and therefore misunderstands its semantic function. It is not a uniquely denoting term. Rather, it is analogous to the term "$i$" for some root of $-1$ in the complex field. It seems quite right to say that "$i$" is nothing more than a skolem term for the existence claim
(*) $\exists x(x^2 + 1 = 0)$
which is true of the complex field $\mathbb{C}$. Of course, if $x^2 + 1 = 0$, then $(-x)^2 + 1 = 0$. So, if $i$ witnesses (*), then so does $-i$. More generally, the field $\mathbb{C}$ is invariant under complex conjugation, $z \mapsto z^{\ast}$, which is an automorphism of $\mathbb{C}$. So, if $\phi[z]$ holds in $\mathbb{C}$, then $\phi[z^{\ast}]$ holds in $\mathbb{C}$ too. This means that $i$ and $-i$, whatever they are, cannot be discerned (by monadic formulas) in $\mathbb{C}$. But this is not necessarily a problem. As soon as we have introduced "$i$" as a skolem term, we must then admit a certain amount of semantic indeterminacy.

Skolem extensions are conservative. So, we can now think of $ZFC$ as our basic foundational theory of mathematics, and we extend it to $ZFC^{sk}$ with various skolemizations. This now looks like it is dealing with strange entities, such as a unique $i$ (which is some set) and a unique $\mathbb{N}$ (which is some set). But, properly speaking, we have merely introduced new linguistic entities---skolem terms---whose semantic behaviour is indeterminate, but harmless (because of conservation).

The Skolemization Approach for abstract structures is quite attractive, both conceptually and ontologically. (I had thought of it myself years ago in fact, but I'm not happy with it.) It provides a simulacrum of reference to sui generis mathematical entities, in a way that is proof-theoretically harmless. It implements a kind of eliminative structuralism. Some of the questions raised against ante rem structuralists now become pseudo-questions. Perhaps there are still problems with it; my problems with it is that I actually do believe in the sui generis entities, and I want a theory of structure which fits with the theory of possible worlds too.

The Isomorphism Type approach identifies the abstract structure of $\mathcal{A}$ with the class
$\{\mathcal{B} \mid \mathcal{B} \cong \mathcal{A}\}$
of all isomorphic copies. One has to be careful here with large/small issues. So, $\mathcal{A}$ has to be a set-sized model. One may think of the view as a form of eliminative structuralism, if talk of classes is regarded as a facon de parler. I find it unsatisfying, but can't really think of a good knock-down argument against it, except to say that it doesn't seem to extend to a Leibniz invariant theory of worlds.

The Structure Identity/Univalence Approach is one that has emerged from the work of Awodey and Voevodsky, and has been discussed quite a lot by category theorists and type theorists over the last few years and is connected to Homotopy Type Theory. To be honest, though, I simply don't know enough category theory to make a reliable evaluation. I suspect, but I'm not entirely sure of this, that it does not in fact implement what is intended by Benacerraf or other structuralists for their "way out". Structuralists want there to be a unique $\hat{\Phi}_{\mathcal{A}}$ that all distinct isomorphic copies of $\mathcal{A}$ have in common. Univalence considers generalized notions of equivalence between mathematical objects: in particular, path equivalence, from homotopy theory. But equivalence is not identity. Mathematical structuralists, like Shapiro, Resnik and Hellman, want equivalent (i.e., isomorphic) things to have identical structure---and not merely to have things that are equivalent in one way be equivalent in some other way. Having said that, the whole approach is also bound up with the notion of "identity types"/"equality types" in intuitionistic type theory, and this is something that I find rather baffling (my own fault). I'd prefer to treat identity $=$ as primitive and undefinable. Possibly the notions "identity types"/"equality types" are best thought of as notions of indiscernibility, not identity. That is, $X$ and $Y$ are indiscernible somehow (cannot be discerned, by some discerning apparatus), rather than that $X$ and $Y$ are the same thing.

Finally, the Axiomatic Approach. My MCMP colleague Hannes Leitgeb has some unpublished work on an axiomatic theory of graphs. From conversations, I think I understand the basic framework of the approach; and, within that approach, one can state Leibniz Abstraction ("isomorpic graphs are identical") as an axiom. The other axioms build up "ante rem" abstract graphs in a way reminiscent of the set-existence axioms of Zermelo set theory (e.g., new graphs can be formed from others by "adding" nodes).

Overall, I think the Diagram Approach has definite advantages over the first three, because it yields a "Leibniz invariant theory of worlds" too. For a world $w$ may be defined as follows:
$w = \hat{\Phi}_{\mathcal{A}}[\vec{\mathsf{R}}]$
where $\mathsf{R}_0, \mathsf{R}_1, \dots$ are relations-in-intension (these must be taken as primitive). So, if
$\mathcal{B} \cong \mathcal{A}$, 
$w = \hat{\Phi}_{\mathcal{B}}[\vec{\mathsf{R}}]$
And so when isomorphic models $\mathcal{A}, \mathcal{B}$ represent worlds $w_1$ and $w_2$ with respect to the same relations, then
$w_1 = w_2$. 
This is Leibniz Equivalence, which is, I think, a constraint on what worlds are. I.e.,
Isomorphic models, with the same intensional content, represent the same world
The distinct but isomorphic models $\mathcal{A}, \mathcal{B}$, etc., are "gauge choices" for $w$, and can be chosen arbitrarily. This is what happens in General Relativity: isomorphic spacetime models $(M, g_{ab}, \dots)$ are "gauge choices" that represent the same world.

(It also seems to me that Leitgeb's axiomatic approach to abstract structure can also be extended to a corresponding theory of Leibniz invariant possible worlds, but on this I am very unsure how it would work.)

(I will probably add some links later.)


  1. I think I understand how your diagram approach can get us structures. But you suggest you want to also locate mathematical objects like 2 and 4. Are they, on your approach, places in the natural number structure? (And if so, which natural number structure? The naturals equipped only with the successor function technically form a different structure from the naturals equipped only with addition, though they obviously have much in common.) Do you have a formal way of characterising places in a structure, like you do the structures themselves?

    1. Thanks Anon,

      I'm not a structuralist - so, I think of 2 and 4 as "sui generis" objects and not to be reduced to sets or to be understood structurally. In fact, I think structuralism for arithmetic is completely wrong-headed. I think Frege's theory of arithmetic is fine; we have
      |X| = |Y| iff X ~ Y
      as a primitive axiom for cardinalitiies. Then $x$ is a natural number iff $x = |X|$, for a finite set $X$. And
      $0 = |\varnothing|$
      $1 = |\{0\}|$
      $2 = |\{0,1\}|$, etc.

      Yes, your point about the signature -- expanding/removing distinguished relations/operations -- is right and important, I think. The fact that one can introduce new relations/operations is indeed a powerful argument against structuralism. For one can delete them as well, leaving just $N$! For a structuralist view, that shouldn't happen.

      On the diagram view -- well, all of these, except Leitgeb's (probably) -- the domain/carrier set is "thrown away"; so there are, strictly speaking, no "places". However, there is the diagram formula $\Phi(\vec{X})$, and this has $n$ existentially quantified first-order variables "corresponding" to the domain elements of the model we started with: these bound first-order variables correspond to "places"/"nodes". So, somewhat loosely speaking,
      "object o occupies place p"
      is a bit like a semantic relation,
      "p is a variable that labels object o".
      And this is why labelling an "unlabelled graph" corresponds to skolemization of the diagram formula.

      (Leitgeb's view may be a "nodal realist" one, which is, I think, what Shapiro has in mind)


  2. That's interesting - I'd been tempted (and presumably I contracted this from reading structuralists) to think that the natural numbers had to in some sense be parts of and jointly constitute the structures defined over them, but I can see that that isn't actually necessary.

    How do you deal with, say, individual real numbers, though? They have to include the naturals, so they must be similar sorts of thing, but they can't be cardinalities of sets.

  3. The usual structuralist idea is to take second-order arithmetic and think of the natural number structure as ante rem structure of the unique-up-to-isomrphism (full) model. This is, in essence, Shapiro's proposal. This is a kind of implicit definition approach. But, as a "sui-generis-ist", I actually prefer Frege's set up, because it has other virtues: e.g., applicability is automatic.

    For the reals, it seems less clear how to get sui generis reals. One certainly can do this by using an abstraction principle, but it involves "completing" a dense ordering (essentially, the order-compeletion of the rationals), so I suspect that the reals cannot be divorced from their ordering. Roughly, real numbers are abstracted from Dedekind sections. (And for integers and rationals one does the same thing, using abstraction principles - for integers, the abstraction involves "completing" the additive monoid $(N,+)$, and the rationals involve completing with respect to multiplication. Integers are abstracted from pairs of natural numbers; and rationals are abstracted from pairs of integers.)

    How do you deal with, say, individual real numbers, though? They have to include the naturals, so they must be similar sorts of thing, but they can't be cardinalities of sets.

    Right, and, in fact, structuralists have problems here, concerning how to try and ensure that $\mathbb{N} \subseteq \mathbb{R}$ - this is not clear at all, if these domains belong to "different structures", as it were. Even so, though I haven't thought about the algebra involved for ages, I think one uses an embedding $e : (\mathbb{N},0,1,<,+,\times) \to (\mathbb{R},0,1,<,+,\times)$.