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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .