Topic 4 of 8

Sets, functions, and relations

Step 21 · Proofs and discrete maths topics

Combine sets with union, intersection and complement, classify functions as one-to-one or onto, and recognize equivalence relations and the classes they create.

Set operations

A set is a collection of elements. A ∪ B holds everything in A or B; A ∩ B holds what is in both; A − B holds what is in A but not in B. A ⊆ B means every element of A is also in B.

Example: Computing

A = $\{1, 2, 3, 4\}$ and B = $\{3, 4, 5\}$ . Find A ∪ B, A ∩ B and A − B.

The union holds everything in either set.
The intersection holds 3 and 4.
A − B holds 1 and 2.

Answer $\{1, 2, 3, 4, 5\}$ , $\{3, 4\}$ and $\{1, 2\}$

Example: The power set

How many subsets does $\{a, b, c\}$ have?

Each element is either in a subset or out of it: 2 × 2 × 2 choices.

Answer8, from the empty set up to the whole set

One-to-one and onto functions

A function f: A → B gives each element of A exactly one element of B. It is one-to-one (injective) if different inputs give different outputs, onto (surjective) if every element of B is reached, and a bijection if both. Bijections are exactly the functions with inverses.

Example: A bijection

Is f(x) = 2x + 3 from ℝ to ℝ one-to-one? Onto?

If 2a + 3 = 2b + 3 then a = b: one-to-one.
Any y is reached from x = (y − 3) ÷ 2: onto.

AnswerBoth: a bijection

Example: Neither

Is f(x) = x² from ℝ to ℝ one-to-one? Onto?

f(2) = f(−2), so it is not one-to-one.
No x gives −1, so it is not onto.

AnswerNeither

Relations and equivalence

A relation on a set pairs some elements with others. An equivalence relation is reflexive (a ~ a), symmetric (a ~ b gives b ~ a) and transitive (a ~ b and b ~ c give a ~ c). It splits the set into separate equivalence classes.

Example: Same remainder

On the integers, say a ~ b when a − b is divisible by 3. Is this an equivalence relation?

a − a = 0 is divisible by 3: reflexive.
If 3 divides a − b, it divides b − a: symmetric.
If 3 divides a − b and b − c, it divides their sum, a − c: transitive.

AnswerYes, with three classes: remainders 0, 1 and 2

Example: Not an equivalence

Is 'a ≤ b' an equivalence relation on the integers?

It is reflexive and transitive.
But 1 ≤ 2 while 2 ≤ 1 is false, so it is not symmetric.

AnswerNo

Try it yourself

Work each one on paper first, then open the answer to check.

A = $\{1, 2\}$ and B = $\{2, 3\}$ . What is A ∩ B?
Show answer
$\{2\}$
How many subsets does a set of 5 elements have?
Show answer
32
Is f(x) = x³ from ℝ to ℝ a bijection?
Show answer
Yes
Is f(n) = 2n from the integers to the integers onto?
Show answer
No: odd numbers are never reached
Which property of an equivalence relation does 'a < b' fail first?
Show answer
Reflexive: a < a is false
How many classes does 'same remainder when divided by 5' create on the integers?
Show answer
5