I'm trying to do the problem 8.2 of the book Notes on Set Theory of Moschovakis.

I want to prove that Axiom of Choice is equivalent to this statement:

$$\forall A\neq \emptyset,\, \forall f:A\longrightarrow B, \,\exists g: B\longrightarrow A \text{ such that } \forall x\in A,\, f(g(f(x)))=f(x).$$

I'm using this form of axiom of choice

(AC) $$(\forall x\in A)(\exists y\in B) P(x,y) \Rightarrow (\exists f:A\longrightarrow B)(\forall x\in A)P(x,f(x))$$

To prove that (AC) implies I think if we make

$$P(x,y)\Longleftrightarrow y\in x\setminus (\cup A \setminus x)$$

then $g(x)=f^{-1}(x)$ if $x\in\operatorname{Im}(f), g(x)=$ an arbitrary element of $A$ otherwise, is well defined and satisfies the statement. Is this legal?

I would like you to give a hint to prove the other implication.

  • $\begingroup$ $y\in x\setminus(\bigcup A\setminus x)$ definitely isn’t right: why would you expect $y$, an element of $B$, to be an element of $x\in A$? Note also that your version of $\mathsf{AC}$ doesn’t imply that the guaranteed $f$ is injective, so you can’t assume that $f^{-1}$ exists. $\endgroup$ – Brian M. Scott Feb 16 '15 at 19:17

You can't quite write $f^{-1}(x)$, since $f$ might not be injective, or reversible.

The key here is to note two things:

  1. (Which you've done) It doesn't matter how you define $g$ outside $\operatorname{Im}(f)$, since $A$ is not empty, this can be any arbitrary choice.

  2. We need the axiom of choice to produce $g$, so $P(x,y)$ needs to be between $B$ and $A$ (the roles are reversed here). Try $P(b,a)\iff f(a)=b$.

In the other direction, the goal is to have the function which exists as promised by the assumption to be your choice function. So $\exists g$ and $\exists f$ should be somewhat similar.

So given $X$ and $Y$ such that $P\subseteq X\times Y$ and $\operatorname{dom}(P)=X$, we need to find some $A$ and $B$ and a function $f\colon A\to B$ such that the map $g\colon B\to A$ will help us define $h\colon X\to Y$ for which $P(x,h(x))$ holds.

Note that $h$ chooses for each $x$ some element $y\in\{y\mid P(x,y)\}$. What would happen if we take $A=P$ and $B=X$, and $f(x,y)=x$, what does $g\colon X\to A$ will guarantee us? And what can we define from it?

  • $\begingroup$ Thank you. You always help me with set theory! $\endgroup$ – MaríaCC Feb 16 '15 at 21:08
  • $\begingroup$ My students didn't believe me at first, but it is my hobby, teaching set theory. $\endgroup$ – Asaf Karagila Feb 16 '15 at 21:20
  • $\begingroup$ Good productive hobby! $\endgroup$ – MaríaCC Feb 16 '15 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.