NSF

Question 1

What is a Statement?

Answer 1

A statement or assertion is an expression which can be a complete sentence by itself, and is either true or false.

Question 2

What is a Negation?

Answer 2

If P is a statement, the negation of P is the statement “not P” (that is “P is false”)

Question 3

What is an Implication?

Answer 3

Suppose that P and Q are statements. The statement “If P then Q” is called an implication. It is false if P is true and Q is false. Otherwise it is true. We write P ⇒ Q to mean “If P then Q”.

Question 4

What is a converse?

Answer 4

The converse of P ⇒ Q is the implication Q ⇒ P

Question 5

What is the contrapositive?

Answer 5

The contrapositive of P ⇒ Q is the implication (not Q) ⇒ (not P)

Question 6

What is a counterexample?

Answer 6

to disprove a “for all” statement, you need to give an example for which the statement isn’t true

Question 7

What is divisibility?

Answer 7

Suppose d, n ∈ N. We say that d divides n if there exists some k ∈ N with n = dk. We write d | n to mean that d divides n.

Question 8

What is a prime number?

Answer 8

n is prime if n > 1 and n has no factors except 1 and n

Question 9

What is a composite number?

Answer 9

n is composite if n > 1 and n is not prime.

Question 10

What is prime factorisation?

Answer 10

every natural number n can be written as a product of primes, and this “prime factorisation” is unique (up to re-ordering)

Question 11

What is the Fundamental Theorem of Arithmetic?

Answer 11

The fact that prime factorisation is unique up to re-ordering

Question 12

What is the greatest common divisor?

Answer 12

The greatest common divisor of a and b is the largest natural number d
such that d | a and d | b. We write gcd(a, b) for the greatest common divisor of a and b.

Question 13

What does it mean to be coprime?

Answer 13

We say that a and b are coprime if gcd(a, b) = 1. This means they have no common factors except 1

Question 14

What is the lowest common multiple

Answer 14

The lowest common multiple of a and b is the smallest m ∈ N such that a | m and b | m. We write lcm(a, b) for the lowest common multiple of a and b

Question 15

How do you calculate the lcm(a,b)

Answer 15

ab/gcd(a,b)

Question 16

What is the Cartesian product?

Answer 16

If A and B are sets, the Cartesian product of A and B is the set of all ordered pairs (a, b) with
a ∈ A and b ∈ B. We denote this by A × B

Question 17

What is the cardinality of a set?

Answer 17

If A is a finite set then the cardinality of A is the number of elements it contains

Question 18

What is a Power set?

Answer 18

If X is a set, we define the power set of X to be the set of all subsets of X. It is denoted by P(X)

Question 19

Theorem 5.2 cardinality of a power set

Answer 19

Suppose X is a finite set, and |X| = n. Then |P(X)| = 2^n

Question 20

What is a function?

Answer 20

Let A and B be sets. A function from A to B is a rule which assigns an element of B to each element of A

Question 21

When is a function Injective?

Answer 21

f is injective if f(a1) ̸= f(a2) whenever a1, a2 ∈ A and a1 ̸= a2

Question 22

When is a function Surjective?

Answer 22

f is surjective if for every b ∈ B there is some a ∈ A with f(a) = b

Question 23

When is a function Bijective?

Answer 23

f is bijective if it is both injective and surjective

Question 24

What is an Inverse to a function?

Answer 24

Suppose f : A → B is a function. An inverse to f is a function g : B → A satisfying the two conditions:

1. g(f(a)) = a for all a ∈ A
2. f(g(b)) = b for all b ∈ B

Question 25

When is a function invertible?

Answer 25

When it is bijective

Question 26

What is the restriction of a function?

Answer 26

Suppose f : A → B is a function, and D ⊆ A. The restriction of f to D is the function g : D → B defined by g(d) = f(d) for all d ∈ D. This function is written as f|D

Question 27

Cardinality of bijections on two sets A and B

Answer 27

