When does $A^A=2^A$ without the axiom of choice?

Question

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.

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$. — Eric Wofsey, Feb 24 '13 at 06:21
Because of the question "When does $A^A=2^A$ without the axiom of choice?", I could't help but comment - when A=2... — Daniel Spector, Feb 24 '13 at 09:10
Which for some reason is excluded from the initial statement :) — Adam Epstein, Feb 24 '13 at 09:54
I wasn't sure whether or not the additional question makes it eligible for [reference-request]. — Asaf Karagila, Feb 24 '13 at 21:19
Thanks Andres, I didn't notice that typo (I can't type the accent on my keyboard, but that's another story!) — Asaf Karagila, Feb 25 '13 at 00:37
@Daniel Spector, also when $A=0$ (as some people define $0^0=1$). :) — JRN, Feb 25 '13 at 00:47
Does it known whether $\forall A,2^{A\times A} = 2^A$ implies $AC$? — Yair Hayut, Dec 26 '13 at 07:31
@Yair: That's an equivalent question to the second one I ask here. — Asaf Karagila, Dec 26 '13 at 13:02
Maybe we can say something like this: take a model of $\neg AC$ in which $\forall A,,|A|+|A|=|A|$. Now if you have in addition for every infinite set $A$ a set $B$ with $A\leq 2^B$ and $2^{A} = 2^{2^B}$ (sort of very weak $GCH$) then it would follow that $A^A = 2^A$ for every $A$: it is true for $X = P(B)$, since $|X \times X| = 2^{|B| + |B|} = 2^{|B|} = |X|$, and for $A\leq X$ with $|2^A| = |2^X|$, $2^X \cong 2^A \leq A^A \leq X^X \cong 2^X$. — Yair Hayut, May 08 '14 at 19:49
@Yair: I'm not quite clear on your idea there. Maybe you can explain it tomorrow? — Asaf Karagila, May 08 '14 at 20:23

score 28 · Accepted Answer · edited Aug 08 '18 at 12:26

28

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 :)

edited Aug 08 '18 at 12:26

Martin Sleziak

4,608

answered Jul 02 '14 at 11:17

Ioanna

1,252
13
15

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...) – Asaf Karagila Jul 02 '14 at 12:07
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. – Asaf Karagila Jul 02 '14 at 14:43
1

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...) – Ioanna Jul 02 '14 at 14:45
oops, was writing the comment while you posted yours. I don't know whether $x!=x^x$ either. – Ioanna Jul 02 '14 at 14:47
2

@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. – Andreas Blass Jul 02 '14 at 15:14
1

@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. – Asaf Karagila Jul 02 '14 at 15:21
In the Pincus model for all infinite $x$, $x!=2^x=x^x=x^x-x!$. – Ioanna Jul 02 '14 at 15:26
In fact, according to [Pincus78], whose argument I found to be correct, in the Pincus model:
for all infinite $x$, $x!=2^x=x^x=x^x-x!=|\mathcal{F}(x)|$ holds for all set valued operators $\mathcal{F}$ such that: (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$, and (3)$\mathsf{ZFC}$ proves $2^x=|\mathcal{F}(x)|$ for infinite $x$. The question now is, what other interesting $\mathcal{F}$ can we think of? :)
– Ioanna Jul 02 '14 at 15:42
@Asaf, i just edited the answer to incorporate the comments, and try to dispel any confusion with these $\mathcal{F}$, upon which the construction of the model does not depend on. – Ioanna Jul 02 '14 at 16:00

When does $A^A=2^A$ without the axiom of choice?

1 Answers1