Talk:Surjection iff Right Inverse

The statement that any surjection has a right inverse is in fact equivalent to the axiom of choice. Is there a page about this? I can easily provide three equivalent forms of the axiom of choice, and a proof of equivalence:

Any surjection $f: X \to Y$ has a right inverse.

For every $X \ne \O$ there exists a function:

$f: \powerset X \setminus \set \O \to X$

such that $f(Y)\in Y$ for each $Y\subset X$ with $Y \ne \O$.

Let $\family {X_i}_{i \mathop \in I}$ be a family of sets such that $X_i \neq \O$ for each $i\in I$.

Then:

$\ds \prod_{i \mathop \in I} X_i \ne \O$

where

$\ds \prod_{i \mathop \in I} X_i = \set {f: I \to \bigcup_{i \mathop \in I} X_i : \forall i \in I: f(i) \in X_i}$

Who has ideas on how to add them? I do not want to add it while there are other proofs of equivalence on, say, two out of these.

Second of all, I have found plenty more equivalent forms of the axiom of choice, while these three easily follow from on another, the others might not... JSchoone 16:31, 31 January 2012 (EST)

Excuse me ... you have actually read this page?? There are two proofs, both of which are specific about the use of AoC. There is even a category for proofs of AoC and there are already quite a few equivalent statements. AoC itself is defined as your final statement, using the language of cartesian products. --prime mover 17:23, 31 January 2012 (EST)

I have, but it says nowhere, that it is equivalent to the axiom of choice, it just says that this page follows from the axiom of choice. It is quite a difference. Still I cannot find the page where this is proven, so if you can, please tell me where it is and accept my apologies for not looking well enough. JSchoone 05:46, 1 February 2012 (EST)

Sorry, I misunderstood. I understand what you mean now.

What we are saying here, then, is:

a) If the Axiom of Choice holds, then Surjection iff Right Inverse is true.

b) If the Axiom of Choice does not hold, then there exists a set whose subsets do not admit a choice function. Therefore it is possible to construct a surjection such that the preimages of the elements of the range do not admit a choice function, and therefore such a right inverse can not be constructed.

Fair enough, it should be straightforward to amend this page so that (b) above can be formulated. Feel free to do so.

What puzzled me was your two statements of the Axiom of Choice above, as though it were new to ProofWiki. As I said,. this is already all covered, except for (b) above, as I mentioned. We also have several other equivalences of AoC. The usual wording is: this result is true if AoC holds - but we rarely add the wording in the other direction: "if AoC fails to hold, then so does this result." This is what is usually meant when we say "This result depends on AoC." I never thought of is as worth raising. --prime mover 08:57, 1 February 2012 (EST)

The converse statement appears more useful and powerful if one states it as: 'This result implies AoC'. The non-emptiness of Cartesian products and the principle of cardinal comparability (trichotomy law) are too important for me to consider the negation of AC; more so as negating AC makes stuff (like Banach-Tarski) only undecidable, not false. --Lord_Farin 09:44, 1 February 2012 (EST)

The thing is this. There are many results which are usually reported "dependent upon AoC". In this context, this is the same as saying "If AoC is true, then this result is true. If AoC is false, then so is this result." Thus, all results which are dependent upon AoC can be reported as being equivalent to AoC.

Now, some results are usually reported as being "equivalent to AoC", in particular, Zorn's Lemma, the Hausdorff Maximality Principle and the Well-Ordering Principle. These come across as being singled out, if you like, as being "special" results which depend upon AoC, because (so you understand from the books that talk about them) "AoC is dependent upon these results" blah blah ... and no mention is made that all these other sundry results (e.g. this one) are in some way less "significant" because they are merely stated as being "dependent upon AoC" not "equivalent to it".

That woolly thinking stops here! Every result which depends on AoC is equivalent to AoC! Shout it loud!

From now, and JSchoone has opened my eyes, all results reported here as "dependent on AoC" will be reported to be (and proved to be) "equivalent to AoC". The category "AoC" will be re-annotated to be defined as "These results are all equivalent to AoC".

Comments? (It might not be me doing the above work today because I have had some plans made for me which will soak up a fair amount of time this evening.) --prime mover 14:01, 1 February 2012 (EST)

What about the 'Axiom of Countable Choice' and, more importantly, Countable Union of Countable Sets is Countable? Both are not implying AC, but do depend on it. The distinction is significant enough to be made, at least in my opinion. Maybe 'Category:Equivalents to AC' or something like that? --Lord_Farin 16:45, 1 February 2012 (EST)

I don't know. I haven't read a textbook that discusses them. If these are things that need to be defined and explained, then go to it. I have insufficient knowledge. --prime mover 18:08, 1 February 2012 (EST)