Unit 1 of 4 · BCA Sem 1

Unit 1: Sets

Mathematics notes · PTU syllabus (UGCC2501)

4 min read5 topics16 exam questions
On this page
  1. Unit summary
  2. Introduction to sets
  3. Representation of sets
  4. Types of sets
  5. Subsets, proper subsets and power set
  6. Operations on sets
  7. Key terms
  8. Quick revision
  9. Important questions

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
1

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.

Key termsBasic notation
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
ComparisonWell-defined vs not well-defined
Well-defined set
Not a set

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.

2

Topic 2

Representation of sets

ComparisonMethods of representing a set
Roster (tabular) method
Set-builder method

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}

ProcessConverting between the two methods
  1. 1Read the property in the set-builder form
  2. 2Find every element that satisfies it
  3. 3List them in braces — roster form
  4. 4In reverse, find the common property of the listed elements
  5. 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.

GraphVenn diagram of two overlapping sets
UABA onlyA ∩ BB only

Overlap = elements common to A and B; outside the circles but inside the rectangle = elements of U in neither set

3

Topic 3

Types of sets

ComparisonTypes of sets (part 1)
Meaning
Example

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

ComparisonTypes of sets (part 2)
Meaning
Example

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.

GraphDisjoint sets
UAB

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.

4

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.

Key termsProperties of subsets
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)
GraphSubset: A ⊂ B
UBA

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 subset0123Total
Number of subsets of a 3-element set13318
Number of subsets of a 4-element set146416
Key formulasCounting subsets
  • 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ⁿ

5

Topic 5

Operations on sets

ComparisonSet operations
Definition
Notation and meaning

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

OperationResult
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}
GraphUnion A ∪ B
UAB

Shaded: all of A together with all of B

GraphIntersection A ∩ B
UAB

Shaded: only the common region

GraphDifference A − B
UAB

Shaded: the part of A outside B

GraphSymmetric difference A Δ B
UAB

Shaded: elements in A or B but not in both

GraphComplement A′
UA

Shaded: everything in U outside A

Laws of set algebra

Laws of set operations

LawStatement
CommutativeA ∪ B = B ∪ A and A ∩ B = B ∩ A
Associative(A ∪ B) ∪ C = A ∪ (B ∪ C) and (A ∩ B) ∩ C = A ∩ (B ∩ C)
DistributiveA ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) and A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
IdentityA ∪ ∅ = A and A ∩ U = A
IdempotentA ∪ A = A and A ∩ A = A
DominationA ∪ U = U and A ∩ ∅ = ∅
ComplementA ∪ A′ = U, A ∩ A′ = ∅, (A′)′ = A
De Morgan(A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′
ProcessProving a set identity
  1. 1

    Take an arbitrary element x of the left side

  2. 2

    Show that x belongs to the right side (so LHS ⊆ RHS)

  3. 3

    Take an arbitrary element of the right side

  4. 4

    Show it belongs to the left side (so RHS ⊆ LHS)

  5. 5

    Conclude LHS = RHS

  6. 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)

Key formulasCardinality formulas
  • 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.

GraphThree-set Venn diagram with region counts
U (80 students)MathsPhysicsChemistry201313105757 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

  1. Q1.Define a set. Is "the set of tall students" well-defined?
  2. Q2.Write {x : x ∈ ℕ, 3 < x < 8} in roster form.
  3. Q3.What is the difference between a null set and a singleton set?
  4. Q4.Distinguish equal sets and equivalent sets.
  5. Q5.How many subsets does a set with 5 elements have?
  6. Q6.Write the power set of {1, 2}.
  7. Q7.Define the symmetric difference of two sets.
  8. Q8.State De Morgan's laws.
  9. Q9.If n(A) = 25, n(B) = 30 and n(A ∩ B) = 10, find n(A ∪ B).
  10. Q10.What is the complement of a set?

Long-answer questions

  1. Q1.Explain the roster and set-builder methods of representing sets with examples.
  2. Q2.Explain the different types of sets with examples.
  3. Q3.Explain union, intersection, difference, symmetric difference and complement with Venn diagrams.
  4. Q4.State and verify De Morgan's laws for given sets.
  5. 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.
  6. 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.

WhatsApp us