# Are isomorphic structures really indistinguishable?

I always believed that in two isomorphic structures what you could tell for the one you would tell for the other... is this true? I mean, I've heard about structures that are isomorphic but different with respect to some property and I just wanted to know more about it.

EDIT: I try to add clearer informations about what I want to talk about. In practice, when we talk about some structured set, we can view the structure in more different ways (as lots of you observed). For example, when someone speaks about $\mathbb{R}$, one could see it as an ordered field with particular lub property, others may view it with more structures added (for example as a metric space or a vector space and so on). Analogously (and surprisingly!), even if we say that $G$ is a group and $G^\ast$ is a permutation group, we are talking about different mathematical object, even if they are isomorphic as groups! In fact there are groups that are isomorphic (wrt group isomorphisms) but have different properties, for example, when seen as permutation groups.

-
What property would they be different with respect to? – Potato Jun 2 '12 at 18:42
@Potato: a property which is not captured by the notion of isomorphism you're considering! – Qiaochu Yuan Jun 2 '12 at 20:57
One example is topological spaces and metric spaces. There are metric spaces that are homeomorphic (topologically isomorphic, ie. same open sets) but that are not isomorphic as metric spaces (for example, one is complete and the other is not). – Mikko Korhonen Jun 3 '12 at 10:54

It depends on the structure you are talking about. Isomorphisms are defined to respect a given structure - for example in the category of sets the isomorphisms are just bijections. Any two sets with a bijection between them are virtually indistinguishable - the elements are just labelled differently. However, in the category of groups, the isomorphisms respect the group structure, so given two isomorphic groups they are indistinguishable as groups - i.e. if I multiply two elements in one group, the answer is the corresponding multiplication in the isomorphic group.

Basically isomorphisms will preserve the structure that is inherent in the maps you define between objects in a given category. If you want your maps to preserve a certain property, you define them that way.

For an example, if you consider metric spaces, you can consider only (continuous) functions between then which preserve distances, or those that do not have to. The notion of isomorphism is different in both cases.

-
Just to add to the example at the bottom, in $\mathbb{R}^2$ you can have an open disc of radius 1 isomorphic to an open disc of radius 2 as topological spaces (both with the subspace topology of $\mathbb{R}^2$) but distances are not preserved. – Paul Slevin Jun 3 '12 at 18:28
Good examples. I'd like to point out that --- while bijections are isomorphisms of sets --- a set theorist can often distinguish between two isomorphic' sets. For example, one might be transitive and the other not, or one might be $\in$-well-founded and the other not (in the absence of the Axiom of Foundation). Set theorists are often interested in combinatorial properties of sets that aren't invariant under bijection, in the same way that a group theorist is probably interested in properties of groups that aren't invariant under bijection. – Zach N Jun 5 '12 at 19:52
...but a group theorist is unlikely to be interested in a property of groups that isn't invariant under group isomorphism. – Zach N Jun 5 '12 at 19:52
@ZachN : sorry, but I do not think it is so. I think that a group theorist would notice that two permutation groups are not (necessarily) similar even if they are isomorphic as abstract groups. – Oo3 Jun 6 '12 at 12:17

You should learn some category theory. It provides some elegant language for discussing the issues you're running into.

In fact there are groups that are isomorphic (wrt group isomorphisms) but have different properties, for example, when seen as permutation groups.

As I said above, if you want to talk about properties of permutation groups which are not captured as properties of groups, then you don't want to talk about isomorphism of groups but isomorphism of permutation groups. More precisely, we can define the category $\text{GrpAct}$ of group actions and talk about isomorphism in this category. This is the category whose objects are triples $(G, X, \rho)$ where $G$ is a group, $X$ is a set, and $\rho : G \to \text{Aut}(X)$ an action of $G$ on $X$; and whose morphisms $(G_1, X_1, \rho_1) \to (G_2, X_2, \rho_2)$ are pairs $(\phi, f)$ where $\phi : G_1 \to G_2$ is a homomorphism and $f : X_1 \to X_2$ is a set map satisfying $$\rho_1(g)(x) = \rho_2(\phi(g))(f(x))$$

