General Distributive Law and Axiom of Choice

Question

Where can I find the proof of the fact that general distributive law of union over intersection and intersection over union is equivalent to Axiom of Choice?

The mathematical formulation of the general distributive law of intersections over unions if as follows: Suppose that $\{A_{ij}\mid \langle i,j\rangle\in I\times J\}$ is a family of sets, then: $$\Large\bigcap_{i\in I}\bigcup_{j\in J} A_{ij}=\bigcup_{f\in J^I}\bigcap_{i\in I}A_{i\, f(i)}$$

Answer 1

I don’t know a reference, but I can give you a fairly short proof. (I want it available as a reference for myself, even if you really want only a reference.)

The harder direction is that the general distributive law in question implies $\mathsf{AC}$. I’ll prove $\mathsf{AC}$ in the following form: for any sets $X$ and $Y$, each surjection $f:X\to Y$ has a right inverse.

Proof: Let $X$ and $Y$ be sets, and let $f:X\to Y$ be surjective. For $\langle y,x\rangle\in Y\times X$ let $$A(y,x)=\begin{cases}\{0\},&\text{if } y=f(x)\\0,&\text{otherwise}\;.\end{cases}$$ For each $y\in Y$ there is an $x\in X$ such that $y=f(x)$, so $\bigcup_{x\in X}A(y,x)=\{0\}$, and therefore $$\bigcup_{g\in{^YX}}\bigcap_{y\in Y}A\big(y,g(y)\big)=\bigcap_{y\in Y}\bigcup_{x\in X}A(y,x)=\{0\}\;.$$ Thus, there is a $g\in{^YX}$ such that $$\bigcap_{y\in Y}A\big(y,g(y)\big)=\{0\}\;,$$ i.e., such that $y=f\big(g(y)\big)$ for each $y\in Y$. Clearly $f\circ g=\operatorname{id}_Y$, as desired. $\dashv$.

The other direction is routine. Assume $\mathsf{AC}$. Given sets $A(i,j)$ for $\langle i,j\rangle\in I\times J$, suppose that $x\in\bigcap_{i\in I}\bigcup_{j\in J}A(i,j)$; then $J_x(i)=\{j\in J:x\in A(i,j)\}\ne\varnothing$ for each $i\in I$. Let $\xi:I\to J$ be a choice function for $\{J_x(i):i\in I\}$; then

$$x\in\bigcap_{i\in I}A\big(i,\xi(i)\big)\subseteq\bigcup_{\varphi\in{^IJ}}\bigcap_{i\in I}A\big(i,\varphi(i)\big)\;.$$ On the other hand, if $x\in\bigcup_{\varphi\in{^IJ}}\bigcap_{i\in I}A\big(i,\varphi(i)\big)$, then there is a $\varphi\in{^IJ}$ such that

$$x\in\bigcap_{i\in I}A\big(i,\varphi(i)\big)\subseteq\bigcap_{i\in I}\bigcup_{j\in J}A(i,j)\;.$$