Weak Choice Principles and Sierpiński's Theorem

Assume AC, let $R$ be serial on $X\mathrm{\ne }\mathrm{\varnothing }$, and fix $a\in X$. Apply AC to the successor sets $R[x]=\{y:xRy\}$ to get a function $s:X\to X$ with $xRs(x)$. Repeated successor sets use the same selected value.

Assume DC and let $(X_n)$ be a nonempty-set family. The set $T$ of finite functions $t$ with domain some $n<\omega$ and $t(i)\in X_i$ contains the empty function. One-step extension is serial: for a particular $t$, one point of $X_n$ extends it. DC starting at the empty function gives nested $t_n$ of domain $n$. Their union is a function on omega selecting from each $X_n$.

Recurse with $x_0=a$ and $x_{n+1}=s(x_n)$. This is the prescribed path and proves AC implies DC.

The remaining implications restrict the eligible input families: nonempty finite sets are nonempty sets, and pairs are finite nonempty sets; AC also applies to any set-indexed family of pairs. This includes singleton-valued families without additional choices.

Assume the version without a starting point. Fix a serial $R$ on $X\mathrm{\ne }\mathrm{\varnothing }$ and $a\in X$. Let $T$ consist of nonempty finite $R$-paths starting at $a$. It contains $(a)$. The relation of extending by exactly one term is serial, since the last point has a successor. Obtain a path $(t_n)$ in $T$ under this relation.

The $t_n$ are nested and have lengths $\mathrm{len}(t_0)+n$. Their union has domain omega, starts at $a$, and satisfies $x_{n}R{x}_{n+1}$ at each index, since some finite path contains both coordinates. This is the prescribed-start version.

Conversely, on a nonempty $X$ fix one $a\in X$ and apply prescribed-start DC, then forget the value of its first term. This one existential selection does not invoke AC.

Under DC take an $R$-path and put $F_n=\{x_n\}$. These are DMC levels. Countable finite choice follows from DC as well.

Conversely, take DMC levels for a serial relation. For each $n$ the set of linear orders on the nonempty finite $F_n$ is nonempty and finite (enumerate that single finite set to see this). Countable finite choice supplies an order ${<}_n$ for every $n$.

Under MC select, once for all $x\in X$, a finite nonempty $H(x)\subseteq R[x]$. Fix $a\in X$ and set $F_0=\{a\}$, $F_{n+1}={\bigcup }_{x\in F_n}H(x)$. A finite union of finite sets is finite by finite induction, and each member has a successor in the next nonempty level. This recursion proves DMC.

Start at the ${<}_0$-least point and take the ${<}_{n+1}$-least $R$-successor in $F_{n+1}$. Such a successor exists by the universal successor clause of DMC. The rule is a self-map on tagged states $(n,x)$, so recursion supplies a path. Starting-point-free DC now implies full DC.

Under countable choice select $x_n\in X_n$ and use $\{x_n\}$ for the CMC selection.

Assume AC and let $\mathcal{F}$ have finite character. If $Y\in \mathcal{F}$, every subset of $Y$ belongs to $\mathcal{F}$, since its finite subsets are finite subsets of $Y$. In particular $\mathrm{\varnothing }\in \mathcal{F}$. For a nonempty inclusion-chain $\mathcal{C}\subseteq \mathcal{F}$, every finite subset of $\bigcup \mathcal{C}$ is contained in one chain member: choose finitely many covering members and take the largest among them. Thus $\bigcup \mathcal{C}\in \mathcal{F}$. The empty chain has upper bound $\mathrm{\varnothing }$.

Assume Tukey and let $(X_i{)}_{i\in I}$ be any nonempty-set family. Inside $I\times {\bigcup }_i{X}_i$ let $\mathcal{G}$ consist of graphs of partial functions $g$ satisfying $g(i)\in X_i$. It contains the empty graph. A graph fails the conditions only by a bad pair $(i,x)$ with $x\mathrm{\notin }{X}_i$, or by two pairs with the same first coordinate and different values. These witnesses have sizes one and two, so $\mathcal{G}$ has finite character.

Apply Zorn to $(\mathcal{F},\subseteq )$ to obtain an inclusion-maximal member.

A maximal $g\in \mathcal{G}$ must have domain $I$: at an omitted $i$, any one $x\in X_i$ extends it, contradicting maximality. If $I$ is empty the empty graph already suffices. Thus every family has a choice function.

