NSF Flashcards
What is a Statement?
A statement or assertion is an expression which can be a complete sentence by itself, and is either true or false.
What is a Negation?
If P is a statement, the negation of P is the statement “not P” (that is “P is false”)
What is an Implication?
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”.
What is a converse?
The converse of P ⇒ Q is the implication Q ⇒ P
What is the contrapositive?
The contrapositive of P ⇒ Q is the implication (not Q) ⇒ (not P)
What is a counterexample?
to disprove a “for all” statement, you need to give an example for which the statement isn’t true
What is divisibility?
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.
What is a prime number?
n is prime if n > 1 and n has no factors except 1 and n
What is a composite number?
n is composite if n > 1 and n is not prime.
What is prime factorisation?
every natural number n can be written as a product of primes, and this “prime factorisation” is unique (up to re-ordering)
What is the Fundamental Theorem of Arithmetic?
The fact that prime factorisation is unique up to re-ordering
What is the greatest common divisor?
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.
What does it mean to be coprime?
We say that a and b are coprime if gcd(a, b) = 1. This means they have no common factors except 1
What is the lowest common multiple
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
How do you calculate the lcm(a,b)
ab/gcd(a,b)
What is the Cartesian product?
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
What is the cardinality of a set?
If A is a finite set then the cardinality of A is the number of elements it contains
What is a Power set?
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)
Theorem 5.2 cardinality of a power set
Suppose X is a finite set, and |X| = n. Then |P(X)| = 2^n
What is a function?
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
When is a function Injective?
f is injective if f(a1) ̸= f(a2) whenever a1, a2 ∈ A and a1 ̸= a2
When is a function Surjective?
f is surjective if for every b ∈ B there is some a ∈ A with f(a) = b
When is a function Bijective?
f is bijective if it is both injective and surjective
What is an Inverse to a function?
Suppose f : A → B is a function. An inverse to f is a function g : B → A satisfying the two conditions:
- g(f(a)) = a for all a ∈ A
- f(g(b)) = b for all b ∈ B
When is a function invertible?
When it is bijective
What is the restriction of a function?
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
Cardinality of bijections on two sets A and B
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|
What is the image of a function?
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}
What is the inverse image?
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}
What is a relation?
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
When is a relation Reflexive?
reflexive if a R a for all a ∈ X
When is a relation Symmetric?
symmetric if a R b implies b R a, for a, b ∈ X
When is a relation Anti-symmetric?
anti-symmetric if a R b and b R a imply that a = b, for a, b ∈ X
When is a relation Transitive?
transitive if a R b and b R c imply that a R c, for a, b, c ∈ X
What is a Sequence?
A sequence is an ordered list a1, a2, a3, . . . of elements of some set X
What is a Subsequence?
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
When is a sequence increasing?
increasing if xk < xk+1 for all k ∈ N
When is a sequence decreasing?
decreasing if xk > xk+1 for all k ∈ N
When is a sequence weakly increasing?
weakly increasing if xk ⩽ xk+1 for all k ∈ N
When is a sequence weakly decreasing?
weakly decreasing if xk ⩾ xk+1 for all k ∈ N
When is a sequence constant?
constant if xk = xk+1 for all k ∈ N
What are Real numbers?
A real number is an infinite decimal.
Which is made by the combination of both rational and irrational numbers
What is an upper bound of a set X?
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.
What is the Supremum?
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
What is a complex number?
A complex number is an expression a + bi where a, b ∈ R. We write C for the set of all complex numbers
What is the complex conjugate?
. 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)
Modulus of a complex number
The modulus of z is √a^2 + b^2; it is denoted by |z|.
Argument of a complex number
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)
Polar form of complex numbers
z = r(cos θ + i sin θ)
Conjugate of the polar form
z(dashed) = r(cos θ − i sin θ) = r(cos(−θ) + i sin(−θ))
De Moivre’s Theorem
For all n ∈ N and θ ∈ R
(cos θ + i sin θ)^n = cos(nθ) + i sin(nθ)
