I was just reading a description of the axiom of choice, and something about it has been bothering me. There's one particular case I'm hoping someone can explain:

Suppose there is an infinite set of sets S, such that for every set A in S, (where A is defined as being a non-empty set where for every x in A there is at most 1 function f that, when given the set A as input, chooses the element x), there is another set B where B contains every element in A, and in addition for every x in A (which remember is also in B, by the definition of B) there is another element, y in B, distinct from x, but such that y is indistinguishable from x to the function f, so that f is unable to choose between the two elements. It seems to me that if, as I understand the axiom of choice to mean, there is some function f2 capable of choosing an element from every set in S, there must (by the definition of S) be a further set in S from which the function f2 cannot choose an element. This is obviously a contradiction, so either I've just disproved the axiom of choice with a few minutes thought (unlikely!) or I've gone wrong somewhere... but where?

I'm also curious as to how I would describe my case in the formal language of set theory, but mostly I want to know where I went wrong.


Two people have now commented that "it is always false that there is only one function f returning x on input A", so let me redefine A and B. A is just defined as a non-empty set, and B is such that every x in A occurs in B, and for every x in A, for every f which chooses x from A, there is a y in B such that f cannot distinguish it from x (and so cannot choose) when given B as input.

Also, to clarify: S is not a set of all sets - it is only the set of all sets which either contain exactly one item, or match the conditions described above for the set B, that is to say that there is another set in S to which it bears the relation of B to A as described above. Conceptually, I think of it as an infinite line of sets - one set A contains one element, then there is another set B which contains all x in A plus some additional elements, then another set, and so on. Hope that is clear.

  • $\begingroup$ What do you mean $x$ and $y$ are indistinguishable to $f$? The function $f$, as you described it earlier, maps from $S$ to $\bigcup\limits_{A\in S} A$, and $S$ does not contain $x$ or $y$. $\endgroup$ – Alex Becker Mar 10 '12 at 1:26
  • $\begingroup$ @Alex The function f choose one element from a given set, so I suppose you could apply it to S, but what I meant here is that f is the function that when given the set A chooses x from it, and when given the set B cannot choose between x and y. Sorry I don't know how to write that formally. $\endgroup$ – Benubird Mar 10 '12 at 1:36
  • 1
    $\begingroup$ I also think that you are not being clear on what "chooses" mean. The axiom of choice says: if $X$ is a set of sets, and every element of $X$ is nonempty, then there exists a function $f\colon X\to\cup X = \{z\mid\exists A(z\in A\land A\in X)\}$ such that $f(A)\in A$ for every $A\in X$. So... how does $f$ "distinguish" or "fail to distinguish" among elements of $A$? $\endgroup$ – Arturo Magidin Mar 10 '12 at 6:53
  • 2
    $\begingroup$ @Benubird: A function is just an assignment of objects in the codomain to objects in the domain. It need not have any internal logic or be describable by any finite means. $\endgroup$ – Zhen Lin Mar 10 '12 at 14:06
  • 5
    $\begingroup$ @Benubird: And so we come to the real reason for your confusion: you don't understand what a "function" is in the context of set theory. There is nothing that involves "some logic by which it selects elements." Functions are not rational actors; they don't "do" things; they simply are. $\endgroup$ – Arturo Magidin Mar 10 '12 at 21:26

I think that first we need to review what is the axiom of choice, and what can happen in its absence.

The axiom of choice asserts that if we have a collection $X$ of nonempty sets, then we can choose from each one. What does "choose" mean? It means that there is a function whose domain is $X$ and for every $a\in X$ we have that $f(a)\in a$.

Why is this a useful axiom? If we have a finite collection of nonempty sets and in a process of a proof we want to choose from every set in that collection, we can write:

There exists $a_1\in A_1$ and there exists $a_2\in A_2$ and so on ... such that $a_1$ has this property and $a_2$ has that property ...

