subset

A subset of a given set $A$ is a set $B$ that may be viewed as contained within $A$.

In material set theory, a **subset** of a set $A$ is a set $B$ with the *property* that

$x \in B \;\Rightarrow\; x \in A$

for any object $x$ whatsoever. One writes $B \subseteq A$ or $B \subset A$ (depending on the author) if $B$ has this property. Set theory's axiom of extensionality says that $A = B$ if (and only if) $A \subseteq B$ and $B \subseteq A$ (although this is only strong enough for well-founded set?s).

In structural foundations of mathematics, this definition doesn't make sense, because there is no global membership predicate $\in$ (and there may not be a global equality predicate either). Accordingly, we define a **subset** of $A$ to be a set $B$ with the *structure* of an injection

$i\colon B \hookrightarrow A .$

We can still define a *local* membership predicate $\in_A$ as follows: Given an element $x$ of $A$ and a subset $B$ (technically, $(B,i)$) of $A$,

(1)$x \in_A B \;\Leftrightarrow\; \exists(y\colon B),\; x = i(y) .$

Similarly, we can define a local containment predicate $\subseteq_A$ as follows: Given subsets $B$ and $C$ of $A$,

$B \subseteq_A C \;\Leftrightarrow\; \forall(x\colon A),\; x \in B \;\Rightarrow\; x \in C .$

We can also define a local equality predicate $=_A$ on subsets of $A$:

$B =_A C \;\Leftrightarrow\; B \subseteq C \;\wedge\; C \subseteq B .$

In foundations that already have a global equality predicate on sets (and functions between equal sets), this local equality predicate must be interpreted as an equivalence relation; then a **subset** of $A$ is technically an equivalence class of injections to $A$ rather than simply an injection to $A$.

In any case, if $A$ is a subset of $B$, then $B$ is a **superset** of $A$.

As you can see from the right-hand sides of the above sequence of definitions, one usually suppresses the subscript $A$ from the notation. Even the right-hand side of (1) may use a local equality relation on elements of $A$. It may be necessary to distinguish $x\colon E$ (the *typing declaration* introducing a variable $x$ for an element of a given set $E$) from $x \in_A E$ (the *proposition* that a given element $x$ of a given set $A$ is a member of a given subset $E$ of $A$). Some authors may use $x \in A$ for either or both of these, trusting on context (particularly whether $x$ has been introduced before) to distinguish them. Another notational convenience is to suppress the injection $i$, writing $y$ instead of $i(y)$.

The concept of subset as it appears here generalises to subobject in category theory. To be precise, a subset of $A$ is exactly a subobject of $A$ when $A$ is thought of as an object of the category Set. The concept of superset then generalises to a notion of extension analogous to that of field extension.

When the abstract set $A$ is fixed, a subset $B$ of $A$ may be thought of as a **concrete set**.

Revised on July 30, 2012 11:15:18
by Toby Bartels
(98.16.162.107)