Learning Objectives

• Define sets, membership, the empty set and subset relations.
• Prove set equality using double inclusion ($A \subseteq B$ and $B \subseteq A$).
• Translate set concepts to Java's Set<T> interface.
• Apply element-chasing proofs to verify set relationships.
• Implement isSubset, union, intersection in Java and verify properties.

Concept Overview

What Is a Set?

A set is an unordered collection of distinct elements. Two sets are equal if and only if they contain the same elements.

Roster and Set-Builder Notation

• Roster notation: $A = \{1, 2, 3\}$
• Set-builder notation: $A = \{x \in \mathbb{Z} \mid x > 0 \text{ and } x \leq 3\}$

Key Properties

1. No duplicates: $\{1, 1, 2\} = \{1, 2\}$.
2. No order: $\{1, 2, 3\} = \{3, 1, 2\}$.
3. Sets can contain sets: $\{1, \{2, 3\}\}$ has two elements.

Subsets

$A \subseteq B$ means $\forall x : x \in A \rightarrow x \in B$.

To prove $A \subseteq B$: Take an arbitrary $x \in A$ and show $x \in B$.

To disprove $A \subseteq B$: Find a specific $x \in A$ with $x \notin B$ (counterexample).

Set Equality via Double Inclusion

To prove $A = B$:

1. Show $A \subseteq B$ (every element of $A$ is in $B$).
2. Show $B \subseteq A$ (every element of $B$ is in $A$).

Why this matters in CS:

• Sets model collections of unique items: user IDs, permissions, states, visited nodes.
• Database queries use set semantics (SQL DISTINCT, UNION, INTERSECT).
• Type systems use subsets: "Integer is a subset of Number."

Formal Notation

Worked Examples

Example 1: Proving a Subset Relationship

Claim: If $A = \{x \in \mathbb{Z} \mid x \text{ is divisible by } 6\}$ and $B = \{x \in \mathbb{Z} \mid x \text{ is divisible by } 3\}$, then $A \subseteq B$.

Proof. Let $x \in A$. Then $6 \mid x$, so $x = 6k$ for some $k \in \mathbb{Z}$. But $x = 6k = 3(2k)$, and since $2k \in \mathbb{Z}$, we have $3 \mid x$, so $x \in B$. Since $x$ was arbitrary, $A \subseteq B$. $\blacksquare$

Example 2: Disproving a Subset

Claim: $B \subseteq A$ (with $A$, $B$ as above).

Disproof. Counterexample: $9 \in B$ (since $3 \mid 9$) but $9 \notin A$ (since $6 \nmid 9$). So $B \not\subseteq A$. $\blacksquare$

Example 3: Set Equality by Double Inclusion

Claim: $\{x \in \mathbb{Z} \mid x^2 = x\} = \{0, 1\}$.

Proof.

• ($\subseteq$): If $x^2 = x$, then $x^2 - x = 0$, so $x(x-1) = 0$, giving $x = 0$ or $x = 1$.
• ($\supseteq$): $0^2 = 0$ ✓ and $1^2 = 1$ ✓.

Both inclusions hold, so the sets are equal. $\blacksquare$

Example 4: Empty Set Is a Subset of Every Set

Claim: $\emptyset \subseteq A$ for any set $A$.

Proof. We must show $\forall x (x \in \emptyset \rightarrow x \in A)$. Since $x \in \emptyset$ is always false, the implication is vacuously true. $\blacksquare$

Example 5: Connecting to Module 1 — Divisor Sets

Claim: For positive integer $n$, let $D(n) = \{d \in \mathbb{Z}^+ \mid d \text{ divides } n\}$. If $a \mid b$, then $D(a) \subseteq D(b)$.

Proof. Let $d \in D(a)$, so $d \mid a$. Since $a \mid b$, by transitivity of divisibility (Module 1, Class 2), $d \mid b$, so $d \in D(b)$. $\blacksquare$

Proof Techniques Spotlight

Element-Chasing

The standard technique for proving set relationships:

To prove $A \subseteq B$:

"Let $x \in A$. [Show that $x$ satisfies the conditions for membership in $B$.] Therefore $x \in B$."

To prove $A = B$:

"($\subseteq$): Let $x \in A$. ... Therefore $x \in B$.

($\supseteq$): Let $x \in B$. ... Therefore $x \in A$.

By double inclusion, $A = B$."

To prove $A \cap B \subseteq C$:

"Let $x \in A \cap B$. Then $x \in A$ and $x \in B$. [Use both facts to show $x \in C$.]"

Java Deep Dive

import java.util.*;
import java.util.stream.*;

public class SetMembershipLibrary {

    // --- Membership and Subset ---

    /**
     * Check whether every element of A is contained in B.
     * Implements: A ⊆ B ≡ ∀x (x ∈ A → x ∈ B)
     */
    public static <T> boolean isSubset(Set<T> a, Set<T> b) {
        for (T x : a) {
            if (!b.contains(x)) return false;
        }
        return true;
    }

    /**
     * Check set equality via double inclusion.
     * A = B iff A ⊆ B and B ⊆ A
     */
    public static <T> boolean setEquals(Set<T> a, Set<T> b) {
        return isSubset(a, b) && isSubset(b, a);
    }

    // --- Set Construction ---

    /**
     * Build a set from a predicate (set-builder notation).
     * { x ∈ universe | predicate(x) }
     */
    public static <T> Set<T> setBuilder(Set<T> universe,
                                         java.util.function.Predicate<T> predicate) {
        Set<T> result = new HashSet<>();
        for (T x : universe) {
            if (predicate.test(x)) result.add(x);
        }
        return result;
    }

    /**
     * Compute the set of positive divisors of n.
     * D(n) = { d ∈ Z+ | d divides n }
     * Connects to Module 1.
     */
    public static Set<Integer> divisorSet(int n) {
        Set<Integer> result = new TreeSet<>();
        for (int d = 1; d <= Math.abs(n); d++) {
            if (n % d == 0) result.add(d);
        }
        return result;
    }

    // --- Intersection and Union ---

    /**
     * A ∩ B = { x | x ∈ A and x ∈ B }
     * Returns a new set (does not mutate inputs).
     */
    public static <T> Set<T> intersection(Set<T> a, Set<T> b) {
        Set<T> result = new HashSet<>(a);
        result.retainAll(b);
        return result;
    }

    /**
     * A ∪ B = { x | x ∈ A or x ∈ B }
     * Returns a new set (does not mutate inputs).
     */
    public static <T> Set<T> union(Set<T> a, Set<T> b) {
        Set<T> result = new HashSet<>(a);
        result.addAll(b);
        return result;
    }

