Set notation, membership, subsets, operations, Venn diagrams, Cartesian products, predicates, quantifiers, and relations — the precise language that unifies logic, proof, and computing
This chapter introduces one of the most important languages in all of modern mathematics and computer science: the language of sets. A set is a precise way to describe a collection of objects. Once you know how to write, read, and work with sets, you gain a tool that appears in every branch of mathematics and in nearly every area of computing — databases store records in tables that behave like sets, programming languages use set-like structures to filter and classify data, logic uses sets to interpret quantifiers, and proof uses sets to express domains and conditions.
By the end of this chapter, you will be able to describe collections precisely, perform operations on sets, interpret diagrams that represent set relationships, build Cartesian products, write and evaluate statements about all objects or some objects, and recognize relations as structured sets of ordered pairs. You will also see how these ideas connect to filtering, searching, classifying, and defining rules in computing systems.
A library database stores information about books. A librarian wants to find all books that are either in the science section or checked out, but not both. How would you describe that collection precisely? How would you describe the collection of books that are in the science section and also checked out? How would you describe the books in the science section but not checked out? These questions are about how to describe collections of objects precisely, how to combine descriptions, and how to express conditions logically. That is exactly what set theory studies.
A set is a well-defined collection of distinct objects. The objects in a set are called its elements or members. When we say a set is well-defined, we mean there is a clear rule or description that determines whether any given object belongs to the collection or does not. There should be no ambiguity.
This requirement matters. Consider the phrase "the collection of interesting numbers." Is 42 interesting? Is 7 interesting? Different people might answer differently. That collection is not well-defined, so it is not a set in the mathematical sense. Compare that to "the collection of even integers between 1 and 10." This is well-defined. For any candidate — say, 6 — you can check each condition mechanically. For 7: is it even? No. So 7 does not belong. There is no room for debate.
Sets can contain numbers, letters, words, points, functions, other sets, or any objects, as long as the collection is clearly defined. A set is unordered: the set containing 1, 2, and 3 is the same set as the one containing 3, 1, and 2. A set is also non-repeating: each element appears at most once.
The words set and list mean different things. A list can have repeated items and a specific order. A set has no repeated items and no ordering. When you write a set, you are describing a collection, not a sequence.
To say that an object belongs to a set, we use the symbol ∈, read "is an element of." To say that an object does not belong, we use ∉, read "is not an element of." Sets are named with capital letters by convention. Elements are referred to by lowercase letters or specific values.
If A = {1, 2, 3, 4, 5}, then:
3 ∈ A (3 is an element of A — true)
7 ∉ A (7 is not an element of A — true)
B = {a, e, i, o, u}. Determine whether each is true or false: (a) e ∈ B, (b) b ∈ B, (c) u ∈ B, (d) y ∈ B.e appears in B → true.b does not appear in B → false; write b ∉ B.u appears in B → true.y does not appear in B → false; write y ∉ B.
Roster notation lists elements between curly braces: {1, 2, 3, 4, 5} or {2, 4, 6, 8, …}. It works well for small or patterned sets. Set-builder notation describes a set by giving a domain and a rule that elements must satisfy:
{x | P(x)} Read: "the set of all x such that P(x)."
The vertical bar | is read "such that." A colon : may be used instead. Both notations are equivalent.
Standard number sets: ℕ natural numbers · ℤ integers · ℤ⁺ positive integers · ℚ rationals · ℝ reals
| Set-Builder Form | Description | Roster Form |
|---|---|---|
{x | x is even and x > 0} | Positive even integers | {2, 4, 6, 8, …} |
{x ∈ ℤ | x² < 25} | Integers whose square is less than 25 | {−4, −3, −2, −1, 0, 1, 2, 3, 4} |
{n ∈ ℕ | n is divisible by 3} | Multiples of 3 | {3, 6, 9, 12, …} |
{1, 4, 9, 16, 25} using set-builder notation.{n² | n ∈ ℤ⁺ and n ≤ 5}{x ∈ ℤ | −3 ≤ x ≤ 3}.{−3, −2, −1, 0, 1, 2, 3}The vertical bar in set-builder notation means "such that." It is different from absolute value bars |x|. In context, you can tell them apart: set-builder notation always has a variable before the bar and a condition after it, inside curly braces.
If every element of a set A is also an element of a set B, then A is a subset of B, written A ⊆ B. To check whether A ⊆ B, ask: for every element in A, is that element also in B? If you can find even one element in A that is not in B, then A ⊄ B.
A proper subset is a subset that is not equal to the whole set. If A ⊆ B and A ≠ B, then A ⊊ B. Every set is a subset of itself — that is called a trivial subset. The power set of A, written 𝒫(A), is the set of all subsets of A. If A has n elements, then 𝒫(A) has 2ⁿ elements.
C = {1, 2, 3} and D = {1, 2, 3, 4, 5}. True or false: (a) C ⊆ D, (b) D ⊆ C, (c) C ⊊ D, (d) C ⊆ C.If A = {1, 2}, then 𝒫(A) = {∅, {1}, {2}, {1,2}}. Four subsets, which is 2² = 4. You will prove the general formula using induction in Chapter 5.
In any given discussion, there is usually a background collection of all possible objects under consideration. This is the universal set, often denoted U. It is not a fixed mathematical object — it depends on context. If you are discussing integer properties, U might be ℤ. If classifying students, U might be all enrolled students.
The empty set, denoted ∅ or {}, contains no elements. For any candidate object, the answer to "does this belong to ∅?" is always "no." The empty set is a subset of every set, because the condition "every element of ∅ is in A" is vacuously satisfied — there are no elements to check. The empty set is unique: there is only one set with no elements.
∅ vs. {0}: The set {0} contains one element (the number zero). ∅ contains nothing. They are not the same.
∅ vs. {∅}: The set {∅} contains one element — the empty set itself. It is not empty.
∅ is not "nothing": The empty set is a well-defined mathematical object. It exists; it simply has no members.
A = {2, 4, 6, 8}. Determine whether each is true or false: (a) 4 ∈ A, (b) 5 ∈ A, (c) {4} ∈ A, (d) {4} ⊆ A, (e) ∅ ⊆ A, (f) A ⊆ A.{x ∈ ℤ | −2 ≤ x ≤ 4}, (b) {x ∈ ℤ | x² = 9}, (c) {x ∈ ℤ | x > 5 and x ≤ 8}.A = {1, 2, 3}. List all subsets of A. How many are there? Does the count equal 2³?∅ ⊆ {∅}. Explain your reasoning carefully.| Operation | Symbol | Definition | Membership Condition |
|---|---|---|---|
| Union | A ∪ B | All elements in A or B or both | x ∈ A or x ∈ B |
| Intersection | A ∩ B | All elements in both A and B | x ∈ A and x ∈ B |
| Difference | A ∖ B | Elements in A but not in B | x ∈ A and x ∉ B |
Two sets are disjoint if their intersection is empty: A ∩ B = ∅. Disjoint sets share no elements at all.
A = {2, 4, 6, 8, 10} and B = {1, 2, 3, 4, 5}. Compute (a) A ∪ B, (b) A ∩ B, (c) A ∖ B, (d) B ∖ A.A ∪ B = {1, 2, 3, 4, 5, 6, 8, 10}
A ∩ B = {2, 4}
A ∖ B = {6, 8, 10} (in A, not in B)
B ∖ A = {1, 3, 5} (in B, not in A)
A ∖ B and B ∖ A are generally not equal. Set difference is not commutative. Always read the direction carefully: A minus B removes B's elements from A, not the other way around.
The complement of a set A, written Ā or Aᶜ, is the set of all elements in the universal set U that are not in A. The complement depends entirely on what U is. Always identify the universal set before computing a complement.
Ā = {x ∈ U | x ∉ A} (equivalently, Ā = U ∖ A)
A ∪ Ā = U A ∩ Ā = ∅ Ā̄ = A Ū = ∅ ∅̄ = U
These identities mirror the logical laws from Chapter 2: p ∨ ¬p is a tautology; p ∧ ¬p is a contradiction.
U = {a, b, c, d, e, f} and B = {b, d, f}. Find B̄.B̄ = {a, c, e}B ∪ B̄ = {b,d,f} ∪ {a,c,e} = {a,b,c,d,e,f} = U. ✓A Venn diagram is a visual representation of sets and their relationships. A rectangle represents the universal set U. Circles inside the rectangle represent sets. The position of a point inside or outside a circle represents membership or non-membership.
Draw a rectangle labeled U. Inside, draw two overlapping circles labeled A (left) and B (right). The diagram divides the rectangle into four regions: Region I — inside A only (A ∖ B). Region II — inside both circles (A ∩ B). Region III — inside B only (B ∖ A). Region IV — outside both circles but inside U (complement of A ∪ B). Shade Region II to represent A ∩ B. Shade Regions I and II to represent A. Shade Regions I, II, and III to represent A ∪ B.
Sport only: 30 − 10 = 20
Instrument only: 20 − 10 = 10
Both: 10
Total (sport or instrument): 20 + 10 + 10 = 40
Neither: 50 − 40 = 10
Draw a rectangle labeled U. Inside, draw three overlapping circles labeled A, B, and C, arranged so that all three pairs overlap and a center region exists where all three meet. This creates 7 interior regions and 1 exterior region. The regions represent: A only; B only; C only; A ∩ B only (not C); A ∩ C only (not B); B ∩ C only (not A); A ∩ B ∩ C (all three); and outside all three circles. Three-set Venn diagrams support inclusion-exclusion counting, studied in Chapter 7.
An ordered pair (a, b) is a pair of objects in which order matters. The pair (a, b) is not the same as the pair (b, a) unless a = b. This differs from a set, where {a, b} = {b, a}.
The Cartesian product of two sets A and B, written A × B, is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. The size of A × B equals |A| · |B|. Note that A × B ≠ B × A in general.
A × B = {(a, b) | a ∈ A and b ∈ B}
|A × B| = |A| · |B|
The real coordinate plane ℝ² is the Cartesian product ℝ × ℝ. Each point (x, y) is an ordered pair.
A = {H, T} and B = {1, 2, 3, 4, 5, 6}. List A × B and state its size. (This models flipping a coin and rolling a die.)A × B = {(H,1), (H,2), (H,3), (H,4), (H,5), (H,6),
(T,1), (T,2), (T,3), (T,4), (T,5), (T,6)}
Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A = {1, 3, 5, 7, 9}, B = {2, 3, 5, 7}, C = {4, 5, 6, 7, 8}.
A ∪ BA ∩ BA ∖ BB ∖ AĀB̄(A ∪ B) ∩ CA ∩ B ∩ CĀ ∪ B̄ (compare to A ∩ B̄)Ā ∩ B̄ (compare to A ∪ B̄)Note: Problems 9 and 10 are related to De Morgan's Laws for sets.
The conditions used in set-builder notation — like "x is even" or "x > 5" — are examples of predicates. A predicate is a statement that contains a variable and becomes a proposition (true or false) when that variable is replaced by a specific value from a given domain. We write P(x) to denote a predicate with variable x. The domain from which x is drawn is called the domain of discourse.
| Predicate | P(4) | P(7) |
|---|---|---|
P(x): x is even | True (4 is even) | False (7 is odd) |
Q(n): n² > 10 | True (16 > 10) | True (49 > 10) |
R(x,y): x + y = 10 | R(4,6): True | R(7,2): False |
A predicate contains a variable and has no truth value until the variable is assigned a value. A proposition has a definite truth value. Quantifiers convert predicates into propositions by making claims about an entire domain.
∀x, P(x) Universal: "For all x, P(x)." True only if P(x) holds for every element x in the domain. One failure makes it false.
∃x, P(x) Existential: "There exists an x such that P(x)." True if P(x) holds for at least one element. False only if P(x) fails for every element.
Negation rules:
¬(∀x, P(x)) ≡ ∃x, ¬P(x)
¬(∃x, P(x)) ≡ ∀x, ¬P(x)
A counterexample is a single element of the domain for which the predicate P(x) fails. Finding one counterexample is enough to disprove a universal statement. Checking 99% of cases is not sufficient to prove it true.
∀n ∈ ℤ, n² ≥ 0. (b) Evaluate ∃n ∈ ℤ, n + 1 < n. Write the negation of each and give its truth value.(a) Original: ∀n ∈ ℤ, n² ≥ 0
TRUE: for any integer, squaring gives a non-negative result.
Negation: ∃n ∈ ℤ, n² < 0
FALSE: no integer has a negative square.
(b) Original: ∃n ∈ ℤ, n + 1 < n
This means 1 < 0, which is impossible.
FALSE.
Negation: ∀n ∈ ℤ, n + 1 ≥ n
TRUE: n + 1 > n for every integer.
When a predicate has two variables, statements can involve two quantifiers in sequence. The order matters critically.
| Statement | Reading | Truth (domain ℤ) |
|---|---|---|
∀x ∃y, x + y = 0 | For every x, there exists some y (depending on x) with x + y = 0. | True: choose y = −x. |
∃y ∀x, x + y = 0 | There exists one y that works for every x simultaneously. | False: no single y satisfies x + y = 0 for all x at once. |
The order of quantifiers changes the meaning of a statement fundamentally. ∀x ∃y allows y to depend on x. ∃y ∀x requires one fixed y to work for every x. These are not interchangeable. Always read quantifiers from left to right.
∀n ∈ ℤ, n + 1 > n (b) ∀n ∈ ℤ, n² ≥ 0 (c) ∀n ∈ ℤ, n² > 0 (d) ∃n ∈ ℤ, n² = 2 (e) ∃n ∈ ℤ, n² = 9
∀x ∈ ℤ, x² ≥ 0 (b) ∃x ∈ ℤ, x + x = x (c) ∀x ∈ ℤ ∃y ∈ ℤ, x + y = 0
∀x ∃y, x · y = 0 (b) ∃y ∀x, x · y = 0 (c) ∀x ∃y, x + y = 10 (d) ∃x ∀y, x + y = 10
A relation between two sets A and B is a set of ordered pairs drawn from the Cartesian product A × B. More precisely, a relation R from A to B is a subset of A × B: R ⊆ A × B. When a pair (a, b) belongs to R, we say that a is related to b under R, and we write aRb or (a, b) ∈ R.
A relation can also be defined from a set to itself — a relation on a set A is a subset of A × A.
A = {1, 2, 3} and B = {1, 2, 3, 4, 5, 6}. Define a relation D from A to B by: (a, b) ∈ D if and only if a divides b. List all pairs in D.D = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6),
(2,2), (2,4), (2,6),
(3,3), (3,6)}
| Property | Condition | Meaning |
|---|---|---|
| Reflexive | (a,a) ∈ R for all a ∈ A | Every element is related to itself. |
| Symmetric | If (a,b) ∈ R, then (b,a) ∈ R | Relation goes both ways. |
| Transitive | If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R | Relation chains. |
A relation that is simultaneously reflexive, symmetric, and transitive is called an equivalence relation. Equivalence relations appear throughout algebra, number theory, and computing. The congruence modulo n relation from Chapter 6 is an important example.
A = {1, 2, 3} and R = {(1,1), (2,2), (3,3), (1,2), (2,1)}. Is R reflexive? Symmetric? Transitive?Reflexive: (1,1), (2,2), (3,3) all in R → YES
Symmetric: (1,2) ∈ R and (2,1) ∈ R ✓
(1,1), (2,2), (3,3) are self-paired ✓ → YES
Transitive: (1,2) ∈ R and (2,1) ∈ R → need (1,1) ∈ R ✓
(2,1) ∈ R and (1,2) ∈ R → need (2,2) ∈ R ✓
All other chains either don't arise or are covered → YES
A function from A to B is a special type of relation: a subset of A × B in which every element of A appears as the first coordinate of exactly one pair. Functions are relations with an extra uniqueness condition. This is why both functions and relations are defined as sets of ordered pairs.
The set operations in this chapter are directly implemented in the tools that manage data and power computing systems. They are not abstract constructions invented for purely theoretical purposes.
| Computing Context | Set Operation | Example |
|---|---|---|
| SQL query with WHERE | Set-builder / subset selection | SELECT * FROM Users WHERE city = 'Chicago' returns a subset of the Users table. |
| SQL UNION / INTERSECT | ∪ and ∩ | Combine or intersect result sets from two queries. |
| SQL JOIN | Cartesian product + filter | Produces ordered tuples from two tables, filtered by a join condition. |
| Keyword search (all terms) | Intersection | Documents matching "discrete" AND "mathematics" = their intersection. |
| Keyword search (any term) | Union | Documents matching "discrete" OR "mathematics" = their union. |
| Access control | Relation membership | Access granted if (user, action, resource) ∈ PermittedAccess. |
In classification problems (machine learning), a category is a set — a collection of objects satisfying certain conditions. Deciding whether a new object belongs to a category is a membership question: does this object satisfy the predicate that defines the set? Every classifier, at its core, evaluates a predicate P(x) and assigns x to the set for which P(x) is true.
A = {1, 2, 4}. Define R on A by: (a, b) ∈ R if a divides b. List all pairs in R. Is R reflexive? Symmetric? Transitive?The number 3 is an integer. The set {3} is a collection containing one element. They are different objects. Writing 3 = {3} is incorrect. Correctly: 3 ∈ {3} (3 is a member of the set {3}).
The empty set ∅ is a well-defined mathematical object. It is a subset of every set. The set {∅} contains one element — the empty set itself. These distinctions are essential in proof.
The correct statement is 1 ∈ {1, 2, 3}. The ⊆ symbol is for sets, not elements. Write: {1} ⊆ {1, 2, 3} (the set containing 1 is a subset). Write: 1 ∈ {1, 2, 3} (the element 1 is a member).
Correct: elements in both A and B → A ∩ B (intersection uses "and"). Elements in A or B → A ∪ B (union uses "or"). Trust the definitions, not the English phrasing alone.
The complement Ā = U ∖ A. Without knowing U, the complement is undefined. Always identify the universal set before computing a complement.
Ordered pairs are not sets. (2, 5) ≠ (5, 2) unless 2 = 5. The set {2, 5} = {5, 2} because sets are unordered, but ordered pairs record position.
These are fundamentally different. The first allows y to depend on x. The second requires one fixed y to work for every x. In general, ∃y ∀x is a stronger claim and is often false when the first is true.
A universal statement must hold for every element in the domain — not just many of them. Checking finite cases proves nothing in general. To prove ∀n, P(n), you must give a general argument. To disprove it, find one counterexample.
Correct negation: ¬(∀x, P(x)) ≡ ∃x, ¬P(x). The negation flips the quantifier from ∀ to ∃ and negates the predicate. Simply negating the predicate without flipping the quantifier is wrong.
Written explanations are expected for each question.
Let U = {1,2,3,4,5,6,7,8}, A = {1,2,3,4}, B = {3,4,5,6}.
A ∪ BA ∩ BA ∖ BĀĀ ∩ B̄A ∪ B̄ = Ā ∩ B̄ is false; show A ∪ B̄ ≠ Ā ∩ B̄. Then correctly state De Morgan's Law for ∪ and verify it.Domain: ℤ. Determine true or false. If false, give a counterexample.
∀n, 2n > n∃n, n² = n∀n, n² ≥ 0∃n, n³ = n∀n, n + 0 = n∃n, n + n = nWrite the negation of each. Simplify so ¬ applies only to predicates.
∀x ∈ ℤ, x > 0∃x ∈ ℤ, x² = 2∀n ∈ ℕ, n is even∃x ∀y, x + y = yEach problem contains an error. Identify it and write the correct answer.
What is wrong? What is the correct statement and why?
Identify the error. What operation gives {3}? What is A ∪ B?
What is the correct negation? State the rule and apply it.
Explain the error. When are two ordered pairs equal?
What is wrong with this reasoning? What would it actually take to prove a universal statement?
Write complete mathematical arguments using set-builder definitions and logical equivalences.
A ∪ B̄ = Ā ∩ B̄. Use the set-builder definitions and logical equivalences from Chapter 2.A = {x ∈ ℤ | 0 < x < 8 and x is odd}. List the elements of A.{0, 1, 4, 9, 16} in set-builder notation.∅ ⊆ {∅}. Explain.U = {1,2,3,4,5,6,7,8}, A = {1,2,3,4}, B = {3,4,5,6}.A ∪ B, A ∩ B, A ∖ B, and Ā.A ∪ B̄ = Ā ∩ B̄.A = {0, 1} and B = {a, b, c}. List all elements of A × B.A × B × A have?∀n ∈ ℤ, 2n > n; (b) ∃n ∈ ℤ, n² = n.∀n ∈ ℤ, n² > 0. Is the original true or false? Is the negation true or false?A = {1, 2, 4}. Define R on A by (a, b) ∈ R if a divides b. List all pairs in R. Is R reflexive? Symmetric? Transitive?You now have a precise language for describing collections, conditions, and relationships. Sets give you a way to talk about domains. Quantifiers give you a way to make claims about all or some members of a domain. Relations give you a way to express structured connections between elements.
Chapter 4 takes this foundation and asks: how do you prove that a statement about sets, integers, or quantified claims is true? You will learn the methods mathematicians use to justify general claims — direct proof, proof by contrapositive, proof by contradiction, proof by cases — and you will write complete, rigorous proofs for the first time. The vocabulary from this chapter — element, subset, universal statement, existential statement, predicate, domain — will be the objects about which you prove things. The logic from Chapter 2 will supply the inference rules. Chapter 4 brings them together into mathematical proof.