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 here aren't 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 are the most fundamental notation in set theory. They enclose all the elements that belong together into a single object.

• Order is irrelevant and duplicates collapse. $\{1, 2, 3\}$ and $\{3, 1, 2\}$ are the same set, and $\{1, 1, 2\}$ is just $\{1, 2\}$.
• Roster form lists elements explicitly, which works well when sets are small and finite: $\{a, b, c\}$.
• Ellipsis notation handles larger patterns: $\{1, 2, 3, \ldots, 100\}$ lists the integers from 1 to 100 without writing all of them.

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

This defines sets by a property rather than listing every element. Read it 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, which roster form can't do.
• The vertical bar $\mid$ (or sometimes a colon $:$) separates the variable from its defining condition.
• You'll often see a domain restriction on the left side: $\{x \in \mathbb{Z} \mid x > 0\}$ means "all positive integers," which is more precise than just $\{x \mid x > 0\}$.

Element Of: $\in$

This symbol asserts that a specific object belongs to 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\}$ is true, but $\{2\} \not\in \{1, 2, 3\}$ because the singleton set $\{2\}$ is not the same object as the number $2$. (However, $\{2\} \in \{\{2\}, 3\}$ would be true, since $\{2\}$ is listed as an element.)

Not an Element Of: $\notin$

This negates membership. $4 \notin \{1, 2, 3\}$ states that 4 is absent from the set.

• Critical for complement definitions. $x \in A'$ means exactly that $x \notin A$ (and $x \in U$).
• Appears in counterexample proofs. Showing one element $\notin$ a set can disprove a universal claim like "all even numbers are in $A$."

---

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$

$A \subseteq B$ means "every element of $A$ is also in $B$." Formally: 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$. This is vacuously true: there's no element in $\emptyset$ that could fail to be in $A$.
• To prove $A \subseteq B$, pick an arbitrary $x \in A$ and show it must be in $B$.

Proper Subset: $\subset$

$A \subset B$ means $A \subseteq B$ AND $A \neq B$. In other words, $B$ contains everything $A$ does, plus at least one extra element.

• If $A = \{1, 2\}$ and $B = \{1, 2, 3\}$, then $A \subset B$.
• If $A = \{1, 2\}$ and $B = \{1, 2\}$, then $A \subseteq B$ is true but $A \subset B$ is false.
• Watch notation variations. Some textbooks use $\subsetneq$ for proper subset and reserve $\subset$ to mean the same as $\subseteq$. Know your course's convention.

---

Special Sets: The Boundaries

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

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

The empty set contains no elements. It's 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$.
• Common mistake: Don't write $\{\emptyset\}$ when you mean $\emptyset$. The set $\{\emptyset\}$ actually contains one element (the empty set itself), so its cardinality is 1, not 0.

Universal Set: $U$

The universal set contains all elements under consideration. It 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$, because you need to know what "everything outside $A$" means.

---

Set Operations: Combining and Separating

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

Union: $\cup$

Union 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. This connection is essential when translating between set theory and propositional logic.
• The result is always at least as large as the larger input set.

Intersection: $\cap$

Intersection 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.
• The result is always at most as large as the smaller input set.

Set Difference: $\setminus$ or $-$

Set difference gives you 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. For example, $\{1,2,3\} \setminus \{2,3,4\} = \{1\}$, but $\{2,3,4\} \setminus \{1,2,3\} = \{4\}$.
• Relates to complement. $A \setminus B = A \cap B'$ when working within a universal set.

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

The complement is everything in the universal set that's 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'$
  • $(A \cap B)' = A' \cup B'$

These laws are worth memorizing. The pattern: when you "push" the complement through, union and intersection swap.

---

Counting and Constructing New Sets

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

Cardinality: $|A|$

Cardinality counts the number of elements in a set. If $A = \{a, b, c\}$, then $|A| = 3$.

• Inclusion-exclusion principle for unions: $|A \cup B| = |A| + |B| - |A \cap B|$. You subtract the intersection because those elements got counted twice.
• For three sets: $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$.
• Infinite sets have cardinality too, but for this course, focus on finite sets.

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

The power set is the set of all subsets of $A$, including $\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 a given subset, giving 2 choices per element.
• Example: $\mathcal{P}(\{1, 2\}) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$. That's $2^2 = 4$ subsets from two elements.
• Note the types: Elements of $\mathcal{P}(A)$ are sets, not individual elements. So $\{1\} \in \mathcal{P}(\{1, 2\})$ is true, but $1 \in \mathcal{P}(\{1, 2\})$ is false.

Cartesian Product: $\times$

The Cartesian product gives 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|$. The pair $(1, 2)$ is different from $(2, 1)$.
• Foundation for relations and functions. Any relation $R$ from $A$ to $B$ is a subset of $A \times B$, and any function $f: A \to B$ is a special kind of relation.
• Example: If $A = \{1, 2\}$ and $B = \{x, y\}$, then $A \times B = \{(1,x), (1,y), (2,x), (2,y)\}$.

---

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\}$.