    /**
     * A \ B = { x | x ∈ A and x ∉ B }
     */
    public static <T> Set<T> difference(Set<T> a, Set<T> b) {
        Set<T> result = new HashSet<>(a);
        result.removeAll(b);
        return result;
    }

    // --- Verification Methods ---

    /**
     * Verify A ∩ B ⊆ A (a basic set identity).
     */
    public static <T> boolean verifyIntersectionSubset(Set<T> a, Set<T> b) {
        Set<T> inter = intersection(a, b);
        return isSubset(inter, a);
    }

    /**
     * Verify: if a | b then D(a) ⊆ D(b).
     * Connects divisibility (Module 1) with set theory.
     */
    public static boolean verifyDivisorSubset(int a, int b) {
        if (b % a != 0) return false;  // a does not divide b
        return isSubset(divisorSet(a), divisorSet(b));
    }

    // --- Demonstration ---

    public static void main(String[] args) {
        System.out.println("=== Set Membership Library ===\n");

        // Basic sets
        Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(Arrays.asList(2, 3, 4, 5, 6));
        Set<Integer> c = new HashSet<>(Arrays.asList(1, 2, 3));

        System.out.println("A = " + a);
        System.out.println("B = " + b);
        System.out.println("C = " + c);

        // Subset tests
        System.out.println("\nC ⊆ A? " + isSubset(c, a));       // true
        System.out.println("A ⊆ B? " + isSubset(a, b));         // false (1 ∉ B)

        // Set operations
        System.out.println("\nA ∩ B = " + intersection(a, b));   // {2,3,4}
        System.out.println("A ∪ B = " + union(a, b));            // {1,2,3,4,5,6}
        System.out.println("A \\ B = " + difference(a, b));      // {1}

        // Verify A ∩ B ⊆ A
        System.out.println("\nA ∩ B ⊆ A? " + verifyIntersectionSubset(a, b));

        // Set-builder notation
        Set<Integer> universe = IntStream.rangeClosed(1, 20)
                .boxed().collect(Collectors.toSet());
        Set<Integer> evens = setBuilder(universe, n -> n % 2 == 0);
        Set<Integer> divBy3 = setBuilder(universe, n -> n % 3 == 0);
        System.out.println("\nEvens in [1,20]: " + new TreeSet<>(evens));
        System.out.println("Div by 3 in [1,20]: " + new TreeSet<>(divBy3));
        System.out.println("Even ∩ DivBy3: " + new TreeSet<>(intersection(evens, divBy3)));

        // Divisor sets (connecting to Module 1)
        System.out.println("\nD(12) = " + divisorSet(12));
        System.out.println("D(6)  = " + divisorSet(6));
        System.out.println("6 | 12? " + (12 % 6 == 0));
        System.out.println("D(6) ⊆ D(12)? " + verifyDivisorSubset(6, 12));
    }
}

Historical Context

Georg Cantor (1845–1918) created set theory in the 1870s–1880s, defining a set as "a gathering together into a whole of definite, distinct objects of our perception or thought." His work on infinite sets (countable vs. uncountable) sparked a revolution in mathematics.

Ernst Zermelo and Abraham Fraenkel formalized set theory axiomatically (ZF/ZFC) in the early 20th century, addressing paradoxes like Russell's paradox ($\{x \mid x \notin x\}$).

In computer science, sets appear everywhere: hash sets, tree sets, bit vectors. Java's Set<T> interface directly mirrors the mathematical concept: contains() for $\in$, addAll() for $\cup$, retainAll() for $\cap$.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. Let $A = \{1, 2, 3\}$, $B = \{2, 3, 4\}$. Is $A \subseteq B$? Is $B \subseteq A$? Is $A = B$?

A2. How many subsets does $\{a, b, c\}$ have? List them all.

A3. True or false: $\emptyset \in \{1, 2, 3\}$. True or false: $\emptyset \subseteq \{1, 2, 3\}$.

A4. If $|A| = 5$ and $A \subseteq B$, what is the minimum possible value of $|B|$?

Slide Set B: Proof Problems

B1. Prove: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$ (transitivity of subset).

B2. Prove: $A \cap B \subseteq A$ for any sets $A$ and $B$.

B3. Prove or disprove: If $A \subseteq B$ and $A \subseteq C$, then $A \subseteq B \cap C$.

Slide Set C: Java Coding Problems

C1. Write a method <T> Set<T> symmetricDifference(Set<T> a, Set<T> b) that returns elements in exactly one of the two sets.

C2. Write a method that takes a List<Integer> and returns a Set<Integer> of duplicates.

C3. Implement divisorSet(int n) and verify that D(6) ⊆ D(12).

Full Problem Set

Discrete Math Problems

DM1. Let $A = \{1, 2, 3, 4, 5\}$, $B = \{3, 4, 5, 6, 7\}$. Compute $A \cap B$, $A \cup B$, $A \setminus B$, $B \setminus A$.

DM2. Prove by element-chasing: $A \cap (B \cup C) \supseteq (A \cap B) \cup (A \cap C)$.

DM3. Prove that $A \subseteq B$ if and only if $A \cap B = A$.

DM4. Let $E = \{n \in \mathbb{Z} \mid n \text{ is even}\}$ and $O = \{n \in \mathbb{Z} \mid n \text{ is odd}\}$. Prove $E \cap O = \emptyset$ and $E \cup O = \mathbb{Z}$.

DM5. Prove that $|\mathcal{P}(\emptyset)| = 1$ and identify the single element of $\mathcal{P}(\emptyset)$.

DM6. Prove: $A \setminus B = A \cap \overline{B}$ (where $\overline{B}$ is the complement of $B$ relative to a universal set $U$).

Java Programming Problems

JP1. Write a method boolean isSubset(Set<Integer> a, Set<Integer> b) and test with at least 5 pairs of sets.

JP2. Implement set-builder notation: Set<Integer> setBuilder(int low, int high, Predicate<Integer> p) returning all integers in $[\text{low}, \text{high}]$ satisfying $p$. Use it to build the set of primes less than 100.

JP3. Write a method that, given two sets $A$ and $B$, verifies the identity $|A \cup B| = |A| + |B| - |A \cap B|$ by computing both sides.

JP4. Implement divisorSet(int n) and write tests verifying: if $a | b$ then $D(a) \subseteq D(b)$. Test for $a = 6, b = 30$ and $a = 4, b = 12$.

JP5. Write a method that partitions a set of integers into two subsets: primes and composites (connecting to Module 1).

Bridge Problems

BR1. Prove mathematically that for positive integers $a$ and $b$, $D(\gcd(a,b)) = D(a) \cap D(b)$. Then write Java code to verify this for all pairs $(a,b)$ with $1 \leq a, b \leq 50$.

