Saturday, 17 August 2013

The Abstract Structure of an Omega Sequence

Suppose that $(\omega, <)$ is the usual $\omega$-sequence where $\omega$ is the set of finite von Neumann ordinals and $<$ is their order (i.e., $\alpha < \beta$ iff $\alpha \in \beta$). On the Diagram Conception, the abstract structure of $(\omega, <)$ is the proposition expressed by the following infinitary diagram formula $\Phi(X,Y)$:
$\exists V[\bigwedge_{i \neq j} (x_i \neq x_j) \wedge \bigwedge_{i \in \omega} Xx_i \wedge \forall x(Xx \to \bigvee_{i \in \omega} (x = x_i)) \wedge
 \bigwedge_{i,j \in \omega} \pm_{ij} Yx_i x_j ]$
where $V = \{x_0, x_1, \dots\}$ and $\pm_{ij}Yx_ix_j$ is $Yx_ix_j$ if $i < j$ and $\neg Yx_ix_j$ otherwise.

Categoricity ensures that, for any $(A,R)$ (a relational model, with a single binary relation $R \subseteq A^2$), we have:
$(A,R) \models \Phi(X,Y)$ if and only if $(A,R) \cong (\omega,<)$.
On a certain version of structuralism, "ante rem structuralism", there would be an abstract, "ante rem", $\omega$-sequence: and this would itself be an $\omega$-sequence, say
$\Omega = (N, <_{N})$,
whose domain $N$ contains "nodes". But this approach seems to face the following problem, which is a modification of Einstein's "Hole argument". Let
$\pi : N \to N$
be any non-trivial permutation of the nodes and let $\pi_{\ast}[<_N]$ be the resulting ordering and let
$\pi_{\ast}\Omega = (N, \pi_{\ast}[<_N])$. 
$\pi_{\ast}\Omega \neq \Omega$
$\pi_{\ast}\Omega \cong \Omega$
So, which one is the "real" abstract, ante rem, $\omega$-sequence?

Instead, I think the abstract structure of any $\omega$-sequence is not itself an $\omega$-sequence; rather, it's a purely structural, infinitary, second-order proposition, whose models are the $\omega$-sequences.

[UPDATE (18th August 2013):
Robert Black in the comments below alerted me to this mini-"Hole"/permutation argument appearing before, in Geoffrey Hellman's article,
Hellman, G. 2007: "Structuralism", in Shapiro 2007 (ed.), Oxford Handbook of the Philosophy of Mathematics and Logic
Geoffrey puts it like this (Here $SGS$ is Shapiro's sui generis "ante rem" structuralism):
In fact, $SGS$, seems ultimately subject to the very objection of Benacerraf ["What Numbers Could Not Be"] that helped inspire recent structuralist approaches to number systems in the first place. Suppose we had the ante rem structure for the natural numbers, call it $\langle N, \varphi, 1 \rangle$, where $\varphi$ is the privileged successor function, and $1$ the initial place. Obviously, there are indefinitely many other progressions, explicitly definable in terms of this one, which qualify equally well as referents for our numerals and are just as “free from irrelevant features”; simply permute any (for simplicity, say finite) number of places, obtaining a system $\langle N, \varphi^{\prime}, 1^{\prime} \rangle$, made up of the same items but “set in order” by an adjusted transformation, $\varphi^{\prime}$.
Why should this not have been called “the archetypical ante rem progression”, or “the result of Dedekind abstraction”?
We cannot say, e.g., “because 1 is really first”, since the very notion “first” is relative to an ordering; relative to $\varphi^{\prime}$, $1^{\prime}$, not $1$, is “first”. Indeed, Benacerraf, in his original paper, generalized his argument that numbers cannot really be sets to the conclusion that they cannot really be objects at all, and here, with purported ante rem structures, we can see again why not, as multiple, equally valid identifications compete with one another as “uniquely correct”. Hyperplatonist abstraction, far from transcending the problem, leads straight back to it. (Hellman, "Structuralism", pp. 11-12 in the preprint).
My $\Omega$ above corresponds to Hellman's $\langle N, \varphi, 1 \rangle$ and my $\pi_{\ast}\Omega$ corresponds to Hellman's $\langle N, \varphi^{\prime}, 1^{\prime} \rangle$.]


  1. This argument isn’t new, (it’s die to Geoffrey Hellman, I think) and there’s a pretty obvious strategy for answering it. *The* pure abstract omega-sequence is supposed to carry no extra structure at all. Now if the permuted version is not identical with the original version, then that can only be because it still carries with it the old ordering as well, in other words it’s got extra structure, and is therefore not *the* pure abstract one.

    1. I am not (at the moment) convinced by this answer. According to the ante rem structuralist, the nodes of the omega-sequence are themselves fully-fledged objects. If so, then there is the permutation π(0)=1, π(1)=0, π(n)=n for n>1 and, hence, there is the distinct isomorphic structure π∗Ω = (N,<*) in which 1<*0 (<* being Jeff's π∗[<_N]). The purported answer (as I'm (mis?)understanding it) suggests that somehow π∗Ω simply morphs back into Ω. But how, if the nodes of Ω are fully-fledged objects? How is π∗Ω not a wholly distinct (albeit isomorphic) structure in which the objects 0 and 1 — the first and second nodes of Ω — are permuted? The difficulty suggests to me that the idea of the ante rem structuralist that the nodes of Ω are themselves objects doesn't sit well with the idea that Ω is a "pure abstract structure".

  2. Hi Robert, thanks - do you know where Hellman has this? Shapiro might have discussed something akin to this too, I guess. It'd be interesting to see how it's discussed. Leon Horsten mentioned something like this to me too, several years ago, when I mentioned permutations, so maybe Leon?
    It works against the idea that the pure abstract omega-sequence is itself a model, in the conventional sense: that is, a structured set, something of the form "a domain+structure".
    (I'm fairly sure that Hannes Leitgeb's theory of abstract graphs can avoid this "permutation problem", and can state "isomorphic abstract graphs are identical".)



  3. I think you'll find it in Hellman's 'Structuralism' article in the Shapiro _Handbook_.

  4. Great - thanks, Robert. I'll see if I can find it.


  5. Thanks again, Robert - I found it and I've updated the post and included Hellman's formulation of this permutation argument.



  6. This is obviously incorrect. If omega sequences were permutationally isomorphic, then I'd agree, but as it stands the infinitary properties of these sequences precludes that.