# Describe the relation between two sets

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.

-
Is this really the notation you were given? – arjafi Dec 15 '12 at 9:15
You could write \{\} for braces in LaTeX. As Arthur remarked the notation seems a bit strange. – Asaf Karagila Dec 15 '12 at 9:16
OIC, thank for the tips – Samuel Dec 15 '12 at 9:19
Tell me if this notation looks more like your book. Let $S_n=\{a_1,a_2,\dots,a_n\}$ and $S_{n+1}=\{a_1,a_2,\dots,a_{n+1}\}$. How is $\mathscr P(S_n)$ related to $\mathscr P(S_{n+1})$? Answer: $\mathscr P(S_{n+1})=\mathscr P(S_n)\cup\{A\cup\{a_{n+1}\}:A\in\mathscr P(S_n)\}$. My best guess at the interpretation here is that your $P(S_n)$ is powerset, and the $\vee$ symbols are set union, i.e. $\cup$. Am I correct? – Mario Carneiro Dec 15 '12 at 9:25
yes you are right – Samuel Dec 15 '12 at 9:27

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)\}.$$

-

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.

-

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)\}$.
-