If $P=\mathrm{\varnothing }$, its empty subset is maximal. Otherwise use MC to fix $s(U)$ finite nonempty in every nonempty $U\subseteq P$. The minimal elements $m(U)$ of $s(U)$ form a nonempty finite antichain: descent in a finite strict poset terminates, and two minimal points cannot be comparable.

Recurse for $\xi <h(\mathcal{P}(P))$. Given earlier antichains, let $U_{\xi }$ be the points outside their union incomparable with every point in that union. Set $A_{\xi }=m(U_{\xi })$ if it is nonempty, and $A_{\xi }=\mathrm{\varnothing }$ otherwise. Earlier and later nonempty stages are disjoint and mutually incomparable.

If every stage were nonempty, $\xi \mapsto A_{\xi }$ would inject $h(\mathcal{P}(P))$ into $\mathcal{P}(P)$ because the stages are disjoint. Thus some $U_{\xi }$ is empty. The union of the stages before the first such index is an antichain to which no point can be added.

For a linearly ordered $(Q,<)$ form the poset of pairs $(U,u)$ with $\mathrm{\varnothing }\mathrm{\ne }U\subseteq Q$ and $u\in U$, ordered by $(U,u)\le (V,v)$ iff $U=V$ and either $u=v$ or $u<v$. A maximal antichain contains exactly one pair above each $U$: at most one by linearity, at least one because otherwise any $(U,u)$ could be added. Its graph specifies a selector $c(U)\in U$.

Recursively remove $c$ of the remaining subset of $Q$ until it is empty, using a fixed stop symbol thereafter. If this did not stop before $h(Q)$, the removed points would give an injection of that ordinal into $Q$. Their order of removal therefore well-orders all of $Q$. For $Q=\mathrm{\varnothing }$ the empty order suffices.

The power set of any ordinal $\alpha$ is linearly ordered by its characteristic functions: at the least element of the symmetric difference compare $0<1$. Transitivity follows because for three functions the first two comparison indices either differ (the earlier decides) or agree (the value order decides). Under MC the antichain hypothesis holds, so the first two steps apply to this linear order.

By hierarchy exhaustion, choose an ordinal $\beta$ with $A\in V_{\beta }$.

The stage $V_{\beta }$ is transitive, so $A\in V_{\beta }$ implies $A\subseteq V_{\beta }$.

Put $\theta =\beta +\omega$. Then $\theta$ is a limit ordinal and $\beta \le \theta$; monotonicity of the hierarchy gives $V_{\beta }\subseteq V_{\theta }$, hence $A\subseteq V_{\theta }$.

Fix $A\subseteq V_{\theta }$ with $\theta$ limit and let $k=h(V_{\theta })$. By the hypothesis fix a single well-order $W$ of $\mathcal{P}(k)$. No sequence of arbitrary well-orders is chosen.

Define well-orders $W_{\beta }$ of $V_{\beta }$ for $\beta <\theta$ recursively. At zero use the empty order. Given $W_{\beta }$, its unique order isomorphism $e_{\beta }:V_{\beta }\to {\eta }_{\beta }$ has ${\eta }_{\beta }<k$, since $V_{\beta }\subseteq V_{\theta }$. Order $V_{\beta +1}=\mathcal{P}(V_{\beta })$ by transporting the restriction of $W$ along $u\mapsto e_{\beta }[u]\in \mathcal{P}(k)$.

At a limit $\lambda \le \theta$, order elements first by their least stage of appearance below $\lambda$, then within the same stage by its already constructed order. Every nonempty subset has a least appearance index and a least element at that index, so this is a well-order. This defines the limit rule and also the final order on $V_{\theta }$. Restrict it to $A$.

For any family of nonempty sets apply the result to its union and select the least member of each set. The empty family uses the empty function. This proves AC from the powerset hypothesis; MC supplies that hypothesis. Conversely AC supplies a point in each nonempty set, whose singleton is a multiple selection.

For an injective nonsurjective $f:X\to X$, fix $a\mathrm{\notin }f[X]$ and put $a_n=f^n(a)$. If $a_m=a_n$ with $m<n$, cancel $f$ repeatedly to get $a=f^{n-m}(a)\in f[X]$, impossible. Thus $n\mapsto a_n$ injects omega into $X$.

Given an injection $n\mapsto a_n$, send $\ast$ to $a_0$, each $a_n$ to $a_{n+1}$, and every other point of $X$ to itself. This is a bijection $X\bigsqcup \{\ast \}\to X$. Conversely, restricting any such bijection to $X$ is injective and misses the image of $\ast$, proving Dedekind infinitude.

