## Friday, 27 July 2012

### Individuation for Structured Sets and Leibniz Abstraction

The notion of a structured set appears throughout mathematics. A simple example might be a linear ordering $(X, \leq)$ of some kind. In this case, $X$ is called the domain, or carrier set. And then $\leq$ is simply a binary relation on $X$.

Note that we normally represent this structured set as $(X, \leq)$. That is, as the ordered pair of the carrier set and the distinguished relation. More generally, a structured set is represented as an ordered tuple,
$(X, R_1, \dots, R_n)$
So far as I can see, nothing hinges on the fact that there are finitely many distinguished $R_i$s. One might have an infinite sequence $(R_{\alpha} \mid \alpha \in I)$ of distinguished relations, but it is simpler to consider the case of a "finite signature", as the lingo puts it. So, in the simplest case of a domain $X$ and a single distinguished relation $R$, we have a structured set usually represented by,
$(X, R)$
One might wonder why we take the ordered pair of $X$ and $R$ in that order. Could we not take
$(R, X)$
as a representation of the structured set with domain $X$ and relation $R$?
The answer seems to be: yes. In fact, all that seems to be required is that given the "components" -- the domain $X$ and the distinguished relation $R$ - the corresponding structured set is uniquely determined.
So, instead of representing the structured set with domain $X$ and distinguished relation $R$ as the pair $(X,R)$, let us write $\sigma_{X,R}$ to mean "the structured set whose domain is $X$ and whose distinguished relation is $R$. Then the sole individuation condition is:
Individuation Principle for Structured Sets
$\sigma_{X,R} = \sigma_{X^{\prime}, R^{\prime}}$ iff $X = X^{\prime}$ and $R = R^{\prime}$.
Taking $\sigma_{X,R}$ to be the ordered pair $(X,R)$ verifies this, and also taking it to be the ordered pair $(R,X)$ would verify it too.
So: structured sets are the same structured set exactly if they have the same domain and their distinguished relations are identical.

But this clearly allows that structured sets can be distinct but isomorphic. In other words, there will be lots of cases where,
$\sigma_{X,R} \neq \sigma_{X^{\prime}, R^{\prime}}$ and $\sigma_{X,R} \cong \sigma_{X^{\prime}, R^{\prime}}$
Example. Consider $(\mathbb{N}, \leq)$ and let $\pi : \mathbb{N} \rightarrow \mathbb{N}$ be the transposition that swaps $0$, and $1$, leaving all other $n \in \mathbb{N}$ alone. Then define:
$n \leq^{\prime} k$ iff $\pi(n) \leq \pi(k)$.

Clearly, the new ordered set $(\mathbb{N}, \leq^{\prime})$ is distinct from $(\mathbb{N}, \leq)$, since $\leq$ is extensionally distinct from $\leq^{\prime}$. However, $(\mathbb{N}, \leq^{\prime}) \cong (\mathbb{N}, \leq)$, since the transposition $\pi$ is an isomorphism.

That is, structured sets violate the following indiscernibility principle for abstract structures:
If $A_{X,R} \cong A_{X^{\prime}, R^{\prime}}$ then $A_{X,R} = A_{X^{\prime}, R^{\prime}}$
So, how do we find entities that play this role?
It looks like they can't be structured sets, for structured sets can be distinct but isomorphic. (On the other hand, one might argue that the abstract structure $A_{X,R}$ might not be required to be the same structured set as one started with! So which structured set is it? What is its domain? One idea is that one has a background universe of "nodes" (or maybe collections $D_{\kappa}$ of nodes, for any given cardinality $\kappa$), from which to build abstract structured sets. This approach might work. I'm not sure.)
To generalize somewhat, suppose that $\mathcal{M}$ and $\mathcal{M}^{\prime}$ are structured sets. We'd like to identify $A_{\mathcal{M}}$ and $A_{\mathcal{M}^{\prime}}$ as the corresponding abstract structures, but we don't know what such a thing is. All we know is that we want to have an individuation condition, a kind of abstraction principle,
Leibniz Abstraction
$A_{\mathcal{M}} = A_{\mathcal{M}^{\prime}}$ iff $\mathcal{M} \cong \mathcal{M}^{\prime}$.
That is, given structured sets, the abstract structures are identical exactly if the structured sets are isomorphic. However it is extremely unclear how to define such entities $A_{\mathcal{M}}$ satisfying the required condition.