# Choiceless non-free algebras

This post is a bit different, as it’s somewhat more of a curiosity I recently noticed. It’s a theorem of $\textsf{ZFC}$ that every type of of algebraic structure has a free algebra, similar to the notion of a free group, free module and so on. How about without choice? It turns out that the theory

$\textsf{ZF}+\textsf{F}:\equiv\textsf{ZF}+"\text{There is an algebraic type which does not admit free algebras}"$

has considerable consistency strength. It consistency-wise implies $\textsf{AD}^{L(\mathbb R)}$ and is consistency-wise implied by a proper class of strongly compacts.

Let me first define exactly what we mean by an algebraic type and what it means for such a type to admit free algebras. By an algebraic type I mean a pair $(\mathcal L,\mathcal T)$, where $\mathcal L$ is a language without any relation symbols and $\mathcal T$ an $\mathcal L$-theory. Here we allow the function symbols in $\mathcal L$ to have arbitrary arity. To every algebraic type $\sigma:=(\mathcal L_\sigma,\mathcal T_\sigma)$ we can thus associate the class $\text{Mod}(\sigma)$ of all $\mathcal L_\sigma$-structures that satisfy $\mathcal T_\sigma$. For instance, if we picked $\mathcal L_\sigma:=\{e,\cdot\}$ with $e$ a constant symbol and $\cdot$ a binary function symbol, and picked

$\mathcal T_\sigma:=\{\forall x\forall y\forall z(x(yz)=(xy)z), \forall x(xe=x\land ex=x)\}$,

then $\text{Mod}(\sigma)$ is just the class of all monoids.

To every such $\text{Mod}(\sigma)$ we also have homomorphisms between them, in the classical model-theoretic context (so that these would be monoid homomorphisms in the above example). This gives us a category $\mathcal C_\sigma$ with objects the structures in $\text{Mod}(\sigma)$ and the associated homomorphisms between them. In the above example we would simply get $\mathcal C_\sigma=\textsf{Mon}$, the category of monoids.

To every such category $\mathcal C_\sigma$ we always have a functor $U:\mathcal C_\sigma\to\textsf{Set}$, which simply “forgets” about all the extra structure, i.e. taking the reduct to the empty language. This functor $U$ is called the forgetful functor. I then say that $\sigma$ admits free algebras if the forgetful functor has a left adjoint. That is, there exists a functor $F:\textsf{Set}\to\mathcal C_\sigma$ such that for every set $X$ and $A\in\textsf{Mod}(\sigma)$,

$\mathcal C_\sigma(FX,A)\cong\textsf{Set}(X,UA)$.

In the running example we could choose $F:\textsf{Set}\to\textsf{Mon}$ to send a set $X$ to the set of all finite words on the elements of $X$, i.e. that

$FX:=({^{<\omega}}X,\cdot)$,

where the operation $\cdot$ is merely concatenation of sequences. Then to every function $f:X\to UA$ we can define $\varphi_f:FX\to A$ as

$\varphi_f(\langle\rangle):=e$
$\varphi_f(\langle x_1,\hdots,x_n\rangle):=f(x_1)\cdot f(x_2)\cdots f(x_n)$,

and the function $f\mapsto\varphi_f$ is indeed bijective, making $F$ a left adjoint to the forgetful functor.

Okay, so that was a few definitions. It turns out that given any algebraic type admits free algebras, in the presence of choice. This is done analogous to the above example, by constructing the set of all words of elements of a given set. Some care must be taken however, as we don’t want our words to infinitely nest, which is done by considering words to be certain well-founded trees instead, see Blass (1983). Without choice it turns out to be a different story.

Theorem (Blass, 1983). Assume $\textsf{ZF}$. Then every algebraic type admits free algebras iff there is a proper class of regular cardinals.

This conversion of the problem turns out to be fruitful, as we now have the following upper bound of our hypothesis.

Theorem (Gitik, 1980). Assume that there exists a proper class of strongly compact cardinals. Then there exists a model of $\textsf{ZF}$ in which $\text{cof}(\aleph_\alpha)=\aleph_0$ for every ordinal $\alpha$.

Ostensibly, this theorem seems a bit of an overkill, as we just require the cardinals to be singular and not necessarily having cofinality $\aleph_0$. Furthermore we only require that the class of regular infinite cardinals is bounded, and not only containing $\aleph_0$, but that might be equiconsistent. As for lower bounds, we have the following recent result, building on Busche and Schindler (2009).

Theorem (Adolf ’17). Assume $\textsf{ZF}$ and that the regular cardinals are bounded. Then there is a model of $\textsf{AD}_{\mathbb R}+\Theta\text{ is regular}$.

This result is accomplished by using the core model induction technique in a choiceless context. The result assumes that every uncountable cardinal is singular, but the proof only requires that the regular cardinals are bounded. We then have that

$\textsf{AD}_{\mathbb R}+\Theta\text{ is regular}\leq_{\text{Con}} \textsf{ZF}+\textsf{F}\leq_{\text{Con}}\text{There is a proper class of strongly compacts}$.

This is still an enormous span, so it would be interesting if it turns out that $\textsf{ZF}+\textsf{F}$ is consistency-wise below a superstrong, making it interact with all the determinacy theories we got in that area.

EDIT: Changed the lower bound to a recent result of Adolf.

References

• Blass, A.: “Words, free algebras, and coequalizers”,  Fund. Math. 117, 1983.
• Gitik, M.: “All uncountable cardinals can be singular”, Israel J. Math. 35, 1980.
• Busche, D. and Schindler, R.: “The strength of choiceless patterns of singular and weakly compact cardinals”, Annals of Pure and Applied Logic 159, 2009