Non smallness of the set of anafunctors without AC?

Trying to construct a model category constructively is difficult. One often mention the fact that without the axiom of choice one cannot prove that the localization of the category of small categories at weak equivalence (i.e. functor which are fully faithful and essentially surjective) is locally small (ie. have small hom set) as an argument for the non existence of a model structure on cat that have these weak equivalences.

But actually proving that this cannot be proved is not easy:it can be shown that very weak choice principle like WISC or Makkai "small cardinality selection axiom" are enough to implies that this localization is locally small and we don't have that many model where those axioms fails.

My question is: Are we actually able to prove that the local smallness of this localization cannot be proved in ZF ?

I will now give some details on this, for non category theory people:

Without the axiom of choice, Makkai has introduced the notion of 'anafunctor' which generalize the notion of functors in order to describe explicitely this localization.

In fancy words, his definition can be formulated as follow: The category of categories is a Brown category of fibrant objects, with fibrations being the isofibrations and weak equivalences being the fully faithful and essentially surjective functors (trivial fibrations are hence the functors which are fully faithful and surjective on objects).

Anafunctors $X \rightarrow Y$ are then spans $X \leftarrow Z \rightarrow Y$ where $Z \rightarrow X$ is a trivial fibrations, and we know by the work of Brown that homotopy class of such spans compute the localization of the category of categories at 'weak equivalences'.

In a more down to earth approach, and following Makkai's paper:

The idea of Makkai is that an anafunctor is like a functor but where the image of an object is not uniquely defined, but, following classical categorical philosophie, only well defined up to unique isomorphism.

More precisely: If $X$ and $Y$ are (small) categories, an anafunctor from $X$ to $Y$ is the data of:

-A set $|F|$ and a surjective map $\pi: |F| \rightarrow |X|$ (where $|X|$ denotes the set of objects of $|X|$).

-On consider $F$ as a category over $X$ such that $\pi$ is extended into a fully faithful functor $\pi:F \rightarrow X$ (i.e. $Hom_F(a,b):=Hom_X(\pi(a),\pi(b))$.

-One has a functor $f$ from $F$ to $Y$.

This fits the idea explained above as follow: if you have an object $x \in X$, you compute its image by $F$ by taking any $z \in |F|$ such that $\pi(z)=x$ and taking the image of $z$ by $f$. If one chose of a different $z'$ then there is a unique isomorphism between $z$ and $z'$ which is send to the identity of $x$ and this induce a canonical isomorphism between $f(z)$ and $f(z')$.

I refer to the paper of Makkai linked above for how anafunctor are composed as it is not relevant to the question...

The only thing we need to know here is when two anafunctors are isomorphic (equivalent): Let $F$ and $G$ be two anafunctors from $X$ to $Y$. One can construct a category $F \times_{X} G$ whose set of objects is:

$$|F| \times_{|X|} |G| = \{ (x,y), x \in |F|, y \in |G|,, \text{ whose images in X are equal}\}$$

and whose morphisms are the morphism between the projection to $X$. One then has two functors from $F \times_X G$ to $Y$ given respectively by $f$ and $g$ composed with the projection to $F$ and $G$.

An isomorphism of anafunctors is given by an isomorphism between these two functors from $F \times_X G$ to $Y$. More explicitly:

for each $x \in |F|, y \in |G|$ having the same image in X, one has an isomorphism $\theta_{x,y}: f(x) \rightarrow g(y)$ in $Y$, such that for every $a:x \rightarrow x'$ an arrow in $F$, and $b: y \rightarrow y'$ an arrow in $G$ such that $a$ and $b$ have the same image in $X$ then one has a commutative square:

$$\theta_{x',y'} \circ f(a) = g(b) \circ \theta_{x,y}$$

Then the localization of the category of small categories at weak equivalences has the 'set' of isomorphisms class of anafunctors between $X$ and $Y$ has morphism from $X$ and $Y$, hence the claim we want to disprove is: for all small category $X$ and $Y$ there is only a set of isomorphism class of anafunctor from $X$ to $Y$.

More precisely: one wants to have a set of anafunctors such that any anafunctor is isomorphic to one in this chosen set.

Let me mention a special case that will probably be easier to understand and which I think is equivalent to the general case:

If $X$ is a discrete category (a set, seen as a category with only identity arrow) and $Y=BG$ is a category which have only one object with a group $G$ of endomorphism.

An anafunctor from $X$ to $Y$ is the data of a set $\pi:E \twoheadrightarrow X$ together with for each $a,b \in E$ such that $\pi(a)=\pi(b)$ an element $g_{a,b} \in G$ such that $g_{a,b} =g_{b,a}^{-1}$ , $g_{a,a}=1_G$ and $g_{a,b} g_{b,c} = g_{a,c}$ (indeed $g_{a,b}$ is the image of the unique morphism from $a$ to $b$ corresponding to the identity of $\pi(a)$).

Two such anafunctors $(E,g)$ and $(E',g')$ are isomorphic if and only if there exists a function $t_{a,a'}$ which maps any pairs $(a \in E,a'\in E')$ having the same image in $X$ to $t_{a,a'} \in G$ such that $g_{a,b} t_{b,b'}= t_{a,b'}$ and $t_{a,a'} g'_{a',b'} = t_{a,b'}$.

Moreover, Makkai (still in the paper linked above) has a theory of "saturated anafunctor" which construct for each such anafunctor an isomorphic "saturated anafunctor" which in this case are anafunctors of the form:

$\pi : E \twoheadrightarrow X$ is a surjection and $E$ caries an action of $G$ such that for each $a,b \in E$ having the same image in $X$ there is a unique $g \in G$ such that $g.b= a$. One then define $g_{a,b}$ has being this unique $g$.

two such anafunctor are isomorphic if and only if they are isomorphic as set over $X$ endowed with a $G$ action.

Here again, what we want to prove more precesely is that there exists a set $F$ of anafunctors such that any anafunctor is isomorphic to one in this set.

Such anafunctor are generally called principale $G$-bundle over $X$, or $G$-torsor over $X$, and their isomorphism class form Giraud's definition of the non-abelian cohomology $H^1(X,G)$ of the discrete space $X$.

Andreas Blass has show that the triviality of all the $H^1(X,G)$ is equivalent to the axiom of choice, but here we just want to prove that they are sets.

• Why can't you show that WLOG the objects of $Z$ are a subset of $X \times Y$, and then use powerset to show it is locally small? This seems too easy, but I can't see why it fails. – aws Mar 14 '17 at 11:37
• I don't think that works. If you start from a general $Z$, then you construct $Z'$ whose objects are the images of objects of $Z$ in $|X| \times |Y|$ (by $|X|$ I mean the object of $X$). As the functors from $Z$ and $Z'$ to $X$ has to be an equivalence morphisms are just morphisms between the $X$ components, but I don't see how you construct a functor $Z' \rightarrow Y$, you know what to do on objects, but you have lost all the information of the action on morphisms... (it is encoded in the choice of a $z \in |Z|$ over $(x,y)$) – Simon Henry Mar 14 '17 at 13:30
• I wish I had the time to understand this question. – Asaf Karagila Mar 14 '17 at 15:02
• @AsafKaragila : I'm lacking the time right now, but tomorrow I'll edit the question to include more explicit definitions of anafunctors and equivalences of anafunctors not relying on Brown categories in case it helps. – Simon Henry Mar 14 '17 at 16:51
• I've been wondering this since my work in this area. Thanks for asking this! – David Roberts Mar 31 '17 at 23:13

I don't know much about class forcing, so I'll just sketch a Frankel Mostowski style model that I think gives a model of $\mathbf{ZFA}$ where local smallness fails.

We take the domain to be the discrete category on $\mathbb{N}$ and the codomain to be the group $\mathbb{Z}/2$, i.e. the category with one object, and a single nontrivial morphism, which we'll write as $g$, and the identity, $1$. We'll show that local smallness for this domain and codomain implies a certain set theoretic statement and then show that the statement is independent of $\mathbf{ZFA}$.

Say that a family of pairs is a countable family of sets $X = (X_n)_{n \in \mathbb{N}}$ such that for every $n$, $X_n$ has cardinality $2$. We say two families of pairs $X$ and $Y$ are isomorphic if there is a choice of bijections for each $n$, $\phi_n \colon X_n \rightarrow Y_n$. Note that since there exists a bijection $X_n \cong 2$ for every $n$, if we assume countable choice then we can choose such a bijection for each $n$ to show $X$ is isomorphic to the family of pairs constantly equal to 2. We'll show that local smallness implies there is a set of families of pairs $P$ that contains a representative of every isomorphism class.

Given a family of pairs $X$, we view it as an anafunctor from $\mathbb{N}$ to $\mathbb{Z}/2$ as follows. Let $Z$ be the category with objects $\coprod_{n \in \mathbb{N}} X_n$ and morphisms consisting of isomorphisms $f_n \colon x \rightarrow y$ for every $n$ and for $x \neq y \in X_n$ and otherwise just identity morphisms. We are forced to take $F(f_n) = 1_n$ and we take $G(f_n) := g$ (the nontrivial morphism in $\mathbb{Z}/2$). Then we have

Lemma Two families of pairs are isomorphic if and only if the corresponding anafunctors are equivalent.

Proof Suppose the ananfunctors corresponding to $X$ and $Y$ are equivalent. Then, by the characterisation of equivalence in the question, there is a natural transformation $\theta$ between the two functors $X \times_{\mathbb{N}} Y \rightarrow \mathbb{Z}/2$. Given $x \in X_n$ and $y \neq y' \in Y_n$, note that the naturality of $\theta$ implies that one of $\theta_{x, y}$ and $\theta_{x, y'}$ must be $g$ and the other 1. We define $\phi_n(x)$ to be the unique $y \in Y_n$ such that $\theta_{x, y} = 1$. This gives a choice of bijections. The converse is similar.

Lemma Any anafunctor from $\mathbb{N}$ to $\mathbb{Z}/2$ is equivalent to one given by a family of pairs.

Sketch proof Suppose we are given a category $Z$ and functors $F \colon Z \rightarrow \mathbb{N}$ and $G \colon Z \rightarrow \mathbb{Z}/2$ making an anafunctor. We define an equivalence relation $\sim$ on each fibre $F^{-1}(n)$. Note that since $F$ is full and faithful, for any $x, x' \in F^{-1}(n)$ there is a unique isomorphism $f \colon x \rightarrow x'$. We set $x \sim x'$ if $G(f) = 1$. This gives an equivalence relation and there are at most two equivalence classes. We define a family of pairs $X$ by taking $X_n$ to be the quotient if there are two equivalence classes and to be $2$ if there is only one equivalence class. These turn out to be equivalent anafunctors.

The above two lemmas together imply that local smallness implies the existence of a set of families of pairs containing a representative of every isomorphism class.

We now sketch a proof that this is independent of $\mathbf{ZFA}$. In the metatheory assume choice, and the existence of an inaccessible, $\kappa$. Let $G$ be the group $(\operatorname{Sym}(2))^\kappa$. Then $G$ acts on $\kappa \times 2$ by $g.(\alpha, i) := g(\alpha).i$, and this restricts to an action on $\alpha \times 2$ for every $\alpha < \kappa$.

We define $V_{\alpha, \beta}$ for $\alpha, \beta < \kappa$ by recursion on $\alpha$. Take $V_{\alpha + 1, \beta} := \mathcal{P}((\beta \times 2) \amalg V_{\alpha, \beta})$ and take unions at limit stages. We then set $V := \bigcup_{\alpha, \beta < \kappa} V_{\alpha, \beta}$. The action of $G$ on $\kappa \times 2$ lifts to an action on $V$ in the usual way, and we take $V^{\mathrm{fs}}$ to be the subset of elements with hereditary finite support relative to $\kappa \times 2$. I think $\mathbf{ZFA}$ should hold in this model.

Now to sketch a proof that there is no set of families of pairs containing a representative of every isomorphism class in the model. Suppose for a contradiction that $P$ is such a set. Let $\lambda < \kappa$ be such that $P \in V_{\lambda, \lambda}$. Define a family of pairs $X$ by taking $X_n$ to be the pair of atoms $\{(\lambda + n, 0), (\lambda + n, 1) \}$. By assumption there is a family of pairs $Y$ in $P$ and a function $\phi \colon \coprod_\mathbb{N} Y_n \rightarrow X_n$ giving a bijection for each $n$. Since $\phi$ has a finite support, there must be some $N$ such that $\lambda + N$ contains a support for $\phi$. Let $g \in G$ be the element that swaps $(\lambda + N, 0)$ and $(\lambda + N, 1)$ and fixes everything else. Then $g$ must fix both $\phi$, and everything in the transitive closure of $P$. So for $y \in Y_N$ we have $g.(\phi(N, y)) = \phi(N, y)$ giving a contradiction.

• So you want a proper class of Russell sets, such that there is no set of "all Russell cardinals". This is doable. You don't need inaccessible cardinals or whatnot. I can sketch a class forcing argument if you want. – Asaf Karagila Mar 30 '17 at 18:03
• Yes; if I'm correct that would be sufficient to show local smallness is independent of $\mathbf{ZF}$. – aws Mar 30 '17 at 18:11
• I'm pretty sure that that part works now. I've just noticed the comments at the end of the question apply because a set admits a $\mathbb{Z}/2$-action satisfying the "saturated" condition given if and only if it has exactly 2 elements. So, I would be interested to see a sketch of the class forcing proof. – aws Mar 30 '17 at 18:52
• @aws this might be able to be phrased more topos-theoretically, which is probably what Simon is more comfortable with, using techniques as in my paper dx.doi.org/10.1007/s11225-015-9603-6 (identical free version: arxiv.org/abs/1311.3074 - note that it was written in parallel with Asaf's paper on the same topic), using the large topological group (Z/2)^ORD in place of your (Z/2)^\kappa for inaccessible \kappa – David Roberts Mar 31 '17 at 23:21
• @Simon: I admit that I find it weird when people use my full name. But also, I'm quite happy with how much effort has been put into this page. On account of all the users involved, I think. I consider this to be a moderate success of MathOverflow (with the only thing better would be a paper resulting of the whole thing). – Asaf Karagila Apr 1 '17 at 20:00

This is a supplementing answer to aws' answer. In this answer I sketch the a class-symmetric extension in which there is a proper class of Russell sets, and there is no set of Russell cardinals.

(Recall that a Russell set is a set which can be partitioned into countably many pairs, such that no infinite family of those pairs admits a choice function.)

We work in $\sf ZFC+GCH$, where $\sf GCH$ is assumed for simplicity. $\DeclareMathOperator{\dom}{dom} \DeclareMathOperator{\sym}{sym} \DeclareMathOperator{\fix}{fix} \newcommand{\PP}{\Bbb P} \newcommand{\cG}{\mathcal G} \newcommand{\HS}{\mathsf{HS}} \newcommand{\ZF}{\mathsf{ZF}} \newcommand{\cF}{\mathcal F} \newcommand{\id}{\operatorname{id}} \newcommand{\tup}[1]{\langle #1\rangle}$

If $\PP$ is a forcing, and $\{\dot x_i\mid i\in I\}$ is a set (or class) or $\PP$-names, we define $\{\dot x_i\mid i\in I\}^\bullet$ to be the $\PP$-name $\{\tup{1_\PP,\dot x_i}\mid i\in I\}$. This extends to ordered pairs, and naturally to sequences.

1 Localized failure

Fix a regular cardinal $\kappa$. Let $\PP_\kappa$ be the following presentation of adding a Cohen subset to $\kappa$. We mimic the construction of Cohen's second model.

A condition in $\PP_\kappa$ is a partial function $p\colon\omega\times 2\times\kappa\to2$, such that $|\dom p|<\kappa$.

We define the following names, for $(n,i,m)\in\omega\times2\times\omega$:

• $\dot x_{n,i,m}=\{\tup{p,\check\alpha}\mid p(n,i,m,\alpha)=1\}$,
• $\dot X_{n,i}=\{\dot x_{n,i,m}\mid m\in\omega\}^\bullet$, and
• $\dot S_n=\{\dot X_{n,i}\mid i<2\}^\bullet$.

Next we define the automorphism group $\cG_\kappa$, to be permutations $\pi$ of $\omega\times2\times\omega$ moving only finitely many points and satisfying that if $\pi(n,i,m)=(n',i',m')$, then $n=n'$; and for all $n$, either $i=i'$ or $i'=1-i$. It will be clearer to understand, once we see how these act on the names defined above:

• If $p\in\PP_\kappa$, then $\pi p(\pi(n,i,m),\alpha)=p(n,i,m,\alpha)$. This is the standard way this action is defined. It extends to $\PP_\kappa$-names recursively: $\pi\dot x=\{\tup{\pi p,\pi\dot y}\mid\tup{p,\dot y}\in\dot x\}$.

• $\pi\dot x_{n,i,m}=\dot x_{\pi(n,i,m)}$,

• $\pi\dot X_{n,i}=\dot X_{n,i'}$ if there are some $m$ and $m'$ such that $\pi(n,i,m)=\pi(n,i',m')$, and
• $\pi\dot S_n=\dot S_n$.

In other words, for every pair $A_n$, we decide whether or not we switch the elements in that pair, and separately, we may permute the elements of each set in the pair.

Finally, we take $\cF_\kappa$ to be the normal filter of subgroups generated by fixing finitely many points. Namely, if $E\subseteq\omega\times2\times\omega$ is finite, $\fix(E)$ is the group of all automorphisms which fix all the points in $E$ pointwise; and $\cF_\kappa$ is generated by $\fix(E)$ for $E$ finite.

We say that a name is symmetric if $\{\pi\mid \pi\dot x=\dot x\}\in\cF_\kappa$; and hereditarily symmetric if also every name which appears inside $\dot x$ is hereditarily symmetric.

We denote by $\HS$ the class of hereditarily symmetric names. If $G$ is a generic filter, then $\HS^G=\{\dot x^G\mid\dot x\in\HS\}$ is a model of $\ZF$. Let $M$ denote $\HS^G$, and we omit the dots to indicate the interpretations of the names, e.g. $\dot A_n^G$ is $A_n$ and so on.

Standard arguments show that:

1. Each $\dot x_{n,i,m}$ is symmetric (and thus hereditarily symmetric),
2. Each $\dot X_{n,i}$ is symmetric (and thus ...),
3. The sequence $\tup{\dot A_n\mid n<\omega}^\bullet$ is hereditarily symmetric.
4. The name $\dot A=\{\dot X_{n,i}\mid(n,i)\in\omega\times 2\}^\bullet$ is hereditarily symmetric.

So all these will then be in $M$. Moreover,

1. For all $n$ and $i$, $X_{n,i}$, in $M$ is a Dedekind-finite set.
2. $A$ is a Russell set in $M$. Specifically, $\{A_n\mid n<\omega\}$ is a partition witnessing that.

2 Global failure

Let $D$ be a class of regular cardinals. For example, all regular cardinals. For every $\kappa$ in $D$, note that $\PP_\kappa$ is $\kappa$-closed. Let $\PP$ be the Easton product of the $\PP_\kappa$'s. We then define an Easton support product of the groups and filters.

The class of hereditarily symmetric names of this system will include all the Russell sets we added by each $\PP_\kappa$. So it remains to show that there is no set of Russell sets which catch all of them up to equi-cardinality.

But then we get this quite easily. Any set of Russell sets will be added by some condition, and then some large enough $\kappa$ will add a new Russell set.

You can find details of a similar construction here:

Karagila, Asaf, Embedding orders into the cardinals with $\mathsf {DC}_{\kappa}$, Fundam. Math. 226, No. 2, 143-156 (2014). ZBL1341.03068.

• You can also use a finite support product. Interestingly enough. The proof of this goes through the method of symmetric iterations, which is part of my Ph.D. dissertation. You can find such a construction in my paper "Fodor's lemma can fail everywhere" (arxiv.org/abs/1610.03985). – Asaf Karagila Mar 31 '17 at 17:33
• (I should also say about that in contrast to the Fodor's lemma global failure, in this case, when appealing to iterated symmetries, you don't need to do any preparatory forcing.) – Asaf Karagila Apr 1 '17 at 5:50