This is effectively choosing an element from the sets, and inductively we have that we can choose from every finite collection of nonempty sets. However induction only covers the finite cases. What happens if the collection is infinite? We cannot write an infinitely long formula, so instead the axiom of choice comes in to save the day and we can say that there exists a choice function and use $f(A_i)$ as $a_i$.

Note that this is not limited to countably infinite collections, they can be larger and wilder than anything you can imagine.

Life without choice, is life in a model in which we can only say that some collections of nonempty sets do not have choice functions. There are still things which we can choose from.

How can we assure that we can choose from something? One way is if we can effectively write down a property that is satisfied by a unique element from every set.

For example, consider $X=\{A\subseteq\mathbb N\mid A\neq\varnothing\}$, this is a family of nonempty sets. Do we need the axiom of choice to choose exactly one element from every $A\in X$? No. We have the order $<$ on the natural numbers which has the property that every nonempty set has a $<$-minimal element.

We can therefore use this $<$ as a helper to select from every element of $X$. And indeed the function $f(A)=\min_< A$ is well-defined (every $A$ is nonempty thus has a minimal element, and the order is linear so this element is unique) and we have defined it without the magical machine which is the axiom of choice.

Russell's Strange Drawer, is the analogy Russell used to explain why the axiom of choice is needed in some cases. What are those cases? For example, if you do not have this sort of structure which allows you to choose from the sets.

Russell used the fact that shoes have predefined properties of being "left shoe" and "right shoe", while socks (often) lack that property and you only know which is the left sock after you wore the sock on your left foot.

This is translated into the idea that if you have finitely many pairs of socks then by induction you can always choose one from each pair (try that for yourself, put the socks in pairs and since you have a finite number of pairs of socks you can go and pick one from each pair). With shoes you can also do that "manually" and choose one shoe from each pair, however one can simply claim:

I choose the left shoe from each pair! There is exactly one left shoe in every pair, therefore this is a unique choice!

Note that this did not require that there are any limitations on how many shoes you have. Even if you had Imelda Marcos's collection of 2700 (read: infinitely many) pairs of shoes you can still say that you choose the left one from each pair.

With the socks, however, you cannot make such a choice. As we remarked before about choosing from a pair of socks: socks are indistinguishable in the sense that there is no left sock or right sock. Those are a posteriori properties.

Russell's analogy was given to say that there are models without the axiom of choice in which you have a collection of infinitely many pairs, but you cannot choose exactly one element from each pair.

Russell gave the analogy in 1907, several years later Fraenkel defined what is now known as Fraenkel's second model in which such a collection of pairs was formalized into a proper mathematical object.

Fraenkel's model is a model which is constructed to have a collection of the form $\{P_i\mid i\in\mathbb N\}$ such that $P_i\cap P_j=\varnothing$ for $i\neq j$ and $|P_i|=2$ for all $i$, and there is no function $f(i)\in P_i$ for all $i$.

By inspecting every pair individually it is possible for us to distinguish between its two elements, and so by inspecting finitely many pairs we can still choose one from every pair. However there is no uniform way to distinguish between the elements of each pair at once. There is no unifying property like "right shoe", or "minimal element" which we can use here.

There is a lot to say on the definition and construction of this model, on the fact that we can perhaps distinguish between the elements in a larger universe, but not in the smaller one (external vs. internal definition). However this is going beyond the scope of a post on math.SE.

The question in the comments, namely if we can only distinguish $n$ pairs at a time, is simply due to the fact that if $f$ chooses from $P_0,\ldots,P_n$ then its domain is only $\{0,\ldots,n\}$ (or $\{P_0,\ldots,P_n\}$) and since $n+1$ is not in the domain of $f$ it cannot choose from $P_{n+1}$.

Alas it is not the sets which distinguish between the elements of each pair. It is us. To distinguish means to assert that they are different and to choose one and not the other. We can do that since the set is of size $2$ so we can fix a bijection with $\{1,2\}$ and say which is the first and which is the second element. However due to the lack of further structure on the pairs (and on the collection of all "socks", $\bigcup_n P_n$) we can only tell to which pair a sock belongs to and not which sock is which (in that pair).

