Set Specification

Why

We want to construct new sets out of old ones. So, can we always construct subsets?

Definition

We will say that we can. More specifically, if we have a set and some statement which may be true or false for the elements of that set, a set exists containing all and only the elements for which the statement is true.

Roughly speaking, the principle is like this. We have a set which contains some objects. Suppose the set of playing cards in a usual deck exists. We are taking as a principle that the set of all fives exists, so does the set of all fours, as does the set of all hearts, and the set of all face cards. Roughly, the corresponding statements are “it is a five”, “it is a four”, “it is a heart”, and “it is a face card”.

For any statement and any set, there is a subset whose elements satisfy the statement.

We call this the principle of specification. We call the second set (obtained from the first) the set obtained by specifying elements according to the sentence. The principle of extension says that this set is unique. All our basic principles about sets (other than the principle of extension) assert that we can construct new sets out of old ones in reasonable ways.

Notation

Let $A$ denote a set. Let $s$ denote a statement in which the symbol $x$ and $A$ appear unbound. We assert that there is a set, denote it by $B$, for which belonging is equivalent to membership in $A$ and satisfaction of $s$. In other words,

\[ (\forall x)((x \in B) \iff ((x \in A) \land s(x))). \]

We denote $B$ by $\Set*{x \in A}{s(x)}$. We read the symbol $\mid$ aloud as “such that.” We read the whole notation aloud as “a in A such that...” We call it set-builder notation.

Nothing contains everything

As an example of the principle of specification and an important consequence, consider the statement $x \not\in x$. Using this statement and the principle of specification, we can prove that there is no set which contains every other set.

No set contains all sets.¹

Suppose there exists a set, denote it $A$ which contains all sets. In other words, suppose $(\exists A)(\forall x)(x \in A)$. Use the principle of specification to construct $B = \Set{x \in A}{x \not\in x}$. So $(\forall x)(x \in B \iff (x \in A \land x \not\in x))$ In particular, $(B \in B \iff (B \in A \land B \not\in B))$. So $B \not\in A$.

We might call such a set, if we admitted its existence, a universe of discourse or universal set. With the principle of specification, a “principle of a universal set” would give a contradiction (called Russell’s paradox). ↩︎