Asaf Karagila
I don't have much choice...

Equivalent to the axiom of choice that I didn't know about

There are 3 comments on this post.

First I must apologize. I wanted to write a second post about forcing and preserving choice principles (I gave a nice talk in the student seminar about a week after the previous post), and I had a lot of things to say. I just ended up not writing it, and for absolutely no good reason. And somehow things continued that way and I felt more and more awkward to post anything because of that, but the vicious cycle must break somewhere.

I recently tried to figure out the consequence of some forcing in \(\ZF\). This has led me to the following statement:

There exists $X$ such that there exists a surjective $f\colon X\to X$ which does not admit and inverse. (That is a function $g\colon X\to X$ such that $g$ is injective and $f(g(x))=x$.)

This seems a little unlikely. Luckily I met Thomas Jech at the Mostowski 100 conference. I asked him about this, and he came up with an example, and said that the "right" question is whether or not this is equivalent to the axiom of choice. Based on his idea I came up with a simple proof for the general case, outlined below.

The axiom of choice fails if and only if there exists a set $X$ and a surjection $f\colon X\to X$ without an inverse.

The proof is quite simple. Suppose the axiom of choice holds, then the principle fails trivially; but suppose that the axiom of choice fails. In particular there is a surjection \(f\colon A\to B\) which does not admit an inverse, moreover we may assume \((A\times\omega)\cap B=\varnothing\). Consider \(X=A\times\omega\cup B\), and \(g\colon X\to X\) defined in the following way, fix some \((a,n)\in A\times\omega\) and define \(g\) to be : \[g(x)=\begin{cases}f(u) & x=\tup{u,2k+1}\in A\times\omega\\ (u,k) & x=\tup{u,2k}\in A\times\omega\\ (a,n) & x\in B\end{cases}\]

Clearly the map is a surjection. However it does not admit an inverse, since \(f\) does not admit an inverse. \(\square\)

The example given by Jech, by the way is to take a model where \(\aleph_1\nleq\frak c\) and do a similar trick as above with \(X=\Bbb R\cup\omega_1\).

In other very exciting news, I am going to be the teaching assistant of no other than Azriel Levy in the upcoming naive set theory course!


There are 3 comments on this post.

By Junyan Xu
(Oct 19 2013, 22:12)

Isn't x|->x, (u,k)|->(u,2k) an inverse of g?

By Junyan Xu
(Oct 19 2013, 22:21)

I think you meant to map x\in B to some fixed element in A\times\omega, then it works.

By Asaf Karagila
(Oct 20 2013, 00:48 In reply to Junyan Xu)

Yes, you're right. Thank you!

Want to comment? Send me an email!