# Is there a formal notion of equivalence between structures with potentially different signatures?

What is the appropriate notion of equivalence between structures with potentially different signatures?

Consider an example from abstract algebra. Whether a group is defined as a pair $(X,*),$ or as a triple $(X,*,e)$ where $e$ is the identity, probably shouldn't influence the theory of groups. These two descriptions are essentially "equivalent" in some sense.

On the other hand, whether a magma is defined as a pair $(X,*),$ or as a triple $(X,*,e)$ where $e$ is allowed to be any element of $X$, probably should influence the theory, because we've chosen a distinguished element and presumably this will influence what we mean by a "magma isomorphism," for example.

As another example, consider that a topological space can be viewed as a pair $(X,\mathcal{O})$ such that $\mathcal{O} \subseteq \mathcal{P}(X)$ is closed with respect to arbitrary unions etc. Alternatively, it can be viewed as a pair $(X,\mathcal{K})$ such that $\mathcal{K} \subseteq \mathcal{P}(X)$ is closed with respect to arbitrary intersections etc. Note that, in the case where $X$ is of finite cardinality, a pair $(X,\mathcal{X})$ will be a topological space in the first sense if and only if it is a topological space in the second sense. See also, finite topological space. Nonetheless, the two descriptions are usually considered equivalent.

So here's my question. Consider two structures, $X$ and $Y$. I want to make rigorous the question, "are they essentially the same?" Supposing that such a question is ill-posed, I want to make rigorous the question, "do they define essentially the same group?" Importantly, consider the structures "in a vacuum," and not viewed as models of any particular theory.

-
Are you sure the Wikipedia link of signature is correct? :-) –  Asaf Karagila Feb 13 '13 at 13:16

Let $\mathfrak A=(A,\Sigma,(f_\mathfrak{A})_{f\in \Sigma})$ be a structure in which $A$ is the domain, $\Sigma$ is a signature, and $f_{\mathfrak A}$ is a family of interpretations of the operations of $\Sigma$.

Let $\mathfrak B=(B,\Xi,(g_\mathfrak{B})_{g\in \Xi})$ be a different structure.

Define a "structure morphism" $\mathfrak A\to\mathfrak B$ to be a function $\mu:A\to B$ such that there exists a family $(\phi_f)_{f\in\Sigma}$ of formulas in the language of $\Xi$, such that the number of free variables of $\phi_f$ is the arity of $f$ and such that for each $f\in\Sigma$ it holds that $$\forall a,a_1,\ldots,a_n \in A:\quad \Big[\mathfrak A\vDash a=f(a_1,\ldots,a_n)\Big] \iff \Big[\mathfrak B\vDash \phi_f(\mu(a),\mu(a_1),\ldots,\mu(a_1))\Big]$$

Then the composition of structure morphisms is clearly a structure morphisms, and we have a category of theory-less structures and structure morphisms where isomorphic objects could be considered to be "essentially the same".

Alternatively, you might want to consider the formulas $(\phi_f)_{f\in\Sigma}$ to be part of the morphism, but them you probably want to quotient out equvialent formulas, such that $(\mu,(\phi_f)_{f\in\Sigma})$ and $(\mu,(\psi_f)_{f\in\Sigma})$ are the same morphism iff $$\mathfrak B \vDash \forall \vec x: \phi_f(\vec x)\leftrightarrow \psi_f(\vec x)$$ in order to get a definition of composition that's not too arbitrary.

-
I like it. Surely this has been studied before? –  goblin Feb 13 '13 at 21:28

The language of category theory provides a very rigorous setting for such, and more general, equivalences. Basically, under any reasonable definition of algebraic structure (with whatever signature) there will be associated a natural notion of morphisms and these will form a category (sometimes a weak category, but let's forget about that subtlety). Now, for two categories there is a notion of isomorphism (which is the usual notion, a bijective function that preserves the structure). But categories in the wild are very rarely isomorphic while they still may be equivalent. Categorical equivalence is a bit more difficult to describe since it requires the notion of natural transformation (which can be compared to the notion of homotopy). The definition will appear in any text on categories.

To answer your question in the context of the above, it is very often the case the algebraic or topological structures defined using very different signatures or underlying machinery turn out to give rise to equivalent categories. Examples include: groups defined with a signature including an identity constant or not (the resulting categories in this case will actually be isomorphic), heaps and groups (the resulting categories will be equivalent but not isomorphic), sober space and spatial locales (yields equivalent but non-isomorphic categories), topological spaces defined using open sets vs. closed sets vs. Kuratowski closure operation (will yield isomorphic categories) and many more.

Of particular importance in modern homotopy theory (and other areas) is a more subtle situation where the relevant categories are not equivalent but the relevant $\infty$-categories are equivalent. This requires much more machinery than the above so I'll just mention the famous example due to Quillen that the $\infty$-category of simplicial sets is equivalent to the $\infty$-category of the homotopy theory of topological spaces.

Buzz words: Isomorphism of categories, equivalence of categories, Quillen model structures.

-
To be honest, I'm having a little difficulty connecting this answer to the question I was trying to ask, but probably failed to articulate. In other words, I think my question was expressed poorly. Consider two structures, $X$ and $Y$. I want to make rigorous the question, "are they essentially the same?" Supposing that such a question is ill-posed, I want to make rigorous the question, "do they define essentially the same group?" So I guess what I'm saying is, consider the structures in a vacuum, and not viewed as models of some theory. –  goblin Feb 13 '13 at 7:44
When structures are given in isolation it is very difficult to compare them, even theoretically. It is quite unnatural to consider just one single group, defined this way, and one single group defined another way, and ask if they are essentially the same. It is most natural to ask if given these two groups relate to the other structures of the same kind in the same way. This is also answered category theoretically: An object c in a category C is essentially the same as an object d in a category D, if there is an equivalence of categories F:C-->D that maps c to d. –  Ittay Weiss Feb 13 '13 at 7:49
Oh. Fair enough. Out of curiosity, is it true that two categories are equivalent if and only if their skeletons are isomorphic? –  goblin Feb 13 '13 at 7:51
yes, though in practice this is rarely a useful criterion. –  Ittay Weiss Feb 13 '13 at 7:52
Are you sure it's unnatural to compare them? Like, what if we can translate between the languages of the two structures or something? –  goblin Feb 13 '13 at 7:56