On a weak choice principle
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.
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)
- Monro, G.P., Independence results concerning Dedekind finite sets. Journal of the Australian Mathematical Society (Series A) (1975), 19 : pp 35-46.
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.