Sets

Set theory was conceived in the late 19th century by the German mathematician Georg Cantor (1845–1918) while investigating trigonometric series and the mathematical continuum. Today, it serves as the universal foundational language in which all of modern mathematics is formulated.

A set is a well-defined collection of distinct mathematical objects. The objects belonging to a set are called its elements or members.

• Valid Sets: "The collection of all vowels in the English alphabet" — well-defined, since {a, e, i, o, u} is unambiguous. "The collection of all prime numbers less than 20" — well-defined ({2, 3, 5, 7, 11, 13, 17, 19}).
• Invalid Collections (Not Sets): "The collection of the five best cricketers in India" — not well-defined, because the descriptor "best" is subjective and varies from person to person. "The collection of difficult chapters in Class 11 Math" — not a set.

Sets are conventionally denoted by uppercase English letters ($A, B, C, X, Y, Z$), while their elements are denoted by lowercase letters ($a, b, c, x, y, z$), numbers, or mathematical symbols.

• If $x$ is an element of set $A$, we write $x \in A$ (read as "$x$ belongs to $A$" or "$x$ is an element of $A$").
• If $x$ is not an element of set $A$, we write $x \notin A$ (read as "$x$ does not belong to $A$").

There are two principal methods used to describe or specify a set:

The following symbols are globally standardized in mathematics:

• $\mathbb{N} = \{1, 2, 3, 4, \dots\}$ : Set of all natural numbers (positive integers).
• $\mathbb{W} = \{0, 1, 2, 3, \dots\}$ : Set of all whole numbers.
• $\mathbb{Z}$ or $\mathbb{I} = \{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\}$ : Set of all integers.
• $\mathbb{Z}^+$ or $\mathbb{N}$ : Set of all positive integers; $\mathbb{Z}^-$ : Set of all negative integers.
• $\mathbb{Q} = \left\{\frac{p}{q} : p, q \in \mathbb{Z}, q \neq 0, \gcd(p, q) = 1\right\}$ : Set of all rational numbers.
• $\mathbb{R}$ : Set of all real numbers (rationals and irrationals combined).
• $\mathbb{C} = \{a + ib : a, b \in \mathbb{R}, i = \sqrt{-1}\}$ : Set of all complex numbers.

Understanding the taxonomy of sets and the precise hierarchy of subset inclusion is essential for algebraic logic and analysis.

• Empty Set (Null Set / Void Set): A set that contains no elements at all. Denoted by the Scandinavian letter $\emptyset$ or by empty braces $\{\}$.
  Cardinality: $n(\emptyset) = 0$.
  Examples: $A = \{x \in \mathbb{R} : x^2 + 1 = 0 \text{ and } x \in \mathbb{R}\} = \emptyset$; $B = \{x \in \mathbb{N} : 1 < x < 2\} = \emptyset$.
  Critical Trap: $\{\emptyset\}$ is NOT an empty set! It is a singleton set containing one element, which happens to be the empty set. Similarly, $\{0\}$ is a singleton set containing the number 0.
• Singleton Set (Unit Set): A set containing exactly one element. $n(A) = 1$.
  Example: $A = \{x \in \mathbb{N} : x^2 = 9\} = \{3\}$. The set of even prime numbers: $\{2\}$.
• Finite Set vs. Infinite Set:
  A set is finite if it is empty or consists of a definite, countable number of elements. The number of distinct elements in a finite set $A$ is called its cardinal number or cardinality, denoted by $n(A)$ or $|A|$.
  A set whose element count is not finite is an infinite set (e.g., $\mathbb{N}, \mathbb{Z}, \mathbb{R}$, or the set of points on a line segment).
• Equal Sets ($A = B$): Two sets $A$ and $B$ are equal if and only if they have exactly the same elements.
  Symbolically: $A = B \iff (\forall x, x \in A \iff x \in B)$.
  Example: $A = \{1, 2, 3\}$ and $B = \{x \in \mathbb{N} : (x-1)(x-2)(x-3) = 0\} \implies A = B$.
• Equivalent Sets ($A \sim B$): Two finite sets $A$ and $B$ are equivalent if they have the same cardinality, i.e., $n(A) = n(B)$. There exists a one-to-one correspondence (bijection) between their elements.
  Fundamental Fact: Equal sets are always equivalent, but equivalent sets need not be equal! (e.g., $\{1, 2, 3\} \sim \{a, b, c\}$ since both have cardinality 3, but they are not equal).

A set $A$ is said to be a subset of a set $B$ if every element of $A$ is also an element of $B$.

• Every set is a subset of itself: For any set $A$, $A \subseteq A$ (reflexive property).
• The empty set is a subset of every set: For any set $A$, $\emptyset \subseteq A$.
• Proper Subset ($A \subset B$): If $A \subseteq B$ and $A \neq B$, then $A$ is a proper subset of $B$, meaning $B$ contains at least one element that is not in $A$.
  Example: If $A = \{1, 2\}$ and $B = \{1, 2, 3\}$, then $A \subset B$.
