Set Operations

Introduction

Set operations are procedures that combine or relate sets to form new sets, fundamental for discrete mathematics, logic, probability, and computer science. They enable formal manipulation of collections, providing tools for classification, analysis, and problem-solving. Core operations include union, intersection, difference, complement, and Cartesian product.

"Sets are the building blocks of mathematics; operations on sets reveal the structure underlying mathematical reasoning." -- Herbert B. Enderton

Basic Set Operations

Definition of a Set

Set: well-defined collection of distinct objects, elements denoted by braces {}. Example: A = {1,2,3}.

Notation

Elements: a ∈ A means "a is an element of A". Subsets: A ⊆ B means "A is subset of B".

Purpose

Operations combine sets to define new sets, analyze relations, and support proofs.

Union

Definition

Union (A ∪ B): set containing all elements in A, or B, or both.

Formal Expression

A ∪ B = {x | x ∈ A or x ∈ B}

Properties

Commutative: A ∪ B = B ∪ A. Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C). Idempotent: A ∪ A = A.

Example

A = {1,2,3}, B = {3,4,5} then A ∪ B = {1,2,3,4,5}.

Visual Representation

Venn diagram: overlapping circles, shaded area covers both sets.

Intersection

Definition

Intersection (A ∩ B): set of elements common to A and B.

Formal Expression

A ∩ B = {x | x ∈ A and x ∈ B}

Properties

Commutative: A ∩ B = B ∩ A. Associative: (A ∩ B) ∩ C = A ∩ (B ∩ C). Idempotent: A ∩ A = A.

Example

A = {1,2,3}, B = {3,4,5} then A ∩ B = {3}.

Visual Representation

Venn diagram: overlapping circles, shaded area is common section.

Difference

Definition

Difference (A \ B): set of elements in A but not in B.

Formal Expression

A \ B = {x | x ∈ A and x ∉ B}

Properties

Non-commutative: A \ B ≠ B \ A. Difference with empty set: A \ ∅ = A.

Example

A = {1,2,3}, B = {3,4,5} then A \ B = {1,2}.

Visual Representation

Venn diagram: shaded area is part of A excluding overlap with B.

Complement

Definition

Complement (A^c or A'): all elements not in A, relative to universal set U.

Formal Expression

A^c = {x | x ∈ U and x ∉ A}

Properties

Double complement: (A^c)^c = A. Complement of universal set: U^c = ∅.

Example

U = {1,2,3,4,5}, A = {1,2} then A^c = {3,4,5}.

Visual Representation

Venn diagram: shaded region outside A within U.

Symmetric Difference

Definition

Symmetric difference (A △ B): elements in A or B but not both.

Formal Expression

A △ B = (A \ B) ∪ (B \ A)

Properties

Commutative: A △ B = B △ A. Associative: (A △ B) △ C = A △ (B △ C). Identity: A △ ∅ = A.

Example

A = {1,2,3}, B = {3,4,5} then A △ B = {1,2,4,5}.

Visual Representation

Venn diagram: shaded areas excluding intersection.

Cartesian Product

Definition

Cartesian product (A × B): set of ordered pairs (a,b) where a ∈ A, b ∈ B.

Formal Expression

A × B = {(a,b) | a ∈ A, b ∈ B}

Properties

Non-commutative: generally A × B ≠ B × A. Cardinality: |A × B| = |A| × |B|.

Example

A = {1,2}, B = {x,y} then A × B = {(1,x),(1,y),(2,x),(2,y)}.

Applications

Used in defining relations, functions, coordinate systems.

Subset and Superset

Subset Definition

A ⊆ B means every element of A is in B.

Proper Subset

A ⊂ B means A ⊆ B and A ≠ B.

Superset Definition

B ⊇ A means B contains all elements of A.

Properties

Reflexive: A ⊆ A. Transitive: If A ⊆ B and B ⊆ C then A ⊆ C.

Example

A = {1,2}, B = {1,2,3} then A ⊆ B, B ⊇ A.

Laws and Properties

Idempotent Laws

A ∪ A = A, A ∩ A = A.

Commutative Laws

A ∪ B = B ∪ A, A ∩ B = B ∩ A.

Associative Laws

(A ∪ B) ∪ C = A ∪ (B ∪ C), (A ∩ B) ∩ C = A ∩ (B ∩ C).

Distributive Laws

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

De Morgan's Laws

(A ∪ B)^c = A^c ∩ B^c, (A ∩ B)^c = A^c ∪ B^c.

// Distributive Law ExampleA ∪ (B ∩ C)= (A ∪ B) ∩ (A ∪ C)// De Morgan's Law Example(A ∪ B)^c= A^c ∩ B^c

Applications

Logic and Proofs

Set operations correspond to logical operators: union = OR, intersection = AND, complement = NOT. Used in formal proofs, predicate logic.

Probability Theory

Events as sets; operations describe combined events. Union for "either/or", intersection for "both", complement for "not".

Database Queries

Set operations model relational algebra: unions combine results, intersections find common records, differences exclude.

Computer Science

Data structures, automata theory, language design use set operations extensively.

Discrete Structures

Power sets, partitions, equivalence relations rely on operations for construction and analysis.

References

• Enderton, H. B., "Elements of Set Theory," Academic Press, 1977, pp. 1-150.
• Rosen, K. H., "Discrete Mathematics and Its Applications," McGraw-Hill, 7th ed., 2012, pp. 75-130.
• Halmos, P. R., "Naive Set Theory," Springer, 1960, pp. 10-50.
• Suppes, P., "Axiomatic Set Theory," Dover Publications, 1972, pp. 1-105.
• Herstein, I. N., "Topics in Algebra," 2nd ed., Wiley, 1975, pp. 45-80.