Let P(X) denote the set of all subsets (including Ø and X) of a set X. Write out the elements of P(Ø), P({a}), and P({r,s,t}). If #X=n, a finite number, what is #P(X)? Prove your assertion.
Any help would be appreciated. Thanks.
Let P(X) denote the set of all subsets (including Ø and X) of a set X. Write out the elements of P(Ø), P({a}), and P({r,s,t}). If #X=n, a finite number, what is #P(X)? Prove your assertion.
Any help would be appreciated. Thanks.
Plato, I disagree with $\displaystyle P(\phi)= \{\phi, \{\phi\}\}$. $\displaystyle \{\ph\}$ is NOT a subset of $\displaystyle \phi$.
It is true that [tex]P(\{\phi\})= \{\phi, \{\phi\}\}[tex]. Did you misread the problem?
To show how many subsets an n-element set has, consider each element of the n-element set. For a particular subset, each element is either in the subset or it is not. Hence, there are two possibilities for each element. Since each element may belong or not belong to a subset independent of any other elements that may or may not be part of the subset, you can apply the product principle to count how many subsets there are.
Show that $\displaystyle 2^{[n]}\subseteq 2^{[n+1]}$. Then show that $\displaystyle 2^{[n+1]} = 2^{[n]}\cup \bigcup_{A\in 2^{[n]}}\{A\cup \{n+1\}\}$. Show that is a disjoint union of sets (since no set in $\displaystyle 2^{[n]}$ contains $\displaystyle n+1$ and is just twice the number of elements in $\displaystyle 2^{[n]}$.
This about the same a the reply just above. The notation is simpler.
$\displaystyle \mathcal{P}(\{1\})=\{\emptyset,\{1\}\}$ That is two sets, or $\displaystyle 2^1=2$
Suppose we know that $\displaystyle \mathcal{P}\{1,2,\cdots,n\}$ contains $\displaystyle 2^n$ sets.
It should be clear to you that $\displaystyle \mathcal{P}\{1,2,\cdots,n\}\subset\mathcal{P}\{1,2 ,\cdots,n,n+1\}$. Right?
The only 'new' sets on the right look like $\displaystyle G\cup\{n+1\}$ where $\displaystyle G\in\mathcal{P}\{1,2,\cdots,n\}$.
We get one new set for each $\displaystyle G$ on the left.
So we now have $\displaystyle 2^n+2^n=2(2^n)=2^{n+1}$ sets on the right.
A variation on that theme (proof by induction). If n= 0, then the set is empty and has only one subset, the empty set. Now, suppose that, for some positive integer, k, P(A)= 2^k whenever A has k members. Let B be a set containing k+ 1 members. Since k+1> 0, B has at least one member. Choose one and call it "b". No consider the collection of all subsets of B that do NOT contain b. That is the same as the set of all subsets of B\{b} which has k members and so 2^k subsets. But if any subset, C, of B [b]does[b] contain b, the assignment C-> C\{b} is one-to-one and onto. That is, there is a one-to-one correspondence between subsets of B which contain a and those that do not. Since there are 2^k sets that do not contain b and 2^k subsets of B that do contain b. There are a total of 2^k+ 2^k= 2(2^k)= 2^{k+1} subsets of B.
And if you are looking for a more combinatorial argument, you can make a counting argument.
You want to count the number of subsets of $\displaystyle X$ which has $\displaystyle n$ elements. For each $\displaystyle x\in X$ a subset which contains $\displaystyle x$ is distinct from a subset that does not. So, each element gives 2 possibilities that are independent for each element of $\displaystyle X$. By the product principle, the number of subsets would be...
Can you finish the proof?