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

## Unions of setsEdit

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 of sets, there exists a set such that if and only if for some .

**Definition** Given a set of sets, we call a set as in the Axiom of Union, a *union* over and denote it .

**Example** Let , and . Now let . Then .

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

**Proof** If and were both unions over then iff for some . Similarly iff for some . Thus iff , and so by extensionality.

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

**Definition** If we denote by and call it the *union* of and .

**Theorem** If and are sets then is a set.

**Proof** By the Axiom of Pair, is a set. Thus by the Axiom of Union is a set.

## ComprehensionEdit

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 of which we are allowed an unlimited supply, and constants, i.e. specific sets say, and must be built up using a finite number of the following:

- Expressions of the form and are formulas, called
*atomic formulas*, for all variables and constants and .

- If and are formulas then , , , and are formulas.

- If is a formula then and are formulas.

Here stands for logical *or*, is logical *and*, is logical negation, is *implies* and stands for *if and only if*, which we shall often abbreviate *iff*.

The expression is called a *universal quantifier*. It means *for all sets *. The expression is an *existential quantifier*. It means *there exists a set *.

**Example** Given a set the expression is an example of a formula.

Although symbols , , etc., and 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, can be written . Similarly, can be written .

**Definition** In a formula, any variable inside an expression of the form or of the form 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 and a property there exists a set consisting of the for which 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 can have finitely many free variables, so is sometimes denoted where the are free variables. But we suppress this technicality for now and just write .

**Theorem** The set of elements of a set for which a property holds is unique.

**Proof** This follows by noting that if there were two such sets and then iff and holds. However, this is the case iff . Thus iff and the result follows by extensionality.

**Definition** The set of elements of a set for which holds is denoted .

We can read the vertical bar as *such that*.

**Example** If then .

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 setsEdit

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

```
```

The formula in the comprehension consists of two predicates from the language of sets, and , joined by the logical conjunction *and* from formal logic.

More generally, we have the following.

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

```
```

**Example** Let , and . If then .

**Theorem** Let be a set of sets. Then is a set.

**Proof** This is a set by the axioms of union and comprehension.

The following is a useful definition.

**Definition** Two sets and are said to be *disjoint* if .

**Example** The sets and are disjoint since their intersection is empty.

## ExercisesEdit

- Show that if and are sets then if and only if .

- Let , and be sets. Show that there exists a set whose elements are , and .

- Suppose and are sets with for all . Let and . Show that .