# How short can we state the Axiom of Choice?

How short can we state a principle which is equivalent with the Axiom of Choice under $ZF$? The principle should be a sentence in the language of set theory with only $\in$ and$=$ as extralogical relation signs; I thus disregard solutions that appeal to selectors as the epsilon operator. My motivation is to extend an interpretation of $ZF$ to one of $ZFC$, and a short sentence schema will make my work - simpler and shorter.

Update: On the basis of comments I have developed an answer with a challenge as to whether we may improve.

-
Can you give just one example of a solution that you wouldn't disregard, whether long or not or simple or not? –  Todd Trimble Aug 17 '14 at 20:42
I conjecture that the selection operators that you want to exclude are things like Hilbert's epsilon operator (also known as Bourbaki's tau operator) that are built into the language and thus try to make AC part of the underlying logic. In other words, I conjecture that you would not object to a formulation asserting, in the usual language of set theory, the existence of some sort of selection function. –  Andreas Blass Aug 17 '14 at 21:18
Okay, thanks Frode. As a friendly suggestion: please consider editing your question to take into account Andreas's (correct) conjecture, and please consider removing the word "simple" (or "simply") since that's not so easy to measure, and specify shortness as the desired criterion. I think you then want to specify that you are looking for formulae written in the formal language of ZF -- in that case I think the question becomes crystal clear. –  Todd Trimble Aug 17 '14 at 22:58
The choice of tagging really throws the question off-track. It has nothing to do with category theory, or with topos theory. It's a question about logic and perhaps set theory or the axiom of choice. It took me nearly 10 minutes of confusion to understand the question, and it seems I'm not the only one who was confused. Perhaps a better choice of tags can help. –  Asaf Karagila Aug 18 '14 at 0:13
@Asaf Karagila I did not tag it with category theory or topos theory, and will attempt to untag those two topics. –  Frode Bjørdal Aug 18 '14 at 0:18

The following paper by Kurt Maes is focused on a version of the question at hand here, namely, finding an equivalent formulation of AC in the language of set theory using the fewest number of quantifiers, rather than merely the shortest length. In his main result, Maes finds a 5-quantifier assertion equivalent to the axiom of choice. The statement is built on the same statement as in François's answer, but modified to use fewer quantifiers (Maes has five, in comparison with ten for François; but of course François wasn't trying to minimize that quantity).

Maes's result refuted a conjecture of Harvey Friedman, which in the introduction the author mentions was stated on F.O.M., that it would not be possible to state a formulation of the axiom of choice using only five quantifiers.

Please see Maes's solution in his paper.

