Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

share|improve this question
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.