2
$\begingroup$

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?

  • 2
    You should try to prove it yourself: $2^{|A|}\le |Part(A)|\le |A|^{|A|}=2^{|A|}$.2012-12-03
  • 0
    @Berci: Good idea, though that's a different problem. I just think this problem should have already been covered by some textbook.2012-12-03
  • 1
    Textbooks earn much less than your own effort.2012-12-03
  • 0
    @Berci: Thanks, I shall remember your words.2012-12-03

1 Answers 1

3

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

  • 0
    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?2012-12-03
  • 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.2012-12-03
  • 0
    LOL I'm really enjoying your answer and humour. Thanks.2012-12-03
  • 0
    Ah, I was confused between ordinals and cardinals. Thanks for pointing that out.2012-12-03
  • 0
    I think that is a "duplicate answer" (of yours) to a duplicate question! ;-)2013-01-11
  • 0
    @amWhy: Sounds reasonable, but it's easier to write these than look for previous duplicates (at least sometimes...)2013-01-11
  • 0
    I completely agree! :-)2013-01-11