Subset and Proper Subset

Comparing Sets by Their Elements

In Set Membership, we used $x\in A$ to ask whether a particular object $x$ is an element of a set $A$. Subset notation uses membership to compare two sets. Instead of testing one candidate object, we check whether every element of one set is also an element of another.

For example, let $A=\{2,5\}$ and $B=\{1,2,5,8\}$. Each element of $A$ is an element of $B$: $2\in B$ and $5\in B$. We therefore say that $A$ is a subset of $B$, and write $A\subseteq B$. The claim is about all the elements of $A$, not about whether the set $A$ itself appears as an element of $B$.

Formally, $A\subseteq B$ means that for every object $x$, if $x\in A$, then $x\in B$. This condition does not require $A$ and $B$ to have different elements. It permits the possibility that they are the same set. A proper subset is a subset that is not equal to the set containing it.

Throughout this tutorial, $\subseteq$ denotes “is a subset of, possibly equal to,” and $\subsetneq$ denotes “is a proper subset of.” These symbols make the equality distinction explicit.

Keep membership and subset separate. The statement $x\in A$ relates an object $x$ to a set $A$. The statement $A\subseteq B$ compares two sets and says that every element of $A$ belongs to $B$. A set being a subset of another does not mean that it is an element of that set.

Definition and First Examples

Let $A$ and $B$ be sets. The definition of subset is $$ A\subseteq B \quad\Longleftrightarrow\quad \forall x,\ \bigl(x\in A\Longrightarrow x\in B\bigr). $$ In words, there must be no element of $A$ that fails to belong to $B$. To prove a subset claim, take an arbitrary element of the proposed smaller set and show that it belongs to the proposed larger set. To disprove one, it is enough to find a single element that belongs to the first set but not the second.

A set $A$ is a proper subset of $B$, written $A\subsetneq B$, when $A\subseteq B$ and $A\ne B$. Thus every proper subset is a subset, but the two sets must also be unequal. A subset need not be proper.

Worked Example: A Subset That Is Not Proper

Let $C=\{r,4\}$ and $D=\{4,r\}$. The membership proposition for finite rosters from Set Membership tells us that the elements listed in $C$ are $r$ and $4$, and both are also listed in $D$. Therefore every element of $C$ belongs to $D$, so $C\subseteq D$.

The order of entries in a roster does not change which objects the set contains. The two rosters describe the same set, so $C=D$. Consequently, $C\subseteq D$ is true, but $C\subsetneq D$ is false: the proper-subset condition requires inequality as well as inclusion.

Worked Example: Verifying a Proper Subset

Let $E=\{1,3\}$ and $F=\{1,3,7\}$. The elements of $E$ are $1$ and $3$, and $1\in F$ and $3\in F$. Hence $E\subseteq F$.

The object $7$ belongs to $F$, but it does not belong to $E$. Thus the sets cannot be equal: if they were equal, an element of $F$ would also be an element of $E$. We have both $E\subseteq F$ and $E\ne F$, so $E\subsetneq F$.

A Systematic Test for Subset Claims

For finite rosters, a useful method is to examine each element of the proposed subset. If every one passes the membership test for the other set, the subset claim is true. If even one fails, that element is a counterexample to the claim. The roles of the two sets matter: having an element in $B$ that is not in $A$ does not disprove $A\subseteq B$. It can instead help show that the inclusion is proper.

Identify the set being tested element by element.
For the claim $A\subseteq B$, the elements to check are the elements of $A$.

Check each candidate for membership in $B$.
Show that an arbitrary $x\in A$ also satisfies $x\in B$, or check every listed element when $A$ is finite.

For properness, check inequality too.
After establishing $A\subseteq B$, verify $A\ne B$. A distinguishing element can show the sets are unequal.

Worked Example: Finding a Counterexample to Inclusion

Let $G=\{0,2,6\}$ and $H=\{0,2,5,6\}$. To check $G\subseteq H$, inspect all three elements of $G$. We have $0\in H$, $2\in H$, and $6\in H$. Therefore $G\subseteq H$.

Now reverse the proposed relation. For $H\subseteq G$, every element of $H$ would need to belong to $G$. But $5\in H$ and $5\notin G$, since $5$ is not among $0,2,6$. This single witness disproves $H\subseteq G$. In particular, $G$ is a proper subset of $H$, whereas $H$ is not a subset of $G$.

Two Basic Theorems About Subsets

The definition gives useful general facts that do not depend on the sets being finite. First, every set is a subset of itself. This is sometimes called the reflexive property of inclusion. Second, subset relations can be chained: if every element of $A$ belongs to $B$, and every element of $B$ belongs to $C$, then every element of $A$ belongs to $C$.

Theorem (Reflexivity of Subset Inclusion). For every set $A$, $A\subseteq A$.