BR2. Prove: the set of all linear combinations $\{ax + by \mid x, y \in \mathbb{Z}\}$ equals the set of all multiples of $\gcd(a,b)$. Write a Java method that generates both sets for $a, b \leq 20$ and verifies equality (for sufficiently many values).

Solutions

Discrete Math Solutions

DM1. $A \cap B = \{3, 4, 5\}$. $A \cup B = \{1, 2, 3, 4, 5, 6, 7\}$. $A \setminus B = \{1, 2\}$. $B \setminus A = \{6, 7\}$.

DM2. Let $x \in (A \cap B) \cup (A \cap C)$. Then $x \in A \cap B$ or $x \in A \cap C$.

• Case 1: $x \in A \cap B$. Then $x \in A$ and $x \in B$. Since $x \in B$, $x \in B \cup C$. So $x \in A \cap (B \cup C)$.
• Case 2: $x \in A \cap C$. Then $x \in A$ and $x \in C \subseteq B \cup C$. So $x \in A \cap (B \cup C)$.

In both cases, $x \in A \cap (B \cup C)$. $\blacksquare$

DM3. ($\Rightarrow$): Assume $A \subseteq B$. Let $x \in A \cap B$, then $x \in A$, so $A \cap B \subseteq A$. Now let $x \in A$. Since $A \subseteq B$, $x \in B$, so $x \in A \cap B$. Thus $A \subseteq A \cap B$. By double inclusion, $A \cap B = A$.

($\Leftarrow$): Assume $A \cap B = A$. Let $x \in A$. Then $x \in A \cap B$ (since $A = A \cap B$), so $x \in B$. Thus $A \subseteq B$. $\blacksquare$

DM4. ($E \cap O = \emptyset$): Suppose $n \in E \cap O$. Then $2 | n$ and $n = 2k+1$. So $2 | (2k+1)$, meaning $2k+1 = 2m$, giving $1 = 2(m-k)$. But $|2(m-k)| \geq 2$ or $= 0$, so no integer satisfies this. Contradiction.

($E \cup O = \mathbb{Z}$): For any $n \in \mathbb{Z}$, by the quotient-remainder theorem (Module 2), $n = 2q + r$ where $r \in \{0, 1\}$. If $r = 0$, $n \in E$. If $r = 1$, $n \in O$. $\blacksquare$

DM5. $\mathcal{P}(\emptyset) = \{\emptyset\}$. It has exactly one element (the empty set itself is the only subset of the empty set). $|\mathcal{P}(\emptyset)| = 2^0 = 1$. $\blacksquare$

Java Solutions

JP2.

public static Set<Integer> setBuilder(int low, int high,
                                       Predicate<Integer> p) {
    Set<Integer> result = new TreeSet<>();
    for (int i = low; i <= high; i++) {
        if (p.test(i)) result.add(i);
    }
    return result;
}

// Primes less than 100
Set<Integer> primes = setBuilder(2, 99, n -> {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
});

BR1.

// Verify D(gcd(a,b)) = D(a) ∩ D(b)
for (int a = 1; a <= 50; a++) {
    for (int b = 1; b <= 50; b++) {
        int g = gcd(a, b);
        Set<Integer> dGcd = divisorSet(g);
        Set<Integer> inter = intersection(divisorSet(a), divisorSet(b));
        assert dGcd.equals(inter)
            : "Failed for a=" + a + ", b=" + b;
    }
}

Learning Objectives

• Compute union, intersection, difference, complement and Cartesian product.
• Prove the distributive laws using double inclusion and element-chasing.
• Translate set operations to Java's HashSet methods.
• Understand how set operations underlie database queries and search.
• Verify set identities programmatically.

Concept Overview

Set Operations

Core Identities

Commutative laws:

• $A \cup B = B \cup A$
• $A \cap B = B \cap A$

Associative laws:

• $(A \cup B) \cup C = A \cup (B \cup C)$
• $(A \cap B) \cap C = A \cap (B \cap C)$

Distributive laws:

• $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$
• $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

De Morgan's laws for sets:

• $\overline{A \cup B} = \overline{A} \cap \overline{B}$
• $\overline{A \cap B} = \overline{A} \cup \overline{B}$

Absorption laws:

• $A \cup (A \cap B) = A$
• $A \cap (A \cup B) = A$

Cartesian Product

$A \times B = \{(a, b) \mid a \in A, b \in B\}$

$|A \times B| = |A| \cdot |B|$

In Java, the Cartesian product corresponds to nested loops.

Why this matters in CS:

• Database joins are Cartesian products filtered by predicates.
• SQL UNION, INTERSECT, EXCEPT map directly to $\cup$, $\cap$, $\setminus$.
• Bitwise operations on bit masks implement set operations on sets of flags.

Formal Notation

Distributive law (first form):

Proof pattern: show $\text{LHS} \subseteq \text{RHS}$ and $\text{RHS} \subseteq \text{LHS}$.

Worked Examples

Example 1: Distributive Law — Full Proof

Claim: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

Proof.

($\subseteq$): Let $x \in A \cap (B \cup C)$. Then $x \in A$ and $x \in B \cup C$.

• Case 1: $x \in B$. Then $x \in A$ and $x \in B$, so $x \in A \cap B \subseteq (A \cap B) \cup (A \cap C)$.
• Case 2: $x \in C$. Then $x \in A$ and $x \in C$, so $x \in A \cap C \subseteq (A \cap B) \cup (A \cap C)$.

($\supseteq$): Let $x \in (A \cap B) \cup (A \cap C)$.

• Case 1: $x \in A \cap B$. Then $x \in A$ and $x \in B \subseteq B \cup C$. So $x \in A \cap (B \cup C)$.
• Case 2: $x \in A \cap C$. Then $x \in A$ and $x \in C \subseteq B \cup C$. So $x \in A \cap (B \cup C)$.

By double inclusion, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. $\blacksquare$

Example 2: De Morgan's Law for Sets

Claim: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ (relative to universe $U$).

Proof.

($\subseteq$): Let $x \in \overline{A \cup B}$. Then $x \notin A \cup B$, so $x \notin A$ and $x \notin B$. Thus $x \in \overline{A}$ and $x \in \overline{B}$, giving $x \in \overline{A} \cap \overline{B}$.

($\supseteq$): Let $x \in \overline{A} \cap \overline{B}$. Then $x \notin A$ and $x \notin B$. So $x \notin A \cup B$, giving $x \in \overline{A \cup B}$. $\blacksquare$

Example 3: Set Difference Identity

Claim: $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$.

Proof.

