View source for 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)''' 
   <blockquote>''Given a set <math>S</math> of sets, there exists a set <math>U</math> such that <math>x \in U</math> if and only if <math>x \in A</math> for some <math>A \in S</math>.''</blockquote>

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

'''Example''' Let <math>A = \{1, 2, 3\}</math>, <math>B = \{1, 2\}</math> and <math>C = \{1, 5\}</math>. Now let <math>S = \{A, B, C\}</math>. Then <math>\bigcup S = \{1, 2, 3, 5\}</math>. <math>\square</math>

'''Theorem''' Given a set <math>S</math> of sets as in the Axiom of Union, the union over <math>S</math> is unique.

'''Proof''' If <math>U_1</math> and <math>U_2</math> were both unions over <math>S</math> then <math>x \in U_1</math> iff <math>x \in A</math> for some <math>A \in S</math>. Similarly <math>x \in U_2</math> iff <math>x \in A</math> for some <math>A \in S</math>. Thus <math>x \in U_1</math> iff <math>x \in U_2</math>, and so <math>U_1 = U_2</math> by extensionality. <math>\square</math>

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

'''Definition''' If <math>S = \{A, B\}</math> we denote <math>\bigcup S</math> by <math>A \cup B</math> and call it the ''union'' of <math>A</math> and <math>B</math>.

'''Theorem''' If <math>A</math> and <math>B</math> are sets then <math>A \cup B</math> is a set.

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

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

* Expressions of the form <math>u \in v</math> and <math>u = v</math> are formulas, called ''atomic formulas'', for all variables and constants <math>u</math> and <math>v</math>.

* If <math>P</math> and <math>Q</math> are formulas then <math>P \vee Q</math>, <math>P \wedge Q</math>, <math>\neg P</math>, <math>(P \rightarrow Q)</math> and <math>(P \leftrightarrow Q)</math> are formulas.

* If <math>P</math> is a formula then <math>\forall x_i P</math> and <math>\exists x_i P</math> are formulas.

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

The expression <math>\forall x</math> is called a ''universal quantifier''. It means ''for all sets <math>x</math>''. The expression <math>\exists x</math> is an ''existential quantifier''. It means ''there exists a set <math>x</math>''.

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

Although symbols <math>\subseteq</math>, <math>\subset</math>, etc., and <math>\exist !</math> 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, <math>A\subseteq B</math> can be written <math>\forall x(x\in A \rightarrow x\in B)</math>. Similarly, <math>\exists !x P(x)</math> can be written <math>\exists x(P(x)\wedge \forall y(P(y) \rightarrow y = x))</math>.

'''Definition''' In a formula, any variable <math>x_i</math> inside an expression of the form <math>\forall x_i P</math> or of the form <math>\exists x_i P</math> 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)'''
<blockquote>''For a set <math>A</math> and a property <math>P(x, A)</math> there exists a set <math>B</math> consisting of the <math>x \in A</math> for which <math>P(x, A)</math> holds.''</blockquote>

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 <math>P(x, A)</math> can have finitely many free variables, so is sometimes denoted <math>P(x, y_1, y_2, \ldots ,y_n, A)</math> where the <math>y_i</math> are free variables. But we suppress this technicality for now and just write <math>P(x, A)</math>.

'''Theorem''' The set of elements of a set <math>A</math> for which a property <math>P(x, A)</math> holds is unique.

'''Proof''' This follows by noting that if there were two such sets<math>S_1</math> and <math>S_2</math> then <math>x \in S_1</math> iff <math>x \in A</math> and <math>P(x, A)</math> holds. However, this is the case iff <math>x \in S_2</math>. Thus <math>x \in S_1</math> iff <math>x \in S_2</math> and the result follows by extensionality. <math>\square</math>

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

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

'''Example''' If <math>A = \{1, 2, 3\}</math> then <math>\{x \in A \;|\; x \neq 2\} = \{1, 3\}</math>.

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.

   <math>A\cap B = \{x \in A\cup B \;|\; x \in A \;\mbox{and}\; x\in B\}.</math>

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

More generally, we have the following.

'''Definition''' Let <math>S</math> be a set of sets. The ''intersection'' over <math>S</math> is defined by

   <math>\bigcap S = \{x \in \bigcup S \;|\; x \in A \;\mbox{for all}\; A \in S\}.</math>

'''Example''' Let <math>A = \{1, 2, 3\}</math>, <math>B = \{2, 3, 5\}</math> and <math>C = \{1, 2, 3, 4\}</math>. If <math>S = \{A, B, C\}</math> then <math>\bigcap S = \{2, 3\}</math>.

'''Theorem''' Let <math>S</math> be a set of sets. Then <math>\bigcap S</math> is a set.

'''Proof''' This is a set by the axioms of union and comprehension. <math>\square</math>

The following is a useful definition.

'''Definition''' Two sets <math>A</math> and <math>B</math> are said to be ''disjoint'' if <math>A\cap B = \emptyset</math>.

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

== Exercises ==

* Show that if <math>A</math> and <math>B</math> are sets then <math>A \subseteq B</math> if and only if <math>A\cup B = B</math>.

* Let <math>A</math>, <math>B</math> and <math>C</math> be sets. Show that there exists a set whose elements are <math>A</math>, <math>B</math> and <math>C</math>.

* Suppose <math>X_1, X_2, \ldots, X_n</math> and <math>Y_1, Y_2, \ldots, Y_n</math> are sets with <math>X_i \subseteq Y_i</math> for all <math>i</math>. Let <math>S = \{X_1, X_2, \ldots, X_n\}</math> and <math>T = \{Y_1, Y_2, \ldots, Y_n\}</math>. Show that <math>\bigcap S \subseteq \bigcap T</math>.

{{chapnav|Pairs|Classes and foundation}}

{{BookCat}}