Unions and Intersections

The set generator notation $\{ x \mid f(x) \}$ creates new set. Although the notation only generate sets, it is powerful enough define basic set operations: union, intersection, and difference.

Definition Union

The union of two sets $A$ and $B$ is the set of all things which are elements of $A$ , $B$ , or both.

A \cup B = \{ x \mid x \in A \text{ or } x \in B \}

The union operator is useful for combining two sets of things into one such as films seen by two persons can be represented as sets $A$ and $B$ . Now that if they are to go cinema, they can create a new set $C$ to determine the films either of them has seen.

Example Films seen by two friends

Two young friends are trying decide a film to watch, but they can only choose from films either of them owns. Friend $A$ is a Star Wars fan and bought films

A = \{ \textit{A New Hope}, \textit{The Force Awakens} \},

the friend $B$ loves superhero films and has a collection

B = \{ \textit{Iron Man}, \textit{Spiderman 1} \}.

The films they can watch is a union $A \cup B$ which forms a new set

C = \{ \textit{A New Hope}, \textit{The Force Awakens}, \textit{Iron Man}, \textit{Spiderman 1} \}.

We can also consider a "dual" operation to union. This is the operation that forms the set of all elements that are elements of $A$ and are also elements of $B$ . This operation is called intersection. Two sets are called disjoint if their intersection is empty.

Definition Intersection

The intersection of two sets $A$ and $B$ , written $A \cap B$ , is the set of all things which are elements of both $A$ and $B$ .

A \cap B = \{ x \mid x \in A \text{ and } x \in B\}

A practical use is finding common elements of things, e.g. in dating finding common interests and expectations is important. You may discuss food you both like or activities you would enjoy doing together. A way to represent this situation is to define an intersection of interests $C = A \cap B$ . If there is a set of things $D$ you cannot do due to life situation e.g. having children, you can define a set of things you can do using difference operation.

Definition Difference

The set difference $A \setminus B$ is the set of all elements of $A$ which are not also element of $B$ , i.e,

A \setminus B = \{ x \mid x \in A \text{ and } x \notin B \}.

Problem

Implement set data structure, and the basic operations described in this section.