for all $g \in G_1, x \in X_1$. Isomorphism in this category captures isomorphism of permutation groups (the special case where $\rho$ is injective), which is a stronger condition than isomorphism of abstract groups. More precisely, there is a forgetful functor

$$F : \text{GrpAct} \to \text{Grp}$$

sending a group action $(G, X, \rho)$ to the group $G$, and the basic phenomenon you are observing is that two objects $a, b \in \text{GrpAct}$ may not be isomorphic even if $F(a)$ and $F(b)$ are. This is not surprising and is in some sense typical.

Analogously (and surprisingly!), even if we say that G is a group and G∗ is a permutation group, we are talking about different mathematical object, even if they are isomorphic as groups!

From the perspective of category theory, the problem is that groups and permutation groups live in different categories. To compare them, you need to use the forgetful functor $F$, and then you need to distinguish between a permutation group (which lives in $\text{GrpAct}$) and the corresponding abstract group (which lives in $\text{Grp}$) as mathematical objects.

To use a computer science analogy (well, more than an analogy, but...), the forgetful functor typecasts between the types GroupAction and Group, and the isEqual operator is defined differently for the two types (and does not compare a GroupAction and a Group`; you need to typecast first).

-
+1: I like the comparison between casting operators and forgetful functors. – ItsNotObvious Jun 4 '12 at 16:40
I have to admit that indeed categories make it simpler to understand what type the morphisms are, but this is equally simple (and clear) (in many of the cases) to just say "models of theory $T$" or "$\cal L$-structures"... – Asaf Karagila Jun 5 '12 at 20:28

As Paul and Jyrki wrote, isomorphism preserves a structure. Not all possible structures.

If we only consider sets (without structure) then isomorphism is simply a bijection. In this sense $\mathbb N$ and $\mathbb Z$ are indeed isomorphic, since both are countable. If we now want an order isomorphism, then $(\mathbb N,<)$ and $(\mathbb Z,<)$ are no longer isomorphic (assuming that $<$ is the natural order, that is).

Another relatively simple example: consider the fields $\mathbb Q$ and $\mathbb Q(\pi)$. As ordered sets these are isomorphic, every countable, dense linear order without endpoints is isomorphic to $\mathbb Q$. However if you now want the isomorphism to respect the field operations then we cannot find such isomorphism since one of them contains a transcendental element and the other does not.

This is why when talking about isomorphism it should be specified what structure we preserve, or it may be clear from context.

-

I'm not sure, if this is what you are referring to, but here goes...

There are questions that are easy to decide in one structure, but much more difficult in another isomorphic structure. The discrete logarithm problem comes to mind. The additive group $G_1=\mathbf{Z}_{502}$ is generated by $5$, and to a given $x\in G_1$ finding a multiplier $n$ such that $$5n=(5+5+\cdots 5)=x$$ is easy, as the generalized Euclidean algorithm will do it for us.

The multiplicative group $G_2=\mathbf{Z}_{503}^*$ is also cyclic of order $502$ and also generated by $5$. Yet, to a given $x\in G_2$ the problem of finding an exponent (now an exponent as the group is multiplicative) $n$ such that $$5^n=(5\cdot5\cdot5\cdots5)=x$$ is more difficult. The difference in difficulty becomes more pronounced as the size of the groups grows.

The problem is that describing an isomorphism is not enough to translate a question from one structure to the other, if you cannot also describe its inverse.

-
Or, even simpler, consider consider naturals represented normally vs. completely-factored form, i.e. $\rm\:n \to [a,b,c,\cdots],\:$ where $\rm\:n = 2^a 3^b 5^c\cdots.\:$ It is trivial to factor integers in the latter monoid, but not in the former. – Bill Dubuque Jun 2 '12 at 21:02
One way to describe this situation is to say that we want to work in the category of groups but in practice we work in the category of "computer-describable groups" whose morphisms are, say, polynomial-time algorithms computing homomorphisms between such groups, and a polynomial-time homomorphism need not have a polynomial-time inverse even if it is invertible as a group homomorphism... – Qiaochu Yuan Jun 4 '12 at 16:36