On a weak choice principle

Question

[PLEASE SEE EDITS AT BOTTOM OF QUESTION]

Consider the following set-theoretic axiom:

For each set $X$ there exists a set-indexed collection $\{C_i \to X\}_{i\in I_X}$ of surjections such that for every surjection $Z\to X$ there is a map $C_i\to Z$ for some $i$ such that the obvious triangle commutes.

This is known as WISC (Weakly Initial Set of Covers), and can be interpreted as saying Choice fails to hold in at most a 'small' way. It is clearly implied by AC, and I'm willing to bet that it is independent of other usual set-theoretic axioms (ZF, say). WISC is implied by COSHEP (take $I_X$ to be a singleton for all $X$), SVC and AMC.

My questions are these:

• Does anyone know of a weaker choice principle? (Edit: a global choice principle, or at least one for a sizable collection of sets, like all elements $\bigcup_n \mathcal{P}(\mathbb{R}^n)$)

and

• In which popular/common models of set theory does WISC hold? That is, aside from the ones listed at the linked page above (which are particularly category theory-oriented).

(As a bonus question: Come up with a model of ZF that violates WISC or prove we can use forcing to construct one)

---

Edit: There is also the axiom WISC${}_\kappa$, where we require the set $I_X$ to be bounded by some cardinal $\kappa$ (either less than or at most). This is perhaps more interesting than the unbounded case, especially in topological applications.

---

Edit2: Benno van den Berg has now shown that Gitik's model of ZF (Israel J. Math 1980) violates WISC. This model, which relies on the consistency of a large cardinal assumption (that is, the existence of an unbounded collection of strongly compact cardinals), has the property that only $\aleph_0$ is a regular cardinal. What Benno showed was that ZF+WISC implies the existence of an unbounded collection of regular cardinals. Now one can clearly ask (thanks to godelian in the comments) whether weaker large cardinal assumptions suffice. One would only need to find a model of ZF in which there is only a bounded collection of regular cardinals. This to me sounds reasonable.

Answer 1

Since Benno van den Berg's argument is cast in category theoretic language, here is a translation (and slight simplification) for the benefit of set theorists who may be unfamiliar with the terminology. First note that we may assume that the domains $C_i$ in the statement of WISC are all the same (see note at end). Then, since the collection of all surjections $C \to X$ forms a set, a simplified form of WISC is the following:

For every set $X$ there is a set $C$ such that for every surjection $q:Y \to X$ there is a map $s:C \to Y$ such that $q \circ s: C \to X$ is a surjection.

Assuming WISC holds at $\omega$, we show that there is an ordinal of uncountable cofinality, the argument easily generalizes to larger cofinalities. Let $C$ be as in the simplified form of WISC for $X = \omega$.

Let $\mathcal{W}$ be the set of all wellfounded subtrees of $C^{<\omega}$. Each such tree $T$ has a rank $\mathrm{rk}(T) = \mathrm{rk}_T(\langle\rangle)$, where $\mathrm{rk}_T:T \to \mathrm{Ord}$ is defined by the recursive formula $$\mathrm{rk}_T(t) = \sup\lbrace \mathrm{rk}_T(t^\frown\langle x\rangle)+1 : x \in C \land t^\frown \langle x\rangle \in T \rbrace$$ for each $t \in T$. (Note that $\sup \varnothing = 0$ so the leaves of $T$ have rank $0$.) It is straightforward to check that $$\alpha = \lbrace\mathrm{rk}(T) : T \in \mathcal{W}\rbrace$$ is an initial ordinal. We claim that $\alpha$ is a limit ordinal of uncountable cofinality.

We cannot have $\alpha = 0$ since $\mathcal{W} \neq \varnothing$. We also cannot have $\alpha = \beta+1$ for if $\mathrm{rk}(T) = \beta$ then $$T' = \lbrace\langle\rangle\rbrace\cup\lbrace \langle x\rangle^\frown t : x \in C \land t \in T\rbrace$$ is an element of $\mathcal{W}$ with $\mathrm{rk}(T') = \beta + 1 = \alpha$. So $\alpha$ must be a limit ordinal.

To see that $\alpha$ must have uncountable cofinality, suppose instead that $\alpha = \sup_{n \lt \omega} \alpha_n$ where $\langle \alpha_n \rangle_{n \lt \omega}$ is an increasing sequence of ordinals with $\alpha_0 = 0$. Define $q:\mathcal{W}\to\omega$ by $$q(T) = \max\lbrace n \in \omega : \mathrm{rk}(T) \geq \alpha_n \rbrace.$$ Since this is a surjection, there are a surjection $p:C \to \omega$ and a sequence $\langle T_x \rangle_{x \in C}$ of elements of $\mathcal{W}$ such that $$\alpha_{p(x)} \leq \mathrm{rk}(T_x) \lt \alpha_{p(x)+1}$$ for all $x \in C$. But then the tree $$T = \lbrace\langle\rangle\rbrace\cup\lbrace \langle x\rangle^\frown t : x \in C \land t \in T_x \rbrace$$ is an element of $\mathcal{W}$ with $\mathrm{rk}(T) = \alpha$.

---

Since this is not immediately obvious, here is a detailed explanation why the domains $C_i$ in the original statement of WISC can be assumed to be the same. The argument works in Set and any other well-pointed Boolean topos.

We may assume $X \neq \varnothing$. Pick $x_0 \in X$ once and for all. Suppose $p_i:C_i \to X$, $i \in I$, is a set-indexed family of surjections as in the statement of WISC. Let $C = \bigcup_{i \in I} C_i$ and let $\bar{p}_i:C\to X$ be the extension of $p_i$ with $\bar{p}_i(a) = x_0$ for all $a \in C - C_i$. I claim that the surjections $\bar{p}_i:C\to X$, $i \in I$, are also as required for WISC.

Suppose $q:Y \to X$ is a surjection. By hypothesis there are an $i \in I$ and a map $s:C_i \to Y$ such that $q \circ s = p_i$. Extend $s:C_i \to Y$ to $\bar{s}:C \to Y$ by defining $\bar{s}(a) = y_0$ for all $a \in C - C_i$ where $y_0$ is an element of $q^{-1}(x_0)$. Then $q \circ \bar{s} = \bar{p}_i$, as required.

Answer 2

Monro proved in [1] that for every ordinal $\kappa$ we can create a model in which there is a D-finite set mapped onto $\kappa$. He then constructs an Easton product of all these forcing and adjoins a proper class which is D-finite, and composed of a union of a proper class of D-finite sets.

So we first adjoin mutually generic (I believe, this should probably imply that they are incomparable in $\leq,\leq^\ast$ too) D-finite sets, $K_\kappa$ each is a subset of $\kappa$, and they have the property that $K_\kappa$ can be mapped onto $\kappa$ but not onto $\kappa^+$.

This means that for every ordinal there is a proper class of mutually incomparable sets - all D-finite which can be mapped onto the ordinal.

(Interestingly enough he later goes to show that this can be achieved without adding D-finite sets too)

---

1. Monro, G.P., Independence results concerning Dedekind finite sets. Journal of the Australian Mathematical Society (Series A) (1975), 19 : pp 35-46.

Answer 3

After Benno van den Berg's proof, there are now two more proofs:

First, building on his answer, Asaf removed the requirements for large cardinals in

• Asaf Karagila, Embedding Orders Into Cardinals With $DC_\kappa$, Fund. Math. 226 (2014), 143-156, doi:10.4064/fm226-2-4, arXiv:1212.4396.

Second, as suggested by Mike Shulman, a suitable topos of $G$-sets where $G$ is a large topological group violates WISC in its internal language (how to make this construction precise takes a little bit of ingenuity):

• David Michael Roberts, The weak choice principle WISC may fail in the category of sets, Studia Logica Volume 103 (2015) Issue 5, pp 1005-1017, doi:10.1007/s11225-015-9603-6, arXiv:1311.3074.

Answer 4

This is not really an answer, just speculation, but it's too long for a comment.

I suspect that (assuming AC, or maybe just WISC, in the base model) WISC will hold in any ordinary permutation, symmetric, or forcing model, since these correspond very closely to Grothendieck topoi over Set.

I also suspect, however, that a model of ZF violating WISC could be obtained as follows. Let G be a large group and consider the topos of G-sets. This is locally small and cocomplete (although not Grothendieck), so it has an internal model of ZF; I suspect that this model of ZF will violate WISC (for suitable G). Set theorists probably have a name for this model of ZF---a "proper-class permutation/symmetric model"?