• Transitive Property: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.
• Criterion for Set Equality: $A = B \iff (A \subseteq B \text{ and } B \subseteq A)$. This is the primary technique used to prove set identities!

In calculus and real analysis, continuous subsets of the real line $\mathbb{R}$ cannot be listed in roster form. They are defined as intervals:

The power set introduces combinatorial exponential growth into set theory, while Venn diagrams transform abstract set logic into intuitive spatial geometry.

The collection of all possible subsets of a set $A$ is called the Power Set of $A$, denoted by $P(A)$ or $\mathcal{P}(A)$.

Notice that every element of $P(A)$ is itself a set! Furthermore, for any set $A$:

• $\emptyset \in P(A)$ (since $\emptyset \subseteq A$).
• $A \in P(A)$ (since $A \subseteq A$).

If $A$ is a finite set with $n$ elements (i.e., $n(A) = n$), then:

1. The total number of subsets of $A$ is $2^n$, so $n(P(A)) = |P(A)| = 2^n$.
2. The number of proper subsets of $A$ is $2^n - 1$ (excluding the set $A$ itself).
3. The number of non-empty subsets of $A$ is $2^n - 1$ (excluding the empty set $\emptyset$).
4. The number of non-empty proper subsets is $2^n - 2$ (excluding both $\emptyset$ and $A$).

In any mathematical context or investigation, all the sets under discussion are subsets of a fixed, sufficiently comprehensive larger set called the Universal Set, denoted by $U$ or $\xi$.

• In human population studies, $U$ could be the set of all human beings on Earth.
• In 2D coordinate geometry, $U$ is the Cartesian plane $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$.
• In number theory of integers, $U$ is the set of all integers $\mathbb{Z}$.

Introduced by English logician John Venn (1834–1923), Venn diagrams represent sets pictorially:

• The Universal Set $U$ is represented geometrically by the interior of a rectangle.
• Subsets of $U$ (such as $A, B, C$) are represented by closed planar curves, usually circles or ellipses within the rectangle.
• Individual elements are represented by labeled points inside the corresponding regions.
• Subsets ($A \subseteq B$) are drawn with circle $A$ completely lying inside circle $B$.
• Disjoint sets ($A \cap B = \emptyset$) are drawn as non-overlapping, separated circles.

Just as addition and multiplication are fundamental operations on numbers, union, intersection, difference, and complement are fundamental operations that combine sets to produce new sets.

The union of two sets $A$ and $B$ is the set of all elements that belong to $A$, or to $B$, or to both.

Example: If $A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5, 6\}$, then $A \cup B = \{1, 2, 3, 4, 5, 6\}$.

The intersection of two sets $A$ and $B$ is the set of all elements that belong simultaneously to both $A$ and $B$.

Example: For the same $A$ and $B$ above, $A \cap B = \{3, 4\}$.

• Disjoint Sets: If two sets have no elements in common, their intersection is the empty set, i.e., $A \cap B = \emptyset$. Such sets are called mutually disjoint.

The difference of set $A$ and set $B$ (also called the relative complement of $B$ in $A$) is the set of all elements that belong to $A$ but do not belong to $B$.

Important Property: In general, set difference is not commutative: $A - B \neq B - A$ unless $A = B$.

Example: With $A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5, 6\}$:
$A - B = \{1, 2\}$
$B - A = \{5, 6\}$
Notice that $(A - B)$, $(A \cap B)$, and $(B - A)$ are mutually pairwise disjoint sets whose union is $A \cup B$!

The symmetric difference of sets $A$ and $B$ is the set of elements that belong to $A$ or to $B$, but not to both.

Example: For $A = \{1, 2, 3, 4\}$ and $B = \{3, 4, 5, 6\}$, $A \Delta B = \{1, 2\} \cup \{5, 6\} = \{1, 2, 5, 6\}$.
Properties: $A \Delta B = B \Delta A$ (commutative); $A \Delta A = \emptyset$; $A \Delta \emptyset = A$.

Let $U$ be the universal set. The complement of a subset $A \subseteq U$ is the set of all elements in $U$ that do not belong to $A$.

Fundamental Complement Properties:

