How Do You Check if an Element Is in a Set or if One Set Is a Subset of Another?

Use a membership test to check whether an element belongs to a set, and a subset test to check whether every element of one set belongs to another. Mathematically, test whether $x \in A$ or whether $B \subseteq A$.

Membership and Subset Tests

A set is an abstract data type (ADT) that stores distinct, unordered elements. The ADT specifies operations and their behaviour without requiring the programmer to know the underlying implementation.

A subset test can be expressed algorithmically as:

FUNCTION isSubset(B, A)
    FOR EACH element IN B
        IF NOT contains(A, element) THEN
            RETURN false
        END IF
    END FOR
    RETURN true
END FUNCTION

For example, checking whether $\{2,6\} \subseteq \{2,4,6\}$ requires testing both $2 \in A$ and $6 \in A$. Since both membership tests are true, the subset test is true.

A common misconception is that a subset must be smaller than the other set. In fact, every set is a subset of itself, so $A \subseteq A$. Only a proper subset must contain fewer elements. The empty set is also a subset of every set.

Exam Technique

For B4.1 Fundamentals of ADTs, distinguish the operation from its implementation. State that membership checks one element, whereas a subset check applies membership to every element of the candidate subset. If asked to construct an algorithm, include an immediate false result when an element is missing and return true only after all elements have been checked.