Set Operations and Identities

Set theory serves as the foundational language of modern mathematics and computer science, offering a rigorous framework to group, manipulate, and reason about collections of objects. This guide explores fundamental set operations, structural identities, algebraic proof methodologies, and the computational mechanics of set representations.

1. Set Specifications and Foundations

A set is an unordered collection of distinct objects, referred to as elements or members. When an element $a$ belongs to a set $S$ , we write $a \in S$ ; conversely, if $a$ is not a member of $S$ , we write $a \notin S$ .

Specifying Sets

Sets can be defined through several standard notations:

Roster Notation: Listing all elements explicitly within curly braces, e.g., $A = \{1, 2, 3, 4, 5\}$ .
Ellipsis Notation: Using ellipsis for large or infinite collections when the pattern is unambiguous, e.g., $B = \{0, 2, 4, 6, \dots\}$ .

The Principle of Specification

The connection between a logical predicate $P(x)$ and the set it defines is formalized by the Principle of Specification. It states that any predicate $P(x)$ specifies a subset $A$ of a pre-defined universal set $\mathbf{U}$ : $A = \{x \in \mathbf{U} \mid P(x)\}$ Here, is called the of the predicate . Logical relationships map directly to set relationships:

If $P(x) \iff Q(x)$ , then their extensions are equal ( $A = B$ ).
If $P(x) \implies Q(x)$ , then is a subset of ().

Set Inclusion and Power Sets

Subset ( $\subseteq$ ): A set $A$ is a subset of $B$ if every element of $A$ is also an element of $B$ : $A \subseteq B \iff \forall x (x \in A \implies x \in B)$

2. Fundamental Set Operations

Set operations construct new sets by combining or isolating elements of existing sets.

Union ( $\cup$ )

The union of $A$ and $B$ contains all elements that belong to $A$ , to $B$ , or to both: $A \cup B = \{x \mid x \in A \lor x \in B\}$

text

       Union: A ∪ B
   +-------------------+
   |  U                |
   |   /-----\ /-----\ |
   |  /  ***  X  ***  \|
   | |  *****| |*****  |
   |  \  ***  X  ***  /|
   |   \-----/ \-----/ |
   |     A       B     |
   +-------------------+

Intersection ( $\cap$ )

The intersection of $A$ and $B$ contains only the elements that belong to both $A$ and $B$ : $A \cap B = \{x \mid x \in A \land x \in B\}$

text

    Intersection: A ∩ B
   +-------------------+
   |  U                |
   |   /-----\ /-----\ |
   |  /     / \     \  |
   | |     | * |     | |
   |  \     \ /     /  |
   |   \-----/ \-----/ |
   |     A       B     |
   +-------------------+

Disjoint Sets: Two sets $A$ and $B$ are disjoint if they share no common elements, meaning $A \cap B = \emptyset$ .

Set Difference ( $-$ )

