# On a weak choice principle

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

-
I think you need to set some limitations on 'weaker choice principle'. There is a very easy trick: restrict WISC to hold for a particular non-trivial set (often $\mathbb{R}$ but sometimes $\mathcal{P}(\mathbb{R})$ or higher up, if necessary). Assuming this consequence of WISC is nontrivial, it will surely be much weaker. – François G. Dorais Aug 29 '11 at 1:35
Since it is implied by AC, how can WISC "be interpreted as saying Choice is violated" at all? – Ricky Demer Aug 29 '11 at 2:17
I happened to attend today a talk by Benno van den Berg at a workshop and was incidentally led to this article of his: staff.science.uu.nl/~berg0002/papers/WISC.pdf where he proves the independence of WISC from ZF by showing that WISC implies the existence of arbitrarily large regular cardinals. I checked again the nlab page and found out that it was already updated with this information, which answers the bonus question. – godelian Jun 16 '12 at 21:47
David, if you only have a set of regular cardinals then you would need about the same amount of large cardinals as in Gitik's model. – Asaf Karagila Jun 18 '12 at 6:36
@Asaf: Is it known that Gitik's large cardinal hypotheses are necessary? – François G. Dorais Jun 18 '12 at 14:03

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 arbitrary $\kappa \gt \omega$. 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 $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.

-
Francois, maybe I'm just being dense today, but I don't see why you can assume that all the $C_i$ are the same set $C$. And I don't see anything about that in Benno's write-up either; insofar as I understand W-types, he seems to be using trees in which the nodes are labeled by elements of the index set $I$. – Andreas Blass Jun 18 '12 at 20:26
I'll add the argument why the $C_i$'s can all be the same in a minute. I simplified Benno's argument a bit. The labels are not necessary since I'm using subtrees of $C^{<\omega}$. I also removed the extra label $1$ since the usual rank function also takes care of successor ordinals. – François G. Dorais Jun 18 '12 at 20:40
Thanks, Francois. – Andreas Blass Jun 18 '12 at 21:10
Another translation detail... Benno's literal construction would require that trees $T$ in $\mathcal{W}$ are also cleanly branching in the sense that $\lbrace x \in C : t^\frown x \in T \rbrace$ is either $\varnothing$ (label $0$) or all of $C$ (any label $i \in I$). Since it makes no difference in the argument, I did not include that restriction. – François G. Dorais Jun 18 '12 at 21:13
Hmm, this variant (exists a $C$ and a collection of surjections $C \to X$) is just a bit weaker than COSHEP, and should be interesting on its own in settings other than a well-pointed Boolean topos. – David Roberts Jun 19 '12 at 1:35

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"?

-
I was going to comment that the solution set condition from Giraud's theorem should ensure Grothendieck topoi satisfy WISC... – David Roberts Sep 1 '11 at 5:51

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.
-
I made this CW because this is not thoroughly verified, and it's quite late. If anyone takes a look a has an insight - please edit it in! – Asaf Karagila Jun 18 '12 at 22:58
If this works as planned it is a nice argument! – David Roberts Jun 19 '12 at 2:31