Unit 1: Sets
Mathematics notes · PTU syllabus (UGCC2501)
On this page
Unit summary
Set theory is the language of modern mathematics and of computer science — databases, programming types and logic all rest on sets. This unit covers the meaning and representation of sets, the types of sets (null, singleton, finite, infinite, equal, equivalent, disjoint, subset, proper subset, power set, universal set), the set operations union, intersection, difference, symmetric difference and complement, and the laws and counting formulas that go with them.
After this unit you can
- Represent a set by the roster method, the set-builder method and Venn diagrams
- Identify the different types of sets and find the power set of a set
- Perform union, intersection, difference, symmetric difference and complement operations
- Apply the laws of set algebra, De Morgan's laws and cardinality formulas to solve problems
PTU syllabus topics
- Introduction
- representation of sets (roster method, set builder method)
- types of sets (null, singleton, finite, infinite, equal, equivalent, disjoint, subset, proper subset, power set, universal set)
- set operations (union, intersection, difference, symmetric difference)
- complement of a set
Topic 1
Introduction to sets
A set is a well-defined collection of distinct objects; the objects are its elements or members. "Well-defined" means we can say definitely whether any object belongs to it or not.
- Set
- Written with capital letters — A, B, C
- Element
- Written with small letters; a ∈ A means "a belongs to A"
- Not an element
- x ∉ A means "x does not belong to A"
- Cardinal number
- n(A), the number of elements of a finite set
- Braces
- Elements are listed between { } separated by commas
- Standard sets
- ℕ natural numbers, ℤ integers, ℚ rationals, ℝ reals
Example
Vowels of the English alphabet
Beautiful girls of a city
Reason
Membership can be decided
Opinion decides membership
Example
Prime numbers below 20
Good cricketers
Example
A = {2, 3, 5, 7}: 5 ∈ A, 4 ∉ A and n(A) = 4. Repetition does not count — {1, 2, 2, 3} is the same set as {1, 2, 3}, and order does not matter.
Topic 2
Representation of sets
Idea
List all elements within braces
State the property common to all elements
Notation
A = {1, 2, 3, 4, 5}
A = {x : x ∈ ℕ and x ≤ 5}
Best for
Small finite sets
Large or infinite sets
Example
Vowels = {a, e, i, o, u}
Vowels = {x : x is a vowel of the English alphabet}
Infinite set
Use dots: {2, 4, 6, …}
{x : x is a positive even integer}
- 1Read the property in the set-builder form
- 2Find every element that satisfies it
- 3List them in braces — roster form
- 4In reverse, find the common property of the listed elements
- 5State it after the colon — set-builder form
Example
{x : x² − 5x + 6 = 0} = {2, 3} since x² − 5x + 6 = (x − 2)(x − 3). {1, 4, 9, 16, 25} = {x² : x ∈ ℕ and x ≤ 5} in set-builder form.
Venn diagrams
A Venn diagram represents sets as circles inside a rectangle; the rectangle stands for the universal set U.
Overlap = elements common to A and B; outside the circles but inside the rectangle = elements of U in neither set
Topic 3
Types of sets
Null (empty) set
Has no elements — written ∅ or { }
{x : x is a prime between 23 and 29} = ∅
Singleton set
Has exactly one element
{0}, {5}
Finite set
Number of elements can be counted
{1, 2, 3, … , 100}
Infinite set
Counting never ends
ℕ, ℤ, ℝ
Universal set (U)
Contains all elements under discussion
U = ℤ when studying integers
Equal sets
Same elements (order and repetition ignored)
{1, 2, 3} = {3, 1, 2}
Equivalent sets
Same number of elements, n(A) = n(B)
{a, b, c} and {1, 2, 3}
Disjoint sets
No common element, A ∩ B = ∅
{1, 3, 5} and {2, 4, 6}
Overlapping sets
Some but not all elements common
{1, 2, 3} and {3, 4, 5}
Exam tip
Equal sets are always equivalent, but equivalent sets need not be equal. ∅ is not {0} — the first has no element, the second has one element.
A ∩ B = ∅ — the circles do not touch
Example
Examples: A = {1, 2, 3} and B = {3, 1, 2} are equal sets. C = {a, b, c} is equivalent to A, because both have 3 elements. The power set of A has 2³ = 8 subsets, including ∅ and A itself. The set of even prime numbers, {2}, is a singleton.
Topic 4
Subsets, proper subsets and power set
A is a subset of B (A ⊆ B) if every element of A is also an element of B. A is a proper subset (A ⊂ B) if A ⊆ B and A ≠ B.
- Every set is a subset of itself
- A ⊆ A
- The empty set is a subset of every set
- ∅ ⊆ A
- Transitivity
- A ⊆ B and B ⊆ C implies A ⊆ C
- Equality
- A = B if and only if A ⊆ B and B ⊆ A
- Number of subsets
- A set with n elements has 2ⁿ subsets and 2ⁿ − 1 proper subsets (excluding itself, or 2ⁿ − 2 non-empty proper subsets)
Circle A lies wholly inside circle B
The power set P(A) is the set of all subsets of A, including ∅ and A itself. If n(A) = n, then n(P(A)) = 2ⁿ.
Example
A = {a, b, c}: P(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}} — 8 = 2³ subsets.
| Size of subset | 0 | 1 | 2 | 3 | Total |
|---|---|---|---|---|---|
| Number of subsets of a 3-element set | 1 | 3 | 3 | 1 | 8 |
| Number of subsets of a 4-element set | 1 | 4 | 6 | 4 | 16 |
Total subsets
2ⁿ
Subsets with r elements
nCr = n! ÷ [r! (n − r)!]
Proper subsets
2ⁿ − 1
Check
Sum of nCr for r = 0 to n equals 2ⁿ
Topic 5
Operations on sets
Union
All elements in A or B or both
A ∪ B = {x : x ∈ A or x ∈ B}
Intersection
Elements common to A and B
A ∩ B = {x : x ∈ A and x ∈ B}
Difference
Elements in A but not in B
A − B = {x : x ∈ A and x ∉ B}
Symmetric difference
Elements in exactly one of A, B
A Δ B = (A − B) ∪ (B − A)
Complement
Elements of U not in A
A′ = U − A = {x : x ∈ U and x ∉ A}
Example
U = {1, 2, 3, …, 10}, A = {1, 2, 3, 4, 5}, B = {4, 5, 6, 7}.
| Operation | Result |
|---|---|
| A ∪ B | {1, 2, 3, 4, 5, 6, 7} |
| A ∩ B | {4, 5} |
| A − B | {1, 2, 3} |
| B − A | {6, 7} |
| A Δ B | {1, 2, 3, 6, 7} |
| A′ | {6, 7, 8, 9, 10} |
| (A ∪ B)′ | {8, 9, 10} |
Shaded: all of A together with all of B
Shaded: only the common region
Shaded: the part of A outside B
Shaded: elements in A or B but not in both
Shaded: everything in U outside A
Laws of set algebra
Laws of set operations
| Law | Statement |
|---|---|
| Commutative | A ∪ B = B ∪ A and A ∩ B = B ∩ A |
| Associative | (A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C) |
| Distributive | A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
| Identity | A ∪ ∅ = A and A ∩ U = A |
| Idempotent | A ∪ A = A and A ∩ A = A |
| Domination | A ∪ U = U and A ∩ ∅ = ∅ |
| Complement | A ∪ A′ = U, A ∩ A′ = ∅, (A′)′ = A |
| De Morgan | (A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′ |
- 1
Take an arbitrary element x of the left side
- 2
Show that x belongs to the right side (so LHS ⊆ RHS)
- 3
Take an arbitrary element of the right side
- 4
Show it belongs to the left side (so RHS ⊆ LHS)
- 5
Conclude LHS = RHS
- 6
Or verify with a Venn diagram or membership table
Example
Verify De Morgan with A = {1, 2, 3}, B = {3, 4}, U = {1, 2, 3, 4, 5}: A ∪ B = {1, 2, 3, 4}, so (A ∪ B)′ = {5}; A′ = {4, 5}, B′ = {1, 2, 5}, so A′ ∩ B′ = {5} — equal.
Counting with sets (cardinality)
Two sets
n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
Disjoint sets
n(A ∪ B) = n(A) + n(B)
Only A
n(A − B) = n(A) − n(A ∩ B)
Symmetric difference
n(A Δ B) = n(A) + n(B) − 2 n(A ∩ B)
Complement
n(A′) = n(U) − n(A)
Three sets
n(A ∪ B ∪ C) = n(A) + n(B) + n(C) − n(A ∩ B) − n(B ∩ C) − n(A ∩ C) + n(A ∩ B ∩ C)
Example
In a group of 100 students, 60 like cricket, 50 like football and 20 like both. n(C ∪ F) = 60 + 50 − 20 = 90. Neither = 100 − 90 = 10; only cricket = 60 − 20 = 40; only football = 50 − 20 = 30.
Example
In a class of 80, 40 study Maths, 35 Physics, 30 Chemistry; 15 study Maths and Physics, 12 Physics and Chemistry, 10 Maths and Chemistry; 5 study all three. n(M ∪ P ∪ C) = 40 + 35 + 30 − 15 − 12 − 10 + 5 = 73, so 80 − 73 = 7 study none.
Only Maths 20, only Physics 13, only Chemistry 13; M∩P only 10, P∩C only 7, M∩C only 5; all three 5; total in circles = 73
Exam tip
Fill the Venn diagram from the innermost region (all three) outwards: subtract the triple overlap first, then the pair overlaps, then the single regions.
Key terms
- Set
- A well-defined collection of distinct objects
- Roster method
- Listing all elements of a set within braces
- Set-builder method
- Describing a set by a property of its elements
- Null set
- The set with no elements, ∅
- Power set
- The set of all subsets of a set, with 2ⁿ elements
- Disjoint sets
- Sets with no common element
- Union
- Elements that belong to at least one of the sets
- Intersection
- Elements common to the sets
- Symmetric difference
- Elements in exactly one of the two sets
- Complement
- Elements of the universal set not in the given set
- De Morgan's laws
- (A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′
Quick revision
- Roster: list the elements; set-builder: state the property; Venn diagrams use a rectangle for U.
- ∅ ⊆ every set; a set of n elements has 2ⁿ subsets.
- Equal sets are equivalent; equivalent sets need not be equal.
- n(A ∪ B) = n(A) + n(B) − n(A ∩ B); A Δ B = (A − B) ∪ (B − A).
- De Morgan: complement of a union is the intersection of complements, and vice versa.
- Three-set formula has alternating signs: single − pairs + triple.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Define a set. Is "the set of tall students" well-defined?
- Q2.Write {x : x ∈ ℕ, 3 < x < 8} in roster form.
- Q3.What is the difference between a null set and a singleton set?
- Q4.Distinguish equal sets and equivalent sets.
- Q5.How many subsets does a set with 5 elements have?
- Q6.Write the power set of {1, 2}.
- Q7.Define the symmetric difference of two sets.
- Q8.State De Morgan's laws.
- Q9.If n(A) = 25, n(B) = 30 and n(A ∩ B) = 10, find n(A ∪ B).
- Q10.What is the complement of a set?
Long-answer questions
- Q1.Explain the roster and set-builder methods of representing sets with examples.
- Q2.Explain the different types of sets with examples.
- Q3.Explain union, intersection, difference, symmetric difference and complement with Venn diagrams.
- Q4.State and verify De Morgan's laws for given sets.
- Q5.In a survey of 100 people, 60 like tea, 50 like coffee and 20 like both; find how many like only tea, only coffee and neither.
- Q6.Use the three-set cardinality formula to solve a word problem.
Stuck on this unit?
Message SBS on WhatsApp for help with Mathematics, or to ask about studying BCA at Synetic.
