In the previous chapter we studied logical quantifiers — the universal (\( \forall \)) and the existential (\( \exists \)) — which let us make claims about all or some elements of a set. Now it’s time to put that concept on solid ground: sets.
Set theory is the fundamental language of mathematics. Nearly every branch of modern math — algebra, calculus, probability, statistics — is built on top of it.
In this chapter you’ll learn to work with sets precisely, to relate them to one another, and to operate on them using the same logical tools from previous chapters.
Primitive concept of a set
There are concepts in mathematics that are accepted without a formal definition: they are called primitive concepts. Just as “point” and “line” are primitives in geometry, set theory rests on three primitive ideas:
- Set — a collection of objects.
- Element — an object that belongs to a set.
- Membership — the relationship that ties an element to its set.
Even without formal definitions, we can still describe them clearly:
A set is any collection of objects, provided there’s a well-defined rule for deciding whether any given object belongs to it or not. The objects that make it up are called its elements.
Notation and the membership relation
Notation conventions
| Concept | Notation | Example |
|---|---|---|
| Sets | Capital letters | \( A, B, C, \dots, A_1, A_2, \dots \) |
| Elements | Lowercase letters | \( a, b, c, \dots, x_1, x_2, \dots \) |
The membership relation (\( \in \))
The membership relation links an element to a set:
\[ \text{(element)} \in \text{(set)} \]
- If \( x \) is an element of \( A \), we write \( x \in A \) and read “\( x \) belongs to \( A \)”.
- If \( x \) is not an element of \( A \), we write \( x \notin A \) and read “\( x \) does not belong to \( A \)”.
Connection with logic: Membership is a proposition. If \( p: x \in A \), then its negation is \( \neg p: x \notin A \). If \( p \) is true, \( \neg p \) is false, and vice versa — there is no middle ground.
Example. Consider:
\( A = \{x \in \mathbb{R} \mid x^2 – 4 = 0\} \) and \( B = \{x \in \mathbb{R} \mid x^2 + 4 = 0\} \)
- \( 2 \in A \) ✓ because \( 2^2 – 4 = 0 \)
- \( -2 \in A \) ✓ because \( (-2)^2 – 4 = 0 \)
- \( 3 \notin A \) ✗ because \( 3^2 – 4 = 5 \neq 0 \)
- \( 2 \notin B \) ✗ because \( 2^2 + 4 = 8 \neq 0 \) (in fact, \( B = \emptyset \) in \( \mathbb{R} \))
Venn – Euler Diagrams
To build intuition about sets, we represent them graphically using Venn diagrams (also called Venn – Euler diagrams). The idea is simple: draw a closed curve — a circle, oval, or any other shape — and place the elements of the set as points inside it.
The shape of the curve doesn’t matter; what counts is the boundary: everything inside belongs to the set, everything outside does not.
Examples.
1. Let \( A = \{1, 10, 12, 15\} \). Its Venn diagram is:
Each point inside the curve represents an element: \( 1 \in A \), \( 10 \in A \), \( 12 \in A \), \( 15 \in A \). Any number that does not appear inside the curve does not belong to \( A \).
2. Let \( A = \{-1, 3, -5, 0\} \). Its Venn diagram is:
Notice that the position of points inside the curve doesn’t matter, nor does the order in which they’re written — the set is the same either way. All that matters is which elements are inside.
Note: Later, when we work with operations between sets, Venn diagrams will allow us to visualize the union, intersection, difference, and complement immediately. They will be our favorite graphical tool throughout this chapter.
Describing sets
A set is well-defined when there’s no ambiguity about whether any object belongs to it. There are two ways to describe a set:
By extension
You simply list all the elements explicitly, separated by commas and enclosed in curly braces.
Examples:
- \( A = \{1, 2, 3, 4, 5, 6\} \)
- \( V = \{a, e, i, o, u\} \)
- \( B = \{2, 4, 6, 8, \dots\} \) (the ellipsis indicates the pattern continues)
By comprehension (set-builder notation)
Instead of listing elements, you describe what they all have in common — a rule or property that pins down exactly which objects qualify.
General notation: \( A = \{x \in U \mid P(x)\} \)
This reads: “\( A \) is the set of all \( x \) in the universe \( U \) such that \( P(x) \) is true”.
Connection with quantifiers: Do you remember the propositional functions from the previous chapter? The expression \( P(x) \) inside the notation \( \{x \in U \mid P(x)\} \) is exactly that: a property that depends on the variable \( x \). The set consists of all elements of the universe \( U \) for which that property is true.
Comparative table of examples
| By extension | By comprehension |
|---|---|
| \( A = \{1, 2, 3, 4, 5, 6\} \) | \( A = \{x \in \mathbb{Z} \mid 0 < x < 7\} \) |
| \( B = \{1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots\} \) | \( B = \{\frac{1}{n} \mid n \in \mathbb{Z}^+\} \) |
| \( D = \{2, 4, 6, 8, \dots\} \) | \( D = \{2n \mid n \in \mathbb{Z}^+\} \) (positive even numbers) |
| \( E = \{1, 3, 5, 7, \dots\} \) | \( E = \{2n-1 \mid n \in \mathbb{Z}^+\} \) (positive odd numbers) |
| \( G = \{5, 10, 15, 20, \dots\} \) | \( G = \{5n \mid n \in \mathbb{Z}^+\} \) |
Finite and infinite sets
Finite set
A set is finite if it has a specific, countable number of elements — some fixed natural number \( n \).
Examples:
- \( A = \{x \mid x \text{ is a vowel}\} = \{a, e, i, o, u\} \) — has 5 elements.
- \( B = \{x \in \mathbb{N} \mid 5 \leq x < 12\} = \{5, 6, 7, 8, 9, 10, 11\} \) — has 7 elements.
- \( C = \{x \mid x \text{ is a day of the week}\} \) — has 7 elements.
Infinite set
A set is infinite if it’s not finite — you simply can’t count all its elements with any natural number.
Examples:
- \( \mathbb{N} = \{0, 1, 2, 3, \dots\} \) — the natural numbers are infinite.
- \( \{x \in \mathbb{Z} \mid x \text{ is odd}\} = \{\dots, -3, -1, 1, 3, 5, \dots\} \) — the odd numbers are infinite.
- \( \{x \in \mathbb{R} \mid 0 < x < 1\} \) — the open interval \( (0, 1) \) contains infinitely many real numbers.
Note: Sets defined by comprehension with an ellipsis (\( \dots \)) are usually infinite, while those listed completely by extension are finite.
Special sets
Empty set (\( \emptyset \))
The empty set has no elements — we write it as \( \emptyset \) or \( \{\} \).
\[ \emptyset = \{x \mid x \neq x\} \]
Since no object is distinct from itself, this set is empty.
Examples:
- \( \{x \in \mathbb{R} \mid x^2 + 1 = 0\} = \emptyset \) because there’s no real number whose square is \( -1 \).
- \( \{x \in \mathbb{N} \mid 2 < x < 3\} = \emptyset \) because there’s no natural number between 2 and 3.
Fundamental property: The empty set is included in every set: \( \emptyset \subset A \), for any set \( A \). The concept of inclusion will be explained shortly.
Why? The statement \( \forall x: x \in \emptyset \implies x \in A \) is vacuously true — there’s no \( x \in \emptyset \) that could ever make it false. (Remember: \( F \implies q \) is always \( T \).)
Universal set (\( U \))
The universal set is the reference set containing every element under consideration in a given context.
\[ U = \{x \mid x = x\} \]
In a Venn diagram, the universal set is represented as a rectangle that frames all other sets.
Singleton set
A singleton is a set with exactly one element. Given \( a \in U \):
\[ \{a\} = \{x \in U \mid x = a\} \]
Examples:
- \( \{x \in \mathbb{R} \mid x + 2 = 0\} = \{-2\} \)
- \( \{x \in \mathbb{N} \mid 1 < x < 3\} = \{2\} \)
Relations between sets
Given two sets, the fundamental relations between them are inclusion and equality.
Inclusion of sets (subsets)
A set \( A \) is included in \( B \) (or is a subset of \( B \)) if every element of \( A \) also belongs to \( B \).
\[ A \subset B \iff \forall x: (x \in A \implies x \in B) \]
We say “\( A \) is included in \( B \)”, or equivalently “\( A \) is a subset of \( B \)”, “\( A \) is contained in \( B \)”, or “\( A \) is part of \( B \)”. You’ll also see it flipped as \( B \supset A \), which reads “\( B \) contains \( A \)”.
Its negation: \( A \not\subset B \iff \exists x: (x \in A \wedge x \notin B) \)
Notice how quantifiers are used: inclusion uses \( \forall \) with implication, and its negation uses \( \exists \) with conjunction — exactly the negation rules we learned.
Graphically, Venn diagrams allow us to visualize the three possible cases:
Example. Let \( A = \{2, 4, 6, 8\} \) and \( B = \{2, 4, 6, 8, 10, 12\} \).
Let’s check that \( A \subset B \):
- \( 2 \in A \) and \( 2 \in B \) ✓
- \( 4 \in A \) and \( 4 \in B \) ✓
- \( 6 \in A \) and \( 6 \in B \) ✓
- \( 8 \in A \) and \( 8 \in B \) ✓
Every element of \( A \) shows up in \( B \), so \( A \subset B \). ✓
Counterexample. Let \( M = \{a, b, c, d, e\} \) and \( N = \{b, c, d, m, n\} \).
- \( a \in M \) but \( a \notin N \) ✗
That’s all it takes — one counterexample is enough to conclude \( M \not\subset N \).
Proper subset
We say \( A \) is a proper subset of \( B \) if \( A \subset B \) but \( A \neq B \) — \( B \) has at least one element \( A \) doesn’t. Denoted \( A \subsetneq B \).
Properties of inclusion
| Property | Statement | Name |
|---|---|---|
| Inc.1 | \( A \subset A \) | Reflexive |
| Inc.2 | If \( A \subset B \) and \( B \subset C \), then \( A \subset C \) | Transitive |
| Inc.3 | If \( A \subset B \) and \( B \subset A \), then \( A = B \) | Antisymmetric |
| Inc.4 | \( \emptyset \subset A \), for every set \( A \) | Empty set included in all |
Proof of Inc.2 (Transitive):
- \( A \subset B \) — hypothesis
- \( \forall x: x \in A \implies x \in B \) — by definition of \( \subset \)
- \( B \subset C \) — hypothesis
- \( \forall x: x \in B \implies x \in C \) — by definition of \( \subset \)
- \( \forall x: x \in A \implies x \in C \) — by hypothetical syllogism (from 2 and 4): \( (p \implies q) \wedge (q \implies r) \implies (p \implies r) \)
- \( \therefore A \subset C \) — by definition of \( \subset \)
Equality of sets
Two sets are equal if and only if they have the same elements. Formally:
\[ A = B \iff (A \subset B \wedge B \subset A) \]
In other words, to prove two sets are equal, you show each one sits inside the other — a strategy called double inclusion.
Properties of equality:
| Property | Statement | Name |
|---|---|---|
| E.1 | \( A = A \) | Reflexive |
| E.2 | If \( A = B \), then \( B = A \) | Symmetric |
| E.3 | If \( A = B \) and \( B = C \), then \( A = C \) | Transitive |
Disjoint sets
Two sets \( A \) and \( B \) are disjoint if they have no element in common. Symbolically:
\[ A \text{ and } B \text{ are disjoint} \iff \nexists, x : (x \in A \wedge x \in B) \]
In other words, their intersection is empty: \( A \cap B = \emptyset \) (we’ll define intersection formally in a moment).
Examples:
- \( A = \{1, 3, 5, 7\} \) and \( B = \{2, 4, 6, 8\} \) are disjoint, since they share no element. ✓
- \( A = \{a, b, c, d\} \) and \( B = \{r, s, t, u\} \) are disjoint. ✓
- \( A = \{1, 2, 3\} \) and \( B = \{3, 4, 5\} \) are not disjoint, because \( 3 \in A \wedge 3 \in B \). ✗
Number sets
The standard number sets nest inside one another in a hierarchy every math student should know cold:
1. Natural numbers (\( \mathbb{N} \))
\[ \mathbb{N} = \{0, 1, 2, 3, 4, 5, \dots\} \]
These are the counting numbers, including zero.
Is zero a natural number? It depends on the author and convention. Many textbooks on logic, set theory, and the ISO 80000-2 standard include zero: \( \mathbb{N} = \{0, 1, 2, \dots\} \). Other texts, especially from classical tradition and number theory, exclude it: \( \mathbb{N} = \{1, 2, 3, \dots\} \). To distinguish both cases, \( \mathbb{N}_0 \) is often used when zero is included, and \( \mathbb{N}^* \) or \( \mathbb{Z}^+ \) when it is excluded. We’ll go with the convention that includes zero.
2. Integers (\( \mathbb{Z} \))
\[ \mathbb{Z} = \{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\} \]
These extend the natural numbers by adding the negatives.
3. Rational numbers (\( \mathbb{Q} \))
\[ \mathbb{Q} = \left\{\frac{m}{n} ;\middle|; m \in \mathbb{Z} \wedge n \in \mathbb{Z},; n \neq 0\right\} \]
Any number that can be expressed as a ratio of two integers. Their decimal expansion is either terminating or repeating.
4. Irrational numbers (\( \mathbb{I} \))
Real numbers that are not rational. Their decimal expansion is infinite and non-repeating.
Famous examples: \( \sqrt{2} \approx 1.4142\dots \), \( \pi \approx 3.1416\dots \), \( e \approx 2.7182\dots \)
5. Real numbers (\( \mathbb{R} \))
\[ \mathbb{R} = \mathbb{Q} \cup \mathbb{I} \]
The union of rationals and irrationals, represented geometrically by the real number line.
6. Complex numbers (\( \mathbb{C} \))
\[ \mathbb{C} = \{a + bi \mid a \in \mathbb{R} \wedge b \in \mathbb{R},; i = \sqrt{-1}\} \]
These extend the real numbers by introducing the imaginary unit \( i \).
The number-set hierarchy
These sets nest inside one another like Russian dolls:
\[ \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C} \]
Also worth noting: \( \mathbb{Q} \cap \mathbb{I} = \emptyset \) (no number is both rational and irrational) and \( \mathbb{Q} \cup \mathbb{I} = \mathbb{R} \).
Set operations
Just as we have arithmetic operations (addition, subtraction, multiplication), sets have their own operations. Each operation has an associated logical connective:
| Operation | Symbol | Associated logical connective |
|---|---|---|
| Union | \( \cup \) | Disjunction \( \vee \) (“or”) |
| Intersection | \( \cap \) | Conjunction \( \wedge \) (“and”) |
| Difference | \( – \) | Conjunction with negation \( \wedge \neg \) |
| Complement | \( A’ \) | Negation \( \neg \) |
| Symmetric difference | \( \triangle \) | Exclusive disjunction \( \oplus \) (XOR) |
This isn’t a coincidence — set operations inherit the properties of their corresponding logical connectives.
Union of sets (\( A \cup B \))
The union of \( A \) and \( B \) is the set of elements that belong to \( A \), to \( B \), or to both.
\[ A \cup B = \{x \mid x \in A \vee x \in B\} \]
We say “\( A \) union \( B \)” — it’s everything that shows up in \( A \), in \( B \), or in both.
Characterization: \( x \in (A \cup B) \iff x \in A \vee x \in B \)
Negation: \( x \notin (A \cup B) \iff x \notin A \wedge x \notin B \)
When \( A \) and \( B \) are disjoint (no elements in common), the union simply brings together both sets with no overlap:
Detailed example. Let \( A = \{1, 2, 3, 4\} \) and \( B = \{3, 4, 5, 6\} \). Find \( A \cup B \).
Let’s check each candidate against the condition \( x \in A \vee x \in B \):
| \( x \) | \( x \in A \)? | \( x \in B \)? | \( x \in A \vee x \in B \) | \( x \in A \cup B \)? |
|---|---|---|---|---|
| 1 | ✓ | ✗ | T ∨ F = T | ✓ |
| 2 | ✓ | ✗ | T ∨ F = T | ✓ |
| 3 | ✓ | ✓ | T ∨ T = T | ✓ |
| 4 | ✓ | ✓ | T ∨ T = T | ✓ |
| 5 | ✗ | ✓ | F ∨ T = T | ✓ |
| 6 | ✗ | ✓ | F ∨ T = T | ✓ |
\( \therefore A \cup B = \{1, 2, 3, 4, 5, 6\} \)
Notice that even though 3 and 4 appear in both sets, they only show up once in the union — sets don’t have duplicate elements.
Properties of union
| Code | Property | Name |
|---|---|---|
| U.1 | \( A \cup \emptyset = A \) | Identity element |
| U.2 | \( A \cup U = U \) | Absorbing element |
| U.3 | \( A \cup A = A \) | Idempotence |
| U.4 | \( A \cup B = B \cup A \) | Commutative |
| U.5 | \( (A \cup B) \cup C = A \cup (B \cup C) \) | Associative |
| U.6 | \( A \subset A \cup B \) | Upper bound |
| U.7 | \( A \subset B \iff A \cup B = B \) | Inclusion criterion |
| U.8 | If \( A \cup B = \emptyset \), then \( A = \emptyset \wedge B = \emptyset \) | — |
| U.9 | \( A \cup (A \cap B) = A \) | Absorption |
Proof of U.3 (Idempotence): \( A \cup A = A \)
We prove both inclusions.
(I) \( A \cup A \subset A \):
(1) Let \( x \in (A \cup A) \) — hypothesis
(2) \( \implies x \in A \vee x \in A \) — definition of \( \cup \)
(3) \( \implies x \in A \) — by tautology \( p \vee p \iff p \)
(4) \( \therefore A \cup A \subset A \) — from (1) and (3), by definition of \( \subset \)
(II) \( A \subset A \cup A \):
(5) Let \( x \in A \) — hypothesis
(6) \( \implies x \in A \vee x \in A \) — by tautology \( p \iff p \vee p \)
(7) \( \implies x \in (A \cup A) \) — definition of \( \cup \)
(8) \( \therefore A \subset A \cup A \) — from (5) and (7)
From (I) and (II): \( A \cup A = A \). ∎
Intersection of sets (\( A \cap B \))
The intersection of \( A \) and \( B \) is the set of elements common to both.
\[ A \cap B = \{x \mid x \in A \wedge x \in B\} \]
We say “\( A \) intersection \( B \)” — it’s everything that belongs to both \( A \) and \( B \) at the same time.
Characterization: \( x \in (A \cap B) \iff x \in A \wedge x \in B \)
Negation: \( x \notin (A \cap B) \iff x \notin A \vee x \notin B \)
Disjoint sets: If \( A \) and \( B \) have no elements in common, they are said to be disjoint: \( A \cap B = \emptyset \).
When \( A \) and \( B \) are disjoint, they share no elements, so their intersection is empty:
Detailed example. Let \( A = \{a, b, c, d, e\} \), \( B = \{m, n, a, d\} \) and \( C = \{s, a, t, c, d\} \). Find \( A \cap B \), \( B \cap C \) and \( A \cap B \cap C \).
For \( A \cap B \), we check each element against \( x \in A \wedge x \in B \):
| \( x \) | \( x \in A \)? | \( x \in B \)? | \( x \in A \wedge x \in B \) | \( x \in A \cap B \)? |
|---|---|---|---|---|
| a | ✓ | ✓ | T ∧ T = T | ✓ |
| b | ✓ | ✗ | T ∧ F = F | ✗ |
| c | ✓ | ✗ | T ∧ F = F | ✗ |
| d | ✓ | ✓ | T ∧ T = T | ✓ |
| e | ✓ | ✗ | T ∧ F = F | ✗ |
\( \therefore A \cap B = \{a, d\} \)
Similarly: \( B \cap C = \{a, d\} \) and \( A \cap B \cap C = \{a, d\} \).
Properties of intersection
| Code | Property | Name |
|---|---|---|
| I.1 | \( A \cap U = A \) | Identity element |
| I.2 | \( A \cap \emptyset = \emptyset \) | Absorbing element |
| I.3 | \( A \cap A = A \) | Idempotence |
| I.4 | \( A \cap B = B \cap A \) | Commutative |
| I.5 | \( (A \cap B) \cap C = A \cap (B \cap C) \) | Associative |
| I.6 | \( A \cap B \subset A \) | Lower bound |
| I.7 | \( A \subset B \iff A \cap B = A \) | Inclusion criterion |
| I.8 | \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \) | Distributive of \( \cap \) over \( \cup \) |
| I.9 | \( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \) | Distributive of \( \cup \) over \( \cap \) |
| I.10 | \( A \cap (A \cup B) = A \) | Absorption |
Properties I.8 and I.9 are the distributive laws. Both have the same form as distribution in logic: \( p \wedge (q \vee r) \iff (p \wedge q) \vee (p \wedge r) \) and \( p \vee (q \wedge r) \iff (p \vee q) \wedge (p \vee r) \).
Set difference (\( A – B \))
The difference of \( A \) and \( B \) is the set of elements that belong to \( A \) but not to \( B \).
\[ A – B = \{x \mid x \in A \wedge x \notin B\} \]
We say “\( A \) minus \( B \)” — you start with \( A \) and remove anything that also appears in \( B \).
Characterization: \( x \in (A – B) \iff x \in A \wedge x \notin B \)
When \( A \) and \( B \) are disjoint, there’s nothing to take away from \( A \), so \( A – B = A \):
Detailed example. Let \( A = \{1, 2, 3, 4\} \) and \( B = \{2, 4, 5, 6\} \). Find \( A – B \) and \( B – A \).
For \( A – B \):
- \( 1 \in A \wedge 1 \notin B \) → \( 1 \in A – B \) ✓
- \( 2 \in A \wedge 2 \in B \) → \( 2 \notin A – B \) ✗
- \( 3 \in A \wedge 3 \notin B \) → \( 3 \in A – B \) ✓
- \( 4 \in A \wedge 4 \in B \) → \( 4 \notin A – B \) ✗
\( \therefore A – B = \{1, 3\} \)
For \( B – A \):
- \( 5 \in B \wedge 5 \notin A \) → \( 5 \in B – A \) ✓
- \( 6 \in B \wedge 6 \notin A \) → \( 6 \in B – A \) ✓
- \( 2 \in B \wedge 2 \in A \) → \( 2 \notin B – A \) ✗
- \( 4 \in B \wedge 4 \in A \) → \( 4 \notin B – A \) ✗
\( \therefore B – A = \{5, 6\} \)
Important: In general, \( A – B \neq B – A \). Set difference is not commutative.
Properties of set difference
| Code | Property |
|---|---|
| D.1 | \( A – A = \emptyset \) |
| D.2 | \( A – \emptyset = A \) |
| D.3 | \( \emptyset – A = \emptyset \) |
| D.4 | \( (A – B) \subset A \) |
| D.5 | \( A – B = A – (A \cap B) \) |
| D.6 | \( B \cap (A – B) = \emptyset \) |
| D.7 | \( A – (B \cup C) = (A – B) \cap (A – C) \) |
| D.8 | \( A – (B \cap C) = (A – B) \cup (A – C) \) |
Properties D.7 and D.8 are the De Morgan Laws for set difference. Notice the analogy with logic: \( \neg(p \vee q) \equiv \neg p \wedge \neg q \) and \( \neg(p \wedge q) \equiv \neg p \vee \neg q \).
Proof of D.1: \( A – A = \emptyset \)
- Let \( x \in (A – A) \) — hypothesis
- \( \implies x \in A \wedge x \notin A \) — definition of difference
- This is a contradiction (\( p \wedge \neg p \equiv F \)), so no element can belong to \( A – A \).
- \( \therefore A – A = \emptyset \) ∎
Complement of a set (\( A’ \))
Given \( A \subset U \), the complement of \( A \) is everything in the universe that falls outside \( A \).
\[ A’ = U – A = \{x \mid x \in U \wedge x \notin A\} = \{x \mid x \notin A\} \]
We say “\( A \) prime” or “the complement of \( A \).”
Characterization: \( x \in A’ \iff x \notin A \)
Alternative notations: Some textbooks write the complement as \( \overline{A} \) or \( A^c \). All three — \( A’ \), \( \overline{A} \), and \( A^c \) — mean the same thing. We’ll use \( A’ \) throughout.
Relative complement: If \( A \subset B \), the complement of \( A \) with respect to \( B \) is denoted \( C_B A = B – A \).
Example. If \( U = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} \) and \( A = \{5, 6, 7, 8\} \):
\( A’ = U – A = \{1, 2, 3, 4, 9, 10\} \)
Quick check: \( A \cup A’ = U \) ✓ and \( A \cap A’ = \emptyset \) ✓
Properties of the complement
| Code | Property | Name |
|---|---|---|
| C.1 | \( (A’)’ = A \) | Involution (double complement) |
| C.2 | \( A \cup A’ = U \) | Complementarity in union |
| C.3 | \( A \cap A’ = \emptyset \) | Complementarity in intersection |
| C.4 | \( U’ = \emptyset \) | Complement of the universal set |
| C.5 | \( \emptyset’ = U \) | Complement of the empty set |
| C.6 | \( A – B = A \cap B’ \) | Difference as intersection |
| C.7 | If \( A \subset B \), then \( B’ \subset A’ \) | Contrapositive of inclusion |
Proof of C.6: \( A – B = A \cap B’ \)
(a) \( (A – B) \subset (A \cap B’) \):
- Let \( x \in (A – B) \) → \( x \in A \wedge x \notin B \) — definition of difference
- \( \implies x \in A \wedge x \in B’ \) — definition of complement
- \( \implies x \in (A \cap B’) \) — definition of \( \cap \)
(b) \( (A \cap B’) \subset (A – B) \):
- Let \( x \in (A \cap B’) \) → \( x \in A \wedge x \in B’ \) — definition of \( \cap \)
- \( \implies x \in A \wedge x \notin B \) — definition of complement
- \( \implies x \in (A – B) \) — definition of difference
From (a) and (b): \( A – B = A \cap B’ \). ∎
De Morgan’s Laws
De Morgan’s Laws connect complements with unions and intersections. They are one of the most powerful tools in set theory.
De Morgan’s Law 1: \( (A \cup B)’ = A’ \cap B’ \)
The complement of the union is the intersection of the complements.
De Morgan’s Law 2: \( (A \cap B)’ = A’ \cup B’ \)
The complement of the intersection is the union of the complements.
Proof of Law 2: \( (A \cap B)’ = A’ \cup B’ \)
(a) \( (A \cap B)’ \subset A’ \cup B’ \):
- Let \( x \in (A \cap B)’ \) — hypothesis
- \( \implies x \notin (A \cap B) \) — definition of complement
- \( \implies x \notin A \vee x \notin B \) — by logic: \( \neg(p \wedge q) \equiv \neg p \vee \neg q \)
- \( \implies x \in A’ \vee x \in B’ \) — definition of complement
- \( \implies x \in (A’ \cup B’) \) — definition of \( \cup \)
- \( \therefore (A \cap B)’ \subset A’ \cup B’ \) — from (1) and (5)
(b) \( A’ \cup B’ \subset (A \cap B)’ \):
- Let \( x \in (A’ \cup B’) \) — hypothesis
- \( \implies x \in A’ \vee x \in B’ \) — definition of \( \cup \)
- \( \implies x \notin A \vee x \notin B \) — definition of complement
- \( \implies x \notin (A \cap B) \) — by logic: \( \neg p \vee \neg q \equiv \neg(p \wedge q) \)
- \( \implies x \in (A \cap B)’ \) — definition of complement
- \( \therefore A’ \cup B’ \subset (A \cap B)’ \) — from (1) and (5)
From (a) and (b): \( (A \cap B)’ = A’ \cup B’ \). ∎
Connection with logic: De Morgan’s Laws for sets are exactly De Morgan’s Laws for propositions, translated via the correspondence \( \cup \leftrightarrow \vee \), \( \cap \leftrightarrow \wedge \), \( ‘ \leftrightarrow \neg \).
Symmetric difference (\( A \triangle B \))
The symmetric difference of \( A \) and \( B \) contains the elements that are in one or the other, but not in both.
\[ A \triangle B = (A – B) \cup (B – A) = (A \cup B) – (A \cap B) \]
We say “\( A \) symmetric difference \( B \)” — it keeps everything that’s in one set or the other, but throws out anything the two have in common.
Characterization: \( x \in (A \triangle B) \iff (x \in A \wedge x \notin B) \vee (x \notin A \wedge x \in B) \)
In logic, this operation corresponds to exclusive disjunction (XOR): \( p \oplus q \).
When \( A \) and \( B \) are disjoint, there are no common elements to exclude, so the symmetric difference coincides with the union: \( A \triangle B = A \cup B \).
Example. Let \( A = \{1, 2, 3, 4\} \) and \( B = \{2, 3, 5, 6\} \). Find \( A \triangle B \).
Method 1 (by differences): \( A – B = \{1, 4\} \) and \( B – A = \{5, 6\} \) \( A \triangle B = \{1, 4\} \cup \{5, 6\} = \{1, 4, 5, 6\} \)
Method 2 (by union minus intersection): \( A \cup B = \{1, 2, 3, 4, 5, 6\} \) and \( A \cap B = \{2, 3\} \) \( A \triangle B = \{1, 2, 3, 4, 5, 6\} – \{2, 3\} = \{1, 4, 5, 6\} \) ✓
Properties of symmetric difference
| Code | Property | Name |
|---|---|---|
| DS.1 | \( A \triangle A = \emptyset \) | — |
| DS.2 | \( A \triangle \emptyset = A \) | Identity element |
| DS.3 | \( A \triangle B = B \triangle A \) | Commutative |
| DS.4 | \( (A \triangle B) \triangle C = A \triangle (B \triangle C) \) | Associative |
| DS.5 | \( (A \triangle B) \cap C = (A \cap C) \triangle (B \cap C) \) | Distributive with \( \cap \) |
Power set (\( \mathcal{P}(A) \))
Given a set \( A \), its power set \( \mathcal{P}(A) \) is the set of all possible subsets of \( A \) — including \( \emptyset \) and \( A \) itself.
\[ \mathcal{P}(A) = \{X \mid X \subset A\} \]
Key property: \( X \in \mathcal{P}(A) \iff X \subset A \)
If \( A \) has \( n \) elements, then \( \mathcal{P}(A) \) has \( 2^n \) elements.
Detailed examples
1. If \( A = \{1, 2\} \), then \( n(A) = 2 \):
\( \mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\} \)
Verification: \( n[\mathcal{P}(A)] = 2^2 = 4 \) ✓
2. If \( B = \{a, \{1, b\}, c\} \), then \( n(B) = 3 \):
The elements of \( B \) are: \( a \), \( \{1, b\} \) (a set as an element) and \( c \).
\( \mathcal{P}(B) = \{\emptyset, \{a\}, \{\{1, b\}\}, \{c\}, \{a, \{1, b\}\}, \{a, c\}, \{\{1, b\}, c\}, B\} \)
Verification: \( n[\mathcal{P}(B)] = 2^3 = 8 \) ✓
Caution: \( \{1, b\} \) is an element of \( B \), not a subset. That is why the singleton \( \{\{1, b\}\} \) is a subset of \( B \), but \( \{1, b\} \) by itself is not (since \( 1 \notin B \)).
Properties of the power set
| Code | Property |
|---|---|
| P.1 | \( a \in A \iff \{a\} \in \mathcal{P}(A) \) |
| P.2 | \( B \subset A \iff B \in \mathcal{P}(A) \) |
| P.3 | \( \emptyset \in \mathcal{P}(A) \) and \( A \in \mathcal{P}(A) \), for every \( A \) |
| P.4 | \( \mathcal{P}(\emptyset) = \{\emptyset\} \) |
| P.5 | \( A \subset B \implies \mathcal{P}(A) \subset \mathcal{P}(B) \) |
| P.6 | \( \mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B) \) |
| P.7 | \( \mathcal{P}(A) \cup \mathcal{P}(B) \subset \mathcal{P}(A \cup B) \) |
| P.8 | \( A = B \iff \mathcal{P}(A) = \mathcal{P}(B) \) |
Number of elements of a set
The cardinality (or number of elements) of a set \( A \), denoted \( n(A) \) or \( |A| \), is simply the count of distinct elements it contains.
Examples:
| Set | Elements | \( n \) |
|---|---|---|
| \( A = \{1, 3, 5, 6\} \) | 1, 3, 5, 6 | \( n(A) = 4 \) |
| \( B = \{a, b, c, d, e\} \) | a, b, c, d, e | \( n(B) = 5 \) |
| \( C = \{2, 4, 2, 4, 2\} \) | 2, 4 (repeated ones don’t count) | \( n(C) = 2 \) |
| \( D = \emptyset \) | none | \( n(D) = 0 \) |
Note: Sets don’t have repeated elements. Even if you write \( C = \{2, 4, 2, 4, 2\} \), that’s just \( C = \{2, 4\} \), so \( n(C) = 2 \).
Properties of the number of elements
Property 1. If \( A \) and \( B \) are disjoint (\( A \cap B = \emptyset \)):
\[ n(A \cup B) = n(A) + n(B) \]
Property 2. For any pair of finite sets:
\[ n(A – B) = n(A) – n(A \cap B) \]
This makes intuitive sense: once you strip away from \( A \) everything it has in common with \( B \), only the elements unique to \( A \) are left.
Inclusion-exclusion principle
Property 3. (Formula for two sets)
If \( A \) and \( B \) are finite sets:
\[ n(A \cup B) = n(A) + n(B) – n(A \cap B) \]
Why subtract the intersection? Because when you add \( n(A) + n(B) \), the elements in both sets get counted twice.
Special case: If \( A \cap B = \emptyset \) (disjoint), this reduces to Property 1: \( n(A \cup B) = n(A) + n(B) \).
Example. In a group of 40 students, 25 study mathematics, 20 study physics, and 10 study both. How many study at least one?
\( n(M \cup F) = n(M) + n(F) – n(M \cap F) = 25 + 20 – 10 = 35 \)
Property 4. (Formula for three sets)
\[ n(A \cup B \cup C) = n(A) + n(B) + n(C) – n(A \cap B) – n(A \cap C) – n(B \cap C) + n(A \cap B \cap C) \]
Proof:
\( n(A \cup B \cup C) = n[A \cup (B \cup C)] \)
\( = n(A) + n(B \cup C) – n[A \cap (B \cup C)] \) — formula for 2 sets
\( = n(A) + n(B) + n(C) – n(B \cap C) – n[(A \cap B) \cup (A \cap C)] \) — distributive and formula for 2
\( = n(A) + n(B) + n(C) – n(B \cap C) – [n(A \cap B) + n(A \cap C) – n(A \cap B \cap C)] \)
\( \therefore n(A \cup B \cup C) = n(A) + n(B) + n(C) – n(A \cap B) – n(A \cap C) – n(B \cap C) + n(A \cap B \cap C) \)
The three-set Venn diagram with mutual intersections generates 7 regions:
- \( n_1 \): only in \( A \)
- \( n_2 \): only in \( B \)
- \( n_3 \): only in \( C \)
- \( n_5 \): only in \( A \cap B \)
- \( n_4 \): only in \( A \cap C \)
- \( n_6 \): only in \( B \cap C \)
- \( n_7 \): in \( A \cap B \cap C \)
Summary of properties
| Law | Union (\( \cup \)) | Intersection (\( \cap \)) |
|---|---|---|
| Idempotence | \( A \cup A = A \) | \( A \cap A = A \) |
| Commutative | \( A \cup B = B \cup A \) | \( A \cap B = B \cap A \) |
| Associative | \( (A \cup B) \cup C = A \cup (B \cup C) \) | \( (A \cap B) \cap C = A \cap (B \cap C) \) |
| Identity | \( A \cup \emptyset = A \) | \( A \cap U = A \) |
| Absorbing | \( A \cup U = U \) | \( A \cap \emptyset = \emptyset \) |
| Complement | \( A \cup A’ = U \) | \( A \cap A’ = \emptyset \) |
| De Morgan | \( (A \cup B)’ = A’ \cap B’ \) | \( (A \cap B)’ = A’ \cup B’ \) |
| Distributive | \( A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \) | \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \) |
| Absorption | \( A \cup (A \cap B) = A \) | \( A \cap (A \cup B) = A \) |
| Involution | \( (A’)’ = A \) | |
| Difference | \( A – B = A \cap B’ \) | \( n(A – B) = n(A) – n(A \cap B) \) |
| Sym. difference | \( A \triangle B = (A – B) \cup (B – A) \) | \( A \triangle B = (A \cup B) – (A \cap B) \) |
| Inclusion-exclusion | \( n(A \cup B) = n(A) + n(B) – n(A \cap B) \) |
Solved exercises
Exercise 1. If \( U = \{1, 2, 3, 4, 5, 6, 7, 8, 9\} \), \( A = \{2, 4, 6, 8\} \), \( B = \{1, 3, 5, 7, 9\} \) and \( C = \{3, 4, 5\} \). Find \( (A \cup C)’ \cap B \).
Solution:
- \( A \cup C = \{2, 3, 4, 5, 6, 8\} \)
- \( (A \cup C)’ = U – (A \cup C) = \{1, 7, 9\} \)
- \( (A \cup C)’ \cap B = \{1, 7, 9\} \cap \{1, 3, 5, 7, 9\} = \{1, 7, 9\} \)
Exercise 2. Simplify \( F – (F – G) \) using definitions.
Solution:
\( F – (F – G) \)
\( \equiv x \in F \wedge x \notin (F – G) \) — def. of difference
\( \equiv x \in F \wedge \neg(x \in F \wedge x \notin G) \) — def. of difference
\( \equiv x \in F \wedge (x \notin F \vee x \in G) \) — De Morgan: \( \neg(p \wedge q) \equiv \neg p \vee \neg q \)
\( \equiv (x \in F \wedge x \notin F) \vee (x \in F \wedge x \in G) \) — distributive
\( \equiv \text{False} \vee (x \in F \wedge x \in G) \) — contradiction: \( p \wedge \neg p \) is always false
\( \equiv x \in F \wedge x \in G \) — identity: \( \text{False} \vee q \equiv q \)
\( \equiv x \in (F \cap G) \) — definition of \( \cap \)
\( \therefore F – (F – G) = F \cap G \) ✓
Exercise 3. Prove that \( (A – B) \cup (B – A) = (A \cup B) – (A \cap B) \).
Proof:
\( (A – B) \cup (B – A) \)
\( = (A \cap B’) \cup (B \cap A’) \) — by C.6: \( X – Y = X \cap Y’ \)
\( = [(A \cap B’) \cup B] \cap [(A \cap B’) \cup A’] \) — distributive of \( \cup \) over \( \cap \)
\( = [(A \cup B) \cap (B’ \cup B)] \cap [(A \cup A’) \cap (B’ \cup A’)] \) — distributive
\( = [(A \cup B) \cap U] \cap [U \cap (A’ \cup B’)] \) — by C.2: \( X \cup X’ = U \)
\( = (A \cup B) \cap (A’ \cup B’) \) — by I.1: \( X \cap U = X \)
\( = (A \cup B) \cap (A \cap B)’ \) — by De Morgan (Law 1)
\( = (A \cup B) – (A \cap B) \) — by C.6 ∎
Exercise 4. If \( A = \{1, 2, 3\} \), determine \( \mathcal{P}(A) \) and verify that its cardinality is \( 2^{n(A)} \).
Solution:
\( A \) has three elements (\( n(A) = 3 \)). Here are all its subsets, grouped by size:
| Subsets with 0 elements | Subsets with 1 element | Subsets with 2 elements | Subsets with 3 elements |
|---|---|---|---|
| \( \emptyset \) | \( \{1\} \), \( \{2\} \), \( \{3\} \) | \( \{1, 2\} \), \( \{1, 3\} \), \( \{2, 3\} \) | \( \{1, 2, 3\} \) |
\( \therefore \mathcal{P}(A) = \{\emptyset,; \{1\},; \{2\},; \{3\},; \{1, 2\},; \{1, 3\},; \{2, 3\},; \{1, 2, 3\}\} \)
That gives \( n[\mathcal{P}(A)] = 2^3 = 8 \) ✓
Exercise 5. A survey of 100 students found: 50 study Mathematics (\( M \)), 40 study Physics (\( F \)), 35 study Chemistry (\( Q \)), 20 study both Math and Physics, 15 study both Math and Chemistry, 10 study both Physics and Chemistry, and 5 study all three. How many students study none of the three?
Solution:
Data: \( n(U) = 100 \), \( n(M) = 50 \), \( n(F) = 40 \), \( n(Q) = 35 \), \( n(M \cap F) = 20 \), \( n(M \cap Q) = 15 \), \( n(F \cap Q) = 10 \), \( n(M \cap F \cap Q) = 5 \).
We apply the inclusion-exclusion formula for three sets:
\[ n(M \cup F \cup Q) = n(M) + n(F) + n(Q) – n(M \cap F) – n(M \cap Q) – n(F \cap Q) + n(M \cap F \cap Q) \]
\[ n(M \cup F \cup Q) = 50 + 40 + 35 – 20 – 15 – 10 + 5 = 85 \]
So the number of students who don’t study any of the three:
\[ n(M \cup F \cup Q)’ = n(U) – n(M \cup F \cup Q) = 100 – 85 = 15 \]
\( \therefore \) 15 students study none of the three subjects. ✓
Exercise 6. Prove the absorption law: \( A \cup (A \cap B) = A \).
Proof:
We’ll show both inclusions hold.
(I) \( A \subset A \cup (A \cap B) \):
By property U.6, every set is a subset of any union it appears in — so this holds automatically. ✓
(II) \( A \cup (A \cap B) \subset A \):
- Let \( x \in A \cup (A \cap B) \) — hypothesis
- \( \implies x \in A \vee (x \in A \wedge x \in B) \) — def. of \( \cup \) and \( \cap \)
- Case 1: If \( x \in A \), then \( x \in A \). ✓
- Case 2: If \( x \in A \wedge x \in B \), then \( x \in A \) by simplification (\( p \wedge q \implies p \)). ✓
- In both cases, \( x \in A \).
- \( \therefore A \cup (A \cap B) \subset A \)
From (I) and (II): \( A \cup (A \cap B) = A \). ∎
What’s next?
With set theory under your belt, you’re ready for the topics that build directly on it: relations, functions, and the Cartesian product. Sets will serve as the domains and codomains of functions, and everything we covered here will let you work rigorously across any area of mathematics.
Did you find this post useful? Drop a comment with your questions or suggestions — and stay tuned for the next installment in this series!