Intro to Uni Maths

Question 1

Define a natural number

Answer 1

non-negative whole number

Question 2

Define a binary operation

Answer 2

A binary operation ∗ on a set S associates an element x ∗ y in S with each ordered
pair (x, y) where x, y are in S

Question 3

What is the smallest set where the following holds?:
0 is in the set
and if n ∈ N then n + 1 ∈ N

Answer 3

The natural numbers

Question 4

Proof by induction:
What is the initial case/step?
What is the inductive step?
What is the inductive hypothesis?

Answer 4

Initial case: When n=0, or the first statement to be proved
Inductive step: Showing the (n + 1)th statement follows from the nth statement
Inductive hypothesis: The assumption that the nth statement is true

Question 5

Optional - Prove the principle of induction:

Answer 5

Let S be the set of natural numbers such that P(n) is true. Then 0 ∈ S as we know P(0) is
true. Further if n ∈ S then P(n) is true, so that P(n + 1) is true or equivalently n + 1 ∈ S.
Thus S has the properties that (i) 0 ∈ S and (ii) if n ∈ S then n + 1 ∈ S. As N is the smallest
such subset with these properties then N is contained in S. Hence S = N.

Question 6

Describe the strong form of induction

Answer 6

Let P(n) be a family of statements for n ≥ 0. Suppose
that
• (Initial Step) P(0) is true;
• (Inductive Step) for any n ≥ 0, if P(0), P(1), . . . , P(n) are all true then so is P(n + 1).
Then P(n) is true for all n ≥ 0

Question 7

Describe induction where the intital step uses N, not 0

Answer 7

Let N be an integer and let P(n) be a family of statements for n ≥ N. Suppose that
• (Initial Step) P(N) is true;
• (Inductive Step) for any n ≥ N, if P(n) is true then P(n + 1) is also true.
Then P(n) is true for all n ≥ N.

Question 8

Optional - Prove the Strong form of Induction

Answer 8

For n ≥ 0, let Q(n) be the statement ‘P(k) is true for 0≤k≤n’. The assumptions of the
above theorem are equivalent to: (i) Q(0) (which is the same as P(0)) is true and (ii) if Q(n) is true
then Q(n + 1) is true. By induction (as stated in Theorem 9) we know that Q(n) is true for all n.
As P(n) is a consequence of Q(n), then P(n) is true for all n

Question 9

Every non-empty subset of the natural numbers has a [ ] element

Answer 9

minimal

Question 10

A strictly decreasing sequence pf natural numbers is [ ]

Answer 10

finite

Question 11

Define addition of natural numbers

Answer 11

(i) x + 0 := x for all x ∈ N.

(ii) x + (n + 1) := (x + n) + 1.

Question 12

Describe associativity

Answer 12

x + (y + z) = (x + y) + z for all x, y, z ∈ N

Question 13

Describe commutativity

Answer 13

x + y = y + x for all x, y ∈ N.

Question 14

What is the binomial coefficient?

Answer 14

(n k) = n!/(k!(n-k)!)

where 0 ≤ k ≤ n

Question 15

Prove the identity for (x+y)^n

Answer 15

pg 12

Question 16

What does T ⊆ S mean?

Answer 16

T is contained in S or
T is a subset of S or
whenever x ∈ T then x ∈ S

Question 17

What does ∅ represent?

Answer 17

The empty set

Question 18

Does the order of elements in a set matter?

Answer 18

No

Question 19

Define a power set

Answer 19

Give a set A its power set, denoted P(A), is the set of all subsets of A.
(Fancy P)

Question 20

Define the following bounded intervals:
(a,b)
(a,b]
[a,b]
(a, ∞)

Answer 20

(a, b) = {x ∈ R : a < x < b}
(a, b] = {x ∈ R : a < x b}
[a, b] = {x ∈ R : a x b}
(a, ∞) = {x ∈ R : a < x}

Question 21

What does A\B mean in set theory?

Answer 21

The complement of B in A, written A\B, or sometimes A−B, is the subset consisting of those
elements that are in A and not in B, that is:
A\B = {x ∈ A : x /∈ B} = A ∩ B’

Question 22

Define when two sets are disjoint

Answer 22

A∩B = ∅

Question 23

What is the Cartesian product?

Answer 23

Let S and T be sets. Their Cartesian product S × T is the set of all ordered pairs
(s, t) where s ∈ S and t ∈ T. Note that — as the name suggests — order matters in an ordered pair.
So (1, 2) ≠ (2, 1) whilst {1, 2} = {2, 1} as sets

