One might think that, trivially, the "opposite" of AC is $\neg$AC. However, thinking about it differently, I'm not sure this is intuitively the case.

AC says that every set has a choice function. However, we can prove the existence of many choice functions (e.g. the finite ones) without AC. So, in particular AC just gives us the "non-constructive" choice functions. In general, throughout mathematics, it is often said that AC is only necessary to prove the existence of non-constructive sets. So, one might be tempted to say that the axiom which is intuitively the "opposite" of AC is V=L, which says that all sets are constructible. However, we've already known for a long time that V=L implies AC! So, is it just wrong to characterize AC as "nonconstructive"? Would a constructivist be wary of AC?

Intuitively, I think most people would characterize the "opposite" of AC to be the axiom that any set whose existence requires the Axiom of Choice doesn't exist. The intuitive thought behind this is much stronger than $\neg$AC, which just says there exists at least one set without a choice function. However, this intuition is pretty flawed in a number of ways. For one, it would have to quantify over non-existent sets! Barring this, I think the main difficulty is that, as evidenced by V=L, the relativity of the notion of set makes this idea unworkable. Is it unworkable? What is the best candidate for an axiom that is the opposite of AC? Can we do no better than just $\neg$AC?

  • 1
    $\begingroup$ Note that $V=L$ doesn't say that everything is constructive -- it merely says that everything is ordinal constructible. All of the ordinals get a free pass, even ones above $\omega_1^{CK}$ that may not have definite descriptions. $\endgroup$ – hmakholm left over Monica Nov 11 '14 at 19:58
  • 2
    $\begingroup$ The Mycielski-Steinhaus axiom of determinateness? It implies that no uncountable set of real numbers can be well-ordered, which is probably as close as you can get to the opposite of "every set can be well-ordered". Implies nonexistence of such AC-monsters as nonmeasurable sets, non-Baire sets, etc. $\endgroup$ – bof Nov 11 '14 at 20:05
  • $\begingroup$ @bof This is a great candidate for what I was looking for. Thanks! $\endgroup$ – Taro Nov 11 '14 at 20:06
  • 1
    $\begingroup$ @bof: Who calls it "determinanteness" nowadays? Pretty much everyone calls it "determinacy". :-) $\endgroup$ – Asaf Karagila Nov 11 '14 at 20:13
  • 1
    $\begingroup$ @DavidBuiles J. Mycielski & H. Steinhaus, "A mathematical axiom contradicting the axiom of choice", Bull. Acad. Polon. Sci. 10 (1962), 1-3. $\endgroup$ – bof Nov 11 '14 at 20:46

First let me point out that you are mixing "constructive" and "constructible". There are plenty of non-constructive sets which are constructible. In particular because constructive usually refers to something more akin to the "definable from the usual structure of mathematical objects" and not "there is a set theoretic formula which defines it out of the blue".

The negation of the axiom of choice is as non-constructive as the axiom of choice. Just like the axiom of choice doesn't tell us what the choice function might be, the negation of the axiom of choice doesn't tell us what is the family of sets which does not have a choice function. It could be that the axiom of choice fails, for the first time, in some arbitrarily high von Neumann rank; or it could be that it only fails for very very very large families of sets; or it could be that it fails for particular type of families of sets, while it holds for other.

We can't say. In order to draw practical conclusions from the failure of the axiom of choice we usually have to assume more. For example "there is an infinite Dedekind-finite set of real numbers" is a failure of the axiom of choice which is more specific than just "the axiom of choice fails".

To solve this problem of non-constructivity you don't need to negate the axiom of choice, you need to change the system from a deeper place. Probably the law of excluded middle, which is responsible for us being able to assure that the non-constructive objects exist. This is why most constructive systems reject this law; and there is a theorem that the axiom of choice implies the law of excluded middle.

