Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I suppose this problem should be a commonplace, but I only find this one, in which notations are kind of idiosyncratic, along with a glaring defect.

My question is where I can find a more formal proof?

share|improve this question
2  
You should try to prove it yourself: $2^{|A|}\le |Part(A)|\le |A|^{|A|}=2^{|A|}$. –  Berci Dec 3 '12 at 11:50
    
@Berci: Good idea, though that's a different problem. I just think this problem should have already been covered by some textbook. –  Metta World Peace Dec 3 '12 at 11:57
1  
Textbooks earn much less than your own effort. –  Berci Dec 3 '12 at 13:44
    
@Berci: Thanks, I shall remember your words. –  Metta World Peace Dec 3 '12 at 13:58
add comment

1 Answer 1

up vote 3 down vote accepted

I will assume choice, otherwise things get extra messy.

Let $X$ be of cardinality $\kappa$.

  • You have at least $2^\kappa$ partitions:

    Define $\sim$ on $P(X)$ by $A\sim B\iff A=B\lor A=X\setminus B$. Clearly every equivalence class has two members so there are $2^\kappa$ of them, and all but the class of $\{\varnothing,X\}$ define a proper and distinct partition.

  • You don't have more than $2^\kappa$ partitions:

    Since every partition has at most $\kappa$ parts, we can think about it as a surjection from $\kappa$ onto itself. Of course many functions can define the same partition, but the point is that there are at most $\kappa^\kappa=2^\kappa$ functions from $X$ to itself, including those which are not surjective. Therefore there cannot be more than $2^\kappa$ partitions.

We have, if so, $2^\kappa$ partitions of $X$ whenever $|X|=\kappa$.

share|improve this answer
    
Thank you for your answer. I'm still confused with the first part.if $A=X-B$, then we $f(A)=f(B)=\{A,B\}$, so the cardinality should be $2^\kappa/2$. How can we define devision, when multiplication is not commutative? –  Metta World Peace Dec 3 '12 at 12:26
1  
Was I sleeping that long? Did they define division on infinite cardinals during the morning? The calculation should be $2\cdot|P(X)/\sim|=2^\kappa$ therefore $|P(X)/\sim|=2^\kappa$. Also, note that multiplication is commutative for cardinals, even without the axiom of choice. –  Asaf Karagila Dec 3 '12 at 12:29
    
LOL I'm really enjoying your answer and humour. Thanks. –  Metta World Peace Dec 3 '12 at 12:37
    
Ah, I was confused between ordinals and cardinals. Thanks for pointing that out. –  Metta World Peace Dec 3 '12 at 12:43
    
I think that is a "duplicate answer" (of yours) to a duplicate question! ;-) –  amWhy Jan 11 '13 at 14:49
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.