# Thread: |{f:A--> A}| = |{f:A--> 2}| for A infinite. Why?

1. ## |{f:A--> A}| = |{f:A--> 2}| for A infinite. Why?

How does one prove that, for an infinite set A, that $|A|^{|A|}$= $2^{|A|}$, that is, that the set of all functions from A to A has the same cardinality as the set of all functions from A to {0,1}, or equivalently the power set of A?

The moderator asked posters to indicate the proof system in which one is working. The usual set-theoretical methods are fine. I am not working in the constructive universe. If singular cardinals give problems, assume that |A| is a regular cardinal.

How does one prove that, for an infinite set A, that $|A|^{|A|}$= $2^{|A|}$, that is, that the set of all functions from A to A has the same cardinality as the set of all functions from A to {0,1}, or equivalently the power set of A?

The moderator asked posters to indicate the proof system in which one is working. The usual set-theoretical methods are fine. I am not working in the constructive universe. If singular cardinals give problems, assume that |A| is a regular cardinal.
$A^A\subseteq \mathcal{P}(A\times A)\leftrightarrow \mathcal{P}(A)\leftrightarrow 2^A$, where $\leftrightarrow$ means "there is a bijection".

The other direction is trivial.

By the Schroeder-Bernstein Theorem, $|A^A|=|2^A|$.

3. ## P(AXA) to P(A)

Thanks, DrSteve. That makes sense, although I would have liked to know what bijection there is between P(A X A) and P(A). I remember a Gödel pairing function from $\kappa x \kappa$to $\kappa$ for ordinal $\kappa$, but that is defined recursively on the ordinals and does not easily generalize to general sets. Intuitively it is clear that there should be such a bijection, but if you could be more explicit, it would be appreciated.

By the way, a pedantic point: I believe the notation is $|^B$A| = $|A|^{|B|}$, but since this is clumsy to LaTex, your shorthand is fine.

PS: Moderator: I am having some glitches in this computer, so I hope this doesn't go through twice. If it does, just omit one.

4. Given that $|X|=|Y|$ it is easy to produce a bijection between $\mathcal{P}(X)$ and $\mathcal{P}(Y)$.

The only bijection $f: X\times X\rightarrow X$ that comes to mind involves well-ordering $X\times X$ in terms of a well-ordering of $X$. So it seems that AC is required for this. The "larger" pair in this ordering is the one with the larger max, and if the max's are the same, then they are ordered lexicographically.

I'm curious if a bijection can be produced without choice. Certainly it can be done for specific sets (it's easy for the reals, for example), but I don't recall ever trying to do this in general - since I always assume choice I never saw a need.

As far as the function notation is concerned, both are used (depending on the author). I do prefer using the left exponentiation for the set of functions, and right exponentiation for the cardinality, but in latex it's easier to just use right exponentiation for both (in any case, it's technically correct).

5. Originally Posted by DrSteve
The only bijection $f: X\times X\rightarrow X$ that comes to mind involves well-ordering $X\times X$ in terms of a well-ordering of $X$. ).
Wouldn't this be begging the question? That is, as there is no explicit way to well-order an arbitrary set, we only know that (assuming AC) the respective well-orderings exist, but since (AC) we can say this about any two sets, to then say that a bijection exists between their well-orderings would require equal cardinality in the first place, no? Forgive me if I am being obtuse; I always have problems in books when they say "the reader can easily see...."

Originally Posted by DrSteve
...a bijection ...without choice. .....(it's easy for the reals, for example), ..
Are you thinking of space-filling curves?

Thanks for the correction on the function notation.

Wouldn't this be begging the question?
No.

That is, as there is no explicit way to well-order an arbitrary set, we only know that (assuming AC) the respective well-orderings exist,
Right. But whatever about well orderings, at a certain point, from the axiom of choice, we get to the plain theorem: For any infinite set S we have that S is equinumerous with SxS.