School of Mathematics and Statistics UNSW, Sydney
1
MATH3711/5706 : Problem Sheet 0, Revision
In this course, we will use a lot of set theory. You should have picked up all of what you
need to know in first year maths (MATH1241 or MATH1251). Discrete maths would be very
handy but is not necessary. As a quick check, make sure you know the following
Set theory definitions you should know
Domain, codomain, range, invertible function, finite set, one-to-one or injective, onto or
surjective, bijection, composition of functions.
If for some reason, you never learnt one of these, don’t worry, they are fairly straightforward.
Given n sets S1 , . . . , Sn you should know that the product of them is
S1 × S2 × . . . × Sn := {(s1 , . . . , sn )|si ∈ Si for every i}
that is, it is the set of all ordered n-tuples of the form (s1 , . . . , sn ) where si ∈ Si for i = 1, . . . , n.
There is an obvious generalisation to the case where you have an infinite number of sets Si (only
the notation is trickier).
Set theory facts you should know
There are lots of facts about sets which are intuitively obvious which I expect you to know.
You are free to use them in assignments/tests without comment. Below is a sample of set theory
facts you should know.
1. If f : S −→ T is a function and S is finite with |S| elements then the range of f has at
most |S| elements.
2. If f : S −→ T is a one-to-one function and S is finite with |S| elements then the range of
f has |S| elements.
3. The composite of injective functions is injective.
4. If S, T are finite sets with |S|, |T | elements respectively then S × T has |S||T | elements.
5. If f, g are functions such that the composite f g (sometimes denoted f ◦ g) is the identity,
then g is injective and f is surjective.
6. Invertible functions are the same as bijective functions.
Set theory exercises
Computational skills are very important in 1st/2nd year courses. In this course, it is your
set-theoretic/logic skills which will be most important. Below are some exercises to test the
types of skills you should have.
1. For sets R, S, T , show that there are natural bijections between (R × S) × T , R × (S × T )
and R × S × T . (Consequently, we will often identify these and ignore the difference
between them).
2. Find a set S and an injective function f : S −→ S which is not onto. Find all sets with
this property.
1 by Daniel Chan
1
3. (You will need to be able to show sets are the same). Let M2 (R) denote the set of 2 by 2
matrices with entries in R. Show that
n cos θ ± sin θ
o
T
{A ∈ M2 (R)|AA = I} = |θ ∈ R .
− sin θ ± cos θ
4. (You will need to be able to show two functions are the same). Let S be the set
{Batman, Robin} and f : S −→ S be an injection. Show that f 2 = id (where f 2 := f ◦ f
the composite of f with itself).
5. Prove, disprove or salvage if possible the following statements concerning a function f :
S −→ T between sets S, T .
(a) If S1 , S2 ⊆ S then f (S1 ∩ S2 ) = f (S1 ) ∩ f (S2 ).
(b) If S1 , S2 ⊆ S then f (S1 ∪ S2 ) = f (S1 ) ∪ f (S2 ).
(c) If T1 , T2 ⊆ T then f −1 (T1 ∩ T2 ) = f −1 (T1 ) ∩ f −1 (T2 ). (Recall that the pre-image
f −1 (Ti ) of Ti is defined to be {s ∈ S|f (s) ∈ Ti }.)
(d) If T1 , T2 ⊆ T then f −1 (T1 ∪ T2 ) = f −1 (T1 ) ∪ f −1 (T2 ).
6. For sets R, S, T show that R ⊆ T and R ⊆ S if and only if R ⊆ S ∩ T .
7. For a set S we define the diagonal map to be ∆ : S −→ S × S : s 7→ (s, s) and the
projection maps to be p1 : S × S −→ S : (s, s′ ) 7→ s, p2 : S × S −→ S : (s, s′ ) 7→ s′ . For
i = 1, 2 find pi ◦ ∆ and ∆ ◦ pi .
Relations
Let S be a set. A relation ≺ on S is a subset of S × S where we write s ≺ s′ iff (s, s′ ) is
in that subset. The relation is said to be reflexive if it contains the image of the diagonal map
(see exercise 7 above for the definition of this). It is anti-symmetric if for every pair s, s′ ∈ S
satisfying s ≺ s′ , s′ ≺ s we have s = s′ . Finally, it is transitive if for any s, s′ , s′′ ∈ S satisfying
s ≺ s′ , s′ ≺ s′′ we also have s ≺ s′′ . A relation which is anti-symmetric, reflexive and transitive
is said to be a partial order.
1. Let S be a set and P be the set of all subsets of S (this is called the power set of S). Show
that ⊆ is a partial order on S.
2. Consider a partial order ≺ on a set S defined by R ⊆ S × S. If T ⊂ S, show that T × T ∩ R
is a partial order on T . Do you understand what this partial order is? It is called the
induced partial order.
3. Make up your own examples.
A relation ≺ is symmetric if for any s, s′ ∈ S with s ≺ s′ we have s′ ≺ s. A symmetric,
reflexive and transitive relation is called an equivalence relation. Equivalence relations are
usually denoted by more symmetric looking symbols such as ∼, ≡ rather than asymmetric ones
like ≺. Given an equivalence relation ≡ on a set S, the equivalence class of some s ∈ S is
{s′ ∈ S|s′ ≡ s} and is typically denoted [s]. Note reflexivity implies s ∈ [s].
2
Proposition 0.1 Suppose first that ≡ is an equivalence relation on a set S. Then S is the
disjoint union of its equivalence classes. Conversely, suppose S is the disjoint union of subsets
Si where i runs through some index set I. Define the relation ≡ on S by s ≡ s′ iff s, s′ belong
to some common subset Si (for some i). Then ≡ is an equivalence relation whose equivalence
classes are precisely the subsets Si .
Proof is easy but long and omitted.
The set of equivalence classes is denoted S/ ≡.
1. Show that the image of the diagonal map is an equivalence relation and determine its
equivalence classes.
2. Define a relation on Z by m ≡ n iff 2|(m − n). Show that ≡ is an equivalence relation
and the disjoint union of the above proposition is the partition of Z into even and odd
numbers.
3. Let S := Z × (Z − 0). Define a relation on S by (m, m′ ) ≡ (n, n′ ) iff mn′ = nm′ . Show
that the function f : S/ ≡−→ Q : [(m, m′ )] 7→ m/m′ is a well-defined bijection.