1
$\begingroup$

I have a question like this:

Let $S_n= \{ a_1,a_2,\ldots,a_n \}$ and $S_{n+1}= \{ a_1,a_2,\ldots,a_n,a_{n+1} \}$. Describe how $\mathscr P(S_n)$ is related to $\mathscr P(S_{n+1})$.

The answer provided is like this:

$\mathscr P(S_{n+1})=\mathscr P(S_{n}) \cup \{A \cup \{a_{n+1}\}: A \in \mathscr P(S_{n}) \} $.

I cannot understand why I can't directly write $\mathscr{P} (S_{n+1})= \mathscr{P} (S_{n}) \cap {a_{n+1}}$, and what is the part "$\{A \cup \{a_{n+1}\}: A \in \mathscr P(S_{n}) \} $" means.

  • 0
    Thank, all three answer is very enlightening. Sad, I can only choose one.2012-12-15

3 Answers 3

2

First note that $\newcommand{\power}{\mathscr P}\power(A)$ is a set of sets and $a_{n+1}$ is an element, which may not be a set (depending on context, of course). So to write $\power(S_{n+1})=\power(S_n)\cap a_{n+1}$ is not a well-defined expression.

Secondly you can see that $S_n\subseteq S_{n+1}$, so if $A\in\power(S_n)$ we have $A\subseteq S_n$ and therefore $A\subseteq S_{n+1}$ and so $A\in\power(S_{n+1})$.

Lastly if you take $A\subseteq S_{n+1}$ there are two options,

  1. $a_{n+1}\notin A$. In this case $A\subseteq S_n$ and therefore $A\in\power(S_n)$.
  2. $a_{n+1}\in A$. In this case $A\setminus\{a_{n+1}\}\subseteq\power(S_n)$ and therefore $A$ is in $\{B\cup\{a_{n+1}\}\mid B\in\power(S_n)\}$.
3

The notation encodes a very straightforward observation.

The powerset of $S_{n + 1}$ is the set of all subsets of $S_{n + 1}$. Those subsets are of two kinds: (i) the ones that don't contain $a_{n+1}$ and (ii) the ones that do.

(i) The subsets of $S_{n + 1}$ that don't contain $a_{n+1}$ are of course also the subsets of $S_n$. So the subsets of $S_{n + 1}$ that don't contain $a_{n+1}$ are the members of the powerset of $S_n$.

(ii) The subsets of $S_{n + 1}$ that do contain $a_{n+1}$ are all of the form $A \cup \{a_{n + 1}\}$ for $A$ a subset of $S_{n}$, i.e. are members of the set of all sets $A \cup \{a_{n + 1}\}$ for $A$ a member of the powerset of $S_n$.

So the powerset of $S_{n + 1}$ is the union of the sets talked about in (i) and (ii). Put that in symbols and you are done.

2

The notation $\mathscr P(S_n)$ means the power set of $S_n$, which is the set of all subsets of $S_n$. For example,

$\mathscr P(S_2)=\{\emptyset,\{a_1\},\{a_2\},\{a_1,a_2\}\}.$

This problem is looking at the relationship between the power set of a set and the same set with one extra element, and the answer shows that the new set $\mathscr P(S_{n+1})$ is actually twice as big as $\mathscr P(S_n)$, even though only one new element was added to $S_n$. In response to your question, $S_{n+1}=S_n\cup\{a_{n+1}\}$ is true, but $\mathscr P(S_{n+1})=\mathscr P(S_n)\cup\{a_{n+1}\}$ is not. To continue with the example for $S_2$, let's look at $\mathscr P(S_3)$:

$\mathscr P(S_3)=\{\emptyset,\{a_1\},\{a_2\},\{a_1,a_2\},\{a_3\},\{a_1,a_3\},\{a_2,a_3\},\{a_1,a_2,a_3\}\}.$

Notice that it can be seen as two separate pieces: the first four elements are the same as $\mathscr P(S_2)$, but there are four new elements, each of which contain the new element $a_3$. In fact, you can get these four elements by taking each element $A\in\mathscr P(S_2)$ and adding $a_3$ to it, to get $A\cup\{a_3\}$. The set of all of these, taken together, is $\{A\cup\{a_3\}:A\in\mathscr P(S_2)\}$, and putting that together with the original set $\mathscr P(S_2)$, we get

$\mathscr P(S_3)=\mathscr P(S_2)\cup\{A\cup\{a_3\}:A\in\mathscr P(S_2)\}.$

Generalizing the pattern, we arrive at the desired result:

$\mathscr P(S_{n+1})=\mathscr P(S_n)\cup\{A\cup\{a_{n+1}\}:A\in\mathscr P(S_n)\}.$