Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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 6:21
17  
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 9:10
3  
Which for some reason is excluded from the initial statement :) –  Adam Epstein Feb 24 '13 at 9:54
5  
@Daniel Spector, also when $A=0$ (as some people define $0^0=1$). :) –  Joel Reyes Noche Feb 25 '13 at 0:47
1  
Does anyone have an idea why this was downvoted? –  Asaf Karagila Feb 26 '13 at 6:09
show 8 more comments

1 Answer 1

up vote 12 down vote accepted

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

share|improve this answer
    
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 2 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 2 at 14:43
    
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 2 at 14:45
1  
@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 2 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 2 at 15:21
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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