Axiom of Choice --Example Problem

Question

Q: Suppose that for any set $X$ and any function $f:X\rightarrow X$ there exists $g:X\rightarrow X$ such that $fgf=f$. Prove that any set has a choice function.

My attempt:

Let $A=\left \{a,b,c... \right \}\subset X$ be an arbitrary non-empty set.

Choose $f:X\rightarrow X$ defined by

$x\rightarrow x_{0}$ if $x\in A$

$x\rightarrow x_{1}$ if $x\notin A$

$**$ where $x_{0}$ and $x_{1}$ are arbitrary unique elements of $X**$

By hypothesis, a $g$ exists such that $f(g(f(x)))=f(x)$

$\Rightarrow f(g(f(x_{0}))) = f(x_{0})$

$\Rightarrow g(f(x_{0})) \in \left \{x\in X| f(x) = x_{0} \right \}$

By defintion of $f$, $\left \{x\in X| f(x) = x_{0} \right \} = A$

$\therefore$ Since $g(f(x_{0})) \in A$, $g$ is a choice function that picks an element, $g(f(x_{0}))$, for any set $A$

I feel like this is really close to a correct solution, but the big problem I see with it is that the $**$ step requires that $X$ must have at least two unique elements. My hope is that this can be fixed by just stating that a set with one element $a$ only has one non empty subset $\left \{a \right \}$ and so the choice function can just choose a. Does this fix the proof? Are there any other errors?

Answer 1

The axiom of choice does not state "we can choose an element from any non-empty set". This is just existential instantiation.

The axiom of choice does state "given any set of non-empty set $A$, there is a function $g\colon A\to\bigcup A$, such that $g(a)\in a$ for all $a\in A$".

---

In particular, your solution, as written, is wrong. But as you might feel, you are a bit in the right direction. Depending on other equivalences, or the exact formulation of the axiom of choice that you already proved, the proof ranges between "slightly less easy" and "borderline trivial".

What you should be doing is starting with a family of sets $\{A_i\mid i\in I\}$, and from that engineer a set $X$ and a function $f$, such that the existence of $g$ will guarantee a choice function from the original $\{A_i\mid i\in I\}$.

Answer 2

The issue of $X$ having at least $2$ element is not a big deal.

However, you seemed to aim to prove the axiom of choice for a single set $A$, instead of a given family of nonempty sets. (Note that your definition of $f$ and $g$ depends on $A$.)

So, your proof should rather start with assuming a family $(A_i)_{i\in I}$ of nonempty sets is given, where $I$ is a set, and then provide a choice function $I\to\bigcup_iA_i$.

Hint: Let $X$ be the disjoint union of $A_i$'s, of $I$ and of one more singleton $\{0\}$, and define $f:X\to X$ by sending all elements of $A_i$ to $i$, and all elements of $I$ and $0$ to $0$.