Set theory - Foundations and Basic Concepts

Introduction to Set Theory What is Set Theory? Set theory is the branch of mathematics that studies sets, which are collections of objects called elements. While sets can contain any type of objects, mathematicians primarily work with mathematical objects like numbers, functions, or other sets. What makes set theory particularly important is that it provides the foundational framework for virtually all of modern mathematics—nearly every mathematical concept can be built from set-theoretic principles. At its core, set theory answers fundamental questions: What makes a valid collection? How do we compare collections of different sizes? What operations can we perform on collections? Understanding these concepts is essential for higher mathematics. Basic Concepts and Notation Membership and Subsets When an object belongs to a set, we say it is a member or element of that set. We write this using the membership symbol: $$o \in A$$ This reads as "o is an element of A" or "o belongs to A." One of the most important relationships in set theory is the subset relation. Set $A$ is a subset of set $B$, written $A \subseteq B$, if every element of $A$ is also an element of $B$. This doesn't require that $A$ and $B$ have the same elements—$B$ could be larger. A proper subset, written $A \subset B$, is a subset where $A \subseteq B$ and additionally $A \neq B$. In other words, $B$ must contain at least one element that $A$ does not contain. The distinction between $\subseteq$ and $\subset$ is important: subset allows the sets to be equal, while proper subset does not. Set Operations We can combine or manipulate sets in several useful ways: Union brings sets together. The union of $A$ and $B$, written $A \cup B$, contains all elements that belong to $A$ or to $B$ or to both. Think of it as combining all elements from both sets. Intersection finds what sets have in common. The intersection $A \cap B$ contains all elements that belong to both $A$ and $B$ simultaneously. If no elements are in both sets, the intersection is empty. The visualization above shows how union and intersection work: the left circle represents set $A$, the right circle represents set $B$, and their overlap shows $A \cap B$. Set difference removes elements. The set difference $U \setminus A$ (read as "$U$ minus $A$") contains all elements of $U$ that are not in $A$. When $U$ is understood to be a universal set containing all elements under consideration, we call this the complement of $A$, written $A^c$. Symmetric difference is slightly less intuitive: $A \triangle B$ contains elements that belong to exactly one of the two sets, but not both. This is useful when you want to identify which elements distinguish the two sets from each other. Cartesian product creates pairs. The Cartesian product $A \times B$ consists of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. This operation is fundamental in defining relations and functions. Special Sets Some sets are so important that they have their own notation: The empty set, denoted $\varnothing$ or sometimes $\{\}$, is the unique set containing no elements. Despite having no members, it's a crucial concept—it's the subset of every set, and it serves as the identity element for union (just as 0 is the additive identity). The natural numbers (often denoted $\mathbb{N}$) and real numbers (denoted $\mathbb{R}$) are fundamental infinite sets that appear throughout mathematics. The power set of a set $A$, denoted $\mathcal{P}(A)$, is the set of all subsets of $A$, including $A$ itself and the empty set. This is a critical concept: if $A$ has $n$ elements, then $\mathcal{P}(A)$ has $2^n$ elements. For example, if $A = \{1, 2\}$, then $\mathcal{P}(A) = \{\varnothing, \{1\}, \{2\}, \{1,2\}\}$, which has 4 elements. Understanding Cardinality and Size One of the deepest insights in set theory concerns how we compare the sizes of sets. For finite sets, this is straightforward—$\{1, 2, 3\}$ has 3 elements while $\{a, b\}$ has 2 elements. But what about infinite sets? Cardinality is the formal term for the "size" of a set. Two sets have the same cardinality if we can establish a one-to-one correspondence between their elements—that is, a pairing where each element of one set matches with exactly one element of the other, with no elements left unpaired. This definition works even for infinite sets. Here's something surprising: the set of natural numbers $\{1, 2, 3, 4, ...\}$ has the same cardinality as the set of all integers (positive, negative, and zero). We can pair them up systematically, so they're considered to have equal size despite both being infinite. A set with the same cardinality as the natural numbers is called countably infinite. However, Cantor proved that the set of real numbers is uncountable—it has strictly more elements than the natural numbers, so no one-to-one correspondence is possible. This was a revolutionary discovery: there are different sizes of infinity! Cantor's Theorem and Power Sets Cantor's theorem is one of the most fundamental results in set theory: For any set $A$, the power set $\mathcal{P}(A)$ has strictly larger cardinality than $A$ itself. This is true even for infinite sets. Why is this significant? It means that even if we have an infinite set, its power set is even larger (more infinite, in a sense). This creates a hierarchy of infinities: the natural numbers have a certain cardinality, but the power set of the natural numbers is strictly larger, and the power set of that is even larger, and so on. There is no "largest" infinity. The proof of Cantor's theorem uses a clever diagonal argument and is one of the first places students encounter a genuinely non-constructive proof in mathematics. <extrainfo> Historical Context Naive Set Theory and Paradoxes Modern set theory began in the 1870s when mathematicians like Georg Cantor and Richard Dedekind started systematically studying sets. Their early work, called naive set theory, didn't have formal rules or axioms—it relied on intuition about what made a valid set. This informal approach led to paradoxes. The most famous paradox is Russell's paradox (discovered by Bertrand Russell in 1901): Consider the set $R$ of all sets that do not contain themselves. Does $R$ contain itself? If it does, then by definition it shouldn't. If it doesn't, then by definition it should. This logical contradiction shows that not every intuitive description creates a valid set. These paradoxes revealed that set theory needed a rigorous foundation. In the early 20th century, mathematicians like Ernst Zermelo and Abraham Fraenkel developed axiomatic set theory—a system with formal axioms that avoids these paradoxes. When you hear "Zermelo-Fraenkel set theory" or "ZFC," this is the standard axiomatic framework used in modern mathematics. Transfinite Numbers Cantor introduced notation for different infinities: Transfinite cardinal numbers are denoted with the Hebrew letter aleph ($\aleph$) with subscripts: $\aleph0$ for the cardinality of the natural numbers, $\aleph1$ for the next larger infinity, and so on. Transfinite ordinal numbers extend the concept of "order" or "position" to infinite sets and are denoted using the Greek letter omega ($\omega$). These concepts are mathematically rich but typically explored more deeply in advanced courses. </extrainfo>