Set theory is the mathematical language of computer science, used in database theory, formal languages, and algorithm analysis.

1. Basics of Sets

A set is a well-defined collection of distinct objects.

Types of Sets:

• Null Set (Empty Set): A set containing no elements, denoted by $\emptyset$ or $\{\}$.
• Finite and Infinite Sets: Depending on whether the number of elements is countable or not.
• Power Set: The set of all subsets of a set $A$ is called the power set $P(A)$.
  • Rule: If a set $A$ has $n$ elements, then $n(P(A)) = 2^n$.

2. Set Operations

Common operations used to manipulate sets:

A. Union ($A \cup B$)

Elements that are in $A$, or in $B$, or in both.

B. Intersection ($A \cap B$)

Elements that are in both $A$ and $B$.

C. Difference ($A - B$)

Elements that are in $A$ but not in $B$.

D. Symmetric Difference ($A \Delta B$)

Elements that are in $A$ or $B$, but not in their intersection.
$A \Delta B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$

3. Relations and Functions

A relation from $A$ to $B$ is a subset of $A \times B$.

Functions:

A function $f: A \to B$ is a special type of relation where every element in $A$ is mapped to exactly one element in $B$.

• Domain: The set $A$.
• Range: The subset of $B$ containing all images of elements in $A$.

Summary

Mastering set operations and functions is essential for understanding data structures and relational databases.