48
$\begingroup$

Assuming the axiom of choice the following argument is simple, for infinite $A$ it holds: $$2\lt A\leq2^A\implies 2^A\leq A^A\leq 2^{A\times A}=2^A.$$

However without the axiom of choice this doesn't have to be true anymore. For example if $A$ is an amorphous set (infinite set that cannot be written as a disjoint union of two infinite sets), then it is actually true that $2^A<3^A<4^A<\ldots< A^A$. The reason these inequalities hold is that $A^A$ is actually Dedekind-finite, so whenever we remove elements we strictly decrease in cardinality.

Of course there are still sets that obey the equation $A^A=2^A$, even if $A$ cannot be well-ordered. For example given any set $A$ it is not hard to verify that $A^\omega$ has the property $A^\omega\times A^\omega=A^\omega$. From this follows:

$$2\lt A^\omega\leq 2^{A^\omega}\implies 2^{A^\omega}\leq\left(A^\omega\right)^{A^\omega}\leq \left(2^{A^\omega}\right)^{A^\omega}=2^{A^\omega}$$ (In fact we can replace $\omega$ by any set $\tau$ such that $\tau+\tau=\tau$)

But I have a hard time to believe that these two things are equivalent: $$A^A=2^A\iff A\times A=A.$$

Question I. Is there anything known on the properties of sets for which $A^A=2^A$?

Question II. If $2^A=A^A$ does not characterize the sets for which $A\times A=A$, does the axiom "For every infinite $A$, $2^A=A^A$", imply the axiom of choice?

If the answer is unknown, does this question (or variants, or closely related questions) appeared in the literature?

It seems like a plausible question by Tarski or Sierpiński. I found several other questions I have asked before to be questions that have been asked in one a paper or another.

$\endgroup$
13
  • 3
    $\begingroup$ Given that $A\times A=A$ for all $A$ is equivalent to AC, you could also ask whether the same is true of $A^A=2^A$. $\endgroup$ Feb 24, 2013 at 6:21
  • 28
    $\begingroup$ Because of the question "When does $A^A=2^A$ without the axiom of choice?", I could't help but comment - when A=2... $\endgroup$ Feb 24, 2013 at 9:10
  • 4
    $\begingroup$ Which for some reason is excluded from the initial statement :) $\endgroup$ Feb 24, 2013 at 9:54
  • 9
    $\begingroup$ @Daniel Spector, also when $A=0$ (as some people define $0^0=1$). :) $\endgroup$
    – JRN
    Feb 25, 2013 at 0:47
  • 3
    $\begingroup$ Does anyone have an idea why this was downvoted? $\endgroup$
    – Asaf Karagila
    Feb 26, 2013 at 6:09

1 Answer 1

28
$\begingroup$

David Pincus in "A note on the cardinal factorial" (Fundamenta Mathematicae vol.98(1), pages 21-24(1978)) proves that $A^A=2^A$ does not imply the axiom of choice, therefore it does not characterise the sets for which $A=A\times A$. The counterexample is the model from his paper "Cardinal representatives", Israel Journal of Mathematics, vol.18, pages 321-344 (1974).

As Pincus writes on the last lines of [Pincus78]:

c. Our arguments [ in the proof of "4.The Main Theorem; If $x$ is infinite then $2^x=x!$" ] have made little use of the particular definition of $x!$. Indeed let $\mathcal{F}$ be any set valued operation which satisfies:

(1) The predicate $y\in\mathcal{F}$ is absolute from $M$ to $V$.

(2) $\mathsf{ZF}$ proves $|y|\leq x \Rightarrow |\mathcal{F}(y)|\leq |\mathcal{F}(y)|$ and $|2x|=|x|\Rightarrow 2^x\leq|\mathcal{F}(x)|$ for infinite $x$.

(3) $\mathsf{ZFC}$ proves $2^x=|\mathcal{F}(x)|$ for infinite $x$.

The statement "For every infinite $x$, $2^x=|\mathcal{F}(x)|.$", holds in $M$ (and therefore is not an equivalent to the axiom of choice). Examples of $\mathcal{F}$, apart from $x!$, are $x^x$ and $x^x-x!$.

Therefore, in this Pincus model, $\mathsf{ZF}$ + $\lnot\mathsf{AC}$ + "for all infinite x, $2^x=x!=x^x=x^x-x!=|\mathcal{F}(x)|$" holds for any set valued operator $\mathcal{F}$ as above.

I should say that, after failing to come up with an answer myself, I found out about this by searching into my good old friend the "Consequences of the axiom of choice" by Howard and Rubin, Form 200, and Note 64. I try to reference this book whenever I can :)

$\endgroup$
9
  • $\begingroup$ Strange. I know both papers, but I haven't read them thoroughly. I do recall searching the consequences dictionary and coming up short. I also don't quite understand your first paragraph; if it doesn't imply the axiom of choice, how does it mean it doesn't characterize? (And I haven't forgotten about the email. I'm writing my reply slowly...) $\endgroup$
    – Asaf Karagila
    Jul 2, 2014 at 12:07
  • $\begingroup$ Okay, forget about the part I wrote I don't understand. Too much sleep deprivation. My brain is like cheese. I'm not 100% sure that $x!$ and $x^x$ must have the same cardinality, though. $\endgroup$
    – Asaf Karagila
    Jul 2, 2014 at 14:43
  • 1
    $\begingroup$ Well, the consequences dictionary is not the easiest book to search. I searched for this result a few times before I found it. About my first paragraph, I meant characterisation in the sense that for an infinite set $A$, it is not the case that $2^A=A^A \iff A=A\times A$, in particular $2^A=A^A \not\Rightarrow A=A\times A$. What did you mean by "characterise"? (And no problem at all, I'm not in any position to complain about slow email replies :) I also haven't forgotten about updating the file...) $\endgroup$
    – Ioanna
    Jul 2, 2014 at 14:45
  • 2
    $\begingroup$ @AsafKaragila I don't think $x!=x^x$ in general. We always have an embedding of $x$ into $x^x$, using the constant functions, but I don't think there's always an embedding of $x$ into the set of permutations of $x$. Suppose, for example, that $x$ is the set of atoms in the basic Fraenkel model. $\endgroup$ Jul 2, 2014 at 15:14
  • 1
    $\begingroup$ @Andreas: It is easy to see that $x!\neq x^x$ in general, because in the case of a strongly amorphous set, $x!$ is a proper subset of $x^x$, which is a Dedekind-finite set. So there's that (basically, the basic Fraenkel model, yes). But in Pincus model it might be the case after all, which will answer my question. $\endgroup$
    – Asaf Karagila
    Jul 2, 2014 at 15:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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