Why is the cardinality of set S is 3^n, where S is the collection of all ordered pairs of disjoint subset of {1,2,3,…,n} where n is non negative.
if n = 2, then subset A and B are disjoint and can only contain elements of 1,2, or the empty set, is this correct? I can't get 9 ordered pair. Can someone explain how do I get 9 ordered pair?
Why is the cardinality of set S is 3^n, where S is the collection of all ordered pairs of disjoint subset of {1,2,3,…,n} where n is non negative.
combinatoricselementary-set-theory
Best Answer
Think of there being $3$ sets: Set $A$, set $B$, and set $C$. for each element $s\in \{1, \cdots, n\}$ you have three choices as to where to put it. Here the subset $C$ contains all the elements that are in neither set $A$ nor set $B$. As there are $n$ elements, that makes for $3^n$ total choices.
For $n=2$, the $9$ choices are $$(A,A),\, (A,B), \,(A,C),\,(B,A), \,(B,B), \,(B, C),\,(C,A), \,(C,B), \,(C,C)$$.
Just to clarify things, the choice $(B,C)$, to pick a random one, means that element $1$ is in the second set and element $2$ is in neither the first nor the second. Thus it corresponds to the two disjoint sets $\emptyset, \{1\}$.