19
$\begingroup$

Let ACE (Axiom of Choice for Equinumerous sets) be the following choice principle:

If $S$ is a set of non-empty sets such for any $X,Y\in S$ there is a bijection from $X$ to $Y$, then $S$ has a choice function.

I want to know if ACE implies AC or is strictly weaker.

Motivation

In the case of choice from families of finite sets, the analog of ACE is strictly weaker than AC, i.e. there is a model where for each $n$, every set of $n$-element sets has a choice function, but there is a countable collection of finite sets (of unbounded size) with no choice function. You can get this by taking a permutation model with a set of $p$ atoms for each prime $p$, being acted on by the group $\prod_{p\text{ prime}} \mathbb{Z}/p\mathbb{Z}$, with finite supports.

However, ACE implies every set of finite sets has a choice function. To see this, suppose $S$ is a set of finite non-empty sets. Then $\{X\times\omega | X\in S\}$ is a collection of countable sets, so has a choice function by ACE. It's easy to build a choice function for $S$ from this. 

Improve this question
$\endgroup$

2 Answers 2

Reset to default
35
$\begingroup$

For any set $A$ and nonempty subset $B \subseteq A$, $B \times A^\omega$ is equinumerous with $A^\omega$: there is an injection from $B \times A^\omega$ to $A^\omega$ because $B \subseteq A$, and there is an injection from $A^\omega$ to $B \times A^\omega$ because $B$ is not empty, so by the Schröder-Bernstein theorem there is a bijection. By ACE, this implies there is a choice function on $\{B \times A^\omega | B \subseteq A\}$ (excluding the empty set), which implies there is a choice function on the power set of A (excluding the empty set), which is equivalent to the axiom of choice. So ACE implies AC.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks; I thought it might be something simple like this but I couldn't think of it $\endgroup$
    – Brian Pinsky
    Commented Jan 31 at 3:41
  • $\begingroup$ Doesn't the proof of Schröder–Bernstein itself use choice? $\endgroup$
    – LSpice
    Commented Feb 1 at 18:51
  • 7
    $\begingroup$ No; it may be surprising but the definition of the function in Shroder-Bernstein does not use choice. $\endgroup$
    – Brian Pinsky
    Commented Feb 1 at 19:15
0
$\begingroup$

Au contaire. Like all questions of this kind it depends on the wording.

Let $S$ be an inhabited set of inhabited sets, so we are given $x_0\in X_0\in S$.

If we are also given bijections $f_{X,Y}:X\cong Y$ for each pair $X,Y\in S$ then in particular we have $f_{X_0,Y}:X_0\cong Y$.

Therefore we have a defined element $y=f_{X_0,Y}(x_0)\in Y$ for each $Y\in S$.

No Choice required, if the question is understood in this way.

Indeed, by substituting "inhabited" for "non-empty", Excluded Middle is also avoided.

Improve this answer
$\endgroup$
13
  • 3
    $\begingroup$ I don't understand this answer at all. It seems to me Brian Pinsky's question was quite clear, with no ambiguity how to read it. $\endgroup$
    – Sam Hopkins
    Commented Feb 1 at 17:53
  • 3
    $\begingroup$ This "ambiguity" only appears if you insist on reading the question constructively; since the resulting alternate interpretation of the question is trivial, I don't see the motivation for interpreting the question in this way. (IMO one of the strengths of classical quantifiers is that they let you unambiguously state what level of given-ness you want, the possible pathologies of minimal-givenness notwithstanding.) $\endgroup$
    – Noah Schweber
    Commented Feb 1 at 18:18
  • 6
    $\begingroup$ But if you're going to follow the convention that saying “for all (…) there is (…)” means the data in question are given, then Choice itself is a triviality since “for all $X\in S$ there is $x\in X$” by this convention would mean that we are given a choice function. So yes, ACE doesn't require Choice with this convention, but Choice being true anyway, this is just “True implies True”. $\endgroup$
    – Gro-Tsen
    Commented Feb 1 at 18:20
  • 2
    $\begingroup$ @PaulTaylor I am sympathetic to your reasoning, but I think this answer is for a question that the OP wasn't asking. There's nothing in the question that indicates the OP is considering constructive logic or how that might impact what is more-or-less a classical set theory question. A debate around the constructive-sensitive phrasing is really not helping to answer the OP's question, is all I want to say. $\endgroup$
    – David Roberts ♦
    Commented Feb 2 at 2:45
  • 3
    $\begingroup$ ..was not requested by the OP, but in case others stumbling on this question later did in fact wish to work in a foundation without assuming LEM, here is an alternative perspective, for posterity. By starting one's answer with an "au contraire" it reads like telling the OP they are wrong, and this answer is the real answer to their real question they didn't even know they had. I'm not anti-constructive by any stretch of the imagination, but I wouldn't impose such an answer on someone who was not telling me that's what they wanted. $\endgroup$
    – David Roberts ♦
    Commented Feb 3 at 11:51

You must log in to answer this question.

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