It is truly baffling and mind boggling. Which is why the implications of the axiom of choice (and possible worlds in its absence) cannot really be explained intuitively, except when the intuition is mathematical in nature to begin with.

Further reading:

  1. How do I choose an element from a non-empty set?
  2. Axiom of Choice Examples
  3. Finite choice without AC
  4. axiom of choice: cardinality of general disjoint union
  5. What is the set-theoretic definition of a function? (To complement Arturo's comment on the main question)
  • $\begingroup$ If you have further question, feel free to ask. $\endgroup$ – Asaf Karagila Mar 10 '12 at 13:49
  • $\begingroup$ Thank you, this is a very clear description of the axiom of choice. I am still troubled though, by the case I describe in the question - where for any function f which is capable of choosing one element from each of the first N sets, the N+1 set is such that f cannot choose an element from it. $\endgroup$ – Benubird Mar 10 '12 at 13:58
  • $\begingroup$ @Benubird: I hope that I somewhat answered your question. $\endgroup$ – Asaf Karagila Mar 10 '12 at 14:14
  • $\begingroup$ @Benubird: Do you have any mathematical training? $\endgroup$ – Asaf Karagila Mar 10 '12 at 17:23
  • 1
    $\begingroup$ Thank you! You have completely answered my question, and I just wanted to add that I really appreciate all the time and effort you put into explaining it to me. :) $\endgroup$ – Benubird Mar 13 '12 at 23:52

With regards to the axiom of choice, the ability to choose an element from each subset isn't some algorithmic statement about the complexities of the sets, i.e. for the finite case, you don't need the axiom of choice. It's about obtaining something you can't explicitly construct, but (probably?) should exist.

Moreover, it's absurd to define your sets $A,B$ above. How do you know such a collection of sets exists? If anything, it's pretty easy to see that they don't exist, because you can't stipulate that in a set of sets there should be a point that is only the output of one function. It's very circular to arrive at a contradiction by assuming the existence of objects that encode the contradiction.

  • $\begingroup$ Ok, what about if it's changed so that instead of every x in A having at most one function, I define B such that for every x in A, for every f which chooses x from A, there is a y such that f cannot distinguish it from x. $\endgroup$ – Benubird Mar 10 '12 at 1:46
  • 2
    $\begingroup$ @Benubird: "An element that cannot be distinguished from $x$", or "a $y$ such that $f$ cannot distinguiish it from $x$" is not a mathematical statement, so it cannot form part of a definition. If you can write down an actual mathematical statement that encodes this property,, that will be one thing, but you aren't. You are just trying to wave a magic wand and say "indistinguishable because I say so" without saying what it means. $\endgroup$ – Arturo Magidin Mar 10 '12 at 4:34
  • 4
    $\begingroup$ @Benubird: Your final comment is also misguided. You cannot define things into existence; you can certainly give definitions, but the definitions do not guarantee the existence within the theory of the defined object. I can define a "galatrejo" to be a natural number $n$ such that $0\lt n\lt 1$. But the fact that I've given a definition of "galatrejo" does not guarantee that there is such a thing as a galatrejo (in fact, there isn't). $\endgroup$ – Arturo Magidin Mar 10 '12 at 4:35
  • 2
    $\begingroup$ @Benubird: Functions don't have "paths of internal logic"; your attempt at defining "indistinguishable" is thus based on a fundamental misunderstanding of what a function is. As to your last question, you are still confusing "existence in the 'real world'" with "existence within the mathematical model." $\endgroup$ – Arturo Magidin Mar 10 '12 at 21:29
  • 3
    $\begingroup$ @Benubird: No, I am not making that assumption. And I am not talking philosophy (let alone religion, thanks for the useless link), I am talking mathematics. Which is, after all, what this site is about. All of which is tangential to the real problem here: your "apparent contradiction" arises from a lack of understanding of what "function" means, and from an attempt at shoehorning a fuzzy, incoherent concept ("indistinguishable") into that lack of understanding. $\endgroup$ – Arturo Magidin Mar 12 '12 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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