($\subseteq$): Let $x \in A \setminus (B \cup C)$. Then $x \in A$ and $x \notin B \cup C$. So $x \notin B$ and $x \notin C$. Thus $x \in A \setminus B$ and $x \in A \setminus C$, giving $x \in (A \setminus B) \cap (A \setminus C)$.

($\supseteq$): Let $x \in (A \setminus B) \cap (A \setminus C)$. Then $x \in A$, $x \notin B$, $x \notin C$. So $x \notin B \cup C$, giving $x \in A \setminus (B \cup C)$. $\blacksquare$

Example 4: Cartesian Product

Problem: Let $A = \{1, 2\}$, $B = \{a, b, c\}$. Compute $A \times B$ and $|A \times B|$.

$A \times B = \{(1,a), (1,b), (1,c), (2,a), (2,b), (2,c)\}$

$|A \times B| = 2 \cdot 3 = 6$

Example 5: Connecting Set Operations to Logic

De Morgan's laws for sets follow from De Morgan's laws for logic (Module 3)!

Proof Techniques Spotlight

Double Inclusion with Case Analysis

Many set identity proofs require splitting into cases based on which sets an element belongs to. The pattern:

1. Goal: Prove $X = Y$.
2. ($\subseteq$): Take $x \in X$. Analyze cases from the definition of $X$.
3. ($\supseteq$): Take $x \in Y$. Analyze cases from the definition of $Y$.

Tip: If a definition involves "or" (union), split into cases. If it involves "and" (intersection), use both facts together.

Java Deep Dive

import java.util.*;
import java.util.stream.*;

public class SetOperationsLibrary {

    // --- Core Operations (non-mutating) ---

    public static <T> Set<T> union(Set<T> a, Set<T> b) {
        Set<T> result = new HashSet<>(a);
        result.addAll(b);
        return result;
    }

    public static <T> Set<T> intersection(Set<T> a, Set<T> b) {
        Set<T> result = new HashSet<>(a);
        result.retainAll(b);
        return result;
    }

    public static <T> Set<T> difference(Set<T> a, Set<T> b) {
        Set<T> result = new HashSet<>(a);
        result.removeAll(b);
        return result;
    }

    public static <T> Set<T> complement(Set<T> a, Set<T> universe) {
        return difference(universe, a);
    }

    public static <T> Set<T> symmetricDifference(Set<T> a, Set<T> b) {
        return union(difference(a, b), difference(b, a));
    }

    /**
     * Cartesian product A × B.
     * Each pair is represented as a two-element list [a, b].
     */
    public static <S, T> Set<List<Object>> cartesianProduct(Set<S> a, Set<T> b) {
        Set<List<Object>> result = new HashSet<>();
        for (S x : a) {
            for (T y : b) {
                result.add(Arrays.asList(x, y));
            }
        }
        return result;
    }

    // --- Identity Verification ---

    /**
     * Verify distributive law: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
     */
    public static <T> boolean verifyDistributive(Set<T> a, Set<T> b, Set<T> c) {
        Set<T> lhs = intersection(a, union(b, c));
        Set<T> rhs = union(intersection(a, b), intersection(a, c));
        return lhs.equals(rhs);
    }

    /**
     * Verify De Morgan: complement(A ∪ B) = complement(A) ∩ complement(B)
     */
    public static <T> boolean verifyDeMorgan(Set<T> a, Set<T> b, Set<T> universe) {
        Set<T> lhs = complement(union(a, b), universe);
        Set<T> rhs = intersection(complement(a, universe), complement(b, universe));
        return lhs.equals(rhs);
    }

    /**
     * Verify: A \ (B ∪ C) = (A \ B) ∩ (A \ C)
     */
    public static <T> boolean verifyDiffDistributive(Set<T> a, Set<T> b, Set<T> c) {
        Set<T> lhs = difference(a, union(b, c));
        Set<T> rhs = intersection(difference(a, b), difference(a, c));
        return lhs.equals(rhs);
    }

    /**
     * Verify inclusion-exclusion: |A ∪ B| = |A| + |B| - |A ∩ B|
     */
    public static <T> boolean verifyInclusionExclusion(Set<T> a, Set<T> b) {
        int lhs = union(a, b).size();
        int rhs = a.size() + b.size() - intersection(a, b).size();
        return lhs == rhs;
    }

    // --- Demonstration ---

    public static void main(String[] args) {
        System.out.println("=== Set Operations Library ===\n");

        Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
        Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5, 6, 7));
        Set<Integer> c = new HashSet<>(Arrays.asList(5, 6, 7, 8, 9));
        Set<Integer> u = IntStream.rangeClosed(1, 10).boxed()
                .collect(Collectors.toSet());

        System.out.println("A = " + new TreeSet<>(a));
        System.out.println("B = " + new TreeSet<>(b));
        System.out.println("C = " + new TreeSet<>(c));
        System.out.println("U = " + new TreeSet<>(u));

        // Operations
        System.out.println("\nA ∪ B = " + new TreeSet<>(union(a, b)));
        System.out.println("A ∩ B = " + new TreeSet<>(intersection(a, b)));
        System.out.println("A \\ B = " + new TreeSet<>(difference(a, b)));
        System.out.println("A △ B = " + new TreeSet<>(symmetricDifference(a, b)));
        System.out.println("complement(A) = " + new TreeSet<>(complement(a, u)));

        // Verify identities
        System.out.println("\n--- Identity Verification ---");
        System.out.println("Distributive: " + verifyDistributive(a, b, c));
        System.out.println("De Morgan: " + verifyDeMorgan(a, b, u));
        System.out.println("Diff Distributive: " + verifyDiffDistributive(a, b, c));
        System.out.println("Inclusion-Exclusion: " + verifyInclusionExclusion(a, b));

        // Cartesian product
        Set<String> colors = new HashSet<>(Arrays.asList("R", "G", "B"));
        Set<Integer> sizes = new HashSet<>(Arrays.asList(1, 2));
        System.out.println("\nColors × Sizes = " + cartesianProduct(colors, sizes));
        System.out.println("|Colors × Sizes| = " + cartesianProduct(colors, sizes).size()
                + " (expected " + (colors.size() * sizes.size()) + ")");
    }
}

Historical Context

George Boole (1815–1864) developed Boolean algebra, which treats logical operations as algebraic operations on truth values. The deep parallel between set algebra and Boolean algebra was recognized by Boole himself and later by Augustus De Morgan.

De Morgan's laws were originally stated for propositions (Module 3, Class 1), but they translate directly to sets:

• Logic: $\neg(P \wedge Q) \equiv \neg P \vee \neg Q$
• Sets: $\overline{A \cap B} = \overline{A} \cup \overline{B}$