The set difference $A - B$ (sometimes written as $A \setminus B$ or $A / B$ ) consists of all elements that belong to $A$ but not to $B$ : $A - B = {x$ This can also be expressed using intersection and complementation:

text

    Difference: A - B
   +-------------------+
   |  U                |
   |   /-----\ /-----\ |
   |  /  ***  \     \  |
   | |  *****| |     | |
   |  \  ***  /     /  |
   |   \-----/ \-----/ |
   |     A       B     |
   +-------------------+

Symmetric Difference ( $\oplus$ )

The symmetric difference $A \oplus B$ (or $A \triangle B$ ) contains all elements that belong to either $A$ or $B$ , but not both: $A \oplus B = \{x \mid (x \in A \lor x \in B) \land x \notin (A \cap B)\}$

text

 Symmetric Difference: A ⊕ B
   +-------------------+
   |  U                |
   |   /-----\ /-----\ |
   |  /  ***  \  ***  \|
   | |  *****| |*****  |
   |  \  ***  /  ***  /|
   |   \-----/ \-----/ |
   |     A       B     |
   +-------------------+

Complement ( $\overline{A}$ )

Given a universal set $\mathbf{U}$ , the complement of $A$ , denoted $\overline{A}$ or $A^c$ , consists of all elements in $\mathbf{U}$ that are not in $A$ :

3. Set Identities

Set operations satisfy a rich system of algebraic laws called Set Identities. These identities are directly analogous to logical equivalences in propositional logic, where the operations map as follows:

Union ( $\cup$ ) maps to Logical OR ( $\lor$ )
Intersection ( $\cap$ ) maps to Logical AND ( $\land$ )
Complement ( $\overline{A}$ ) maps to Logical NOT ( $\neg$ )
Universal Set ( $\mathbf{U}$ ) maps to Tautology ()

Summary Table of Set Identities

| Identity Name | Law for Intersection ( $\cap$ ) | Law for Union ( $\cup$ ) | | :--- | :--- | :--- | | Identity Laws | $A \cap \mathbf{U} = A$ | $A \cup \emptyset = A$ | | Domination Laws | $A \cap \emptyset = \emptyset$ | | | | | | | | | — | | | | | | | | | | | | | | | | | | | | | | | | |

4. Methods of Proving Set Identities

Proving that two set expressions are equal (e.g., proving $X = Y$ ) is a core skill in discrete mathematics. We demonstrate four distinct mathematical proof strategies by proving the identity: $A \cap B = B - (B - A)$

Method 1: Algebraic Proof Using Basic Set Identities

This approach treats set operations as an algebraic system, applying known laws step-by-step.

\begin{aligned} B - (B - A) & = B \cap \overline{(B - A)} & (Definition of Difference) \\ = B \cap \overline{(B \cap \overline{A})} & (Definition of Difference) \\ = B \cap (\overline{B} \cup \overline{\overline{A}}) & (De Morgan’s Law) \\ = B \cap (\overline{B} \cup A) & (Double Complement Law) \\ = (B \cap \end{aligned}

Method 2: Verification via Membership Tables

A membership table tracks every logical configuration of an arbitrary element $x$ . A value of $1$ indicates $x$ is a member of the set, while $0$ indicates it is not. Because columns for $A \cap B$ and $B - (B - A)$ are identical for all possible configurations, the identity holds.

| $A$ | $B$ | $A \cap B$ | $B - A$ | $B - (B - A)$ | | :---: | :---: | :---: | :---: | :---: | | 1 | 1 | | 0 | | | 1 | 0 | | 0 | | | 0 | 1 | | 1 | | | 0 | 0 | | 0 | |

Method 3: Double Containment Proof (Mutual Subsets)

To show $X = Y$ , we prove $X \subseteq Y$ and $Y \subseteq X$ independently.

Part A: Prove $A \cap B \subseteq B - (B - A)$

Let $x$ be an arbitrary element such that $x \in A \cap B$ .
This implies $x \in A$ and $x \in B$ .
Since $x \in A$ , it cannot be in (as contains only elements not in ). Thus, .

Part B: Prove $B - (B - A) \subseteq A \cap B$

Let $y$ be an arbitrary element such that $y \in B - (B - A)$ .
By the definition of difference, $y \in B$ and $y \notin B - A$ .

Since both containments hold, the sets are equal.

Method 4: Set-Builder Notation and Logical Equivalences

This method translates the set expressions directly into logical formulas, simplifies them using propositional logic, and translates them back into set-builder notation.

\begin{aligned} B - (B - A) & = {x ∣ x \in B \land x \notin (B - A)} & (Definition of Difference) \\ = {x ∣ x \in B \land \neg (x \in B - A)} & (Definition of Negation) \\ = {x ∣ x \in B \land \neg (x \in B \land x \notin A)} & (Definition of Difference) \\ = {x ∣ x \in B \land (\neg (x \in B) \lor \neg ( \end{aligned}

5. Computer Representation of Sets

In physical hardware and low-level software design, managing sets using traditional pointers and data structures can be inefficient. When the universal set $\mathbf{U}$ is finite and reasonably small (e.g., $n \le 64$ ), we can represent any subset $A \subseteq \mathbf{U}$ as a bit vector (or bit string) of length $n$ .

The Bit Vector Protocol

Establish an arbitrary but fixed ordering of elements in the universe: $\mathbf{U} = \{u_1, u_2, \dots, u_n\}$
Represent a subset by a bit string , where:

Example: English Alphabet Characters

Let the universe be the first 10 letters of the alphabet: $\mathbf{U} = \{a, b, c, d, e, f, g, h, i, j\}$

Let us represent the subset of vowels $V$ and the subset of early alphabet letters $E = \{a, b, c, d, e\}$ :

| Set | Elements Included | Bit Vector | | :--- | :--- | :--- | | Universe $\mathbf{U}$ | $\{a, b, c, d, e, f, g, h, i, j\}$ | 1111111111 | | Vowels $V$ | | | | | | |

Bitwise Operators

This binary representation allows us to compute fundamental set operations using hardware-level bitwise operations in $O(1)$ CPU cycles:

Union ( $\cup$ ) is executed via bitwise OR ( $\lor$ ): $V \cup E \implies \texttt{1000100010} \lor \texttt{1111100000} = \texttt{1111100010} \implies \{a, b, c, d, e, i\}$

Summary

Set Specification: Sets can be specified using roster, ellipsis, or set-builder notation. The Principle of Specification asserts that any logical predicate defines a corresponding subset.
Basic Operations: Set interactions are captured by Union ( $\cup$ ), Intersection ( $\cap$ ), Difference ( $-$ ), Symmetric Difference ( $\oplus$ ), and Complementation ( $\overline{A}$ ).
Identities: Set operations adhere to a Boolean algebraic system of identities (such as De Morgan's, Distributive, and Absorption laws) that perfectly parallel propositional logic equivalences.
Proof Strategies: Set identities can be verified using algebraic manipulation, membership tables, double containment arguments, or translation to logical formulas.

Assessed progress

Set Operations and Identities

Set Operations and Identities

1. Set Specifications and Foundations

Specifying Sets

The Principle of Specification

Set Inclusion and Power Sets

2. Fundamental Set Operations

Union ( $\cup$ )

Intersection ( $\cap$ )

Set Difference ( $-$ )

Symmetric Difference ( $\oplus$ )

Complement ( $\overline{A}$ )

3. Set Identities

Summary Table of Set Identities

4. Methods of Proving Set Identities

Method 1: Algebraic Proof Using Basic Set Identities

Method 2: Verification via Membership Tables

Method 3: Double Containment Proof (Mutual Subsets)

Part A: Prove $A \cap B \subseteq B - (B - A)$

Part B: Prove $B - (B - A) \subseteq A \cap B$

Method 4: Set-Builder Notation and Logical Equivalences

5. Computer Representation of Sets

The Bit Vector Protocol

Example: English Alphabet Characters

Bitwise Operators

Summary

Key Concepts

Set Builder Notation

Set Operations

Set Identities

Double Containment Proof

Bit Vector Representation

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures