Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer

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)\}$.
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.