This parallel is not a coincidence — both propositional logic and set algebra are instances of Boolean algebra, an algebraic structure with two binary operations satisfying the same axioms.

SQL (1970s) adopted set semantics from relational algebra, which Edgar Codd based directly on set theory and first-order logic.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. Let $A = \{1,2,3\}$, $B = \{2,3,4\}$, $C = \{3,4,5\}$. Compute $A \cap (B \cup C)$ and $(A \cap B) \cup (A \cap C)$. Are they equal?

A2. Compute $|A \times B|$ where $A = \{x, y\}$ and $B = \{1, 2, 3, 4\}$.

A3. If $U = \{1,\ldots,10\}$ and $A = \{2,4,6,8,10\}$, what is $\overline{A}$?

Slide Set B: Proof Problems

B1. Prove: $A \cup (A \cap B) = A$ (absorption law).

B2. Prove: $A \triangle B = B \triangle A$ (symmetric difference is commutative).

B3. Prove: $A \setminus B = A \cap \overline{B}$.

Slide Set C: Java Coding Problems

C1. Write a method verifying the second distributive law: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.

C2. Generate all elements of $\{0,1\} \times \{0,1\} \times \{0,1\}$ (all 3-bit strings).

C3. Write a program that generates random sets $A, B, C \subseteq \{1,\ldots,20\}$ and verifies both distributive laws.

Full Problem Set

Discrete Math Problems

DM1. Prove the second distributive law: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.

DM2. Prove both De Morgan's laws for sets using element-chasing.

DM3. Prove: $A \triangle B = (A \cup B) \setminus (A \cap B)$.

DM4. Prove: $|A \times B| = |A| \cdot |B|$ for finite sets.

DM5. Prove: $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$.

DM6. For sets $A$, $B$, $C$, prove or disprove: $A \times (B \cup C) = (A \times B) \cup (A \times C)$.

Java Programming Problems

JP1. Implement all six set operations (union, intersection, difference, complement, symmetricDifference, cartesianProduct) with non-mutating methods and test each.

JP2. Write a method that takes three sets and verifies all identities listed in the concept overview (commutative, associative, distributive, De Morgan, absorption).

JP3. Implement a BitSetOps class that represents sets as BitSet objects and implements union (OR), intersection (AND), complement (FLIP), and difference. Compare performance with HashSet for sets $\subseteq \{0, \ldots, 999\}$.

JP4. Write a method Set<List<Integer>> cartesianPower(Set<Integer> s, int n) that computes $S^n = S \times S \times \cdots \times S$ ($n$ times). Use it to enumerate all $n$-digit strings from a given alphabet.

JP5. Model a simple database query: given a List<Map<String, Object>> (list of records), implement SELECT ... WHERE as set filtering, UNION and INTERSECT using set operations.

Bridge Problems

BR1. Using Module 1's divisibility and Module 4's set theory, prove: $D(\text{lcm}(a,b)) = D(a) \cup D(b)$ (where $D(n)$ is the divisor set). Verify in Java for $1 \leq a, b \leq 30$.

BR2. Prove that De Morgan's laws for sets are equivalent to De Morgan's laws for propositional logic (Module 3). Write a Java program that demonstrates this equivalence by evaluating both the set version and the logical version on corresponding inputs.

Solutions

Discrete Math Solutions

DM1. $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

($\subseteq$): Let $x \in A \cup (B \cap C)$.

• Case 1: $x \in A$. Then $x \in A \cup B$ and $x \in A \cup C$, so $x \in (A \cup B) \cap (A \cup C)$.
• Case 2: $x \in B \cap C$. Then $x \in B$ and $x \in C$. So $x \in A \cup B$ and $x \in A \cup C$, giving $x \in (A \cup B) \cap (A \cup C)$.

($\supseteq$): Let $x \in (A \cup B) \cap (A \cup C)$. Then $x \in A \cup B$ and $x \in A \cup C$.

• If $x \in A$: then $x \in A \cup (B \cap C)$. ✓
• If $x \notin A$: from $x \in A \cup B$, $x \in B$; from $x \in A \cup C$, $x \in C$. So $x \in B \cap C$, giving $x \in A \cup (B \cap C)$. ✓

$\blacksquare$

DM3. $A \triangle B = (A \cup B) \setminus (A \cap B)$

($\subseteq$): Let $x \in A \triangle B = (A \setminus B) \cup (B \setminus A)$.

• Case 1: $x \in A \setminus B$. Then $x \in A$ (so $x \in A \cup B$) and $x \notin B$. Since $x \notin B$, $x \notin A \cap B$. So $x \in (A \cup B) \setminus (A \cap B)$.
• Case 2: $x \in B \setminus A$. Symmetric argument.

($\supseteq$): Let $x \in (A \cup B) \setminus (A \cap B)$. Then $x \in A \cup B$ and $x \notin A \cap B$.

• Since $x \in A \cup B$: $x \in A$ or $x \in B$.
• Since $x \notin A \cap B$: not ($x \in A$ and $x \in B$).
• If $x \in A$: then $x \notin B$ (otherwise $x \in A \cap B$). So $x \in A \setminus B$.
• If $x \in B$: then $x \notin A$. So $x \in B \setminus A$.

Either way, $x \in A \triangle B$. $\blacksquare$

DM6. True. $A \times (B \cup C) = (A \times B) \cup (A \times C)$.

($\subseteq$): Let $(a, x) \in A \times (B \cup C)$. Then $a \in A$ and $x \in B \cup C$.

• If $x \in B$: $(a, x) \in A \times B \subseteq (A \times B) \cup (A \times C)$.
• If $x \in C$: $(a, x) \in A \times C \subseteq (A \times B) \cup (A \times C)$.

($\supseteq$): Let $(a, x) \in (A \times B) \cup (A \times C)$.

• If $(a, x) \in A \times B$: $a \in A$, $x \in B \subseteq B \cup C$, so $(a, x) \in A \times (B \cup C)$.
• If $(a, x) \in A \times C$: similarly. $\blacksquare$

Java Solutions

JP3. (BitSet implementation)

public class BitSetOps {
    private BitSet bits;
    private int universeSize;

    public BitSetOps(int universeSize) {
        this.bits = new BitSet(universeSize);
        this.universeSize = universeSize;
    }

    public BitSetOps union(BitSetOps other) {
        BitSetOps result = copy();
        result.bits.or(other.bits);
        return result;
    }

    public BitSetOps intersection(BitSetOps other) {
        BitSetOps result = copy();
        result.bits.and(other.bits);
        return result;
    }