Question 24

What does S^n mean in set theory?

Answer 24

If n ≥ 1 then we write S^n for all order n-tuples, that is vectors of the form (s₁, s₂, …, s) where sᵢ ∈ S for all i

Question 25

Define the disjoint union of two sets

Answer 25

Their disjoint union A ⊔ B is defined to be
A × {0} ∪ B × {1}
The set A is now identified with A × {0} and B with B × {1} and any element x that is in both A
and B appears twice in the disjoint union as (x, 0) and (x, 1)

Question 26

What is the notation of P implies Q? What are other ways of saying this?

Answer 26

P ⇒ Q
P is sufficient for Q and the Q is necessary for P
if P then Q
Q if P
P only if Q

Question 27

What is the notation of P if and only if Q? What are other ways of saying this?

Answer 27

P ⇔ Q

P is necessary and sufficient for Q

Question 28

What does P ∧ Q and P ∨ Q mean?

Answer 28

Logic:
We write P ∧ Q for the statement “P and Q” which holds when both P and Q are true
We write P ∨ Q for the statement “P or Q” which holds when either P or Q (or both) is
true

Question 29

What does ¬P mean?

Answer 29

We write ¬P for “not P” or the “negation of P”. This is the statement that is true precisely
when P is false, and vice versa

Question 30

What is the universal quantifier?

The existential qualifier?

Answer 30

Universal: ∀
Existential: ∃

Question 31

What is double inclusion?

Answer 31

Let A and B be two subsets of a set S. Then A = B if and

only if A ⊆ B and B ⊆ A

Question 32

State the distributive laws (Set and logic)

Answer 32

Let A, B, C be subsets of a set S. Then
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
and
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
(And equivalent in logic)

Question 33

Prove the distributive laws

Answer 33

pg19

Question 34

What is the distributive law for real numbers?

Answer 34

a(b + c) = ab + ac

Question 35

Does the order of union and intersections matter?

Answer 35

Yes

Question 36

What is the contrapositive of P ⇒ Q? Is this equivalent?

Answer 36

Yes

¬Q ⇒ ¬P

Question 37

State De Morgan’s laws - finite version

Answer 37

¬(P ∧ Q) ⇔ (¬P) ∨ (¬Q);
¬(P ∨ Q) ⇔ (¬P) ∧ (¬Q).

For any number of sets, and same of set theory

Question 38

State De Morgan’s laws - Logical version

Answer 38

Let P(x) be a family of statements,
indexed by the elements x of some set S. Then
¬(∀x ∈ S P(x)) ⇔ ∃x ∈ S ¬P(x);
¬(∃x ∈ S P(x)) ⇔ ∀x ∈ S ¬P(x)

Question 39

What does vacuously true mean?

Answer 39

Whatever the statement P(x), the statement
∃x ∈ ∅ P(x)
is untrue as no such x exists. This means it’s negation
¬(∃x ∈ ∅ P(x)) ⇔ ∀x ∈ ∅ ¬P(x)
is always true, no matter what P (or its negation) is. We say a statement of the form
∀x ∈ ∅ P(x)
is vacuously true. Essentially as ∅ there is no x for which the statement needs verifying, and so
the statement is true.

Question 40

What does “|” mean?

Answer 40

meaning “divides” or “is a factor of”, which compares pairs of positive integers

Question 41

What are |, ≤, ⊆?

Answer 41

Binary relations

Question 42

Define a binary relation

Answer 42

A binary relation (or simply relation) R on a set S is a subset of S × S. If
(s, t) ∈ R (where s, t ∈ S) then we write sRt

Question 43

Define:

Reflexive

Answer 43

Let S be a set, R a relation on S and s, t, u ∈ S

R is reflexive if sRs for all s in S

Question 44

Define:

Symmetric

Answer 44

Let S be a set, R a relation on S and s, t, u ∈ S

R is symmetric if whenever sRt then tRs

Question 45

Define:

Anti-symmetric

Answer 45

Let S be a set, R a relation on S and s, t, u ∈ S

R is anti-symmetric if whenever sRt and tRs then s = t

Question 46

Define:

Transitive

Answer 46

Let S be a set, R a relation on S and s, t, u ∈ S

R is transitive if whenever sRt and tRu then sRu

Question 47

What is a partial order?

