Let ℙ(𝑆) be the collection of all subsets of 𝑆, and ℚ(𝑆) the collection of all proper subsets of 𝑆.

Which of the following hold for every set 𝑆?

ℙ(𝑆) ⊆ ℚ(𝑆)
ℙ(𝑆) ⊇ ℚ(𝑆)
ℙ(𝑆) ⊃ ℚ(𝑆)
ℙ(𝑆) = ℚ(𝑆)

What's exactly wrong with this thought process?

If 𝑆 = {1,2,3}, then

ℙ(𝑆) = {∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

ℚ(𝑆) = {∅,{1},{2},{3},{1,2},{1,3},{2,3}}

ℙ(𝑆) ⊆ ℚ(𝑆) false. ℙ(𝑆) is not a subset of ℚ(𝑆)

ℙ(𝑆) ⊇ ℚ(𝑆) false. ℙ(𝑆) is not a superset of ℚ(𝑆)

ℙ(𝑆) ⊃ ℚ(𝑆) true. ℙ(𝑆) is a proper superset of ℚ(𝑆), and ℚ(𝑆) is not equal to ℙ(𝑆)

ℙ(𝑆) = ℚ(𝑆) false. ℙ(𝑆) and ℚ(𝑆) sets are not subsets of each other.

  • $\begingroup$ P(S) is a powerset of Q(S). Proper superset is, in particular, a superset $\endgroup$ – Wojowu Sep 14 at 20:21
  • 1
    $\begingroup$ How can $\mathbb{P}(S)$ be a proper superset of $\mathbb{Q}(S)$ but not be a superset? $\endgroup$ – Mark Kamsma Sep 14 at 20:21
  • $\begingroup$ @Wojowu You mean "superset", not "powerset". $\endgroup$ – Mark Kamsma Sep 14 at 20:22
  • $\begingroup$ @MarkKamsma Are you saying that both statements are correct? ℙ(𝑆) ⊇ ℚ(𝑆) and ℙ(𝑆) ⊃ ℚ(𝑆)? $\endgroup$ – Gabriel H. Sep 14 at 20:31
  • 1
    $\begingroup$ @MarkKamsma Right, thanks $\endgroup$ – Wojowu Sep 14 at 20:36

The notation $A\subseteq B$ is usually defined as $A\subset B$ or $A=B$. If one of the two things $A\subset B$ or $A=B$ is true, then $A\subseteq B$ must be true as well. Therefore it is impossible that $\Bbb P(S)\supseteq \Bbb Q(S)$ is false when $\Bbb P(S)\supset \Bbb Q(S)$ is true.

Apart from that, your reasoning has another error: you don't need an example set (in your case you use $S=\{1,2,3\}$) to show whether the assertions are true or false. In fact, you shouldn't use an example in a proof, since you then just prove a single special case, instead of a general principle. Of course examples are useful to gain intuition, and I highly encourage to first work out a few examples before you start proving something. But for the proof itself, you have to keep things general.

To show the assertions in a general case, we note that for any set $S$, the set $S$ itself is a subset of $S$ that is not proper. This follows from the definition of what a proper subset is. Furthermore, we know that any proper subset is also a subset (once again by definition of proper subset).

  • $\Bbb P(S)\not\subseteq \Bbb Q(S)$, since the set $S$ is an element of $\Bbb P(S)$ that is not a subset of $\Bbb Q(S)$.
  • $\Bbb P(S)\supseteq\Bbb Q(S)$, since any proper subset is also a subset.
  • $\Bbb P(S)\supset\Bbb Q(S)$, since the set $S$ is an element of $\Bbb P(S)$ that is not an element of $\Bbb Q(S)$, therefore $\Bbb P(S)\neq \Bbb Q(S)$. By the previous point $\Bbb P(S)\supseteq \Bbb Q(S)$, and remember that $\supseteq$ is defined as "$\Bbb P(S)\supset \Bbb Q(S)$ or $\Bbb P(S)= \Bbb Q(S)$". Since the latter is false, the former must be true.
  • $\Bbb P(S)\neq \Bbb Q(S)$, as we saw because $S$ is an element in $\Bbb P(S)$ and not in $\Bbb Q(S)$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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