next up previous contents
Next: Union Up: Operations with sets Previous: Equality   Contents

Intersection

Definition 3.2.7   Let $ A$ and $ B$ be two sets. The intersection of $ A$ and $ B$ is the set of all the elements that $ A$ and $ B$ have in common. We denote:

$\displaystyle A \cap B = \{ x \; \vert \; x \in A \wedge x \in B \}$    

Note that $ A \cap B$ is a subset of $ A$ and a subset of $ B$.

Example 3.2.8   Let $ A=\{a,b,c,d,e \}$ and $ B=\{ a,c,d,h,y,\}$. Then $ A \cap B = \{
a,c,d \}$.

The intersection of two sets can be repesented using Venn diagrams:

Figure 3: The intersection of two sets
\begin{figure}
\centering
\mbox{\epsfig{file=intersection.eps,height=3.5cm}}
\end{figure}

Proposition 3.2.9 (the commutative law)   Let $ A$ and $ B$ be two sets. Then the following equality holds:

$\displaystyle A \cap B = B \cap A.$    

Proof. We use truth table with the following notations:

$\displaystyle \begin{matrix}
 p= & \lq\lq x \in A''\\  
 q= & \lq\lq x \in B''
 \end{matrix}$    

Thus, $ ''x \in A \cup B''$ is equivalent to $ p \vee q$ and $ ''x \in B \cup A''$ is equivalent to $ q \vee p$. Our proposition is equivalent to the commutative law for the logical connector $ \wedge$ (v.s. Proposition prop commutative law for and). $ \qedsymbol$

The commutative law for the intersection of sets can be generalized to the intersection of any (finite) number of sets; the proof is done by induction (v.i. Prop.Definition def Peano).

Proposition 3.2.10 (the associative law)   Let $ A$,$ B$and $ C$ be three sets. Then the following equality holds:

$\displaystyle A \cap (B \cap C )= (A \cap B ) \cap C.$    

We prove it using truth tables, Proposition prop associative law for or, with notations similar to those in the proof of Proposition 2.14.

Figure 4: Intersection: associative law - first part
\begin{figure}
\centering
\mbox{\epsfig{file=InterAssoc-1.eps, height=3.5cm}}
\end{figure}

Figure 5: Intersection: asociative law - second part
\begin{figure}
\centering
\mbox{\epsfig{file=InterAssoc-2.eps, height=3.5cm}}
\end{figure}

The associative law for the intersection of sets can be generalized to the intersection of any (finite) number of sets; the proof is done by induction (v.i. Prop. def Peano). An extension of the associative law for intersection is as follows. Let $ I$ and $ J$ be two sets of indices; if $ \{ A_i , \; i \in I \}$ and $ \{ b_j, \; j \in J \}$ are two families of sets, then

$\displaystyle \left( \underset{i \in I}{\bigcap} A_i \right) \cap \left( \under...
...derset{\begin{matrix}i \in I \\  j \in J \end{matrix}}
 \bigcap (A_i \cap B_j).$    

Proposition 3.2.11   Let $ A$ be any set. Then we have:

$\displaystyle A \cap \emptyset$ $\displaystyle = \emptyset$    
$\displaystyle A\cap A$ $\displaystyle = A$    

This proposition can be proven with truth tables.

Proposition 3.2.12   For any two sets, the following holds:

$\displaystyle A \cap B = A \Longleftrightarrow A \subset B.$    

Here too, use truth tables.
next up previous contents
Next: Union Up: Operations with sets Previous: Equality   Contents
root 2002-06-10