    public BitSetOps complement() {
        BitSetOps result = copy();
        result.bits.flip(0, universeSize);
        return result;
    }

    public BitSetOps difference(BitSetOps other) {
        BitSetOps result = copy();
        result.bits.andNot(other.bits);
        return result;
    }

    private BitSetOps copy() {
        BitSetOps c = new BitSetOps(universeSize);
        c.bits = (BitSet) this.bits.clone();
        return c;
    }
}

BR1.

for (int a = 1; a <= 30; a++) {
    for (int b = 1; b <= 30; b++) {
        int lcm = a * b / gcd(a, b);
        Set<Integer> dLcm = divisorSet(lcm);
        Set<Integer> dUnion = union(divisorSet(a), divisorSet(b));
        assert dLcm.equals(dUnion)
            : "Failed for a=" + a + ", b=" + b;
    }
}

Learning Objectives

• Define and compute power sets, proving $|\mathcal{P}(A)| = 2^{|A|}$.
• Represent indexed families of sets and compute their unions and intersections.
• Define partitions and connect them to equivalence classes (Module 5 preview).
• Implement power set generation using recursion and bit masks in Java.
• Apply subset enumeration and partitioning to algorithmic problems.

Concept Overview

Power Sets

The power set of $A$, written $\mathcal{P}(A)$, is the set of all subsets of $A$.

Example: $\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$

Theorem: If $|A| = n$, then $|\mathcal{P}(A)| = 2^n$.

Proof by induction on $n$:

• Base: $n = 0$. $A = \emptyset$, $\mathcal{P}(\emptyset) = \{\emptyset\}$. $|\mathcal{P}(\emptyset)| = 1 = 2^0$. ✓
• Inductive step: Assume $|\mathcal{P}(S)| = 2^k$ for any set $S$ with $|S| = k$. Let $|A| = k + 1$ and pick $a \in A$. Let $A' = A \setminus \{a\}$, so $|A'| = k$. Every subset of $A$ either contains $a$ or doesn't:
• Subsets not containing $a$: subsets of $A'$, of which there are $2^k$.
• Subsets containing $a$: each is $S \cup \{a\}$ for some $S \subseteq A'$, so there are $2^k$.
• Total: $2^k + 2^k = 2^{k+1}$. $\blacksquare$

Indexed Families of Sets

An indexed family $\{A_i\}_{i \in I}$ assigns a set $A_i$ to each index $i$ in an index set $I$.

In Java: Map<K, Set<V>> represents an indexed family.

Partitions

A partition of set $A$ is a collection of non-empty subsets $\{A_1, A_2, \ldots, A_k\}$ such that:

1. Pairwise disjoint: $A_i \cap A_j = \emptyset$ for $i \neq j$.
2. Cover $A$: $A_1 \cup A_2 \cup \cdots \cup A_k = A$.

Examples:

• $\{E, O\}$ where $E$ = even integers and $O$ = odd integers is a partition of $\mathbb{Z}$.
• Congruence classes modulo $m$ partition $\mathbb{Z}$ into $m$ classes (connects to Module 2).

Key connection: Every equivalence relation on $A$ induces a partition of $A$ into equivalence classes, and every partition determines an equivalence relation. (Module 5 will formalize this.)

Why this matters in CS:

• Subset enumeration (power sets) appears in backtracking, SAT solvers, and combinatorial optimization.
• Partitions model equivalence classes, graph components, union-find structures.
• Indexed families represent grouping operations (SQL GROUP BY, Map-Reduce).

Formal Notation

Worked Examples

Example 1: Power Set Computation

Problem: Compute $\mathcal{P}(\{a, b, c\})$.

Solution:

$|\mathcal{P}(\{a,b,c\})| = 2^3 = 8$. ✓

Example 2: Power Set via Bit Masks

Each subset of $\{a_0, a_1, \ldots, a_{n-1}\}$ corresponds to an $n$-bit integer where bit $i$ indicates whether $a_i$ is included.

For $\{a, b, c\}$:

Example 3: Indexed Family

Problem: Let $A_i = \{i, i+1, i+2\}$ for $i \in \{1, 2, 3\}$. Compute $\bigcup_{i=1}^{3} A_i$ and $\bigcap_{i=1}^{3} A_i$.

$A_1 = \{1, 2, 3\}$, $A_2 = \{2, 3, 4\}$, $A_3 = \{3, 4, 5\}$.

$\bigcup = \{1, 2, 3, 4, 5\}$. $\bigcap = \{3\}$.

Example 4: Partition by Congruence Classes

Problem: Partition $\{0, 1, 2, \ldots, 11\}$ by congruence modulo 3.

$[0]_3 = \{0, 3, 6, 9\}$, $[1]_3 = \{1, 4, 7, 10\}$, $[2]_3 = \{2, 5, 8, 11\}$.

Verification: pairwise disjoint (no overlaps) and union = $\{0, \ldots, 11\}$. ✓

This directly connects to Module 2's congruence classes!

Example 5: Partition into Primes and Composites

Partition $\{2, 3, \ldots, 20\}$ into primes and composites:

• Primes: $\{2, 3, 5, 7, 11, 13, 17, 19\}$
• Composites: $\{4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20\}$

Disjoint? Yes (no number is both prime and composite). Cover? Yes ($|\text{Primes}| + |\text{Composites}| = 8 + 11 = 19 = |\{2, \ldots, 20\}|$). ✓

Proof Techniques Spotlight

Counting via Bijections

To prove $|\mathcal{P}(A)| = 2^n$, we established a bijection between subsets of $A$ and $n$-bit strings. In general:

If there is a bijection $f : X \rightarrow Y$ between finite sets, then $|X| = |Y|$.

This is a powerful counting technique that we'll use more in Module 7.

Partition Arguments

To prove a collection $\{A_1, \ldots, A_k\}$ is a partition:

1. Show each $A_i \neq \emptyset$.
2. Show $A_i \cap A_j = \emptyset$ for $i \neq j$ (often by assuming $x \in A_i \cap A_j$ and deriving $i = j$).
3. Show $\bigcup A_i = A$.

Java Deep Dive

import java.util.*;
import java.util.stream.*;

public class PowerSetLibrary {

    // --- Power Set Generation ---