Proof. Let $A$ be any set, and let $x$ be an arbitrary object. To prove $A\subseteq A$, we must show that $x\in A$ implies $x\in A$. Suppose $x\in A$. The conclusion $x\in A$ is then already true. Thus for every object $x$, membership in $A$ implies membership in $A$. By the definition of subset, $A\subseteq A$.

Theorem (Transitivity of Subset Inclusion). Let $A,B,C$ be sets. If $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$.

Proof. Suppose $A\subseteq B$ and $B\subseteq C$. Let $x$ be an arbitrary object, and suppose $x\in A$. Since $A\subseteq B$, the definition of subset gives $x\in B$. Since $B\subseteq C$, it then gives $x\in C$. We have shown that every $x\in A$ belongs to $C$. Therefore $A\subseteq C$, as required.

Transitivity justifies a chain of inclusions: each step carries an element from one set to the next. The conclusion is an inclusion between the first and last sets; it does not say that any of those sets must be proper subsets. Equality at one or more steps is allowed unless properness has also been established.

Worked Example: Chaining Three Inclusions

Define $$ A=\{2\},\qquad B=\{2,4\},\qquad C=\{0,2,4,9\}. $$ The only element of $A$ is $2$, and $2\in B$, so $A\subseteq B$. The elements of $B$ are $2$ and $4$, and both belong to $C$, so $B\subseteq C$.

By transitivity, $A\subseteq C$. This can also be checked directly: the only element of $A$ is $2$, and $2\in C$. The extra elements of $B$ and $C$ do not obstruct the inclusion. They matter only when deciding whether an inclusion is proper.

The Empty Set and Subset Inclusion

The empty set $\varnothing$ has no elements. It follows that there can be no object in $\varnothing$ that fails to belong to some other set $A$. Hence $\varnothing\subseteq A$ for every set $A$. This statement is sometimes called vacuous inclusion: the universal requirement in the definition of subset has no counterexample when the set on the left has no elements.

Theorem. For every set $A$, $\varnothing\subseteq A$.

Proof. Let $A$ be an arbitrary set. To prove $\varnothing\subseteq A$, the definition requires that for every object $x$, if $x\in\varnothing$, then $x\in A$. There is no object $x$ for which $x\in\varnothing$, because the empty set has no elements. Thus the implication has no instance with a true hypothesis and false conclusion. It follows that every object satisfies the required implication, and therefore $\varnothing\subseteq A$.

When $A$ is nonempty, the inclusion is proper: $\varnothing$ has no elements, while $A$ has at least one, so the sets are unequal. If $A=\varnothing$, the relation is still a subset relation, but it is not proper because the sets are equal.

Worked Example: The Empty Set in a Subset Comparison

Let $K=\{a,\varnothing\}$. The empty set is a subset of $K$, as it is of every set. Also, $\varnothing\ne K$, since $a\in K$ while $a\notin\varnothing$. Therefore $\varnothing\subsetneq K$.

The notation $\varnothing\subsetneq K$ is different from $\varnothing\in K$. In this example both statements happen to be true, but for different reasons. The first says that every element of the empty set is in $K$, a condition with no elements to check. The second says that the empty set itself is one of the elements listed in $K$.

Common Misreadings

A subset claim is directional. From $A\subseteq B$, one may conclude that every element of $A$ is in $B$, but not that every element of $B$ is in $A$. The example $G\subseteq H$ above showed exactly this asymmetry. Reversing the order of the set names changes the claim.

Another common error is to treat “subset” as automatically meaning “proper subset.” The relation $A\subseteq B$ permits $A=B$, as the reflexivity theorem confirms. The proper relation $A\subsetneq B$ includes an additional requirement, $A\ne B$. When a proof establishes only that every element of $A$ belongs to $B$, it has proved $A\subseteq B$, not necessarily $A\subsetneq B$.

Keep the two checks visible. To prove $A\subseteq B$, show element-by-element inclusion. To prove $A\subsetneq B$, show inclusion and show that the sets are unequal. A single element of $B$ that is not in $A$ can establish this inequality after inclusion has been proved.

For each question, use the definition of subset. In a proper-subset question, make sure to address both inclusion and inequality.

Check Your Understanding

Let $A=\{2,6\}$ and $B=\{1,2,6,8\}$. Is $A\subseteq B$? Is $A\subsetneq B$? Explain both conclusions.
Let $C=\{0,3,7\}$ and $D=\{0,3,5,7\}$. Decide whether $C\subseteq D$ and whether $D\subseteq C$. If one relation fails, identify a witness.
For an arbitrary set $M$, explain why $M\subseteq M$ holds. Which part of the definition must be checked?
Suppose $P\subseteq Q$ and $Q\subseteq R$. What subset relation follows? State the theorem that justifies your answer.
Is $\varnothing\subseteq T$ true for every set $T$? Explain what the definition asks you to check and why the answer holds.
Let $E=\varnothing$ and $F=\{6\}$. Decide whether $E\subseteq F$ and whether $E\subsetneq F$. Explain the difference between the two checks.

What You'll Learn