Subset

A subset is a set whose elements are all contained in another set.

Definition

A set $A$ is a subset of a set $B$, written $A \subseteq B$, if every element of $A$ is also an element of $B$:

$$ A \subseteq B \iff (\forall x)(x \in A \Rightarrow x \in B) $$

Proper Subset

$A$ is a proper subset of $B$, written $A \subset B$ or $A \subsetneq B$, if $A \subseteq B$ and $A \neq B$.

Properties

• Every set is a subset of itself: $A \subseteq A$
• The empty set is a subset of every set: $\emptyset \subseteq A$
• If $A \subseteq B$ and $B \subseteq A$, then $A = B$
• If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$ (transitivity)

Power Set

The power set $\mathcal{P}(A)$ is the set of all subsets of $A$:

$$ \mathcal{P}(A) = \{B : B \subseteq A\} $$

If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$.

Related

• set
• cardinality