# Mostowski collapses and universal extensional relational classes

In the following, by a relational class I mean a pair$^1$ $(A,R)$, where $A$ is a class and $R \subseteq V \times V$ is a class relation, such that $R$ is well-founded and set-like on $A$ ($R$ is not assumed to be extensional). Homomorphisms of such classes are defined in the obvious way. Let $G : (A,R) \to (M,\in)$ be the Mostowski collapse of $(A,R)$, i.e. $G(x) = \{G(y) : y \in A , y R x\}$. Is this a functorial construction?

So let $f : (A,R) \to (A',R')$ a homomorphism, does this induce a homomorphism $(M,\in) \to (M',\in)$, such that the obvious diagram commutes? For this we have to check $G(x)=G(y) \Rightarrow G'(f(x))=G'(f(y))$ for all $x,y \in A$. Is this true?

If this works out fine and $R'$ is extensional, then $f$ extends to a homomorphism $(M,\in) \to (A',R')$. Is this extension unique? If yes, we have found a functor which is left-adjoint to the forgetful functor from relational classes to extensional classes.

If this does not work out, what about adding the assumption of transitivity? And if this also does not work, is there nevertheless some left-adjoint, which is then different from the Mostowski collapse?

$^1$ In $ZF$ we can't define pairs of classes, and perhaps the categories above are not well-defined. This does not affect the content of my question, which can be translated to a well-formed statement in $ZF$.

The answer to your first question is no, unfortunately, it is not functorial.

Here is a comparatively simple counterexample. The idea is that two objects in $A$ can collapse to the same point, but gain new elements in $A'$ that differentiate them. Let $A=\{a,b\}$ have two objects, with $R$ the empty relation. So the Mostowski collapse of $(A,R)$ maps both $a$ and $b$ to the emptyset $\varnothing$. Let $A'=\{a,b,c\}$, with $c\mathrel{R'}b$, but otherwise $R'$ is trivial. So the Mostowski collapse of $(A',R')$ maps $a,c\mapsto\varnothing$ and $b\mapsto\{\varnothing\}$. Let $f:A\to A'$ be the inclusion map, which is a homomorphism, since $a$ and $b$ have no relation with respect to $R$ or $R'$. Since we have $G(a)= G(b)$ but $G'(f(a))\neq G'(f(b))$, there can be no commutative diagram here.

But why not insistin on extensionality? In the category of extensional class relations, that is, if your structures $(A,R)$ and $(A',R')$ satisfy extensionality, then the Mostowski collapse is functorial. This is because $G$ and $G'$ are isomorphisms, and it is easy to see that there is the induced homomorphism $h:M\to M'$ defined by $h(G(a))=G'(f(a))$. This is a homomorphism since $G(a)\in G(b)\iff a\mathrel{R} b\iff f(a)\mathrel{R'}f(b)\iff G'(f(a))\in G'(f(b))$, and the diagram commutes by definition.

For the second question, in this extensional case, since $(M',{\in})$ is isomorphic to $(A',R')$, then we get a map $(M,{\in})\to (A',R')$, as you say. It is just the map $h\circ G^{-1}$. In general, there is not a unique map from $(M,{\in})$ to $(A',R')$, however, since for example, when $(A,R)$ is a well-order, then the Mostowski collapse is an ordinal, but if $(A',R')$ is a longer ordinal, there could be many homomorphisms of $(M,{\in})$ to $(A',R')$, since these are just the order-preserving maps. But this map will be unique such that the diagram commutes, since it is determined by those isomorphisms. (But I think you were not actually asking this about the extensional case. I'm not sure what you mean by "adding transitivity", since the Mostowski collapse of any structure is a transitive set, even when the relations are not extensional.)

If you really don't want extensionality, then it would also be sensible to restrict the homomorphism concept to functions $f:A\to A'$ which not only preserve the relation (in both directions), but which also respect equivalence of predecessors; this amounts to being well-defined on the Mostowski collapse. That is, in this category, we think of $\langle A,R\rangle$ as a code for its Mostowski collapse, and the notion of homomorphism should respect that. In this case, the Mostowski collapse will again be functorial.

Lastly, let me mention that several other restrictions of your homomorphism concept are often studied. Namely, in set theory the concept of a $\Sigma_n$-elementary map is prominent for natural numbers $n$. Even $\Sigma_0$-elementary goes beyond the basic concept of homomorphism that I think you intend, but we are often interested in $\Sigma_1$-elementary embeddings or even fully elementary embeddings. Many large cardinal concepts, for example, are characterized by the existence of such embeddings defined on the entire universe into a transitive class.

There seems to be a reasonable category-theoretic question here, about morphisms between well founded relations and the reflection into the full subcategory of reflective ones.

I am a categorist and I think Martin is or was an algebraist and therefore a user of category theory. So please can we forget the set-theoretic notation and jargon. I don't see what "obvious diagram" is meant in the question. It is not possible to get a categorical understanding of a topic by wrapping the existing symbolic notation (especially from set theory) in a few diagrams.

In 1974 at the top of the agenda in category theory was to show that elementary toposes could do everything that sets could do. In particular, several authors gave translations of higher order logic into the axioms for a topos.

Gerhard Osius was the one person who took $$\in$$-structures seriously and reconstructed Zermelo set theory within any elementary topos.

He did this by representing any binary relation $$(X,\prec)$$ as a coalgebra $$\alpha:X\to{\mathcal P} X$$ for the powerset functor, with $$\alpha(x) \;=\; \{y|y\prec x\} \quad\mbox{or}\quad y\prec x\iff y\in\alpha(x).$$ More significantly, he observed that the subset relation from set theory is a coalgebra homomorphism. Such homomorphisms are also characterised as bisimulations and in fact Dimity Mirimanoff had recognised in 1917 that subset inclusions are like this, calling them "isomorphismes".

It is easy to see that $$(\prec)$$ is extensional iff $$\alpha$$ is mono. Osius used recursion, in the form of a 3vs1 coalgebra-to-algebra homomorphism, instead of well-foundedness. The latter was implicit in his work and that of Christian Mikkelsen (who gave a categorical proof of the recursion theorem).

My work in the 1990s gave the definition of a well founded coalgebra for any endofunction of $$\mathbf{Set}$$ that preserves inverse images and proved the recursion theorem for them. In this decade I relaxed the condition on the functor to preserving monos and identified the properties that are required of the category to prove the recursion theorem.

That is enough background to formulate the original question properly: in the category of well founded coalgebras, does the inclusion of the full subcategory of extensional ones have a left adjoint?

The set-theoretic result is attributed to Andrzej Mostowski. It uses recursion and the axiom-scheme of replacement.

However, all that we need, at least for the basic situation, is a quotient of the carrier, which any ordinary mathematician would obtain using an equivalence relation, with no need for Replacement. This is what I did in my 1996 JSL paper.

The equivalence relation is defined by co-recursion, so we could take this step-by-step. The successive quotients are obtained by factorising the structure map $$\alpha$$ as an surjective function followed by an injective one. We obtain the extensional reflection as the fixed point of this construction.

Now this suggests making serious use of categorical tools, in particular replacing "monos" with a factorisation system. This is what I have done in my recent paper Well Founded Coalgebras and Recursion.

The follow-up paper, called Ordinals as Coalgebras applies all of this theory with posets instead of sets and examines various notions of constructive ordinals.

Using the flexibility of category theory, the "Mostowski" extensional quotient and (some version of) the "ordinal rank" are examples of the same construction.

However, in the case of the "plump" ordinals, the iterated factorisation does not converge. $$\omega\cdot 2$$ does not exist in the simplest non-classical elementary topos.

Set theorists will tell me that I need the axiom-scheme of replacement to do it, but my intention is to turn that argument on its head. General transfinite iteration of functors can be expressed using the same categorical ideas as the extensional reflection. I propose this as the replacement for replacement in the native language of category theory, which is to say using adjointness in foundations, as Bill Lawvere taught us.

All of my own work mentioned above, together with full references for Osius and others, is on my website: http://www.paultaylor.eu/ordinals/