Let f : A → B be a function:

(a) If f is injective then |A| ⩽ |B|.

(b) If f is surjective then |A| ⩾ |B|

c) If f is bijective then |A| = |B|

Question 28

What is the image of a function?

Answer 28

Suppose f : A → B is a function, and C ⊆ A. The image of C under A is the set of all values of f at elements of C; that is, the set:

f(C) = {f(a) : a ∈ C}

Question 29

What is the inverse image?

Answer 29

Suppose f : A → B is a function and D ⊆ B. The inverse image of D under f is the set of all elements of A that get mapped to D by f; that is, the set:

f^−1(D) = {a ∈ A : f(a) ∈ D}

Question 30

What is a relation?

Answer 30

Suppose X is a set. A relation on X is a property which may or may not hold for each ordered pair of elements of X

Question 31

When is a relation Reflexive?

Answer 31

reflexive if a R a for all a ∈ X

Question 32

When is a relation Symmetric?

Answer 32

symmetric if a R b implies b R a, for a, b ∈ X

Question 33

When is a relation Anti-symmetric?

Answer 33

anti-symmetric if a R b and b R a imply that a = b, for a, b ∈ X

Question 34

When is a relation Transitive?

Answer 34

transitive if a R b and b R c imply that a R c, for a, b, c ∈ X

Question 35

What is a Sequence?

Answer 35

A sequence is an ordered list a1, a2, a3, . . . of elements of some set X

Question 36

What is a Subsequence?

Answer 36

A subsequence of the sequence (ak )∞
k=1 is a sequence obtained from (ak )∞
k=1 by deleting some
elements and keeping the rest in the same order

Question 37

When is a sequence increasing?

Answer 37

increasing if xk < xk+1 for all k ∈ N

Question 38

When is a sequence decreasing?

Answer 38

decreasing if xk > xk+1 for all k ∈ N

Question 39

When is a sequence weakly increasing?

Answer 39

weakly increasing if xk ⩽ xk+1 for all k ∈ N

Question 40

When is a sequence weakly decreasing?

Answer 40

weakly decreasing if xk ⩾ xk+1 for all k ∈ N

Question 41

When is a sequence constant?

Answer 41

constant if xk = xk+1 for all k ∈ N

Question 42

What are Real numbers?

Answer 42

A real number is an infinite decimal.

Which is made by the combination of both rational and irrational numbers

Question 43

What is an upper bound of a set X?

Answer 43

Suppose X ⊆ R, and u ∈ R. We say that u is an upper bound for X if x ⩽ u for all x ∈ X.
X is bounded above if it has an upper bound.

Question 44

What is the Supremum?

Answer 44

X ⊆ R. A supremum for X is a real number s such that:
⋄ s is an upper bound for X, and
⋄ if t is any other upper bound for X, then t ⩾ s

Question 45

What is a complex number?

Answer 45

A complex number is an expression a + bi where a, b ∈ R. We write C for the set of all complex numbers

Question 46

What is the complex conjugate?

Answer 46

. Let z = a + bi ∈ C be a complex number. The complex conjugate of z is the number a − bi,
denoted by z( with a dash on the top)

Question 47

Modulus of a complex number

Answer 47

The modulus of z is √a^2 + b^2; it is denoted by |z|.

Question 48

Argument of a complex number

Answer 48

If z ̸= 0, the argument of z is the unique θ with b/|z|= sin θ,
a/|z|= cos θ and 0 ⩽ θ < 2π; it is denoted
by arg(z)

Question 49

Polar form of complex numbers

Answer 49

z = r(cos θ + i sin θ)

Question 50

Conjugate of the polar form

Answer 50

z(dashed) = r(cos θ − i sin θ) = r(cos(−θ) + i sin(−θ))

Question 51

De Moivre’s Theorem

Answer 51

For all n ∈ N and θ ∈ R

(cos θ + i sin θ)^n = cos(nθ) + i sin(nθ)