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:

$$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

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

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

Proof. We use truth table with the following notations:

$$\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:

$$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

Figure 5: Intersection: asociative law - second part

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

$$\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:

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

$$A\cap A = A$$

This proposition can be proven with truth tables.

Proposition 3.2.12   For any two sets, the following holds:

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

Here too, use truth tables.