Talk:Axiom of choice

Images at top

I like the new one, but it has the same technical problem as the old one. Take the colored item. No choice axiom needed for that. -- YohanN7 (talk · contribs) 10:11, 5 April 2017‎ (UTC)

Surjection between any two sets?

The article says that the axiom of choice is equivalent to the existence of a surjection between any two sets. Let A be the singleton {a}, let B be a set with two elements. Correct me if I am wrong but it seems impossible to have a surjection from A to B in this case. ~2025-43698-88 (talk) 18:55, 28 December 2025 (UTC)

I think it means in one direction or the other. There's a surjection from B to A.

Now, if one of the sets is empty and the other is not, then there is no surjection in either direction, so that at least would need to be clarified if it currently isn't (I haven't checked). --Trovatore (talk) 19:16, 28 December 2025 (UTC)

It does say that both sets are non-empty. I see your point about allowing the map to be from A to B or from B to A.

Does this result have a name? ~2025-43564-66 (talk) 19:27, 28 December 2025 (UTC)

Apparently it does! It's known as surjective comparability. Bbbbbbbbba (talk) 02:08, 29 December 2025 (UTC)

Re: Kuratowski's lemma

@JRSpriggs:

• Kuratowski's lemma: If ${\mathcal {A}}$ is any family of sets with the property that for any subfamily ${\mathcal {C}}$ of ${\mathcal {A}}$ totally ordered by set inclusion, its union $\cup _{A\in {\mathcal {C}}}(A)$ is an element of ${\mathcal {A}}$, then ${\mathcal {A}}$ contains a maximal element with respect to inclusion.

⁠${\mathcal {C}}=\emptyset$⁠ is always subfamily of ⁠${\mathcal {A}}$⁠, so the prerequisite of the lemma says that ⁠$\cup _{A\in {\mathcal {\emptyset }}}(A)=\emptyset$⁠ is an element of ⁠${\mathcal {A}}$⁠. Therefore it is not necessary to explicitly state that ⁠${\mathcal {A}}$⁠ is nonempty. Bbbbbbbbba (talk) 07:37, 18 February 2026 (UTC)

Disjoint subcollection

To @Galois314:: Could you please provide a proof (both ways) that "For every collection ${\mathcal {A}}$ of nonempty sets, there exists a disjoint subcollection ${\mathcal {C}}$ of sets whose union $\cup _{S\in {\mathcal {C}}}(S)$ intersects every one of the sets of ${\mathcal {A}}$." is equivalent to the axiom of choice. JRSpriggs (talk) 18:50, 24 February 2026 (UTC)

The proofs seem pretty simple at least. For the "AC → this" direction, simply well-order ⁠${\mathcal {A}}$⁠, and let ⁠${\mathcal {C}}=\{S_{\alpha }\in {\mathcal {A}}\mid \forall \beta <\alpha ,\;S_{\alpha }\cap S_{\beta }=\emptyset \}$⁠. For the "this → AC" direction, for any collection ⁠$X$⁠ of nonempty sets, let ⁠${\mathcal {A}}=\{\{(\emptyset ,S),(S,x)\}\mid S\in X,\;x\in S\}$⁠.

The real question to ask is whether this is notable (useful) enough to justify its inclusion. At a glance it looks like a random exercise in a textbook. Bbbbbbbbba (talk) 08:00, 26 February 2026 (UTC)

To Bbbbbbbbba: Thank you. That works. The "this → AC" direction is quite clever. Non-obvious equivalents are probably more useful than the obvious ones. JRSpriggs (talk) 14:29, 26 February 2026 (UTC)

This is a notable property of collections of sets which can be useful at times. For instance, let's say that in a certain proof in analysis or topology, you need to exhibit a covering of a given space by a certain collection of subsets, and it is desired for this collection to have the property of being disjoint. Let's say you are very easily able to construct a covering of this space that is not disjoint, and that you are able to show that any subcollection of this covering whose union intersects all the sets of this covering must itself be a covering of this particular space. Then, using the axiom of choice in the form of this special property of sets, you can immediately deduce that a disjoint covering must also exist (namely as a maximal disjoint subcollection of the non-disjoint covering you constructed). Galois314 (talk) 05:50, 27 February 2026 (UTC)

I should add that another elegant proof of the forward direction (AC -> given statement) can be given using Zorn's lemma (which is itself equivalent to AC). For this, consider the set of all disjoint subcollections ${\mathcal {C}}$ of ${\mathcal {A}}$, partially ordered by set inclusion. Then, the given statement is equivalent to saying that this partially-ordered set has a maximal element (can you see why?). Every chain $\dots \subseteq {\mathcal {C}}_{i-1}\subseteq {\mathcal {C}}_{i}\subseteq {\mathcal {C}}_{i+1}\subseteq \dots$ of disjoint subcollections of ${\mathcal {A}}$ clearly has an upper bound that is also a disjoint subcollection of ${\mathcal {A}}$, namely the union of all the ${\mathcal {C}}_{i}$ in the chain. This then implies by Zorn's lemma that this partially-ordered set indeed has a maximal element, as desired. Galois314 (talk) 00:27, 27 February 2026 (UTC)

Cartesian product

The article says that the Axiom of Choice is equivalent to the statement that The Cartesian product of any collection X of nonempty sets is nonempty. Other formulations of the Axiom of Choice talk about "choosing". My question is: is there a distinction between stating that the Cartesian project is nonempty and stating that one can choose an element from the Cartesian product? If the article is correct, I'd like to see a sentence or two on how "being nonempty" implies that one can "choose an element from the non-empty product" in this context — or a sentence on why this isn't the right question to be asking. Alternatively, if the article needs fixing because being nonempty should be replaced by a statement about choosing, I'd like it to get fixed. Regardless, if you are knowledgeable about this then please consider making appropriate edits. Thank you! —Quantling (talk | contribs) 17:21, 28 May 2026 (UTC)

"Choosing" is just a way to make the statement more intuitive. The mathematical statement doesn't require a chooser. I suppose you could tease out a difference between the two statements in a context where you weren't sure of existential instantiation, but the default approach is to consider existential instantiation to be a law of logic.

Bottom line is, the two statements are not different, and I don't see anything that needs to be fixed here. --Trovatore (talk) 17:38, 28 May 2026 (UTC)

Trovatore is correct. Saying a set S is nonempty and saying one can choose an element from the set S mean the same thing. The only reason we need the axiom of choice is because proofs have to be finite, so we can only make a finite number of choices in a proof. If an infinite number of choices are needed, then we have to have the axiom to allow us to choose a choice-function which gives us all the infinite number of choices in one operation. JRSpriggs (talk) 22:59, 28 May 2026 (UTC)

The Cartesian product is just the set of choice-functions, so making a choice from the Cartesian product is choosing a choice-function. Notice that this does not reduce the infinite number of choices to zero, but merely to one choice. JRSpriggs (talk) 13:11, 29 May 2026 (UTC)

Why does a proof have to be finite? We need to be able to go thru the proof one step at a time and verify that each step is justified so that we know it is true.

Proof using the axiom of choice involves parallelization, that is, we are justifying a possibly-infinite number of cases simultaneously. So there must be some similarity among the cases to make that parallel structure work. Some of the weaker versions of the axiom are restrictions on the degree of similarity among the cases. JRSpriggs (talk) 13:28, 29 May 2026 (UTC)

Might we add a sentence to the article near there that says something like Saying a set is nonempty and saying one can choose an element from the set mean the same thing.? Given that the other formulations discuss "choosing", this clarification could help the reader's understanding of the formulation in terms of the Cartesian product. —Quantling (talk | contribs) 03:13, 1 June 2026 (UTC)

Short of adding a paragraph expressing what I said above, I do not see how or where the article could be improved. So please add what you think is necessary where you think it is necessary. If there is something wrong with it, we will fix it. Thank you. JRSpriggs (talk) 14:12, 1 June 2026 (UTC)

Re-reading the article, I think the confusion is more about "construction" vs. "existence". I've made an edit to the article to try to fix that. If you revert, please do me the favor of explaining the details here. —Quantling (talk | contribs) 16:16, 1 June 2026 (UTC)