Constructing A Choice Function (Munkres Lemma 9.2)

135 Views Asked by At

In Munkres, there's a proof for the existence of a choice function. I understood what was going on until the line underlined in red at the bottom. It seems that all the $B'$ partition $\mathcal{B} \times \cup B_{B \in \mathcal{B}}$. If we use the axiom of choice and create the choice function $c$ that chooses one element from each partition, then we are just creating a function that chooses every $(B,x) \in \mathcal{B} \times \cup B_{B \in \mathcal{B}}$. In particular, one imagines that the rule for $c \subset \mathcal{B} \times \cup B_{B \in \mathcal{B}} $ contains $(B,x_1)$ and $(B,x_2)$ where $x_1$ and $x_2$ are from the same set $B$. So why is the underlined statement true? Maybe I'm not understanding how $c$ is being constructed.

enter image description here

enter image description here

2

There are 2 best solutions below

0
On BEST ANSWER

Maybe I'm not understanding how $c$ is being constructed.

The axiom of choice is not a constructive principle, but asserts the existence of a set with a certain property.

In the present case it asserts the existence of a set $c$ consisting of exactly one element from each $B' \in \mathcal C$. In other words, for each $B' \in \mathcal C$ the set $c \cap B'$ contains a single element.

Let $p : \mathcal B \times \bigcup_{B \in \mathcal B} B \to \mathcal B$ and $q : \mathcal B \times \bigcup_{B \in \mathcal B} B \to \bigcup_{B \in \mathcal B} B$ denote the projections onto the first and the second factor of $\mathcal B \times \bigcup_{B \in \mathcal B} B$.

We have $c \subset \mathcal B \times \bigcup_{B \in \mathcal B} B$. We claim that $p \mid_c : c \to \mathcal B$ is a bijection. Surjectivity is obvious. To check injectivity, consider $(B_1,x_1), (B_2,x_2) \in c$ such that $p(B_1,x_1) = p(B_2,x_2)$. This means $B_1 = B_2 = B$ and $x_1, x_2 \in B$, thus $(B,x_1),(B,x_2) \in c \cap B'$. Since $c \cap B'$ contains a single element, we see that $(B,x_1) = (B,x_2)$.

The desired choice function $\bar c : \mathcal B \to \bigcup_{B \in \mathcal B} B$ is then given as the composition $$\mathcal B \xrightarrow{(p \mid_c)^{-1}} c \hookrightarrow \mathcal B \times \bigcup_{B \in \mathcal B} B \xrightarrow{q} \bigcup_{B \in \mathcal B} B .$$

0
On

The axiom of choice is being used so that $c$ contains exactly one element from each $B' \in \mathcal{C}$. The proof is not "creating a function that contains every $(B, x) \in \mathcal{B} \times \cup_{B \in \mathcal{B}} B$" like you are guessing. Thus $c$ cannot contain both $(B, x_1)$ and $(B, x_2)$ for $x_1 \neq x_2 \in B$ because then it would contain at least two distinct elements of $B'$, contrary to how $c$ was constructed.