3
$\begingroup$

I know that there are many counterintuitive situations that can't be disproved in $ZF$, some enumerated in this answer (I would add the existence of a finite undetermined game, from this answer [by the same author]). However, some of these can be solved with a weaker choice principle than the full Axiom of Choice. I'm looking for ones that can't. What are some counterintuitive statements one can deduce from $ZF + \lnot AC$?

Examples of other statements that can be proven in $ZFC$ but not in $ZF+DC$ (dependent choice) would also be interesting.

$\endgroup$
10
  • $\begingroup$ Given that dependent choice implies countable choice, there's no need to specify both. $\endgroup$ Commented Sep 9, 2021 at 19:25
  • $\begingroup$ @MarkSaving oh I forgot about that, thanks and I'll edit it $\endgroup$
    – acupoftea
    Commented Sep 9, 2021 at 19:26
  • $\begingroup$ One example is: there are sets $A, B$ such that neither $|A| \leq |B|$ nor $|B| \leq |A|$. $\endgroup$ Commented Sep 9, 2021 at 19:32
  • 2
    $\begingroup$ The question about counterintuitive statements that can be deduced from $ZF + \neg AC$ is basically asking for propositions $P$ such that $ZF \vdash P \iff AC$ and taking the negation of $P$. So you're really asking for intuitive statements that are equivalent to the axiom of choice in the first part of your question. $\endgroup$ Commented Sep 9, 2021 at 19:33
  • 1
    $\begingroup$ @acupoftea ZF + $\lnot$AC proves exactly 1) the consequences of ZF 2) the negation of every sentence that implies AC over ZF. How could something be of unknown implication status and still qualify? $\endgroup$ Commented Sep 10, 2021 at 0:40

1 Answer 1

5
$\begingroup$

The thing is that $\lnot\sf AC$ is just as non-constructive as $\sf AC$. Just like $\sf AC$ tells you that every set can be well-ordered, but it doesn't specify the well-ordering; $\lnot\sf AC$ simply tells you that some sets cannot be well-ordered, but it does not specify which sets.

So in general, all you can prove is that statements that are equivalent to $\sf AC$ fail. This may end up as counterintuitive in some cases, but that really depends on your intuition. Some examples:

  1. Some family of non-empty sets does not have any choice functions.
  2. Some two sets cannot be compared in cardinality.
  3. Some vector space does not have a basis.
  4. Some tree (a partial order where every downwards cone is well-ordered) is closed, in the sense that every increasing sequence has an upper bound, but there are no chain which meets every level of the tree.
  5. Some forcing notion $\Bbb P$ and some formula $\varphi(x)$ satisfy that $1\Vdash\exists x\varphi(x)$, but there is no $\Bbb P$-name $\dot x$ such that $1\Vdash\varphi(\dot x)$.
  6. Some surjection does not admit an inverse.
  7. Some set does not admit a group structure.
  8. Some commutative ring with a unit does not have any maximal ideals.

Again, we can just enumerate all the equivalences of the axiom of choice and consider their negation. That's pretty much all we can do here.

We cannot prove that $\sf BPI$ holds, but we cannot prove that it fails. We cannot prove that $\sf DC$ holds, but we cannot prove that it fails either. We cannot prove that $\mathcal{PPPPPPPPPPPPPP}\Bbb R$ can be well-ordered, but we cannot prove that it cannot be well-ordered either. And so on.

But, here are a few things that are at the very least consistent with $\sf ZF+DC+\lnot AC$.

  1. $\Bbb R$ can be partitioned into strictly more parts than elements. Or, just as well, it can be partitioned so that the partition is incomparable with $\Bbb R$ itself.
  2. Some infinite set $A$ satisfies that $|A|<|A\times 2|$.
  3. $\mathcal P(\Bbb R)$ cannot be linearly ordered.
  4. $\Bbb R$ does not have a Hamel basis over $\Bbb Q$.
  5. Some vector space over some field satisfies that every proper subspace has a countable basis, but the space itself does not.
  6. For every set $x$, there is some $A_x$ such that $A_x$ is the union of $\aleph_1$ sets of size $\aleph_1$, and $\mathcal P(A_x)$ can be mapped onto $x$.

And, again, there are a lot more.

$\endgroup$
9
  • $\begingroup$ What is a good reference for proves of the results you mention as consistent with $\sf ZF+DC+\lnot AC$? $\endgroup$ Commented Sep 9, 2021 at 20:25
  • $\begingroup$ One reference: Alan Taylor and Stan Wagon, A paradox arising from the elimination of a paradox, Amer. Math. Monthly vol. 126 (2019), pp. 306-318. $\endgroup$ Commented Sep 9, 2021 at 20:45
  • $\begingroup$ @DanVelleman: I helped with article! (And as far as I understand, actually helped inspire it!) $\endgroup$
    – Asaf Karagila
    Commented Sep 9, 2021 at 20:47
  • $\begingroup$ @mathcounterexamples.net: 1, 3, 4 follow from $\sf ZF+DC+BP/LM$; 2 follow from the existence of an $\aleph_1$-amorphous set, which is consistent with $\sf ZF+DC$; 5 appears in my M.Sc. thesis; and 6 follows from my results in "The Morris model" and "Iterated failures of choice". $\endgroup$
    – Asaf Karagila
    Commented Sep 9, 2021 at 20:49
  • $\begingroup$ I don't understand why it wouldn't be possible that $ZF + \lnot AC$ proves the negation of something stronger than $AC$, or even something like the other implication direction is unprovable, or at least unkown. I'm not expecting it but I don't see the connection with your first paragraph. $\endgroup$
    – acupoftea
    Commented Sep 9, 2021 at 21:05

You must log in to answer this question.

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