Answer 47

Let S be a set and R a relation on S.

We say that R is a partial order on S if R is reflexive, anti-symmetric and transitive

Question 48

What is a total order?

Answer 48

Let S be a set and R a relation on S

A partial order is said to be a total order if for every a, b ∈ S then aRb or bRa (or both)

Question 49

What symbol often denotes partial orders?

Answer 49

≤

Question 50

Give an example of a partial order on P(S) - where P(S) is the power set of the set S

Answer 50

⊆

Question 51

What is an equivalence relation?

Answer 51

We say that a relation R on a set S is an equivalence relation if R is reflexive,
symmetric and transitive

Question 52

What is an equivalence class?

Answer 52

Given an equivalence relation ∼ on a set S with a ∈ S, then the equivalence class
of a, written ¯a or [a] , is the subset
¯a = {x ∈ S : x ∼ a}

Question 53

Let ∼ be an equivalence relation on the set S. What do the equivalence classes of ∼ form?

Answer 53

A partition of S

Question 54

Define a partition of S

Answer 54

Let S be a set and Λ be an indexing set. We say that a collection of subsets Aλ of S
(where λ ∈ Λ) is a partition of S if
(i) Aλ ≠ ∅ for each λ ∈ Λ;
(ii) ∪
λ∈Λ
Aλ = S;
(iii) if λ ≠ µ then Aλ ∩ Aµ = ∅, or equivalently: if Aλ ∩ Aµ ≠ ∅ then λ = µ

Question 55

Theorem 72

Answer 55

pg30

Question 56

A function f : X → Y

What is the domain and codomain of f?

Answer 56

Domain: the set X
Codomain: the set Y

Question 57

What is a mapping/map?

Answer 57

A function

Question 58

What is the image/range of a function?

Answer 58

the set
f(X) = {f(x) : x ∈ X} ⊆ Y

Typically the image f(X) is a proper subset of the codomain Y

Question 59

What does it mean for a function to be well-defined?

Answer 59

(a) The assignment needs to be defined for all elements of the domain with the output in the
codomain
Functions need to be carefully defined on sets of equivalence classes

Question 60

Define the image and pre-image of f

Answer 60

(a) Given A ⊆ X, then the image of A, denoted f(A), is the subset
f(A) = {f(x) : x ∈ A} ⊆ Y.
(b) Given C ⊆ Y , then the pre-image of C, written f⁻¹(C), is the subset.
f⁻¹(C) = {x : f(x) ∈ C} ⊆ X.

Question 61

Let f : X → Y be a function
For any A ⊆ X
describe f⁻¹(f(A))

Answer 61

A ⊆ f⁻¹(f(A))

but do not have equality in general.

Question 62

Let f : X → Y be a function

For any C ⊆ Y describe f(f⁻¹(C))

Answer 62

f(f⁻¹(C)) ⊆ C

but do not have equality in general.

Question 63

What is the composition of two functions?

Answer 63

Given two functions f : X → Y and g : Y → Z the composition g ◦ f : X → Z is
defined by
(g ◦ f)(x) = g(f(x)) for all x ∈ X

Question 64

Is composition associative?

Answer 64

Yes
Let f : W → X, g : X → Y, h: Y → Z be three
functions. Then
f ◦ (g ◦ h) = (f ◦ g) ◦ h

Question 65

Let f : X → Y be a function between two sets

Define Injective

Answer 65

We say that f is 1—1 or injective if whenever f(x₁) = f(x₂) for x₁, x₂ ∈ X then x₁ = x₂

Question 66

Let f : X → Y be a function between two sets

Define Surjective

Answer 66

We say that f is onto or surjective if for each y ∈ Y there exists x ∈ X such that f(x) = y

Question 67

Let f : X → Y be a function between two sets

Define bijective

Answer 67

We say that f is bijective if f is 1—1 and onto

Question 68

If f and g are onto, is g ◦ f onto?

Answer 68

Yes

Question 69

If g ◦ f is onto, is g and f onto?

Answer 69

g is onto, but f isn’t necessarily

Question 70

If f and g are 1-1, is g ◦ f?

Answer 70

Yes

Question 71

If g ◦ f is 1-1, is g and f 1-1?

Answer 71

f is 1-1, but g isn’t necessarily

Question 72

Let f : X → Y with A ⊆ X and B ⊆ Y

Describe f⁻¹(f(A)), if f is 1-1

Answer 72

