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

• Feb 28th 2011, 06:10 AM
|{f:A--> A}| = |{f:A--> 2}| for A infinite. Why?
How does one prove that, for an infinite set A, that $\displaystyle |A|^{|A|}$=$\displaystyle 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.
• Feb 28th 2011, 09:24 AM
DrSteve
Quote:

Originally Posted by nomadreid
How does one prove that, for an infinite set A, that $\displaystyle |A|^{|A|}$=$\displaystyle 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.

$\displaystyle A^A\subseteq \mathcal{P}(A\times A)\leftrightarrow \mathcal{P}(A)\leftrightarrow 2^A$, where $\displaystyle \leftrightarrow$ means "there is a bijection".

The other direction is trivial.

By the Schroeder-Bernstein Theorem, $\displaystyle |A^A|=|2^A|$.
• Mar 1st 2011, 12:09 AM
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 $\displaystyle \kappa x \kappa$to $\displaystyle \kappa$ for ordinal $\displaystyle \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 $\displaystyle |^B$A| =$\displaystyle |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.
• Mar 1st 2011, 02:50 AM
DrSteve
Given that $\displaystyle |X|=|Y|$ it is easy to produce a bijection between $\displaystyle \mathcal{P}(X)$ and $\displaystyle \mathcal{P}(Y)$.

The only bijection $\displaystyle f: X\times X\rightarrow X$ that comes to mind involves well-ordering $\displaystyle X\times X$ in terms of a well-ordering of $\displaystyle 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).
• Mar 1st 2011, 07:05 AM
Quote:

Originally Posted by DrSteve
The only bijection $\displaystyle f: X\times X\rightarrow X$ that comes to mind involves well-ordering $\displaystyle X\times X$ in terms of a well-ordering of $\displaystyle 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...."

Quote:

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.
• Mar 1st 2011, 08:10 AM
MoeBlee
Quote:

Originally Posted by nomadreid
Wouldn't this be begging the question?

No.

Quote:

Originally Posted by nomadreid
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.

Quote:

Originally Posted by nomadreid
but since (AC) we can say this about any two sets,

With the axiom of choice, for any infinite set S, we have S equinumerous with SxS.

Quote:

Originally Posted by nomadreid
to then say that a bijection exists between their well-orderings would require equal cardinality in the first place, no?

No, 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.
• Mar 1st 2011, 10:27 AM
emakarov
I found the book "Real Analysis" by Gabriel Nagy available online here. It has Appendix B where it proves that S x S is equinumerous with S using AC.
• Mar 1st 2011, 09:27 PM