How does one prove that, for an infinite set A, that = , 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.
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 to for ordinal , 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 A| = , 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.
Given that it is easy to produce a bijection between and .
The only bijection that comes to mind involves well-ordering in terms of a well-ordering of . 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).
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...."
Are you thinking of space-filling curves?
Thanks for the correction on the function notation.
No.
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.
With the axiom of choice, for any infinite set S, we have S equinumerous with SxS.
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.