f⁻¹(f(A)) = A

Question 73

Let f : X → Y with A ⊆ X and B ⊆ Y

Describe f(f⁻¹(B)), if f is onto

Answer 73

f(f⁻¹(B)) = B

Question 74

Let f : X → Y with A ⊆ X and B ⊆ Y

In general f(f⁻¹(B)) = B ∩ (?)

Answer 74

f(f⁻¹(B)) = B ∩ f(X)

Question 75

If f⁻¹(f(A)) = A for all A ⊆ X then….

Answer 75

f is 1-1

Question 76

If f(f⁻¹(B)) = B for all B ⊆ Y then….

Answer 76

then f is onto

Question 77

Define an inverse of a function

Answer 77

Let f : X → Y be a function. We say that an inverse for f is a function g : Y → X
such that
g ◦ f = idₓ, f ◦ g = idᵧ

Question 78

Does a function have a unique inverse?

Answer 78

Yes

Question 79

Describe the relationship between bijective and invertible

Answer 79

A function f : S → T is bijective if and only if it is invertible

Question 80

Let f : R → S be a map between non-empty sets R and S

f is 1—1 if and only if there is a map g : S → R such that ….

Answer 80

g ◦ f = idᵣ

Question 81

Let f : R → S be a map between non-empty sets R and S

f is onto if and only if there is a map g : S → R such that…

Answer 81

f ◦ g = idₛ

Question 82

Define the cardinality of a set

Answer 82

Let n ≥ 1 be a natural number and X be a set. We define the cardinality |X| of
X to be n if there is a bijection from X to the set {1, 2, . . . , n} . The cardinality of the empty set is
defined to be 0.

Question 83

A set X is said to be finite if its cardinality …

Answer 83

is some natural number

Question 84

Why is the cardinality of a finite set is well-defined?

Answer 84

Let m, n ∈ N with m < n. There is no bijection between {1, 2, . . . , m} and {1, 2, . . . , n}

Question 85

Describe the pigeonhole principle

Answer 85

Let m, n ∈ N with m > n ≥ 1 and let f : {1, 2, . . . , m} →
{1, 2, . . . , n} . Then there are distinct 1 ≤ x₁ < x₂ ≤ m with f(x₁) = f(x₂). This means that there
is no 1—1 map from {1, 2, . . . , m} to {1, 2, . . . , n} . (The result gets its name from the analogy that if
there are m letters that need to go into n pigeonholes, then at least one hole contains two or more
letters.)

Question 86

Let S and T be finite sets

When is |S| ≤ |T|?

Answer 86

Iff there is a 1-1 map from S to T

Question 87

Let S and T be finite sets

When is |S| ≥ |T|?

Answer 87

Iff there is an onto map from S to T

Question 88

How many bijections are there from {1, 2, . . . , n} to {1, 2, . . . , n}?
Given n ≥ 1

Answer 88

n!

Question 89

How many subsets are there of the set {1, 2, …, n}?

Answer 89

2^n

Question 90

How many subsets are there of the set {1, 2, …, n} with k elements?

Answer 90

(n k)

n choose k

Question 91

A and B are two finite sets

What is the cardinality of the disjoint union A ⊔ B?

Answer 91

|A| + |B|

Question 92

A and B are two finite sets

What is the cardinality of the Cartesian product A × B?

Answer 92

|A| |B|

Question 93

A and B are two finite sets

What is the cardinality of the power set P(A)?

Answer 93

2^|A|

Question 94

A and B are two finite sets

How many maps are there from A to B?

Answer 94

|B|^|A|

Question 95

|A| = |B| if?

Answer 95

there is a bijection from A to B

Question 96

|A| ≥ |B| if?

Answer 96

there is surjection from A to B

Question 97

|A| ≤ |B| if?

Answer 97

there is a injection from A to B

Question 98

What theorem states that if |A| ≥ |B| and |A| ≤ |B| then |A| = |B|?

Answer 98

Cantor-Bernstein-Schröder theorem

Question 99

What proves that there are infinitely many infinities?

Answer 99

any set A has more subsets than it does elements. That is 2^|A| > |A| and shows that
there infinitely many different infinities!

Question 100

Let f : R → S and g : S → T be surjective

Is g ◦ f is surjective?

Answer 100

Yes

Question 101

Let f : R → S and g : S → T be maps, such that g ◦ f is surjective
is f surjective?

Answer 101

Yes