What Operations Can You Perform on a Set (Union; Intersection; Difference)?

A set abstract data type (ADT) stores distinct elements without requiring a fixed order. The three main binary set operations are union, intersection, and difference, each of which produces a set from two input sets.

Under B4.1 Fundamentals of ADTs, the important principle is that an ADT specifies what operations do, independently of how the set is implemented internally.

Let:

$$A = \{1,2,3,4\}, \qquad B = \{3,4,5\}$$

Membership tests give a precise definition. For any element $x$, union requires membership in at least one input set; intersection requires membership in both; and $A \setminus B$ requires membership in $A$ but not in $B$.

Union combines membership: an element belongs to $A \cup B$ if it belongs to $A$, $B$, or both. Repeated values are not retained because sets contain unique elements.

Intersection keeps only shared membership. If two sets have no common elements, their intersection is the empty set, written $\varnothing$.

Difference removes from the first set all elements occurring in the second. It is directional, so:

$$A \setminus B = \{1,2\}, \qquad B \setminus A = \{5\}$$

These operations usually return a new set, leaving the input sets unchanged, unless an implementation explicitly defines an in-place operation. Their results still obey the set invariant: every stored element is unique.

In programs, union can combine permissions, intersection can identify shared users, and difference can find items present in one collection but absent from another.

A common misconception is that set difference is commutative. It is not: while $A \cup B = B \cup A$ and $A \cap B = B \cap A$, generally $$.

Exam technique: For a “determine” or “construct” question, write each resulting element once and check the direction of difference. If asked to explain the ADT, describe the operation’s behaviour rather than assuming an implementation such as an array or hash table.