22
$\begingroup$

Edit: I have now rewritten the question in terms of well-ordering. Before, had I used the axiom of choice directly, which made the question unclear.

The anti-foundation axiom is a nice thing: It not only denies the axiom of foundation, but also gives an interesting structure to the non-founded sets.

I now want to know whether there is a similar axiom that constructively denies the axiom of choice, in the form that for each set a well-ordering exist. In greater detail:

  • If the axiom of choice is not true, then there are usually some sets that still can be well-ordered, for example the countable sets. All sets that can be mapped injectively into a well-ordered set can also be well-ordered. Or in terms of cardinality: All sets smaller than a well-ordered set are also well-orderable.
  • So in a set theory without the axiom of choice, we have two kinds of sets: Small ones, which have a well-ordering, and big ones, which do not have one. A good anti-choice axiom would therefore provide a "natural" division between small and big sets and give the big sets some additional properties that they cannot have under the usual (ZFC) set theory.

So the question is: What can I get instead if I cannot well-order some sets?

Improve this question
$\endgroup$
6
  • 8
    $\begingroup$ The standard example is AD + DC, where AD refutes choice for the continuum, and DC gives choice for countable sets. en.wikipedia.org/wiki/… $\endgroup$
    – user44143
    Commented Feb 12, 2022 at 13:08
  • 1
    $\begingroup$ @MattF. The reason I am not that happy about the axiom of determinacy is that it is a statement about the set of all countable integer sequences and does not provide insight about all non-choice sets -- at least in the form in which it is stated. But maybe there is another formulation. $\endgroup$
    – rimu
    Commented Feb 12, 2022 at 13:22
  • 1
    $\begingroup$ Of possible related interest: What's between the finite and the infinite? and Axiom of choice for sets of finite sets and this paper: John Horton Conway, Effective implications between "finite" choice axioms, pp. 439-458 in Mathias/Rogers (editors), Cambridge Summer School in Mathematical Logic, Lecture Notes in Mathematics #337, Springer-Verlag, 1973 (MR 50 #12725; Zbl 279.02047). $\endgroup$
    – Dave L Renfro
    Commented Feb 12, 2022 at 13:33
  • 2
    $\begingroup$ There are two “parameters” in a putative choice situation (when asking if $\prod_{i\in I} X_i$ is inhabited provided the $X_i$ are): the set $I$ of indices, and the set $X = \bigcup_{i\in I} X_i$ in which the values are taken. I think you're talking about $I$ here, but it might be worth clarifying, and maybe thinking about $X$ as well. $\endgroup$
    – Gro-Tsen
    Commented Feb 12, 2022 at 14:09
  • $\begingroup$ @Gro-Tsen I actually thought in terms of well-ordering but decided to write in terms of choice... But in terms of a choice function, my "choice set" would be a set X for which every family $(X_i)_{i\in I}$ of subsets has a choice function. $\endgroup$
    – rimu
    Commented Feb 12, 2022 at 14:41

1 Answer 1

Reset to default
20
$\begingroup$

There are two ways to understand this. Well. Three.

  1. If $X$ is a set, then $\mathcal P(X)$ admits a choice function.1 This is equivalent to the statement that $X$ can be well-ordered. This means that all the ordinals are "small", and since in $\sf ZF$ the axiom of choice is equivalent to saying that $\mathcal P^2(\alpha)$ admits a choice function for all ordinals, we know that the failure of choice is just saying that for some $\alpha$, $\mathcal P(\alpha)$ is not small anymore.

    If you want this ordinal to be explicit, we can introduce many various axioms that make it so. Most famously, Determinacy implies that $\omega$ already fails that. As do many other axioms.

  2. If $X$ is a set, then we can think of $X$ as small if any family of sets indexed by $X$ admits a choice function. Here we have that finite sets are small; $\sf AC_\omega$ states that countable sets are small; and we can have $\sf AC_X$ for non well-orderable sets $X$ just as well.

    Again, we can make this more explicit, as $\sf AC$ fails, by stating that $\sf AC_\omega$ fails, or even that for any infinite set $X$, there is a family indexed by $X$ which does not admit a choice function.

    We can improve upon this by also providing limitations on how big the sets inside the family are allowed to be, e.g. "every countable family of finite sets admits a choice function", but not so for anything larger: either in index or in content.

  3. We can mix those two. We can think of a set as being small if any well-ordered family of subsets admits a choice function, for example. Or any well-ordered family of subsets by a small ordinal (in the sense of (1), that is) admits a choice function. Etc. etc. etc.

    There's a lot of variety here. And it gets weirder and weirder, and more and more explicit as we dive into this rabbit hole.

