Proof Verification: Cartesian Product of Finitely Many Nonempty Sets is Nonempty (Without AoC)

Question

Synopsis

Please verify my proof. I would also appreciate any tips on how I might improve my mathematical writing. Thank you.

Exercise

Assume that $H$ is a function with finite domain $I$ and that $H(i)$ is nonempty for each $i \in I$. Without using the axiom of choice, show that there is a function $f$ with domain $I$ such that $f(i) \in H(i)$ for each $i \in I$. [Suggestion: Use induction on $\text{card }I$.]

Proof

Let $P(n)$ be the condition that $\text{card }I = n$ and that $H(i)$ is nonempty for each $i \in I$. Let $Q(n)$ be the condition that there exists a function $f$ with $\text{dom}f = I$ and with $f(i) \in H(i)$ for all $i \in I$. Consider the set $S = \{n \in \omega \mid P(n) \Rightarrow Q(n)\}$. We will show through induction that $S$ coincides with $\omega$. The base case is vacuously true. For the inductive hypothesis, suppose that $P(k) \Rightarrow Q(k)$. We wish to show that $P(k^+) \Rightarrow Q(k^+)$. Suppose that $\text{card }I = k^+$. Then there exists a bijection $f$ from $I$ onto $k^+$. Consider the set $A \subseteq I$ where $A = f^{-1}[\![k]\!]$. Clearly, $\text{card }A = k$, and by the inductive hypothesis, there exists a function $g$ with domain $A$ and with the property that for each $i \in A$, $g(i) \in H(i)$. Now consider the set $B \subseteq I$ where $B = f^{-1}[\![k^+ - \{0\}]\!]$. Similarly, $\text{card }B = k$, and the inductive hypothesis suggests the existence of a function $h$ such that $\text{dom }h = B$ and $h(i) \in H(i)$ for all $i \in B$. With these two functions at our disposal, we can now construct a third function $F = g \cup (h \upharpoonright \{f^{-1}(k)\})$ such that $\text{dom}F = I$ and $F(i) = H(i)$ for all $i$ in $I$, satisfying $Q(k^+)$. Hence, $S$ is inductive, and coincides with $\omega$.

Note that $h \upharpoonright \{f^{-1}(k)\}$ denotes the ordered pair $\langle f^{-1}(k), h(f^{-1}(k)) \rangle$

Answer 1

Your proof is correct apart from one error in the definition of $F$: You meant to write $f^{-1}(k)$ instead of $f^{-1}(k^+)$.

The second application of the induction hypothesis seems unnecessary. You can just write $i_0$ for the element of $I\backslash A$, choose an element $x$ of $H_{i_0}$ and define $F=g\cup\{(i_0,x)\}$.

Style Critique: You focus a bit too much on technicalities, which sometimes makes it hard to quickly grasp the idea behind an argument. In particular, it is much better to use the language of natural numbers instead of ordinals, i.e. you should not use the "fact" that natural numbers are elements and subsets of each other, but simply consider them as elements of an ordered set. This also makes notations like $f^{-1}(k)$ (where $k$ could be interpreted as an element or a subset) less ambiguous.

Answer 2

There is no ensurance that the function you get on $A$ will coincide with that on $B$ on $A \cap B$, so in general you will not be able to combine them.

Just take the function on $A$ and extend it by a single chosen pair (no AC needed) to extend it to $I$.

All you need is that if $|I|=n+1$ then $|I\setminus \{i_0\}|=n$ for any $i_0 \in I$ and then we add a choice for $i_0$ from the non-empty $H(i_0)$ to be done. You add the one pair $(i_0, y)$ to the function defined on $I$ etc.

Don't overcomplicate things. You don't need the set $S$ either. Just induct on $P(n)$ as the statement

There exists a choice function for a non-empty family of non-empty sets $\{H(i), i \in I\}$ whenever $|I|=n$.

just as the hint said. The showing a set to be inductive etc. need not be done every time you do an induction proof, it's part of the original proof that induction as a principle of proof is valid. After that you just show $\forall n: P(n)\implies P(n+1)$ directly (and $P(0)$ too).

Answer 3

Synopsis

Taking advice from @Henno Brandsma and @Stefan, I have shortened and simplified my proof considerably. I think in my original proof, I was too held up on trying to "choose" an element without explicitly doing so because I had a misunderstanding of the axiom of choice (which now I know is only needed when one is choosing random elements from an infinite number of sets without an explicit rule). My new proof eliminates this paranoia.

Proof Revision

Let $P(n)$ be the condition that if $\text{card }I = n$ and that $H(i)$ is nonempty for each $i \in I$, then there exists a function $f$ with $\text{dom}f = I$ and with $f(i) \in H(i)$ for all $i \in I$. We will perform induction on $P(n)$. $P(0)$ holds vacuously. For the induction hypothesis, suppose $P(n)$ is true. Then if $|I| = n+1$, $|I - \{i_0\}| = n$ for any $i_0 \in I$. Consider the choice function $g$ on $I - \{i_0\}$ guaranteed by the induction hypothesis. Then the function $h = g \cup \langle i_0, y \rangle$ with $y \in H(i_0)$ defines a choice function satisfying $P(n^+)$. So $P(n)$ holds for all $n \in \omega$.