Subset

In set theory, a subset of a set $B$ is a set $A$ such that every element of $A$ also belongs to $B$. This relationship, called inclusion, is written $A\subseteq B$. It permits $A=B$: a subset need not be smaller than the containing set. If $A\subseteq B$ and $A\ne B$, then $A$ is a proper subset of $B$. Inclusion expresses containment between sets, rather than membership of an individual object in a set. (abstractmath.org)

Definition and notation

The definition can be expressed using first-order logic:

Thus, there must be no element of $A$ outside $B$. Equivalently, $A\not\subseteq B$ means that some $x$ satisfies $x\in A$ and $x\notin B$. The reverse relation is written $B\supseteq A$, read “$B$ is a superset of $A$.” These formulations describe the same containment relationship from opposite directions. (web.stanford.edu)

Proper inclusion is unambiguously written $A\subsetneq B$. The symbol $\subset$ has differing conventions: some authors use it for proper inclusion, while others allow equality. Consequently, the surrounding definitions determine its meaning. For example, the integers form a proper subset of the real numbers, since every integer is real but some real numbers are not integers. (abstractmath.org)

Examples and membership

For $A=\{2,4\}$ and $B=\{1,2,3,4\}$, every element of $A$ occurs in $B$, so $A\subsetneq B$. By contrast, $\{2,5\}\not\subseteq B$, because $5\notin B$. A set-builder expression specifies a subset through a condition:

The restriction $x\in B$ supplies the containing set; the additional condition selects its elements. This construction also works when listing every element is impractical. (abstractmath.org)

Inclusion must be distinguished from membership, denoted $\in$. If $B=\{1,2\}$, then $1\in B$ and $\{1\}\subseteq B$, but $\{1\}\notin B$: its listed elements are numbers, not singleton sets. Sets may themselves be elements of other sets, so membership and inclusion can both apply to the same objects, but neither relation generally implies the other. (web.stanford.edu)

Basic properties and proofs

Every set is a subset of itself. The empty set $\varnothing$ is a subset of every set, because it has no element that could violate the defining condition. This does not mean that the empty set is an element of every set. (abstractmath.org)

Inclusion is reflexive, antisymmetric, and transitive:

• Reflexive: $A\subseteq A$.
• Antisymmetric: $A\subseteq B$ and $B\subseteq A$ imply $A=B$.
• Transitive: $A\subseteq B$ and $B\subseteq C$ imply $A\subseteq C$.

It therefore defines a partial order on any set of sets. It is not generally a total order: $\{1\}$ and $\{2\}$, for example, are incomparable under inclusion. (ocw.mit.edu)

A standard proof of $A\subseteq B$ takes an arbitrary element $x\in A$ and establishes $x\in B$. To disprove inclusion, one counterexample suffices. Set equality is often proved by establishing both $A\subseteq B$ and $B\subseteq A$, rather than comparing descriptions or enumerating elements. (web.stanford.edu)

Relationship to set operations

The intersection $A\cap B$ consists of elements common to both sets, while the union $A\cup B$ contains elements belonging to either. These definitions give useful equivalent tests:

Likewise, $A\subseteq B$ precisely when the difference $A\setminus B$ is empty. These equivalences follow by checking which elements each expression contains. (people.csail.mit.edu)

If both sets lie inside a fixed set $U$, their complements are taken relative to $U$. Inclusion reverses under complementation:

The containing set matters: changing $U$ changes the complement, although it does not change whether $A\subseteq B$. (people.csail.mit.edu)

Power sets and finite counting

The power set $\mathcal P(B)$ is the set of all subsets of $B$. It converts inclusion into membership:

For example,

Both the empty set and the original set are included. (people.csail.mit.edu)

If $B$ has $n$ elements, it has exactly $2^n$ subsets: each element is independently included or excluded. There are $2^n-1$ proper subsets, since only $B$ itself is removed from the count. In combinatorics, the number of subsets containing exactly $k$ elements is the binomial coefficient $\binom nk$. Unlike an ordered selection, a subset does not record the order in which its elements were chosen. (mathworld.wolfram.com)

Inclusion and infinite size

Inclusion and cardinality are distinct. A subset cannot have greater cardinality than its containing set, but a proper subset of an infinite set may have equal cardinality. For example, the even natural numbers form a proper subset of the natural numbers, yet $n\mapsto 2n$ gives a bijection between them. Both are countably infinite. (ocw.mit.edu)

By Cantor’s theorem, however, $\mathcal P(B)$ always has strictly greater cardinality than $B$, even when $B$ is infinite. Thus, the natural numbers have uncountably many subsets, despite having only countably many individual elements. The number of subsets is not determined by treating proper inclusion as ordinary numerical inequality. (ocw.mit.edu)