Subsets and Power Sets

We will often want to compare sets. One kind of comparison is: everything in one set is in the other (set) too. This situation is sufficiently important for us to introduce some new notation.

Definition Subset

If every element of a set $A$ is also an element of $B$ , then we say that $A$ is a subset of $B$ , and we write $A \subseteq B$ . If $A \subseteq B$ but $A \neq B$ , we write $A \subset B$ , and say that $A$ is a proper subset of $B$ .

The notation $\subset$ is used because they are similar to equality operators $\leq$ and $<$ . You may also see $\subsetneq$ in other literature. The corresponding latex symbols are \subset, \subseteq, and \subsetneq.

Example Basics

Every set is a subset of itself, and $\emptyset$ is a subset of every set. The set of even numbers is a subset of the set of natural numbers. Also $\{a, b\} \subseteq \{a, b, c\}$ . But $\{a, b, e\}$ is not a subset of $\{a, b, c\}$ .

Applying subsets is useful for checking validity of something e.g. ensuring that a customer have chosen appropriate combination of items. The chefs check that they have chosen ingredients from available sets before planning the servings. The managers compare software features against the requirements.

Example Pizza toppings

Let all pizza toppings be a $A = \{ ham, kebab, cheese, tomato \}$ . Choosing any subset of toppings would result in a pizza that have name e.g. ham or cheese pizza. A kebab pizza would be a proper subset $B = \{ kebab, cheese \}$ so $B \subset A$ .

In Python the example would be written as

pizza_toppings: set[str] = { "ham", "kebab", "mozzarella", "tomato" }
kebab_pizza: set[str] = { "kebab", "mozzarella" }

print(kebab_pizza.issubset(pizza_toppings))
# True

Proposition

$A = B$ iff both $A \subseteq B$ and $B \subseteq A$ .

Definition Power Set

The set consisting of all subsets of a set $A$ is called power set of $A$ , written $\wp(A)$ :

\wp(A) = \{ B \mid B \subseteq A \}.

The symbol can be written \wp in TeX (perhaps short for Weierstrass p-function). You may also encounter different power set notations that uses different styles of "p" such as $P(A)$ .

Example Different soups

Soups can have any combination of ingredients and still taste good. The chef wants a list of all soups he can make from a set of ingredients $S = \{ salmon, potato \}$ . That power set that describes all combinations is

\wp(S) = \{ \emptyset, \{ salmon \}, \{ potato \}, \{ potato, carrot \} \}.

Problem

List all subsets of $\{ a, b, c, d\}$ .

Problem

Show that if $A$ has $n$ elements, then $\wp(A)$ has $2^n$ elements.