By the least-nonembedding definition, omega embeds into $X$ exactly when $\omega <h(X)$. Negating gives the asserted Dedekind-finite characterization. For finite $X$, including the empty set, no injective nonsurjective self-map exists, as finite counting also shows.

For each positive integer $n$, the set $T_n$ of injective maps $n\to X$ is nonempty: extend a finite tuple by a point outside its finite range, which exists because $X$ is infinite. This finite induction makes no countable choice. Now use countable choice once to select $t_n\in T_n$.

The set $U={\bigcup }_{n>0}\mathrm{ran}(t_n)$ is covered by the coordinate values $t_n(i)$ with $i<n$. Enumerate those pairs by the fixed enumeration of omega squared, discarding pairs outside the domain. This produces a sequence onto $U$. Since $U$ contains $n$ distinct points for every $n$, it is infinite. Retain the first occurrence of each new value; the retained indices form an infinite subset of omega and their increasing enumeration gives a bijection $\omega \to U$.

Composing with the inclusion $U\subseteq X$ yields an injected omega and hence Dedekind infinitude.

If $\mathrm{cf}({\omega }_1)<{\omega }_1$, it must be omega: it is an infinite cardinal and omega is the only countable infinite initial ordinal. Thus there is a cofinal sequence $({\alpha }_n{)}_{n<\omega }$ in ${\omega }_1$.

Each ${\alpha }_n$ is a countable ordinal. Cofinality gives ${\omega }_1={\bigcup }_n{\alpha }_n$ (or use ${\alpha }_n+1$ without changing the argument). Countable choice makes that union countable, contradicting the definition of ${\omega }_1$. The only remaining cofinality is ${\omega }_1$.

In a well-order, the nonempty range of a descending sequence would have a least element $x_n$, contradicted by $x_{n+1}<x_n$. This direction needs no choice.

If the linear order is not a well-order, some nonempty $Y\subseteq X$ has no least point. Linearity implies that every $y\in Y$ has some $z\in Y$ with $z<y$. Apply DC to $yRz$ iff $z<y$, starting from any one point of $Y$. It gives the forbidden descending sequence. The empty order is a well-order and has no such sequence.

Fix the natural pairing $p(m,n)=(m+n)(m+n+1)\mathrm{/}2+n$, which is injective, has $p(0,0)=0$, and is positive otherwise. For $\delta ={\omega }^{\beta }$ with $\beta >0$, write $u,v<\delta$ in Cantor normal form over their common finite list of exponents, using zero coefficients where absent. Replace each coefficient pair $(a,b)$ by $p(a,b)$. The resulting ordinal $q_{\delta }(u,v)$ is below $\delta$, and its unique normal form recovers both inputs. Thus $q_{\delta }:{\delta }^2\to \delta$ is a uniformly defined injection. The empty exponent list represents zero.

For any infinite ordinal $\alpha$, its leading normal-form term gives $\delta ={\omega }^{\beta }$ and a positive finite $n$ with $\delta \le \alpha <\delta (n+1)$. Every $u<\alpha$ has a unique expression $u=\delta k+\rho$, $k\le n$, $\rho <\delta$, obtained from the finitely many consecutive blocks. Send it to $q_{\delta }(\rho ,k)$. This injects $\alpha$ into $\delta$; inclusion injects $\delta$ into $\alpha$. The explicit Schroder–Bernstein construction gives a uniformly defined bijection $b_{\alpha }:\alpha \to \delta$. Conjugating $q_{\delta }$ by $b_{\alpha }$ gives an injection $q_{\alpha }:{\alpha }^2\to \alpha$.

The supplied well-order has a unique order isomorphism $e:Y\to \alpha$. It can be constructed by assigning to each point the set of previously assigned ordinals; recursion supplies the assignment, and induction verifies it is an initial ordinal segment. Transfer $q_{\alpha }$ and the injection $\omega \subseteq \alpha$ to $Y$, obtaining $q:Y^2\to Y$ and $j:\omega \to Y$, with no arbitrary selection.

Define $c_0(\mathrm{\varnothing })=j(0)$ and $c_{n+1}(t)=q(c_n(t\upharpoonright n),t(n))$. Finite induction proves each $c_n:{}^{n}Y\to Y$ injective. Then $t\mapsto q(j(\mathrm{len}(t)),c_{\mathrm{len}(t)}(t))$ injects all finite sequences into $Y$, including length zero. The singleton map injects $Y$ in the other direction. Apply explicit Schroder–Bernstein and invert if necessary to obtain $H$. Every rule just described is definable from the supplied order.

