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

**nomadreid** · February 28th 2011, 06:10 AM

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.

**DrSteve** · February 28th 2011, 09:24 AM

Originally Posted by nomadreid

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|$ .

**nomadreid** · March 1st 2011, 12:09 AM

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.

**DrSteve** · March 1st 2011, 02:50 AM

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

**nomadreid** · March 1st 2011, 07:05 AM

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.

**MoeBlee** · March 1st 2011, 08:10 AM

Originally Posted by nomadreid

Wouldn't this be begging the question?

No.

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.

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.

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.

**emakarov** · March 1st 2011, 10:27 AM

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.

**nomadreid** · March 1st 2011, 09:27 PM

Thanks, emakarov, that is perfect. And thanks, MoeBlee, for your patience.

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

LinkBack

Thread Tools

Display

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

P(AXA) to P(A)

Similar Math Help Forum Discussions

The number of integers are infinite and the integers are in infinite set

Prove: If D is a Dedekind Infinite set then D-{a} is Dedekind infinite.

Does convergence of an infinite series imply convergence of the infinite sequence?

Prove: every set with an infinite subset is infinite

Proof: infinite set minus a fintie set is infinite

Search Tags