10
$\begingroup$

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

$\endgroup$
27
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 29, 2011 at 1:35
  • 2
    $\begingroup$ Since it is implied by AC, how can WISC "be interpreted as saying Choice is violated" at all? $\endgroup$
    – user5810
    Aug 29, 2011 at 2:17
  • 2
    $\begingroup$ 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. $\endgroup$
    – godelian
    Jun 16, 2012 at 21:47
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Jun 18, 2012 at 6:36
  • 2
    $\begingroup$ Hi François. No, this is not known. The large cardinal assumption we currently need to force something like Gitik's result is an almost huge cardinal. This is much weaker than Gitik's original assumptions, but still in the stratosphere. We cannot currently prove any lower bounds that involve large cardinals at or beyond the level of superstrong, and almost huges are well past that. The best result to date is due to Daniel Busche and Ralf Schindler, in "The strength of choiceless patterns of singular and weakly compact cardinals, Ann. Pure Appl. Logic, 159 (2009), pp. 198-248" (...) $\endgroup$ Jun 18, 2012 at 21:09

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$ Jun 18, 2012 at 20:26
  • $\begingroup$ 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. $\endgroup$ Jun 18, 2012 at 20:40
  • $\begingroup$ 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. $\endgroup$ Jun 18, 2012 at 21:13
  • $\begingroup$ 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. $\endgroup$
    – David Roberts
    Jun 19, 2012 at 1:35
  • 1
    $\begingroup$ I've accepted this answer because it was most useful when formulating internal WISC in a topos, and so allowed me to carry out Mike's suggestion in his answer in a stronger way, and violate internal WISC, not just external, which is immediate. $\endgroup$
    – David Roberts
    Dec 14, 2017 at 6:24
3
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ If this works as planned it is a nice argument! $\endgroup$
    – David Roberts
    Jun 19, 2012 at 2:31
3
$\begingroup$

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.
$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I was going to comment that the solution set condition from Giraud's theorem should ensure Grothendieck topoi satisfy WISC... $\endgroup$
    – David Roberts
    Sep 1, 2011 at 5:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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