Essential Set Theory Notations

Why This Matters

Set theory is the language underlying virtually every topic in discrete mathematics—from logic and proof techniques to functions, relations, and combinatorics. When you're working with probability, database queries, or algorithm analysis later in the course, you'll be using these notations constantly. The symbols you'll learn here aren't just abstract squiggles; they're precise tools for describing membership, containment, and combination of mathematical objects.

You're being tested on more than symbol recognition. Exam questions will ask you to translate between set-builder notation and roster form, determine subset relationships, compute cardinalities of combined sets, and apply operations in sequence. Don't just memorize what each symbol looks like—know what logical relationship it expresses and how it connects to other operations. That's what separates a correct answer from a complete one.

---

Describing Sets and Their Elements

Before you can operate on sets, you need to describe them precisely. These notations establish what a set contains and how we specify membership.

Set Notation: $\{ \}$

• Curly braces define a set—the most fundamental notation, enclosing all elements that belong together
• Order is irrelevant and duplicates collapse—$\{1, 2, 3\}$ and $\{3, 1, 2\}$ are identical sets
• Roster form lists elements explicitly, useful when sets are small and finite

Set-Builder Notation: $\{x \mid P(x)\}$

• Defines sets by property rather than listing—read as "the set of all $x$ such that $P(x)$ is true"
• Essential for infinite or large sets—$\{x \mid x > 0\}$ describes all positive numbers concisely
• The vertical bar (or colon) separates the variable from its defining condition

Element Of: $\in$

• Asserts membership in a set—if $A = \{1, 2, 3\}$, then $2 \in A$ is a true statement
• Fundamental to logical proofs—proving $x \in A \cap B$ requires showing $x \in A$ AND $x \in B$
• Distinguishes elements from sets—$2 \in \{1, 2, 3\}$ but $\{2\} \not\in \{1, 2, 3\}$ (the singleton set isn't an element)

Not an Element Of: $\notin$

• Negates membership—$4 \notin \{1, 2, 3\}$ states that 4 is absent from the set
• Critical for complement definitions—$x \in A'$ means $x \notin A$
• Appears in counterexample proofs—showing one element $\notin$ a set can disprove universal claims

---

Containment and Subset Relationships

These notations describe when one set lives entirely inside another—a relationship that's central to proofs and logical arguments.

Subset: $\subseteq$

• Every element of $A$ is also in $B$—$A \subseteq B$ means "if $x \in A$, then $x \in B$"
• Allows equality—a set is always a subset of itself: $A \subseteq A$ is always true
• The empty set is a subset of everything—$\emptyset \subseteq A$ for any set $A$ (vacuously true)

Proper Subset: $\subset$

• Subset but not equal—$A \subset B$ requires $A \subseteq B$ AND $A \neq B$
• $B$ must contain at least one extra element—if $A = \{1, 2\}$ and $B = \{1, 2, 3\}$, then $A \subset B$
• Watch notation variations—some textbooks use $\subsetneq$ for proper subset; know your course's convention

---

Special Sets: The Boundaries

These sets represent the extremes—everything and nothing—and serve as reference points for other operations.

Empty Set: $\emptyset$ or $\{ \}$

• Contains no elements—the unique set with cardinality zero
• Subset of every set—this is vacuously true since there's no element in $\emptyset$ that could fail to be in another set
• Identity for union, annihilator for intersection—$A \cup \emptyset = A$ and $A \cap \emptyset = \emptyset$

Universal Set: $U$

• Contains all elements under consideration—defines the "universe of discourse" for a problem
• Context-dependent—in number theory, $U$ might be $\mathbb{Z}$; in a survey problem, it might be all respondents
• Required for complements—$A'$ only makes sense relative to some universal set $U$

---

Set Operations: Combining and Separating

These operations take existing sets and produce new ones—the algebraic heart of set theory.

Union: $\cup$

• Combines all elements from both sets—$A \cup B = \{x \mid x \in A \text{ OR } x \in B\}$
• Duplicates appear once—$\{1, 2\} \cup \{2, 3\} = \{1, 2, 3\}$, not $\{1, 2, 2, 3\}$
• Corresponds to logical OR—essential connection for translating between set theory and propositional logic

Intersection: $\cap$

• Keeps only shared elements—$A \cap B = \{x \mid x \in A \text{ AND } x \in B\}$
• Can produce the empty set—when $A \cap B = \emptyset$, we call $A$ and $B$ disjoint
• Corresponds to logical AND—intersection is more restrictive than union

Set Difference: $\setminus$ or $-$

• Elements in $A$ but not in $B$—$A \setminus B = \{x \mid x \in A \text{ AND } x \notin B\}$
• Not commutative—$A \setminus B \neq B \setminus A$ in general
• Relates to complement—$A \setminus B = A \cap B'$ when working within a universal set

Complement: $A'$ or $\bar{A}$ or $A^c$

• Everything outside $A$—$A' = \{x \in U \mid x \notin A\}$
• Double complement returns the original—$(A')' = A$
• De Morgan's Laws apply—$(A \cup B)' = A' \cap B'$ and $(A \cap B)' = A' \cup B'$ (memorize these!)

---

Counting and Constructing New Sets

These notations let you measure sets and build more complex structures from simpler ones.

Cardinality: $|A|$

• Counts the number of elements—if $A = \{a, b, c\}$, then $|A| = 3$
• Key formula for unions—$|A \cup B| = |A| + |B| - |A \cap B|$ (inclusion-exclusion principle)
• Infinite sets have cardinality too—but that's a topic for later; focus on finite sets for now

Power Set: $\mathcal{P}(A)$ or $2^A$

• The set of all subsets of $A$—includes $\emptyset$ and $A$ itself
• Cardinality is $2^n$—if $|A| = n$, then $|\mathcal{P}(A)| = 2^n$ (each element is either in or out of each subset)
• Example: $\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$—four subsets from two elements

Cartesian Product: $\times$

• All ordered pairs from two sets—$A \times B = \{(a, b) \mid a \in A \text{ and } b \in B\}$
• Order matters and cardinality multiplies—$|A \times B| = |A| \cdot |B|$
• Foundation for relations and functions—any relation $R$ from $A$ to $B$ is a subset of $A \times B$

---

Quick Reference Table

---

Self-Check Questions

1. What's the difference between $\in$ and $\subseteq$? Give an example where $\{1\} \subseteq A$ is true but $\{1\} \in A$ is false.

2. If $A = \{1, 2, 3\}$ and $B = \{2, 3, 4\}$, compute $A \cup B$, $A \cap B$, $A \setminus B$, and $B \setminus A$. Which two results are equal?

3. Explain why $\emptyset \subseteq A$ is true for every set $A$, using the definition of subset.

4. Compare $\mathcal{P}(A)$ and $A \times A$ when $A = \{a, b\}$. List all elements of each and explain why they have the same cardinality but different types of elements.

5. Using De Morgan's Laws, rewrite $(A \cup B)'$ in terms of complements and intersection. Then verify with $U = \{1, 2, 3, 4\}$, $A = \{1, 2\}$, $B = \{2, 3\}$.