Mathematical Proof and the Principles of Mathematics/Sets/Union and intersection

Unions of sets

The construction that allows us to form sets with more than two elements is the union. It allows us to take existing sets and form a single set containing all the elements of those sets.

Axiom (Union)

Given a set $S$ of sets, there exists a set $U$ such that $x\in U$ if and only if $x\in A$ for some $A\in S$.

Definition Given a set $S$ of sets, we call a set $U$ as in the Axiom of Union, a union over $S$ and denote it $\bigcup S$.

Example Let $A=\{1,2,3\}$, $B=\{1,2\}$ and $C=\{1,5\}$. Now let $S=\{A,B,C\}$. Then $\bigcup S=\{1,2,3,5\}$. $\square$

Theorem Given a set $S$ of sets as in the Axiom of Union, the union over $S$ is unique.

Proof If $U_{1}$ and $U_{2}$ were both unions over $S$ then $x\in U_{1}$ iff $x\in A$ for some $A\in S$. Similarly $x\in U_{2}$ iff $x\in A$ for some $A\in S$. Thus $x\in U_{1}$ iff $x\in U_{2}$, and so $U_{1}=U_{2}$ by extensionality. $\square$

We recover the familiar definition of the union of two sets as follows.

Definition If $S=\{A,B\}$ we denote $\bigcup S$ by $A\cup B$ and call it the union of $A$ and $B$.

Theorem If $A$ and $B$ are sets then $A\cup B$ is a set.

Proof By the Axiom of Pair, $S=\{A,B\}$ is a set. Thus by the Axiom of Union $A\cup B=\bigcup S$ is a set. $\square$

Comprehension

Comprehensions allow us to select elements of an existing set that have some specified property. The Axiom Schema of Comprehension says that such selections define sets.

There is very little restriction on the properties we may use in comprehensions, except that they must be specified with formulas in the language of set theory and formal logic.

We first define what we mean by a formula.

Definition A formula can contain variables $x_{1},x_{2},\ldots$ of which we are allowed an unlimited supply, and constants, i.e. specific sets $A_{1},A_{2},\ldots$ say, and must be built up using a finite number of the following:

• Expressions of the form $u\in v$ and $u=v$ are formulas, called atomic formulas, for all variables and constants $u$ and $v$.

• If $P$ and $Q$ are formulas then $P\vee Q$, $P\wedge Q$, $\neg P$, $(P\rightarrow Q)$ and $(P\leftrightarrow Q)$ are formulas.

• If $P$ is a formula then $\forall x_{i}P$ and $\exists x_{i}P$ are formulas.

Here $\vee$ stands for logical or, $\wedge$ is logical and, $\neg$ is logical negation, $\rightarrow$ is implies and $\leftrightarrow$ stands for if and only if, which we shall often abbreviate iff.

The expression $\forall x$ is called a universal quantifier. It means for all sets $x$. The expression $\exists x$ is an existential quantifier. It means there exists a set $x$.

Example Given a set $A$ the expression $P(x,A)=\forall y(x\in y)\vee (x\in A)$ is an example of a formula. $\square$

Although symbols $\subseteq$, $\subset$, etc., and $\exists !$ for there exists a unique, are not part of the formal language, we can define them in terms of the existing language of set theory.

For example, $A\subseteq B$ can be written $\forall x(x\in A\rightarrow x\in B)$. Similarly, $\exists !xP(x)$ can be written $\exists x(P(x)\wedge \forall y(P(y)\rightarrow y=x))$.

Definition In a formula, any variable $x_{i}$ inside an expression of the form $\forall x_{i}P$ or of the form $\exists x_{i}P$ is said to be bound. All other variables in a formula are said to be free, or arguments of the formula.

We are now in a position to state the Axiom Schema of Comprehension.

Axiom Schema (Comprehension)

For a set $A$ and a property $P(x,A)$ there exists a set $B$ consisting of the $x\in A$ for which $P(x,A)$ holds.

Note that this is not just one axiom, but an axiom for each possible property. We call a collection of axioms like this an axiom schema.

Technically the formula $P(x,A)$ can have finitely many free variables, so is sometimes denoted $P(x,y_{1},y_{2},\ldots ,y_{n},A)$ where the $y_{i}$ are free variables. But we suppress this technicality for now and just write $P(x,A)$.

Theorem The set of elements of a set $A$ for which a property $P(x,A)$ holds is unique.

Proof This follows by noting that if there were two such sets$S_{1}$ and $S_{2}$ then $x\in S_{1}$ iff $x\in A$ and $P(x,A)$ holds. However, this is the case iff $x\in S_{2}$. Thus $x\in S_{1}$ iff $x\in S_{2}$ and the result follows by extensionality. $\square$

Definition The set of elements of a set $A$ for which $P(x,A)$ holds is denoted $\{x\in A\;|\;P(x,A)\}$.

We can read the vertical bar as such that.

Example If $A=\{1,2,3\}$ then $\{x\in A\;|\;x\neq 2\}=\{1,3\}$.

The Axiom Schema of Comprehension is sometimes called the Subset Axiom Scheme or Axiom Schema of Specification, since it guarantees that any subset of a set specified by a formula, is a set.

Intersections of sets

We can define the familiar intersection of two sets in terms of a comprehension.

  $A\cap B=\{x\in A\cup B\;|\;x\in A\;{\mbox{and}}\;x\in B\}.$

The formula in the comprehension consists of two predicates from the language of sets, $(x\in A)$ and $(x\in B)$, joined by the logical conjunction and from formal logic.

More generally, we have the following.

Definition Let $S$ be a set of sets. The intersection over $S$ is defined by

  $\bigcap S=\{x\in \bigcup S\;|\;x\in A\;{\mbox{for all}}\;A\in S\}.$

Example Let $A=\{1,2,3\}$, $B=\{2,3,5\}$ and $C=\{1,2,3,4\}$. If $S=\{A,B,C\}$ then $\bigcap S=\{2,3\}$.

Theorem Let $S$ be a set of sets. Then $\bigcap S$ is a set.

Proof This is a set by the axioms of union and comprehension. $\square$

The following is a useful definition.

Definition Two sets $A$ and $B$ are said to be disjoint if $A\cap B=\emptyset$.

Example The sets $A=\{1,2,3\}$ and $B=\{4,5\}$ are disjoint since their intersection is empty.

Exercises

• Show that if $A$ and $B$ are sets then $A\subseteq B$ if and only if $A\cup B=B$.

• Let $A$, $B$ and $C$ be sets. Show that there exists a set whose elements are $A$, $B$ and $C$.

• Suppose $X_{1},X_{2},\ldots ,X_{n}$ and $Y_{1},Y_{2},\ldots ,Y_{n}$ are sets with $X_{i}\subseteq Y_{i}$ for all $i$. Let $S=\{X_{1},X_{2},\ldots ,X_{n}\}$ and $T=\{Y_{1},Y_{2},\ldots ,Y_{n}\}$. Show that $\bigcap S\subseteq \bigcap T$.