    /**
     * Generate the power set using bit masks.
     * Time: O(n · 2^n), Space: O(n · 2^n).
     * Each integer from 0 to 2^n - 1 represents one subset.
     */
    public static <T> Set<Set<T>> powerSetBitMask(List<T> elements) {
        int n = elements.size();
        Set<Set<T>> result = new HashSet<>();

        for (int mask = 0; mask < (1 << n); mask++) {
            Set<T> subset = new HashSet<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(elements.get(i));
                }
            }
            result.add(subset);
        }
        return result;
    }

    /**
     * Generate the power set recursively.
     * Base: P({}) = {{}}
     * Step: For element a, P(A) = P(A\{a}) ∪ { S ∪ {a} | S ∈ P(A\{a}) }
     */
    public static <T> Set<Set<T>> powerSetRecursive(List<T> elements) {
        Set<Set<T>> result = new HashSet<>();
        if (elements.isEmpty()) {
            result.add(new HashSet<>());  // { {} }
            return result;
        }

        T first = elements.get(0);
        List<T> rest = elements.subList(1, elements.size());
        Set<Set<T>> subsetsOfRest = powerSetRecursive(rest);

        for (Set<T> subset : subsetsOfRest) {
            result.add(new HashSet<>(subset));          // without first
            Set<T> withFirst = new HashSet<>(subset);
            withFirst.add(first);                        // with first
            result.add(withFirst);
        }
        return result;
    }

    // --- Indexed Families ---

    /**
     * Compute the union of all sets in a family.
     * ⋃_{i ∈ I} A_i
     */
    public static <K, V> Set<V> familyUnion(Map<K, Set<V>> family) {
        Set<V> result = new HashSet<>();
        for (Set<V> set : family.values()) {
            result.addAll(set);
        }
        return result;
    }

    /**
     * Compute the intersection of all sets in a family.
     * ⋂_{i ∈ I} A_i
     */
    public static <K, V> Set<V> familyIntersection(Map<K, Set<V>> family) {
        Iterator<Set<V>> iter = family.values().iterator();
        if (!iter.hasNext()) return new HashSet<>();
        Set<V> result = new HashSet<>(iter.next());
        while (iter.hasNext()) {
            result.retainAll(iter.next());
        }
        return result;
    }

    // --- Partitions ---

    /**
     * Partition a set of integers by their remainder modulo m.
     * Returns congruence classes [0]_m, [1]_m, ..., [m-1]_m.
     * Connects to Module 2.
     */
    public static Map<Integer, Set<Integer>> partitionByMod(Set<Integer> s, int m) {
        Map<Integer, Set<Integer>> partition = new TreeMap<>();
        for (int i = 0; i < m; i++) {
            partition.put(i, new TreeSet<>());
        }
        for (int x : s) {
            int cls = Math.floorMod(x, m);
            partition.get(cls).add(x);
        }
        // Remove empty classes (they might not appear in s)
        partition.entrySet().removeIf(e -> e.getValue().isEmpty());
        return partition;
    }

    /**
     * Partition by predicate: elements satisfying p go to "true",
     * others go to "false".
     */
    public static <T> Map<Boolean, Set<T>> partitionByPredicate(
            Set<T> s, java.util.function.Predicate<T> p) {
        Map<Boolean, Set<T>> result = new HashMap<>();
        result.put(true, new HashSet<>());
        result.put(false, new HashSet<>());
        for (T x : s) {
            result.get(p.test(x)).add(x);
        }
        return result;
    }

    /**
     * Verify that a collection of sets forms a valid partition.
     */
    public static <T> boolean isPartition(Set<T> whole, Collection<Set<T>> parts) {
        // Check pairwise disjoint
        List<Set<T>> list = new ArrayList<>(parts);
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).isEmpty()) return false;
            for (int j = i + 1; j < list.size(); j++) {
                Set<T> inter = new HashSet<>(list.get(i));
                inter.retainAll(list.get(j));
                if (!inter.isEmpty()) return false;
            }
        }
        // Check cover
        Set<T> union = new HashSet<>();
        for (Set<T> part : parts) union.addAll(part);
        return union.equals(whole);
    }

    // --- Demonstration ---

    public static void main(String[] args) {
        System.out.println("=== Power Set Library ===\n");

        // Power set
        List<Integer> elems = Arrays.asList(1, 2, 3);
        Set<Set<Integer>> ps = powerSetBitMask(elems);
        System.out.println("P({1,2,3}) has " + ps.size() + " subsets:");
        for (Set<Integer> s : ps) {
            System.out.println("  " + s);
        }

        // Verify: recursive matches bit-mask
        Set<Set<Integer>> psRec = powerSetRecursive(elems);
        System.out.println("\nRecursive method matches bit-mask? " + ps.equals(psRec));

        // Indexed family
        Map<Integer, Set<Integer>> family = new TreeMap<>();
        for (int i = 1; i <= 3; i++) {
            Set<Integer> ai = new TreeSet<>();
            for (int j = i; j <= i + 2; j++) ai.add(j);
            family.put(i, ai);
        }
        System.out.println("\nIndexed family: " + family);
        System.out.println("Union: " + familyUnion(family));
        System.out.println("Intersection: " + familyIntersection(family));

        // Partition by mod
        Set<Integer> nums = IntStream.rangeClosed(0, 11).boxed()
                .collect(Collectors.toSet());
        Map<Integer, Set<Integer>> modPart = partitionByMod(nums, 3);
        System.out.println("\nPartition of {0..11} by mod 3: " + modPart);
        System.out.println("Valid partition? " +
                isPartition(nums, modPart.values()));

        // Partition: primes vs composites
        Set<Integer> range = IntStream.rangeClosed(2, 20).boxed()
                .collect(Collectors.toSet());
        Map<Boolean, Set<Integer>> primePartition = partitionByPredicate(
                range, n -> isPrime(n));
        System.out.println("\nPrimes: " + new TreeSet<>(primePartition.get(true)));
        System.out.println("Composites: " + new TreeSet<>(primePartition.get(false)));
        System.out.println("Valid partition? " +
                isPartition(range, primePartition.values()));
    }

    static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i * i <= n; i++)
            if (n % i == 0) return false;
        return true;
    }
}

Historical Context

Cantor's Power Set Theorem (1891) proved that for any set $A$, there is no surjection from $A$ onto $\mathcal{P}(A)$. For finite sets, this simply says $2^n > n$. For infinite sets, it implies there are different "sizes" of infinity — the power set of the natural numbers is uncountably infinite (the same size as the real numbers).

The concept of partitions links to equivalence classes, formalized by mathematicians in the early 20th century. In CS, the Union-Find data structure (Tarjan, 1975) efficiently maintains partitions with near-constant-time operations.

Power set enumeration ($2^n$ subsets) is the basis of exponential-time algorithms in complexity theory, including brute-force solutions to NP-complete problems like the subset sum problem.

Slide-Ready Problem Sets

Slide Set A: Conceptual Questions

A1. How many elements does $\mathcal{P}(\{1,2,3,4,5\})$ have?