Suppose $G:\mathcal{P}(X)\to \mathrm{Seq}(X)$ is injective. For an infinite well-ordered subset $(Y,<)$ of $X$, let $H:Y\to \mathrm{Seq}(Y)$ be the uniformly defined bijection. Put $D=\{y\in Y:H(y)\in \mathrm{ran}(G)\text{ and }y\mathrm{\notin }{G}^{-1}(H(y))\}$. The inverse here is used only at points in the range, where it is unique.

If $G(D)=H(y)$ for some $y\in Y$, the definition would give $y\in D$ iff $y\mathrm{\notin }D$. Hence $G(D)\mathrm{\notin }\mathrm{Seq}(Y)$. Its finite sequence has a first coordinate outside $Y$; let $a(Y,<)$ be that value. This rule is unique and definable from $G$ and the given order. The sequence cannot be empty, since the empty sequence belongs to $\mathrm{Seq}(Y)$.

Seed a well-order with the image of a supplied injection $\omega \to X$. Recursively for $\xi <h(X)$ append $a(Y_{\xi },{<}_{\xi })$, where $Y_{\xi }$ consists of the seed followed by previously appended elements in index order. At limits take the union of these extending well-orders. Each stage is an infinite well-ordered subset of $X$, so the rule always yields a fresh point. Thus the appended points inject $h(X)$ into $X$, a contradiction.

Fix $a\in X$. The two copies of $X$ inject into $\mathcal{P}(X\bigsqcup \{\ast \})$ by $x\mapsto \{x\}$ and $x\mapsto \{x,\ast \}$. A bijection $X\bigsqcup 1\approx X$ transports this to $X\bigsqcup X⪯\mathcal{P}(X)$. Also $X⪯X\bigsqcup X$.

Local GCH makes $X\bigsqcup X$ equinumerous either with $X$ or with $\mathcal{P}(X)$. The latter would inject the power set into finite sequences: use $(x)$ for the first copy and $(a,x)$ for the second. This is impossible. Thus $X\bigsqcup X\approx X$.

The map taking a subset of a tagged disjoint union to its two component subsets is a bijection $\mathcal{P}(X\bigsqcup X)\to \mathcal{P}(X{)}^2$. Transport along the previous bijection gives $\mathcal{P}(X{)}^2\approx \mathcal{P}(X)$. Singleton coordinates inject $X^2$ into this product, while $x\mapsto (x,a)$ injects $X$ into $X^2$.

Apply local GCH to $X⪯X^2⪯\mathcal{P}(X)$. The power-set endpoint would inject $\mathcal{P}(X)$ into length-two sequences, again impossible; the remaining endpoint is $X^2\approx X$. Together with the product-of-powersets bijection this proves all assertions.

For each injection $f:\alpha \to X$, let $T_f=\{f[\gamma ]:\gamma \le \alpha \}\subseteq \mathcal{P}(X)$. Inclusion well-orders this chain in type $\alpha +1$, because the initial images strictly increase. For each $\alpha <h(X)$, let $B_{\alpha }$ be the set of all such chains of type $\alpha +1$ arising from these injections. It is a nonempty element of ${\mathcal{P}}^3(X)$, and distinct indices give disjoint such sets because a chain has unique order type. Thus $\alpha \mapsto B_{\alpha }$ is injective. For $\alpha =0$ the chain is $\{\mathrm{\varnothing }\}$.

Let $R_{\alpha }$ be the set of all reflexive well-order relations on subsets of $X$ of type $\alpha$. Reflexivity makes the underlying set recoverable from the diagonal, including singleton orders; the empty order has the empty relation. These are nonempty pairwise disjoint subsets of $\mathcal{P}(X^2)$. Thus $h(X)⪯{\mathcal{P}}^2(X^2)$, and a supplied bijection $X^2\approx X$ gives the double-power bound.

If $X$ is infinite and Dedekind-finite, then $h(X)=\omega$: every finite ordinal embeds by finite induction, while omega does not. Each $[X{]}^n$ is nonempty, and these sets of subsets are disjoint for distinct $n$. Hence $n\mapsto [X{]}^n$ injects omega into ${\mathcal{P}}^2(X)$. If $X$ has finite size $n$, $h(X)=n+1$ and $n+1\le 2^{2^n}$ by elementary finite induction; choose an enumeration of this single finite set to realize the injection. This includes $n=0$.

