2
$\begingroup$

Disclaimer: This is a homework problem, but I'm just asking for clarification, not a solution.

We're asked to prove $S(0,1) = 1$, where $S(n,k)$ is "the number of different partitions of [a set of size $n$] into $k$ mutually disjoint subsets", where a partition is defined like so: "Let $X$ be a collection of pairwise disjoint sets and let $Y = \bigcup X$. Then $X$ is called a partition of $Y$ if either (i) $X = Y = \varnothing$; or (ii) $X \neq \varnothing \land \varnothing \notin X$."

As far as I can tell the only set $X$ with $\bigcup X = \varnothing$ and $|X| = 1$ is $X = \{\varnothing\}$, but this does not satisfy either (i) or (ii) of the defintion of a partition. So it seems to me that there are no size 1 partitions of $\varnothing$, and $S(0,1)$ should be $0$, not $1$.

Am I missing something here?

$\endgroup$
1
  • $\begingroup$ You are correct. There are no size-1 partitions of the empty set. $\endgroup$
    – MJD
    Sep 2, 2013 at 20:22

5 Answers 5

1
$\begingroup$

You are right according to that definition. By the way, it can be simplified to "... is called a partition if $\emptyset\notin X$."

$\endgroup$
0
$\begingroup$

Condition (i) describes the partition of the empty set into $0$ non-empty parts (the "non-empty" property being vacuously true).

Condition (ii) implies that all parts in a partition are non-empty.

This is consistent with the definition of the Stirling Numbers of the second kind. The number $S(0,1)=0$ since there are no partitions of the empty set into exactly 1 non-empty part.

$\endgroup$
0
$\begingroup$

I think the author intended the "special case" clause (i) to be "$X=\{\emptyset\}$ and $Y=\emptyset$." That would make $S(0,1)=1$ and it would not be subject to Hagen von Eitzen's simplification of what was actually written.

$\endgroup$
-1
$\begingroup$

I believe you're mistaken when you say that the set $X=\{\varnothing\}$ satisfies $\bigcup X = \varnothing$. It actually satisfies $\bigcup X = \{\varnothing\}$.

The only $X$ satisfying $\bigcup X = \varnothing$ is $X=\varnothing$, the empty set itself.

Does that help?

$\endgroup$
6
  • 2
    $\begingroup$ $\bigcup X=\{\,z\mid \exists y\in X\colon z\in y\,\}$, so $\bigcup\{\emptyset\}=\emptyset$. $\endgroup$ Sep 2, 2013 at 20:21
  • $\begingroup$ It looks like you're saying that the union over a non-empty set is empty. That seems wrong to me. What am I missing? $\endgroup$ Sep 2, 2013 at 20:23
  • 3
    $\begingroup$ You’re not paying careful enough attention to the definition of $\bigcup X$. In order for $x$ to be an element of $\bigcup\{\varnothing\}$, there must be an element $u$ of $\{\varnothing\}$ such that $x\in u$. But the only element of $\{\varnothing\}$ is $\varnothing$, and no $x$ is in $\varnothing$, so $\bigcup\{\varnothing\}$ must be empty. $\endgroup$ Sep 2, 2013 at 20:26
  • 2
    $\begingroup$ It may be helpful to think of it in the following way (even though it is more complicated than necessary.) For any two sets $A$ and $B$ we have $\bigcup\{A,B\} = A \cup B$. Now let $A = B = \emptyset$. $\endgroup$ Sep 2, 2013 at 21:10
  • $\begingroup$ I think I understand. Does that mean it's correct to say that, for any set $X$, we have $\bigcup \{X\} = X$? $\endgroup$ Sep 2, 2013 at 21:14
-1
$\begingroup$

Empty relation on empty set is a equivalence relation .And no.of equivalence relations is equal to no.of partitions .

There is only on equivalence relation on empty set than empty set have one partition also

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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