A2. Is $\{1\} \in \mathcal{P}(\{1,2,3\})$? Is $1 \in \mathcal{P}(\{1,2,3\})$?

A3. Name three ways to partition $\{1,2,3,4,5,6\}$ into exactly two non-empty parts.

Slide Set B: Proof Problems

B1. Prove by induction: $|\mathcal{P}(A)| = 2^{|A|}$ for finite sets.

B2. Prove: congruence classes modulo $m$ form a partition of $\mathbb{Z}$.

B3. Prove: if $\{A_1, \ldots, A_k\}$ is a partition of $A$, then $\sum_{i=1}^{k} |A_i| = |A|$.

Slide Set C: Java Coding Problems

C1. Generate the power set of $\{1,2,3,4\}$ and count subsets of each size. Verify: $\sum_{k=0}^{4} \binom{4}{k} = 16$.

C2. Partition a list of strings by their first letter.

C3. Implement isPartition and test with valid and invalid partitions.

Full Problem Set

Discrete Math Problems

DM1. List all elements of $\mathcal{P}(\{a, b, c, d\})$. How many subsets of size 2 are there?

DM2. Prove by induction: $|\mathcal{P}(A)| = 2^{|A|}$.

DM3. Prove: If $A \subseteq B$, then $\mathcal{P}(A) \subseteq \mathcal{P}(B)$.

DM4. Prove that the congruence classes $[0]_m, [1]_m, \ldots, [m-1]_m$ form a partition of $\mathbb{Z}$.

DM5. Let $f: A \rightarrow B$ be a function. Define $A_b = \{a \in A \mid f(a) = b\}$ for each $b \in B$. Prove that $\{A_b \mid b \in B, A_b \neq \emptyset\}$ is a partition of $A$. (Preview of Module 5.)

DM6. Prove: $\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)$.

DM7. Prove or disprove: $\mathcal{P}(A \cup B) = \mathcal{P}(A) \cup \mathcal{P}(B)$.

Java Programming Problems

JP1. Implement power set generation using both bit masks and recursion. Verify both produce the same result for sets of sizes 0 through 6.

JP2. Write a method List<Set<Integer>> subsetsOfSize(List<Integer> elements, int k) that returns all $k$-element subsets. Verify that the count matches $\binom{n}{k}$.

JP3. Implement Map<Integer, Set<Integer>> partitionByMod(Set<Integer> s, int m) and verify using isPartition.

JP4. Write a subset sum solver: given a set $S$ of integers and a target $t$, enumerate all subsets of $S$ whose sum equals $t$. Use power set generation.

JP5. Implement a general groupBy method: <T, K> Map<K, Set<T>> groupBy(Set<T> s, Function<T, K> classifier) that partitions $s$ by the classifier function.

Bridge Problems

BR1. Implement the subset sum solver from JP4. For a set $S$ with $|S| = n$, the solver checks $2^n$ subsets. Measure the runtime for $n = 10, 15, 20, 25$ and plot the growth. Explain why this is exponential and relate to $|\mathcal{P}(S)| = 2^n$.

BR2. Recall from Module 2 that congruence modulo $m$ is an equivalence relation. Implement a method that takes a set of integers and a modulus $m$, partitions the set by congruence classes, and then verifies: (a) each class is non-empty, (b) classes are pairwise disjoint, (c) their union equals the original set, (d) all elements in a class have the same remainder mod $m$.

Solutions

Discrete Math Solutions

DM2. See proof in Concept Overview above. $\blacksquare$

DM3. Assume $A \subseteq B$. Let $S \in \mathcal{P}(A)$, so $S \subseteq A$. Since $A \subseteq B$, by transitivity of $\subseteq$, $S \subseteq B$, so $S \in \mathcal{P}(B)$. $\blacksquare$

DM4. Let $a, b \in \mathbb{Z}$. If $a \in [i]_m \cap [j]_m$, then $a \equiv i \pmod{m}$ and $a \equiv j \pmod{m}$, so $i \equiv j \pmod{m}$. Since $0 \leq i, j < m$, this means $i = j$. So classes are pairwise disjoint. Every $a \in \mathbb{Z}$ satisfies $a \equiv r \pmod{m}$ for some $r \in \{0, \ldots, m-1\}$ (by quotient-remainder, Module 2), so $a \in [r]_m$. Thus the classes cover $\mathbb{Z}$. $\blacksquare$

DM6. ($\subseteq$): Let $S \in \mathcal{P}(A \cap B)$. Then $S \subseteq A \cap B$, so $S \subseteq A$ and $S \subseteq B$, giving $S \in \mathcal{P}(A)$ and $S \in \mathcal{P}(B)$, i.e., $S \in \mathcal{P}(A) \cap \mathcal{P}(B)$.

($\supseteq$): Let $S \in \mathcal{P}(A) \cap \mathcal{P}(B)$. Then $S \subseteq A$ and $S \subseteq B$, so $S \subseteq A \cap B$, giving $S \in \mathcal{P}(A \cap B)$. $\blacksquare$

DM7. False. Counterexample: $A = \{1\}$, $B = \{2\}$. Then $\{1, 2\} \in \mathcal{P}(A \cup B)$ but $\{1, 2\} \notin \mathcal{P}(A) = \{\emptyset, \{1\}\}$ and $\{1, 2\} \notin \mathcal{P}(B) = \{\emptyset, \{2\}\}$. So $\{1, 2\} \notin \mathcal{P}(A) \cup \mathcal{P}(B)$. $\blacksquare$

Java Solutions

JP2.

public static List<Set<Integer>> subsetsOfSize(List<Integer> elements, int k) {
    List<Set<Integer>> result = new ArrayList<>();
    generateSubsets(elements, k, 0, new HashSet<>(), result);
    return result;
}

private static void generateSubsets(List<Integer> elements, int k,
        int start, Set<Integer> current, List<Set<Integer>> result) {
    if (current.size() == k) {
        result.add(new HashSet<>(current));
        return;
    }
    if (start >= elements.size()) return;
    // Include elements[start]
    current.add(elements.get(start));
    generateSubsets(elements, k, start + 1, current, result);
    current.remove(elements.get(start));
    // Exclude elements[start]
    generateSubsets(elements, k, start + 1, current, result);
}

JP4.

public static List<Set<Integer>> subsetSum(List<Integer> elements, int target) {
    List<Set<Integer>> solutions = new ArrayList<>();
    int n = elements.size();
    for (int mask = 0; mask < (1 << n); mask++) {
        Set<Integer> subset = new HashSet<>();
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) {
                subset.add(elements.get(i));
                sum += elements.get(i);
            }
        }
        if (sum == target) solutions.add(subset);
    }
    return solutions;
}