Intro to Uni Maths Flashcards
Define a natural number
non-negative whole number
Define a binary operation
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
What is the smallest set where the following holds?:
0 is in the set
and if n ∈ N then n + 1 ∈ N
The natural numbers
Proof by induction:
What is the initial case/step?
What is the inductive step?
What is the inductive hypothesis?
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
Optional - Prove the principle of induction:
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.
Describe the strong form of induction
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
Describe induction where the intital step uses N, not 0
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.
Optional - Prove the Strong form of Induction
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
Every non-empty subset of the natural numbers has a [ ] element
minimal
A strictly decreasing sequence pf natural numbers is [ ]
finite
Define addition of natural numbers
(i) x + 0 := x for all x ∈ N.
(ii) x + (n + 1) := (x + n) + 1.
Describe associativity
x + (y + z) = (x + y) + z for all x, y, z ∈ N
Describe commutativity
x + y = y + x for all x, y ∈ N.
What is the binomial coefficient?
(n k) = n!/(k!(n-k)!)
where 0 ≤ k ≤ n
Prove the identity for (x+y)^n
pg 12
What does T ⊆ S mean?
T is contained in S or
T is a subset of S or
whenever x ∈ T then x ∈ S
What does ∅ represent?
The empty set
Does the order of elements in a set matter?
No
Define a power set
Give a set A its power set, denoted P(A), is the set of all subsets of A.
(Fancy P)
Define the following bounded intervals: (a,b) (a,b] [a,b] (a, ∞)
(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}
What does A\B mean in set theory?
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’
Define when two sets are disjoint
A∩B = ∅
What is the Cartesian product?
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
What does S^n mean in set theory?
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
Define the disjoint union of two sets
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)
What is the notation of P implies Q? What are other ways of saying this?
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
What is the notation of P if and only if Q? What are other ways of saying this?
P ⇔ Q
P is necessary and sufficient for Q
What does P ∧ Q and P ∨ Q mean?
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
What does ¬P mean?
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
What is the universal quantifier?
The existential qualifier?
Universal: ∀
Existential: ∃
What is double inclusion?
Let A and B be two subsets of a set S. Then A = B if and
only if A ⊆ B and B ⊆ A
State the distributive laws (Set and logic)
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)
Prove the distributive laws
pg19
What is the distributive law for real numbers?
a(b + c) = ab + ac
Does the order of union and intersections matter?
Yes
What is the contrapositive of P ⇒ Q? Is this equivalent?
Yes
¬Q ⇒ ¬P
State De Morgan’s laws - finite version
¬(P ∧ Q) ⇔ (¬P) ∨ (¬Q);
¬(P ∨ Q) ⇔ (¬P) ∧ (¬Q).
For any number of sets, and same of set theory
State De Morgan’s laws - Logical version
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)
What does vacuously true mean?
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.
What does “|” mean?
meaning “divides” or “is a factor of”, which compares pairs of positive integers
What are |, ≤, ⊆?
Binary relations
Define a binary relation
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
Define:
Reflexive
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
Define:
Symmetric
Let S be a set, R a relation on S and s, t, u ∈ S
R is symmetric if whenever sRt then tRs
Define:
Anti-symmetric
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
Define:
Transitive
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
What is a partial order?
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
What is a total order?
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)
What symbol often denotes partial orders?
≤
Give an example of a partial order on P(S) - where P(S) is the power set of the set S
⊆
What is an equivalence relation?
We say that a relation R on a set S is an equivalence relation if R is reflexive,
symmetric and transitive
What is an equivalence class?
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}Let ∼ be an equivalence relation on the set S. What do the equivalence classes of ∼ form?
A partition of S
Define a partition of S
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 λ = µ
Theorem 72
pg30
A function f : X → Y
What is the domain and codomain of f?
Domain: the set X
Codomain: the set Y
What is a mapping/map?
A function
What is the image/range of a function?
the set
f(X) = {f(x) : x ∈ X} ⊆ Y
Typically the image f(X) is a proper subset of the codomain Y
What does it mean for a function to be well-defined?
(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
Define the image and pre-image of f
(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.
Let f : X → Y be a function
For any A ⊆ X
describe f⁻¹(f(A))
A ⊆ f⁻¹(f(A))
but do not have equality in general.
Let f : X → Y be a function
For any C ⊆ Y describe f(f⁻¹(C))
f(f⁻¹(C)) ⊆ C
but do not have equality in general.
What is the composition of two functions?
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
Is composition associative?
Yes
Let f : W → X, g : X → Y, h: Y → Z be three
functions. Then
f ◦ (g ◦ h) = (f ◦ g) ◦ h
Let f : X → Y be a function between two sets
Define Injective
We say that f is 1—1 or injective if whenever f(x₁) = f(x₂) for x₁, x₂ ∈ X then x₁ = x₂
Let f : X → Y be a function between two sets
Define Surjective
We say that f is onto or surjective if for each y ∈ Y there exists x ∈ X such that f(x) = y
Let f : X → Y be a function between two sets
Define bijective
We say that f is bijective if f is 1—1 and onto
If f and g are onto, is g ◦ f onto?
Yes
If g ◦ f is onto, is g and f onto?
g is onto, but f isn’t necessarily
If f and g are 1-1, is g ◦ f?
Yes
If g ◦ f is 1-1, is g and f 1-1?
f is 1-1, but g isn’t necessarily
Let f : X → Y with A ⊆ X and B ⊆ Y
Describe f⁻¹(f(A)), if f is 1-1
f⁻¹(f(A)) = A
Let f : X → Y with A ⊆ X and B ⊆ Y
Describe f(f⁻¹(B)), if f is onto
f(f⁻¹(B)) = B
Let f : X → Y with A ⊆ X and B ⊆ Y
In general f(f⁻¹(B)) = B ∩ (?)
f(f⁻¹(B)) = B ∩ f(X)
If f⁻¹(f(A)) = A for all A ⊆ X then….
f is 1-1
If f(f⁻¹(B)) = B for all B ⊆ Y then….
then f is onto
Define an inverse of a function
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ᵧ
Does a function have a unique inverse?
Yes
Describe the relationship between bijective and invertible
A function f : S → T is bijective if and only if it is invertible
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 ….
g ◦ f = idᵣ
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…
f ◦ g = idₛ
Define the cardinality of a set
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.
A set X is said to be finite if its cardinality …
is some natural number
Why is the cardinality of a finite set is well-defined?
Let m, n ∈ N with m < n. There is no bijection between {1, 2, . . . , m} and {1, 2, . . . , n}
Describe the pigeonhole principle
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.)
Let S and T be finite sets
When is |S| ≤ |T|?
Iff there is a 1-1 map from S to T
Let S and T be finite sets
When is |S| ≥ |T|?
Iff there is an onto map from S to T
How many bijections are there from {1, 2, . . . , n} to {1, 2, . . . , n}?
Given n ≥ 1
n!
How many subsets are there of the set {1, 2, …, n}?
2^n
How many subsets are there of the set {1, 2, …, n} with k elements?
(n k)
n choose k
A and B are two finite sets
What is the cardinality of the disjoint union A ⊔ B?
|A| + |B|
A and B are two finite sets
What is the cardinality of the Cartesian product A × B?
|A| |B|
A and B are two finite sets
What is the cardinality of the power set P(A)?
2^|A|
A and B are two finite sets
How many maps are there from A to B?
|B|^|A|
|A| = |B| if?
there is a bijection from A to B
|A| ≥ |B| if?
there is surjection from A to B
|A| ≤ |B| if?
there is a injection from A to B
What theorem states that if |A| ≥ |B| and |A| ≤ |B| then |A| = |B|?
Cantor-Bernstein-Schröder theorem
What proves that there are infinitely many infinities?
any set A has more subsets than it does elements. That is 2^|A| > |A| and shows that
there infinitely many different infinities!
Let f : R → S and g : S → T be surjective
Is g ◦ f is surjective?
Yes
Let f : R → S and g : S → T be maps, such that g ◦ f is surjective
is f surjective?
Yes