Within the confines of classical logic, and staying with $\sf ZF$:

  1. You might want to ensure that there are sets which cannot be injected into an ordinal; but you can also require that there are sets which cannot be injected into a power set of an ordinal; and you can continue in this fashion.

    So one option is to say the following: For each ordinal $\alpha$, there is a set which cannot be injected into $\mathcal P^\alpha(\eta)$ for any ordinal $\eta$. (Where $\mathcal P^\alpha$ is defined by iterating power sets, and taking union at limits.)

  2. You might want to say, the axiom of choice implies the existence of all sort of crazy sets of real numbers. I'll choose "Every set is Lebesgue measurable", or "Every set has Baire property" or "Every game is determined". These axioms usually bring "order" to the world of non-constructive sets of reals. These are all consistent with $\sf DC$, which means that you can even develop reasonable analysis in those models.

    And if the axiom of choice is mainly used for "There are some messed up sets of real numbers", things like the axioms above would essentially say "Every set of reals is well-behaved".

  3. You might want to keep your focus on the real numbers, and say "Screw everything, I'm going nuclear" and require that the real numbers are a countable union of countable sets. This has the benefit of destroying completely the usual ways we define measure and category for sets of reals.

    You can even go further than that, and require that for every ordinal $\kappa$, $\mathcal P(\kappa)$ is the countable union of sets of size $\kappa$. This is known as axiom $\sf (K)$, but we don't quite know if it's consistent (relative to very large cardinals, which are necessary to say the least). So you can instead take solace in choose "Every limit ordinal has cofinality $\omega$ which has some messed up consequences as well.

  4. You can decide that you want amorphous sets, since those are "the ultimate counterexample". These are infinite sets that cannot be partitioned into two infinite sets. Strongly amorphous sets have the additional property that any partition is all singletons (except finitely many parts). These sets cannot be linearly ordered, they cannot be mapped onto $\omega$, and their cofinite sets make a complete ultrafilter.

    Strongly amorphous sets cannot be endowed with any reasonable structure; but in general it is possible to have amorphous sets which are vector spaces over finite fields. Those spaces have the strange property that every proper subspace is finite.

And there are many other ways to say "I see the axiom of choice as responsible for ...", then the opposite would be "... fails in the most horrible way imaginable!".

| cite | improve this answer | |
  • 4
    $\begingroup$ Since I'm not quite sure what "best opposite" means, I don't quite know how to answer that; but I'd probably pick a very strong form of negation of the axiom of choice (e.g. one which is somewhat maximal in the amount of damage that occurs). I wouldn't go for denying LEM, because I love that guy and I wouldn't want to deny it from myself. But this also depends on the context that you are looking for. In the confines of $\sf ZF$ and classical logic, negating choice or choosing a strong failure is probably the sane choice; in a context where you can replace the logic, that might be a better one. $\endgroup$ – Asaf Karagila Nov 11 '14 at 20:13
  • 1
    $\begingroup$ David, I've added some parts to my answer after the discussion in the comments here and on the main question. $\endgroup$ – Asaf Karagila Nov 11 '14 at 20:49
  • 1
    $\begingroup$ Oh, it's my pleasure to drone on and on about the axiom of choice until I start foaming at the mouth and fall over backwards. :-P $\endgroup$ – Asaf Karagila Nov 11 '14 at 21:01
  • 1
    $\begingroup$ @AsafKaragila Wow, that was literally your question. I've never seen such an elaborate answer to this subject. Although I'm not completely into the topic, I enjoyed reading the answer :) (+10 if I could) $\endgroup$ – AlexR Nov 11 '14 at 21:41
  • 1
    $\begingroup$ @Asaf: Logic is definitely not my strong suit (nor my weakest), but what does your sentence "there is a theorem that the axiom of choice implies the law of excluded middle" mean? More precisely, how can an adoption of a particular sentence $(AC)$ as an axiom, in whatever language you're working with, impact your choice of logical axioms? $\endgroup$ – Jason DeVito Nov 12 '14 at 2:35

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.