The first bound implies $h(X)<h({\mathcal{P}}^3(X))$ by the definition of Hartogs. For the other strict bound, singleton inclusion gives $h(X)⪯{\mathcal{P}}^4(X)$. Equality would give an injection $\mathcal{P}(A)\to A$ with $A={\mathcal{P}}^3(X)$. Its inverse on its range, extended elsewhere by $\mathrm{\varnothing }$, would be a surjection $s:A\to \mathcal{P}(A)$, impossible since $\{a\in A:a\mathrm{\notin }s(a)\}$ is missed. Thus the comparison is strict.

Fix the injection $j$. For each $x\in X$, the image of $\{x\}\times \mathcal{P}(X)$ cannot lie wholly in the $X$-summand. Otherwise it gives an injection $\mathcal{P}(X)\to X$; its inverse, extended by $\mathrm{\varnothing }$ off the range, would surject $X$ onto its power set.

The ordinal part of that fibre is therefore nonempty. Let $b(x)$ be its least ordinal. Different fibres have disjoint images by injectivity of $j$, so $b:X\to \alpha$ is injective. Pull back the ordinal well-order along $b$: totality follows from injectivity and ordinal trichotomy, and a nonempty subset has the unique point whose image is its image set’s least ordinal. For $X=\mathrm{\varnothing }$ this is the empty order; if $\alpha =0$ the first step forces $X=\mathrm{\varnothing }$.

Put $P=\mathcal{P}(X)$ and $h=h(X)$. Suppose $h⪯P$. Then $X\prec X\bigsqcup h⪯P\bigsqcup P\approx P$. Strictness holds because $X\bigsqcup h\approx X$ would embed $h$ into $X$. For the last bijection, $P\bigsqcup P\approx \mathcal{P}(X\bigsqcup 1)\approx P$, using the omega shift. Local GCH therefore gives $X\bigsqcup h\approx P$.

Singleton injection in the first coordinate and square absorption give $X\times P⪯P^2\approx P$, while $P⪯X\times P$ using one fixed point of $X$. Thus $X\times P\approx P\approx X\bigsqcup h$, and the fibre lemma well-orders $X$.

Let $\lambda$ be the least ordinal equipotent with this well-orderable $X$. Hartogs $h$ is an infinite initial ordinal: an equipotent smaller ordinal would contradict its least-nonembedding property. Moreover $\lambda <h$. Both $X$ and $h$ embed in $h$, so $X\bigsqcup h$ injects into $h\times h\approx h$, and the reverse injection is immediate. Hence $P\approx h$.

If instead $h(X)$ does not inject into $P$, its least nonembedding ordinal satisfies $h(P)\le h(X)$. Since $X$ injects into $P$ by singletons, every ordinal embedding into $X$ embeds into $P$, so $h(X)\le h(P)$. This yields the second branch.

Write $P=\mathcal{P}(X)$ and $Q=\mathcal{P}(P)$. Suppose $P$ is not well-orderable. Then $Q$ is not well-orderable either, since $P⪯Q$. Apply the dichotomy to $X$ and to $P$; both contain an injected omega and satisfy their respective local hypotheses. Their first branches are excluded, so $h(X)=h(P)=h(Q)$.

But square absorption and the double-power bound give $h(X)⪯Q$. Together with the equality in the previous step this embeds the Hartogs number of $Q$ into $Q$, impossible by its defining property. Thus $P$ is well-orderable.

A well-order of $P$ has some ordinal type $\rho$. If $\rho <h(X)$, it would embed into $X$, giving $P⪯X$, which is impossible: invert that injection on its range and extend by the empty subset elsewhere to get a surjection $s:X\to \mathcal{P}(X)$; then $\{x\in X:x\mathrm{\notin }s(x)\}$ is missed. Thus $h(X)\le \rho$ and $h(X)⪯P$. The first dichotomy branch now gives $P\approx h(X)$ and the well-orderability of $X$.

For any set $A$, form $X=A\bigsqcup \omega$. The second summand explicitly embeds omega into $X$, so $X$ and $\mathcal{P}(X)$ are infinite. Global GCH supplies both local hypotheses. Specker well-orders $X$, and restriction well-orders $A$. This also covers finite and empty $A$.

For any family of nonempty sets, well-order its union by the preceding step and take the least member of each set. Replacement forms the resulting choice function. The empty family has the empty function. Thus AC holds.