Subsets and Set Inclusion

Set inclusion is the backbone of the subset lattice used throughout combinatorics, where counting subsets, chains, and antichains of a finite set (Sperner's theorem, the Boolean lattice) all rest on $\subseteq$. In topology, open sets are compared by inclusion to define bases, neighborhoods, and the specialization order on a space. In logic and model theory, one theory "extends" another when its consequences are a superset of the other's, and substructures are literally defined via subset inclusion on domains and compatible operations. In computer science, type systems use subtyping relations that are formally modeled as $\subseteq$ on sets of admissible values, and database theory expresses query containment — whether one query's results are always a subset of another's — as a decidability problem built directly on $\subseteq$. In probability and measure theory, events are subsets of a sample space, and $A \subseteq B$ underlies monotonicity of probability: $P(A) \le P(B)$ whenever $A \subseteq B$. Cryptographic access-control models (like lattice-based security levels) also use inclusion orders on sets of permissions to formalize "who can see what."

Ask the tutor: Can you show me why $A \subseteq B$ and $B \subseteq A$ together forcing $A = B$ actually needs the Axiom of Extensionality, rather than being automatic from the definition of $\subseteq$ alone?

Think of a set as a bag of labeled marbles, and think of $A \subseteq B$ as the claim "every marble in bag $A$ can also be found in bag $B$." This says nothing about whether bag $B$ has extra marbles, and nothing about whether the bags themselves are marbles inside some larger bag. The relation lives entirely at the level of checking each element of $A$ one at a time. This is exactly why $\in$ and $\subseteq$ must never be conflated. If $x \in A$, then $x$ is a single object that happens to be a member of $A$; if $A \subseteq B$, then $A$ is itself a whole set being compared to another whole set. The classic trap: for $A = \{1,2\}$ and $B = \{1, \{1,2\}, 3\}$, it is true that $A \in B$ (since $\{1,2\}$ appears as an element of $B$), but it is false that $A \subseteq B$, because $2 \in A$ while $2 \notin B$. Conversely $1 \in A$ and $1 \in B$, but $1 \subseteq B$ is not even a well-formed possibility to assert casually — $1$ is not a set of the right form for $\subseteq$ to have its usual meaning unless we're in a context where numbers are coded as sets (as with the von Neumann ordinals), and even then it is a separate fact to check. A useful mental picture is a Venn diagram in which the circle for $A$ sits entirely inside the circle for $B$: no part of $A$'s circle sticks outside $B$'s.

The second picture below shows the relation among sets themselves — not elements inside sets, but sets arranged by inclusion — for a tiny concrete family. This is the beginning of the partial-order structure that $\subseteq$ imposes.

Example 1 — a subset check with mixed structure. Let

Is $A \subseteq B$? Is $B \subseteq A$? Checking $A \subseteq B$. We must verify, for each of the three elements of $A$, that it also lies in $B$.

• $2 \in A$: is $2 \in B$? Yes, $2$ is listed explicitly in $B$.
• $4 \in A$: is $4 \in B$? Yes, listed explicitly.
• $\{6\} \in A$: is $\{6\} \in B$? Yes — note carefully that $\{6\}$ is itself one of the listed elements of $B$ (not to be confused with the element $6$, which is a different object from the singleton set $\{6\}$). So $\{6\} \in B$.

All three elements of $A$ pass the test, so $A \subseteq B$. Checking $B \subseteq A$. $B$ has five elements: $2, 4, 6, \{6\}, \{2,4\}$. Take $x = 6$. Is $6 \in A$? Looking at $A = \{2,4,\{6\}\}$, the elements are $2$, $4$, and $\{6\}$ — and $6$ itself (the bare number) is not one of these three objects, since $\{6\}$ is a set containing $6$, not equal to $6$. So $6 \notin A$. This single failure means $B \nsubseteq A$. Conclusion: $A \subsetneq B$ (proper subset), since $A \subseteq B$, $A \ne B$ (they even have different cardinalities, 3 versus 5), and we exhibited $6 \in B \setminus A$.

Example 2 — subsets defined by a condition, requiring an existential witness for non-inclusion. Let

First compute $A$ explicitly: we need integers $n$ with $n^2 < 15$. Checking, $3^2 = 9 < 15$ but $4^2 = 16 \not< 15$, and by symmetry $(-4)^2 = 16 \not< 15$ while $(-3)^2 = 9 < 15$. So

And directly, $B = \{-3,-2,-1,0,1,2,3\}$ as well, by unpacking the inequality. So here $A = B$ exactly — a good moment to note the standard proof strategy for set equality via inclusion in both directions, foreshadowing Set Equality and Extensionality. Let's instead modify the example to make it asymmetric: define

Since $3^2 = 9 < 10$ but $(-3)^2 = 9 < 10$ too, and $2^2=4<10$, checking all cases gives

That's still equal to $B$ — the point is that squares grow slowly near small integers, so let's push further and use $A'' = \{n \in \mathbb Z : n^2 < 5\}$. Then $2^2 = 4 < 5$ but $(-3)^2 = 9 \not< 5$, and checking all integers gives

Now compare with $B = \{-3,-2,-1,0,1,2,3\}$. Claim: $A'' \subseteq B$. Let $n \in A''$ be arbitrary, so $n \in \{-2,-1,0,1,2\}$. In every one of these five cases, $-3 \le n \le 3$ holds (check: $-3\le -2$, and $2 \le 3$, with everything in between trivially satisfying both bounds). Hence $n \in B$. Since $n$ was an arbitrary element of $A''$, $A'' \subseteq B$. Claim: $B \nsubseteq A''$. We must produce one element of $B$ not in $A''$. Take $n = 3 \in B$ (since $-3 \le 3 \le 3$). Is $3 \in A''$? We need $3^2 < 5$, i.e. $9 < 5$, which is false. So $3 \notin A''$. This single witness refutes $B \subseteq A''$. Conclusion: $A'' \subsetneq B$, and the specific witness $n=3$ demonstrates properness — a concrete instance of turning the definition of $\subsetneq$ ("some element of $B$ is missing from $A$") into an explicit numeral.