Understanding axiom of choice from examples

151 Views Asked by At

$ \newcommand{\N}{\mathbb{N}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} $ I thought I understood AC (axiom of choice), but I am now totally confused through some discussions.

Let me examine whether each of the following examples needs AC. Assume ZF.

  1. Choose $ x \in (0, 1) $.
    AC is unnecessary. (One existential quantification over an interval.)

  2. Let $ n \in \N $. Choose $ x \in (0,1)^n $.
    AC is unnecessary because $x$ can be chosen by finite existential quantification.

  3. Let $ A = \{[a, b]| a,b \in \R,~a\le b\} $. There is a function $f:A \to \R$ such that $ f(I) \in I$ for all $ I \in A$.
    AC is unnecessary because we can declare a choice function $c: A \to \R$ defined by $ c(I) = \min I \in I $ for all $I \in A$ though $A$ is infinite.

  4. Let $ A = \{(a, b)| a,b \in \R,~a < b\} $. There is a function $f:A \to \R$ such that $ f(I) \in I$ for all $ I \in A$.
    AC is necessary because there is no finite quantification over $ A $ that specifies the choice of $x$.

  5. Let $ A = \{[a, b] \cap \Q| a,b \in \R,~a < b\} $ and $ B = \{(a, b) \cap \Q| a,b \in \R,~a < b\} $. Either there is a function $f:A \to \R$ such that $ f(I) \in I$ for all $ I \in A$ or there is a function $f:B \to \R$ ....
    AC is necessary by the same reasoning in 4.

  6. Let $ A = \{ (a,b)|a,b \in \Q,~a < b \} ​$. There is a function $f:A \to \R$ such that $ f(I) \in I$ for all $ I \in A$.
    AC is necessary by the same reasoning in 4 though $A$ is countable. I considered this example from the discussion by Karagila, which seems to be inconsistent with what I learned. Does countability assume some important role here?

Would you figure out what I am missing about the notion of AC?

Edit:

I think I overlooked some simple factors in making examples. :) I would like to add one more example:

  1. Let $A \subseteq P(\R)$. There is a function $f:A \to \R$ such that $ f(I) \in I$ for all $ I \in A$.

Then, is 7. the only case AC actually needed?

1

There are 1 best solutions below

4
On BEST ANSWER

In fact $\mathsf{AC}$ is unnecessary in each of the examples in your post (before the edit that added example 7). I'll explain $5B$; in fact, the same choice function works for the other examples you ask about.

(I'm assuming that the "$\le$"s should be "$<$"s when open intervals are concerned, since $(a,a)=\emptyset$ and that has nothing to do with choice.)

The key point isn't that $\mathbb{Q}$ is countable per se, but rather that it is well-orderable (which is weaker). Specifically, fix at the outset a bijection $f:\mathbb{N}\rightarrow\mathbb{Q}$. Now given $a<b$ let $$c_{a,b}=f(\min\{n: f(n)\in (a,b)\}).$$

It's easy to see that $c_{a,b}\in(a,b)\cap\mathbb{Q}$ whenever $a<b$. Consequently the map sending the interval $(a,b)$ to the number $c_{a,b}$ is - modulo appropriate choice of $f$ - a "simply-definable" choice function for the family of intervals in $5B$, and so choice plays no role.