At this point, you might argue, none of these are "constructive negations of choice". Insofar that none of them really pinpoint the exact failure. This is why more structural axioms, such as $\sf AD$, do offer a modicum of success here. Since $\sf AD$ provides us with a fairly rich theory of how badly things get. If you couple it with $V=L(\Bbb R)$, we can say even more about how terrible things can get.

But we can turn our heads to a different path. For example, Monro proved in

Monro, G. P., Decomposable cardinals, Fundam. Math. 80, 101-104 (1973). ZBL0272.02085.

That it is consistent that an infinite set is well-orderable if and only if it cannot be written as the union of two sets of strictly smaller cardinality. In the Cohen model, which Monro studies, this is true, and we have a relatively straightforward description of this odd partition.

There are many axioms like that, which infuse the universe of sets with a sense of chaos, either in the structure of "what type of families have a choice function" or "what kind of sets can be well-ordered". It seems that you're not entirely clear as to what you're looking for exactly, but there's a lot of these things in the literature.

I suggest starting with Herrlich's "Axiom of Choice" book to read about "disasters" and go from there.

Footnotes.

  1. Yes, $\varnothing$ is an issue. But we can just agree that a family of sets $A$ admits a choice function if $\prod (A\setminus\{\varnothing\})$ is non-empty.
Improve this answer
$\endgroup$
6
  • $\begingroup$ How about an axiom with the following flavor: “for every infinite set $I$ and any $I$-indexed family $(G_i)_{i\in I}$ of groups, there exists an $I$-indexed family $(X_i, \sigma_i)_{i\in I}$ of pairs such that $X_i$ is a set, $\sigma_i \colon G_i \times X_i \to X_i$ is an action of $G_i$ on $X_i$ making it into a principal homogeneous set (i.e., $X_i\neq 0$ and $G_i \to X_i, g\mapsto \sigma_i(g,x)$ is bijective for all $x\in X_i$), and $\prod_{i\in I} X_i = \varnothing$”. Might this, or some variation around it, be consistent and a reasonable “anti-choice” axiom? $\endgroup$
    – Gro-Tsen
    Commented Feb 12, 2022 at 18:46
  • 3
    $\begingroup$ Seems like something I addressed in arxiv.org/abs/1911.09285 $\endgroup$
    – Asaf Karagila ♦
    Commented Feb 12, 2022 at 19:24
  • $\begingroup$ "A admits a choice function is ∏A∖{∅} is non-empty." is -> if? And I have trouble seeing how an infinite set can be the union of two sets of strictly smaller cardinality. $\endgroup$
    – Acccumulation
    Commented Feb 13, 2022 at 16:23
  • 2
    $\begingroup$ @Acccumulation: Thanks, that is a typo. And yes, of course you find it hard to see how that's possible. It's just plain weird. Even sets like $\Bbb R$. $\endgroup$
    – Asaf Karagila ♦
    Commented Feb 13, 2022 at 17:06
  • 1
    $\begingroup$ @AlecRhea: I have said it elsewhere before, I am not one for visualizing to begin with. Maybe that's why set theory was always more attractive that other subjects. I do have some intuitive grasp, but the situation is so diverse without choice, so it's not as honed as the "at home intuition" you'd might think about. $\endgroup$
    – Asaf Karagila ♦
    Commented Feb 14, 2022 at 7:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .