Does restricting the range of a collection of nonempty sets to one dominated by the index set require the Axiom of Choice?

87 Views Asked by At

The title was difficult to write, because it is hard to say the property I am looking for in words. Here it is in symbols:

$$\forall i\in I\ A_i\ne\emptyset\implies\exists X\preceq I\ \forall i\in I\ A_i\cap X\ne\emptyset$$

(Note that $X\preceq I$ means $X$ is dominated by $I$, i.e. there is an injection from $X$ to $I$.) Assuming the axiom of choice, this is easy: Pick a function $f$ on $I$ such that $f(i)\in A_i$ for each $i\in I$, and let $X={\rm ran}\,f$. Then $f$ is an onto function from $I$ to $X$, so applying ${\sf AC}$ again, we have $X\preceq I$, and of course $f(i)\in A_i\cap X$.

But the output of this theorem seems considerably less than the choice used to achieve it, and I can't seem to devise a way to get ${\sf AC}$ out of it, so I suspect it is weaker than ${\sf AC}$. Does anyone see how to (a) prove this without ${\sf AC}$, or (b) prove ${\sf AC}$ from this?

1

There are 1 best solutions below

3
On BEST ANSWER

This is a long comment rather than an answer. I can't answer either of your questions; all I'm going to do is restate your theorem in an equivalent but slightly simpler form. Maybe this will make it easier to find it in the literature. Consider the following statements.

(1) If $A_i\ne\emptyset$ for each $i\in I$, then there is a set $X$ such that $|X|\le|I|$ and $A_i\cap X\ne\emptyset$ for each $i\in I$. [Your theorem.]

(2) For any surjective map $f:A\to B$, there is an injective map $g:B\to A$ such that the composite map $fg:B\to B$ is surjective.

(2A) For any surjective map $f:A\to B$, there is a map $g:B\to A$ such that the composite map $fg:B\to B$ is surjective.

(2B) Whenever there is a surjection from $A$ to $B$, there is an injection from $B$ to $A$. [The Partition Principle.]

Without assuming AC, I claim that $\text{(1)}\Leftrightarrow\text{(2)}\Leftrightarrow\text{(2A)}\wedge\text{(2B)}$.

$\underline{\text{(1)}\Rightarrow\text{(2A)}}$: Suppose $f:A\to I$ is surjective. For $i\in I$ let $A_i=\{x\in A:f(x)=i\}$. By (1) there is a set $X$ such that $|X|\le|I|$ and $A_i\cap X\ne\emptyset$ for each $i\in I$. Moreover, we may assume that $X\subseteq A$; then $f\restriction X$ is a surjection from $X$to $I$. Since $|X|\le|I|$, there is a surjection $g:I\to X$. Then $fg:I\to I$ is surjective.

$\underline{\text{(1)}\Rightarrow\text{(2B)}}$: Suppose $f:I\to B$ is surjective. For $i\in I$ let $A_i=\{f(i)\}$. By (1) there is a set $X$ such that $|X|\le|I|$ and $A_i\cap X\ne\emptyset$ for each $i\in I$. It follows that $B\subseteq X$ and so $|B|\le|X|\le|I|$, i.e., there is an injection from $B$ to $I$.

$\underline{\text{(2A)}\wedge\text{(2B)}\Rightarrow\text{(2)}}$: Suppose $f:A\to B$ is surjective. By (2A) there is a map $h:B\to A$ such that $fh:B\to B$ is surjective. Let $C=h[B]$. Since we have surjections from $B$ to $C$ and from $C$ to $B$, it follows by (2B) and the Cantor-Bernstein Theorem that there is a bijection $g:B\to C$. Then $g:B\to A$ is injective, and $fg:B\to B$ is surjective.

$\underline{\text{(2)}\Rightarrow\text{(2A)}\wedge\text{(2B)}}$: Trivial.

$\underline{\text{(2A)}\wedge\text{(2B)}\Rightarrow\text{(1)}}$: Suppose $A_i\ne\emptyset$ for each $i\in I$. Let $\hat{A}_i=\{i\}\times A_i$, and let$$A=\bigcup_{i\in I}\hat{A}_i=\{\langle i,x\rangle:i\in I,x\in A_i\}.$$For $\langle i,x\rangle\in A$, define $f(\langle i,x\rangle)=i$; then $f:A\to I$ is a surjection. By (2A) there is a map $g:I\to A$ such that $fg:I\to I$ is surjective. Let $C=g[I]\subseteq A$ and let $$X=\{x:\langle i,x\rangle\in C\text{ for some }i\in I\}.$$Since we have surjections from $I$ to $C$ and from $C$ to $X$, it follows by (2B) that there is an injection from $X$ to $I$, i.e., $|X|\le|I|$. Now it is easy to see that $A_i\cap X\ne\emptyset$ for each $i\in I$.

P.S. I don't know much about set theory, but I've been told that the Axiom of Determinacy (AD) is consistent with ZF+DC. If the Partition Principle (2B) were provable from ZF+DC, then it would be consistent with AD. However, AD implies that there is no injection from $\omega_1$ to $\mathbb R$. On the other hand, inasmuch as there is a surjection from $\mathbb R$ to $\omega_1$, the Partition Principle implies that there is an injection from $\omega_1$ to $\mathbb R$. Since the Partition Principle is incompatible with AD, it is not a theorem of ZF+DC, and a fortiori neither is your theorem.