Results 1 to 8 of 8

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

  1. #1
    Member
    Joined
    Aug 2010
    Posts
    130

    |{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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Quote Originally Posted by nomadreid View Post
    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|.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Aug 2010
    Posts
    130

    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 \kappato \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 |^BA| = |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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    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).
    Last edited by DrSteve; March 1st 2011 at 03:11 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2010
    Posts
    130
    Quote Originally Posted by DrSteve View Post
    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...."


    Quote Originally Posted by DrSteve View Post
    ...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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by nomadreid View Post
    Wouldn't this be begging the question?
    No.

    Quote Originally Posted by nomadreid View Post
    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 View Post
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Aug 2010
    Posts
    130
    Thanks, emakarov, that is perfect. And thanks, MoeBlee, for your patience.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 5th 2011, 11:47 PM
  2. Replies: 1
    Last Post: October 2nd 2011, 02:26 AM
  3. Replies: 7
    Last Post: October 12th 2009, 10:10 AM
  4. Prove: every set with an infinite subset is infinite
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 31st 2009, 04:22 PM
  5. Proof: infinite set minus a fintie set is infinite
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 24th 2009, 10:54 PM

Search Tags


/mathhelpforum @mathhelpforum