1. $A \cup A' = U$ (Complement Union Law)
2. $A \cap A' = \emptyset$ (Complement Intersection Law)
3. $(A')' = A$ (Law of Involution / Double Complement)
4. $U' = \emptyset$ and $\emptyset' = U$ (Universal and Empty Set Complements)

The algebra of sets provides the symbolic and axiomatic system governing operations on sets. It mirrors Boolean algebra and propositional logic.

Formulated by British mathematician Augustus De Morgan (1806–1871), these laws describe how complementation interacts with union and intersection:

To prove that two sets $X$ and $Y$ are equal, we must demonstrate mutual subset inclusion: $X \subseteq Y$ and $Y \subseteq X$.

Part 1: Prove $(A \cup B)' \subseteq A' \cap B'$

1. Let $x$ be an arbitrary element of $(A \cup B)'$.
2. $\implies x \in (A \cup B)'$
3. $\implies x \notin (A \cup B)$ (by definition of complement)
4. $\implies \text{it is false that } (x \in A \text{ or } x \in B)$
5. $\implies x \notin A \text{ and } x \notin B$ (by basic logic negation of disjunction)
6. $\implies x \in A' \text{ and } x \in B'$ (by definition of complement)
7. $\implies x \in (A' \cap B')$ (by definition of intersection)
8. Since every element of $(A \cup B)'$ is in $A' \cap B'$, we have: $(A \cup B)' \subseteq A' \cap B'$ ... (Equation 1)

Part 2: Prove $A' \cap B' \subseteq (A \cup B)'$

1. Let $y$ be an arbitrary element of $A' \cap B'$.
2. $\implies y \in A' \text{ and } y \in B'$
3. $\implies y \notin A \text{ and } y \notin B$
4. $\implies y \notin (A \cup B)$ (for if $y \in A \cup B$, $y$ would have to be in at least one of them, which contradicts step 3)
5. $\implies y \in (A \cup B)'$ (by definition of complement)
6. Since every element of $A' \cap B'$ is in $(A \cup B)'$, we have: $A' \cap B' \subseteq (A \cup B)'$ ... (Equation 2)

From Equations (1) and (2), by the definition of set equality, we conclude: $(A \cup B)' = A' \cap B'$. $\quad \blacksquare$

Cardinality principles enable mathematicians to compute counts of elements across intersecting sets without double-counting overlapping elements.

Let $A$ and $B$ be finite sets. The union $A \cup B$ can be partitioned into three mutually disjoint subsets: $(A - B)$, $(A \cap B)$, and $(B - A)$.

Therefore: $n(A \cup B) = n(A - B) + n(A \cap B) + n(B - A)$.

Since $n(A) = n(A - B) + n(A \cap B) \implies n(A - B) = n(A) - n(A \cap B)$, and similarly $n(B - A) = n(B) - n(A \cap B)$, substituting yields the master formula:

Important Corollaries:

• If $A$ and $B$ are disjoint ($A \cap B = \emptyset$), then $n(A \cap B) = 0 \implies \mathbf{n(A \cup B) = n(A) + n(B)}$.
• Number of elements in exactly one of $A$ or $B$: $$n(A \Delta B) = n(A - B) + n(B - A) = n(A) + n(B) - 2n(A \cap B) = n(A \cup B) - n(A \cap B)$$
• Number of elements belonging to neither $A$ nor $B$: $$n(A' \cap B') = n((A \cup B)') = n(U) - n(A \cup B)$$

For any three finite sets $A, B$, and $C$:

Why is $n(A \cap B \cap C)$ added at the end? In the single terms $n(A) + n(B) + n(C)$, the central intersection $A \cap B \cap C$ is counted 3 times. In the pairwise subtraction $-[n(A \cap B) + n(B \cap C) + n(C \cap A)]$, it is subtracted 3 times (net count = 0). To account for it exactly once in the union, it must be added back!

• Number of elements belonging to EXACTLY TWO sets: $$n(\text{exactly two}) = [n(A \cap B) + n(B \cap C) + n(C \cap A)] - 3n(A \cap B \cap C)$$
• Number of elements belonging to AT LEAST TWO sets: $$n(\text{at least two}) = [n(A \cap B) + n(B \cap C) + n(C \cap A)] - 2n(A \cap B \cap C)$$
• Number of elements belonging to EXACTLY ONE set: $$n(\text{exactly one}) = n(A) + n(B) + n(C) - 2[n(A \cap B) + n(B \cap C) + n(C \cap A)] + 3n(A \cap B \cap C)$$

Given two non-empty sets $A$ and $B$, the Cartesian Product $A \times B$ is the set of all ordered pairs $(a, b)$ such that $a \in A$ and $b \in B$:

• Ordered Pair: $(a, b) = (c, d) \iff a = c \text{ and } b = d$. Thus, $(1, 2) \neq (2, 1)$.
• Non-Commutative: $A \times B \neq B \times A$ unless $A = B$ or one of the sets is empty.
• Cardinality Theorem: If $n(A) = p$ and $n(B) = q$, then $n(A \times B) = p \times q$.
• The total number of relations from set $A$ to set $B$ is the number of subsets of $A \times B$, which equals $2^{pq}$. (This bridges Chapter 1 to Chapter 2: Relations and Functions!).