5
$\begingroup$

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.

$\endgroup$
17
  • 6
    $\begingroup$ Can you give just one example of a solution that you wouldn't disregard, whether long or not or simple or not? $\endgroup$
    – Todd Trimble
    Aug 17, 2014 at 20:42
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 17, 2014 at 21:18
  • 3
    $\begingroup$ 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. $\endgroup$
    – Todd Trimble
    Aug 17, 2014 at 22:58
  • 2
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Aug 18, 2014 at 0:13
  • 6
    $\begingroup$ @Asaf Karagila I did not tag it with category theory or topos theory, and will attempt to untag those two topics. $\endgroup$ Aug 18, 2014 at 0:18

4 Answers 4

22
$\begingroup$

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 expressed in this manner, it is nevertheless true that proof theory has sometimes made advances by investigating the resource-limited expressive powers of languages.

$\endgroup$
14
$\begingroup$

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)).$$

$\endgroup$
2
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 17, 2014 at 21:21
  • $\begingroup$ @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. $\endgroup$ Aug 17, 2014 at 23:11
8
$\begingroup$

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$.

$\endgroup$
6
  • 3
    $\begingroup$ 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). $\endgroup$
    – Todd Trimble
    Aug 17, 2014 at 21:06
  • 1
    $\begingroup$ The question was clearly not concerned with toposes or category theory, and is more clearly not so after usefully suggested edits. $\endgroup$ Aug 18, 2014 at 9:31
  • 3
    $\begingroup$ @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. $\endgroup$ Aug 18, 2014 at 14:56
  • 2
    $\begingroup$ @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, $\endgroup$ Aug 18, 2014 at 15:03
  • 6
    $\begingroup$ @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. $\endgroup$ Oct 16, 2014 at 12:13
0
$\begingroup$

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?

$\endgroup$
17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Aug 18, 2014 at 10:35
  • 3
    $\begingroup$ 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))$. $\endgroup$ Aug 18, 2014 at 11:12
  • 2
    $\begingroup$ The current version is trivially true by taking $T = \bigcup A$. $\endgroup$ Aug 18, 2014 at 11:23
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 18, 2014 at 15:54
  • 3
    $\begingroup$ 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. $\endgroup$ Aug 18, 2014 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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