The Cardinality of A^A Not Greater Than That of 2^(2^A)

Citation
, XML
Authors

INTRODUCTION

Two sets A and B are said to be disjoint if A cap B=empty, i.e. they have no members in common.

If X and Y are sets, the meanings of X cup Y and left( X cup Y right) are identical. However, left{ X right} cup left{ Y right}  means the same thing as left{ X,Y right}, i.e. the set consisting of the sets X and YX setminus Y means the same thing as X cap Y^c, i.e. the set of members of X which are not members of Y.

Y^X means the collection of mappings of X into Y2^X is shorthand for left{ 0,1 right} ^X2^X means the collection of subsets of X2^empty means the collection left{ empty right} .

A mapping f:Xrightarrow Y is said to be injective or an injection if fleft( x_1 right) =fleft( x_2 right) implies x_1 =x_2 .

Let X,Y be sets. If  there exists an injection f:Xrightarrow Y we may write  left| X right|leleft| Y right|. If left| X right|leleft| Y right| and left| Y right|leleft| X right| we then have left| X right|=left| Y right| and X,Y are said to be equipotent. In this case we write Xapprox Y. If A_1approx A_2 and B_1approx B_2 then A_1 times B_1approx A_2 times B_2.

Note that X^{left{ y right} }approx X. Indeed, let f:X^{left{ y right} }rightarrow X verify fleft( t right) = tleft( y right)  for each t in X^{left{ y right} }. Then f is clearly an injection, so left| X^{left{ y right} } right| le left| X right|. Next let g:Xrightarrow X^{left{ y right} } verify gleft( xright) = left[ yrightarrow x right] , where left[ yrightarrow x right]  is the member of X^{left{ y right} } that maps y to x. This is also an injection, hence left| X right| le left| X^{left{ y right} } right|, and thus left| X right| = left| X^{left{ y right} } right| and X^{left{ y right} }approx X.qed

THEOREM

Theorem: If imageA is nonempty and well-ordered, then left| A^A  right| le left| 2^{left( 2^A right)}right|.

Let s_0 denote the smallest element of A, and let s_1s_2, and s_3 denote its successors under the well-ordering.

Proof of : Define mu:A^Arightarrow 2^{left( 2^A right)} verifying the following:

If S=left{ s right}  for some s in A and fleft( s right) =s, then muleft( f right) left( S right) =1;

If S=left{ s,fleft( s right)  right}  for some s in A and s<fleft( s right) , then muleft( f right) left( S right) =1;

If S=left{ s_0,s,fleft( s right)  right}  for some s in A and fleft( s right) ne s_1 and fleft( s right) <s then muleft( f right) left( S right) =1;

If S=left{ s_0,s_1,s  right}  for some s in A and fleft( s right) =s_0 and s ne s_1  then muleft( f right) left( S right) =1;

If S=left{ s_0,s_1,s_2,s_3  right}  and fleft( s_1 right) =s_0 then muleft( f right) left( S right) =1;

muleft( f right) left( S right) =0 for all other subsets Ssubseteq A.

It is necessary to show that this is an injection.

For each a in A such that muleft( f right) left( left{ a right}  right) =1, we must have fleft( a right) =a.

For distinct a,b in A such that a<b and muleft( f right) left( left{ a,b right}  right) =1, we must have fleft( a right) =b.

For distinct a,b in A and a<b and b ne s_1 and muleft( f right) left( left{ a,b,s_0 right}  right) =1, we must have fleft( b right) =a.

If muleft( f right) left( left{ s_0,s_1,s_2,s_3  right}  right) =1, we must have fleft( s_1 right) =s_0.

Thus mu is an injection.qed

REFERENCE

1. Cantor, Georg (1955, 1915). Contributions to the Founding of the Theory of Transfinite Numbers. New York: Dover.