When I first heard about the Maes result (August 2004, apparently an earlier draft of his paper—I haven't checked the differences), I naturally set myself the task of proving the main result myself, without looking at Maes's argument. I would encourage the same of all of you---before reading further, try to express AC in the language of set theory using only five quantifiers! Here is what I had come up with (retrieved after digging around in my old computer files):

Theorem. AC is equivalent (in ZF) to the following assertion: $$\forall A\exists B\forall a\in A\, \exists x\forall z$$ $$(x \in a \cap B) \wedge (z \in a \cap B \implies z=x) \wedge (a \neq B)$$ $$\text{or }\quad(B \in x) \wedge (x \in A) \wedge (a \neq x)$$ $$\text{or }\quad(B \in A) \wedge (z \notin B).$$

Proof. The point is that in order to get down to only five quantifiers, you have to essentially reuse the quantifiers to cover the various cases. The idea is that clause 1 expresses that $B$ is a selection set for $A$, when $A$ is a family of disjoint nonempty sets (plus something extra useful when $A$ is not like that). Clause 2 expresses that $A$ has elements that are not disjoint (at least two contain $B$). Clause 3 expresses that $A$ contains the emptyset ($B=\emptyset$).

AC easily implies the assertion. If $A$ is a family of disjoint nonempty sets, then we can let $B$ be a selection set for $A$, and verify clause 1. (note: in order to get $(a \neq B)$ in the case that $A$ is a singleton, we can freely add irrelevant elements to $B$ outside of $\bigcup A$.) If $A$ contains non-disjoint sets, we let $B$ be any element which is in at least two elements of $A$, and then we can always be in clause 2, since for any element of $A$ we can find another element of $A$ containing $B$. Finally, if $A$ contains the empty set, we can set $B=\emptyset$, and verify always clause 3.

Conversely, suppose that the stated principle holds. To prove AC, it suffices to construct a selection set for a family $A$ of disjoint non-empty sets. By replacing $A$ if necessary with the isomorphic copy $\{\{w\}\times a\mid a \in A\}$, where $w$ has high rank (such as $w=A$ itself), we may assume that every element of $\bigcup A$ has the same rank. Thus, every element of $A$ has rank one higher than this, and every element of $\bigcup\bigcup A$ has rank lower than this. It follows that no element of $\bigcup A$ is in $A$, and no element of $\bigcup A$ has itself elements in $\bigcup A$.

For such an $A$, we get $B$ by the stated principle. Note now that Clause 2 implies $B \in\bigcup A$, and clause 3 implies $B \in A$. Meanwhile, clause 1 implies both that $B$ has an element in $\bigcup A$ and also that $B$ is not in $A$ (since it implies that $B\cap a$ is nonempty for some other $a\in A$, while sets in $A$ are disjoint). By our assumptions on $A$, these possibilities are mutually exclusive. It follows that $B$ must always be in clause 1, or always in clause 2, or always in clause 3, regardless of $a$, $x$, and $z$. If clause 3 always occurs, then $\emptyset\in A$, a contradiction. If clause 2 always occurs, then $B$ must be in more than one element of $A$, since otherwise we could let $a$ be that element, and this would contradict the disjointness of the elements of $A$. Thus, it must be that clause 1 always occurs. In this case, $B$ is a selection set, and so we have established AC. QED

Although I am not aware of any utility flowing from the fact that AC can be exprssed in this manner, it is nevertheless true that proof theory has sometimes made advances by investigating the resource-limited expressive powers of languages.

-

I suppose you mean a simple sentence in the language of set theory (i.e., with just $=$, $\in$ and logical symbols). I like this version:

Every family of nonempty pairwise disjoint sets has a transversal.

To say that $A$ is a family of nonempty pairwise disjoint sets, you can use the conjunction of $$\forall a(a \in A \to \exists x(x \in a))$$ and $$\forall a \forall b(a \in A \land b \in A \land \exists x(x \in a \land x \in b) \to a = b).$$ To say that $T$ is a transversal for $A$, you can use the conjunction of $$\forall a(a \in A \to \exists x(x \in a \land x \in T))$$ and $$\forall a(a \in A \to \forall x \forall y (x \in a \land x \in T \land y \in a \land y \in T \to x = y)).$$

-
If $\iff$ counts as a logical symbol, then you can say "nonempty pairwise disjoint sets" faster by saying that two of the sets have a common member if and only if they are equal. –  Andreas Blass Aug 17 '14 at 21:21
@François What you give is a formalization of what Russell and others used to call the multiplicative axiom, and it fits my bill but I hoped it should be possible to express something even more concise. –  Frode Bjørdal Aug 17 '14 at 23:11

The simplest formulation of the axiom of choice in a topos is that every epi is split.

$e:X\to Y$ is epi if for all $f,g:Y\rightrightarrows Z$, if $f\cdot e=g\cdot e$ then $f=g$.

$e:X\to Y$ is split if there is some $m:Y\to X$ with $e\cdot m={\mathsf{id}}_X$.

-
That was what I first thought of too. But I wondered whether this is the type of thing OP would disregard (I didn't understand his criteria). –  Todd Trimble Aug 17 '14 at 21:06
The question was clearly not concerned with toposes or category theory, and is more clearly not so after usefully suggested edits. –  Frode Bjørdal Aug 18 '14 at 9:31
@FrodeBjørdal This answer really has nothing to do with toposes or categories. It is simple enough to translate the English sentence "every surjection splits" into a string of symbols in first order language of set theory. It is probably not the shortest in that language, but it is definitely shortest in some other languages. –  Steven Gubkin Aug 18 '14 at 14:56
@Steven Gubkin My belief that the answer had to do with toposes or categories stemmed from the edit story of my question, as Paul Taylor misleadingly tagged my question with toposes and category theory, –  Frode Bjørdal Aug 18 '14 at 15:03
@FrodeBjørdal: this is set-theoretic! Although Paul used the word "topos", $X$, $Y$ and $Z$ are sets for your purposes. It might not be the kind of set theory you want to think about, but it's set theory all the same. –  Tom Leinster Oct 16 '14 at 12:13

We can have a shorter expression for AC by developing suggestions in a comment by Andreas to an answer by François and relying upon a proposal by Emil in the comments section below:

$\forall A(\forall a\forall b(a\in A\wedge b\in A\rightarrow (\exists x(x\in a\wedge x\in b)\leftrightarrow a=b))\rightarrow\exists T\forall a(a\in A\rightarrow\exists x\forall y(y=x\leftrightarrow y\in a\wedge y\in T)))$

Can we do better?

-
You may want to add that $\forall a(a\in A\rightarrow\exists u(u\in a))$ to state that $A$ is a collection of non-empty sets. –  Asaf Karagila Aug 18 '14 at 10:35
Why should I forget the formal statement? This $is$ about finding the most effective formal statement. The point is that $\forall a(a\in A\rightarrow\exists x(x\in a))$ follows from $\forall a,b(a\in A\wedge b\in A\rightarrow (\exists x(x\in a\wedge x\in b)\leftrightarrow a=b))$. –  Frode Bjørdal Aug 18 '14 at 11:12
The current version is trivially true by taking $T = \bigcup A$. –  François G. Dorais Aug 18 '14 at 11:23
The correct conclusion is $\exists T\,\forall a\in A\,\exists!x\,(x\in a\land x\in T)$, or expanding the abbreviations, $\exists T\,\forall a\,(a\in A\to\exists x\,\forall y\,(y=x\leftrightarrow y\in a\land y\in T))$. No need to make it complicated. –  Emil Jeřábek Aug 18 '14 at 15:54
Frode, you can certainly shorten it by adding logical symbols like $\exists!$ in the same way that you shortened my version using $\leftrightarrow$. For a definite answer, you would need to clarify the list of logical symbols that can be used. That said, the verification task for a definite answer looks very unpleasant. –  François G. Dorais Aug 18 '14 at 16:35

The Question seems to me a bit vague, and especially its motivation (is not clear to me at all). Thus I will offer just this:

Every surjection admits a semi-inverse.

-
This is not a formal statement in the language of $\in$, though. (And how different is it from Paul Taylor's answer below?) –  Asaf Karagila Oct 14 '14 at 10:34
Simply stating that a statement or question is vague, is itself neither useful nor precise. –  Frode Bjørdal Oct 14 '14 at 16:19

Thanks to all who have been suggesting very useful and true answers here and helped articulate the one developed by me. I was unfortunately unable to log in here for almost two months, so I could not relate normally here. These problems disappeared when I reverted to Google Chrome from Mozilla Firefox as browser.

The answers that gained in as far as having been adopted by me in the longish manuscript http://arxiv.org/abs/1407.3877 are (1) the Zermelian answer reminded by François G. Dorais which towards the end of v5 and v6 which is useful to my mathematical reasoning in isolating an interpretation of ZFC given £ plus some extra assumptions, and (2) the answer given by me with a lot of help by others such as Emil and Andreas proves most useful in stating an axiomatization of ZFC on page 30 of v6 of my manuscript.

Clearly, Joel David Hamkins' answer and link to answers to a more precise question than was my concern here, are very interesting in their own right; mathematically these are more interesting than my concerns here, but sometimes we have concerns which are not of such deep mathematical interest e.g. as when we develop something for divulgation.

I will mark this answer of mine as the one accepted, if I may, as it in the spirit of meritocracy attempts to give credit where credit is due; also, this may attract the attention of those who participated here.

-
You don't have to be democratic in selecting an answer for acceptance, but the spirit of democracy would suggest accepting the answer with the most votes. –  Matt F. Oct 15 '14 at 9:59
OK, so I change "democracy" into "meritocracy". –  Frode Bjørdal Oct 16 '14 at 11:18