Foundations

Question 1

Is 0 considered to be in the Natural Numbers?

Answer 1

Yes

Question 2

What is the Axiom of Extension?

Answer 2

Suppose that X and Y are sets and that for any x∈X we have x∈Y and for any y∈Y we have y∈X, then X=Y.

Question 3

Define a subset.

Answer 3

Suppose X is a set and for any x∈X we have x∈Y, then we call X a subset of Y, denoted X⊂Y.
If X and Y are not equal, X is a proper subset of Y.

Question 4

What is a singleton?

Answer 4

A set with one element.

Question 5

What is a function?

Answer 5

A function f:X->Y consists of the following:
-A domain X
-A codomain Y
-A rule f which for every x∈X gives an element f(x)∈Y.

Question 6

What is the identity function?

Answer 6

The function that maps x to itself
ie. Id(x) = x

Question 7

What is an injection, surjection and bijection?

Answer 7

Suppose that X and Y are sets and f:X->Y is a function, then:
-Suppose that for every x,x’∈X, if f(x)=f(x’) then x=x’, we call f injective
-Suppose that for every y∈Y, there is some x∈X so f(x)=y, we call f surjective.
Suppose that f is both injective and surjective, we call f bijective.

Question 8

What is cardinality and when is a set finite.

Answer 8

Cardinality is the number of elements in a set.
If f:X->Y is a bijective function the X and Y have the same cardinality, denoted |X|=|Y|
A set X is finite if |X|= n for some n∈N

Question 9

What is Cantor’s Theorem?

Answer 9

Suppose the X is a set and f is a function f:X->P(X) from X to its power set, then f is not a surjection.

Question 10

What is an ordered pair?

Answer 10

Suppose that X and Y are sets. Suppose that x, x′ ∈ X
and y, y′ ∈ Y are elements. Then an ordered pair (x, y) contains x and y, in that order.
Two ordered pairs (x, y) and (x′, y′) are equal if and only if x = x′ and y = y′.
If (x, y) is an ordered pair then we call x its first entry and y its
second entry.

Question 11

What is the set of ordered pairs from two sets?

Answer 11

Suppose that X and Y are sets. Then the collection
of all ordered pairs with first entry from X and second from Y is
X × Y = {(x, y) ∣ x ∈ X, y ∈ Y } and is called the cartesian product of X and Y .

Question 12

What is a relation?

Answer 12

A relation R from X to Y consists of the following.
● A set X, called the domain.
● A set Y , called the codomain.
● A subset of X × Y .
If X = Y then we say that R is “a relation on X”. If (x, y) is an element of R we may denote this by writing xRy.
The empty set is a subset of X × Y ; this gives the empty relation.
Likewise X × Y is a subset of itself; this gives the universal relation.
When X = Y then the set {(x, y) ∈ X^2 ∣ x = y} gives the identity relation on X.

Question 13

When is a relation graphical?

Answer 13

Suppose that X and Y are sets. A relation G from X to Y is graphical if for every x ∈ X there is exactly one y ∈ Y so that (x, y) lies in G.

Question 14

Is a function a relation?

Answer 14

A function f∶ X → Y is a relation G, from X to Y , which is graphical. If (x, y) lies in G then we write f(x) = y

Question 15

What is a list?

Answer 15

Suppose that A is a set. Suppose that n is a natural number. A list L is a function L∶ [n] → A. We call n the length of the list L. We also say that the elements of L are taken from A.

Question 16

State the known Union qualities?

Answer 16

(1) X ∪ ∅ = X (identity)
(2) (X ∪ Y ) ∪ Z = X ∪ (Y ∪ Z) (associativity)
(3) X ∪ Y = Y ∪ X (commutativity)
(4) X ⊂ Y if and only if X ∪ Y = Y (absorption)
(5) X ∪ X = X (idempotent)

Question 17

State the known Intersection qualities?

Answer 17

(1) X ∩ ∅ = ∅ (annihilator)
(2) (X ∩ Y ) ∩ Z = X ∩ (Y ∩ Z) (associativity)
(3) X ∩ Y = Y ∩ X (commutativity)
(4) X ⊂ Y if and only if X ∩ Y = X (absorption)
(5) X ∩ X = X (idempotent)

Question 18

What is set difference?

Answer 18

Suppose that X and Y are sets. The collection X − Y = {x ∈ X ∣ x ∉ Y } is called the set-theoretic difference of X and Y .

Question 19

What is the link between a function being injective/surjective and inverses?

Answer 19

Suppose that X and Y are non-empty sets. Suppose that
f∶ X → Y is a function. Then we have the following.
(1) f is injective if and only if f has a left inverse.
(2) f is surjective if and only if f has a right inverse.
(3) f is bijective if and only if f has an inverse. In this case the
inverse is unique.

Suppose that X, Y , and Z are sets. Suppose that f∶ X → Y and g∶ Y → Z are functions. Then we have the following.
(1) If f and g are injective then so is g ○ f.
(2) If f and g are surjective then so is g ○ f

Question 20

What is an iteration?

Answer 20

Suppose that X is a set. Suppose that f is a function
on X. Then we define
(1) f^(0) = IdX and
(2) for any n ∈ N we define f^(n+1) = f ○ f^(n).
We say that f^(n) is the n-th iterate of f.

Question 21

What is an orbit?

Answer 21

Suppose that X is a set. Suppose that f is a function
on X. Then for any x ∈ X we define
Of (x) = {f^(n)(x) ∣ n ∈ N}
We call Of (x) the forward orbit of x under f.

Question 22

What is the Cantor-Schroder-Bernstein Theorem?

Answer 22

Suppose that X and Y are sets. Suppose that f∶ X → Y and g∶ Y → X are injections. Then there is a bijection h∶ X → Y .

Question 23

What does it mean for a relation to be Reflexive, Symmetric and Transitive?

Answer 23

Suppose that X is a set. Suppose that R ⊂ X2 is a relation on X.
● Suppose that, for all x ∈ X, we have xRx. Then we say that R is reflexive.
● Suppose that, for all x, y ∈ X, we have that xRy implies yRx. Then we say that R is symmetric.
● Suppose that, for all x, y, z ∈ X, we have that xRy and yRz implies xRz. Then we say that R is transitive.

Question 24

What is an Equivalence Relation?

Answer 24

Suppose that X is a set. A relation on X is an equivalence relation if it is reflexive, symmetric, and transitive.

Question 25

What does it mean for a relation to be Antisymmetric?

Answer 25

Suppose that X is a set. Suppose that R is a relation on X. Then R is antisymmetric if, for all x and y in X we have
● if xRy and yRx then x = y.

Question 26

What is a Partial Order?

Answer 26

Suppose that X is a set. Suppose that R is a relation on X. If R is reflexive, antisymmetric, and transitive, then R is a partial order

Question 27

What is a Total Relation?

Answer 27

Suppose that X is a set. Suppose that R is a relation on X. We say that R is a total relation if, for all x and y we have xRy or yRx.

Question 28

What is a Total Order?

Answer 28

Suppose that X is a set. Suppose that R is a relation on X. We say that R is a total order if it is reflexive, antisymmetric, transitive, and total.

Question 29

What is a Partition?

Answer 29

Suppose that X is a set. Suppose that P ⊂ P(X) has the following properties:
● If P’ ∈ P then P’ is non-empty.
● X = ⋃(P’∈P) P’.
● If P’, Q ∈ P then either P’ = Q or P’ ∩ Q = ∅.
Then we call P a partition of X. The elements P’ ∈ P are called the parts of the partition.

Question 30

What is an Equivalence Class?

Answer 30

Suppose that X is a set. Suppose that E is an equivalence relation on X. Suppose that x lies in X. We define the set [x]E = {y ∈ X ∣ xEy} to be the equivalence class of x.

Question 31

How are Equivalence Classes related to Partitions?

Answer 31

Suppose that X is a set. Suppose that E is an equivalence relation on X. Then the quotient X/E (the set of all equivalence classes) is a partition of X.

Proof. We must verify that {[x]E ∣ x ∈ X} is a partition of X.
Since E is reflexive we have that x lies in [x]E. Thus [x]E is nonempty. Also, since this holds for all x we have that X = ⋃x∈X[x]E.
Suppose that x and y lie in X. If [x]E is disjoint from [y]E then
there is nothing left to show. So suppose that z lies in [x]E ∩[y]E. Thus
xEz and yEz. By symmetry we have zEy. By transitivity we have
xEy. Suppose now that w is any element in [y]E. Thus yEw. Since
xEy, by transitivity we have xEw. Thus [y]E ⊂ [x]E.
The same argument, swapping x and y throughout, proves that
[x]E ⊂ [y]E. From Lemma 1.16 implies [x]E = [y]E, as desired.

Question 32

What does it mean for two numbers to be congruent modulo n?

Answer 32

Suppose that a, b, and n are integers. We say that a and b are congruent modulo n if there is some integer k so that a = b+kn. That is, a − b is a multiple of n.

Question 33

How does modular addition, multiplication and negation work?

Answer 33

Suppose that n is an integer. We call [0]n and [1]n the zero and one of Z/nZ. Suppose that a and b are integers. We define the following operations on Z/nZ.
● [a]n + [b]n = [a + b]n (addition)
● [a]n × [b]n = [a × b]n (multiplication)
● −[a]n = [−a]n (negation)

Question 34

What is a Boolean and Boolean Operator?

Answer 34

A boolean is an element of the set B = {T,F}.

Suppose that n is a natural number. Suppose that B = {T,F}. Recall that Bn is the cartesian product of B with itself, n times. We call a function f∶Bn → B a boolean operator. The number n is called the arity of f.

Question 35

What are the Basic Boolean Operators?

Answer 35

NOT, OR, AND, IMPLIES, EQUIVALENT TO
(¬, ∨, ∧, →, and ↔)

-NOT, OR, AND are all normal

For two booleans P and Q
P Q (P→Q) (P↔Q):
T T T T
T F F F
F T T F
F F T T

Question 36

What two basic boolean operators can any other operator be written in terms of?

Answer 36

Any boolean operator can be written as a composition of the operators ¬ and ∨.

Question 37

What is a Tautology?

Answer 37

Suppose that n is a natural number. Suppose that B = {T,F}. Suppose that f∶Bn → B is a boolean operator. We call f a tautology if f(x) = T for all x ∈ Bn. We call f an antinomy if f(x) = F for all x ∈ Bn.

Question 38

How many primes are there?

Answer 38

Theorem 14.2. There are arbitrarily large primes.

Proof of Theorem 14.2. Recalling the discussion of Section 13.1, we begin by fixing a natural number n. We now must find a prime p larger than n.
Let P be the set of primes less than or equal to n. We know the set P is finite. So let (pi)^k−1,i=0
be the list of elements of P, say in order of size. We define N to be one, plus the product of these primes. That is:
N = 1 + p0 ⋅ p1 ⋅ p2 ⋅ ⋯ ⋅ pk−1
Suppose that p lies in P. Thus N is congruent to one modulo p. In particular N is not divisible by p.
We know that every natural number is divisible by some prime so the natural number N is divisible by some prime, say q. We deduce that q does not lie in P. From the definition of P we deduce that q is greater than n.

Question 39

How are natural numbers divisible by primes?

Answer 39

Suppose that n is a natural number greater than one. Then n is divisible by some prime.

Proof. Suppose that n is a natural number, greater than one. Let S be the set of divisors of n which are greater than one. That is,
S = {k ∈ N ∣ k > 1 and k divides n}
Note that n lies in S, so S is not empty.
Applying the well-ordering principle, let s be a least element of S. If s is prime we are done. So, for a contradiction, suppose that s is not prime. So s is divisible by some natural number t strictly between one and s. Since divisibility is transitive, we deduce that t lies in S. So s was not a least element of S, a contradiction.

Question 40

What is the Well-Ordering Principle?

Answer 40

Suppose that S is a subset of N. If S is non-empty, then S has a least element.

Question 41

Are prime factorisations unique?

Answer 41

Suppose that n is a natural number, greater than zero. Then n has a unique factorisation into primes.

Question 42

What is the Pigeon-hole Principle?

Answer 42

-If there are more pigeons than holes, and
-If every pigeon is in some hole, then
There some hole contains two or more pigeons.

e.g.
Suppose that n is a natural number. Suppose that
f∶ [n] → [n + 1] is a function. Then f is not a surjection.
Proof by induction

Question 42

What does it mean for a number to be prime and when are two numbers coprime?

Answer 42

We say p is a prime number if it has exactly two factors, 1 and p (so 1 is not a prime number).
If the highest common factor of a and b is 1, then a and b are said to be coprime.

Question 43

How does the HCF and LCM of two numbers multiply?

Answer 43

Suppose a, b ∈ N then we have
hcf(a, b) × lcm(a, b) = a × b.

Proof. Let h = hcf(a, b) a so a = hm and b = hn for some m, n ∈ N where m and n
are coprime (using unique factorisation into primes). So lcm(a, b) = mnh. Now compute
a × b = hm × hn = h × (nmh) this is precisely hcf(a, b) × lcm(a, b) as required.

Question 44

How can any integer be written as a division with remainder?

Answer 44

Theorem 18.8. If a ∈ Z and b ∈ N∗ then ∃! r, q ∈ Z such that a = bq + r where 0 ≤ r < b. I.e. divide a by b gives q times a plus remainder term r.

Proof. Fix b ∈ N∗, prove existence of q, r by induction on a. P(a) is the statement ”there exists q, r such that a = qb + r where 0 ≤ r < b”. We can assume b > 1 since if b = 1 then a = ab so q = a and r = 0 so we are done.
P(1) is true since we can choose q = 0 and r = 1 < b and 1 = 0b + 1.
Suppose P(k) is true so that there exists a q and 0 ≤ r < b such that k = qb+r. Consider
k + 1 = qb + r + 1. Either r + 1 = b or r + 1 < b. In the first case take k + 1 = (q + 1)b + 0
and in the second k + 1 = qb + (r + 1). So P(k + 1) is true. Hence by induction it is true for all a ∈ N∗. The choice of b was arbitrary so true for all a, b ∈ N∗.

Question 45

How is the HCF of two numbers related to their linear combinations?

Answer 45

If h = hcf(a, b) and d = xa + yb for some x, y ∈ Z then h | d.

Proof. If h = hcf(a, b) then h | a and h | b. Therefore a = hm for some m ∈ Z and b = hn
for some n ∈ Z. Therefore
d = ax + by = mhx + nhy = h(mx + ny)
so h | d.

Question 46

What is Euclid’s Algorithm?

Answer 46

Given a, b ∈ N with a > b > 0 (re-ordering if necessary) we can write:
- a = q1b + r1 where b > r1 ≥ 0
- b = q2r1 + r2 where r1 > r2 ≥ 0
- r1 = q3r2 + r3 where r2 > r1 ≥ 0
in general rt = qt+2rt+1 + rt+2 with rt+1 > rt+2 ≥ 0.

Theorem 19.1 (Euclid’s Algorithm). Given the above algorithm on a, b:
(1) It stops. That is ∃k ∈ N such that rk−1 = qk+1rk + rk+1 and rk = qk+2rk+1 + 0,
(2) In this case rk+1 = hcf(a, b),
(3) ∃x, y ∈ Z such that hcf(a, b) = xa + yb.

Question 47

What is Bezout’s Lemma and the special case where a and b are coprime?

Answer 47

Let a, b be positive integers. Then hcf(a, b) is the smallest positive integer so that it can be written in the form xa + yb where x, y ∈ Z.

If a and b, natural numbers, are coprime, then any positive integer can be written as xa + yb for some x, y ∈ Z

Question 48

How does a prime number divide a product of two natural numbers?

Answer 48

Theorem 19.5. If p is a prime number, a, b ∈ N with p | ab, then either p | a or p | b (or both).

Proof. We will show that if p | ab and p ∤ b then p | a. If p ∤ b then hcf(p, b) = 1 so ∃x,
y ∈ Z such that 1 = xp + yb therefore a = xap + yab but p | (xap) since p is an explicit factor, and p | (yab) since by hypothesis p | ab, so therefore p | (xap + yab) and so p | a proving the result.

Question 49

What is the Fundamental Theorem of Arithmetic?

Answer 49

Theorem 20.1 (Fundamental Theorem of Arithmetic). Every n ∈ N can be written uniquely as a product of primes.

Proof. We prove by induction
(1) (Can be factorised) by (strong) induction P(n) is the statement ”∀ 2 ≤ m ≤ n, m
can be factorised into primes”.
P(2) is true since 2 = 2. Suppose P(k) true, all 2 ≤ m ≤ k can be factorised into
primes, then
* either k + 1 is prime, whence k + 1 = k + 1 is the factorisation into primes
* or (k + 1) = ab where a, b ∈ N and 2 ≤ a, b ≤ k. So by inductive hypothesis each
a, b is a product of primes, so (k + 1) = ab gives k + 1 as a product of primes.
(2) (Can be factorised uniquely) Suppose that
n = p1p2 . . . pr = q1q2 . . . qm
where all the pi and qi are primes. First consider p1 divides q1q2 . . . qm = n (p1 divides n).
Either p1 | q1 or p1 | q2q3 . . . qm (p | ab then p | a or p | b). In the first case p1 = q1
since q1 is prime. In second case p1 | q2 or p1 | q3q4 . . . qm. Continuing we conclude
that p1 = qi for some i. Without loss of generality say p1 = q1, reordering if necessary.
So now
p2p3 . . . pr = q2q3 . . . qm
by dividing by p1 = q1. Now repeat the argument with p2. Inductively we get p1 = q1,
p2 = q2 up to pr = qm with r = m.

Question 50

How many primes are there?

Answer 50

There are infinitely many primes.

Proof. Suppose not, so there are a finite number of primes p1, p2, . . . , pn for some n.
Consider N = p1p2 . . . pn+1. None of the pi divide N since this leaves remainder 1, so none of the pi are in the prime factorisation of N, but the Fundamental Theorem of Arithmetic says we can uniquely factorise N by primes, so there must exist prime(s) in addition to p1, p2, . . . , pn contradicting the hypothesis (note, we have not said that N is prime, although it could be).

Question 51

What is the Chinese Remainder Theorem?

Answer 51

Suppose n1, n2, . . . nk are integers, all of which are pairwise coprime (any two are coprime). Then for any integers a1, a2, . . . , ak there is an integer x satisfying
x ≡ ai (mod ni) for 1 ≤ i ≤ k.

Question 52

What is a Unit and how do units relate to HCF?

Answer 52

A number a ∈ Z/mZ is called a unit if it has a multiplicative inverse in Z/mZ.

A number a ∈ Z/mZ is a unit iff hcf(a, m) = 1

Question 53

What is the Euler Totient Function?

Answer 53

The Euler Totient Function, ϕ(n), is the number of positive integers less than or equal to n that are relatively prime to n, alternatively, ϕ(n) is the number of units in Z/nZ.
For example
ϕ(1) = 1,
ϕ(12) = 4 (1, 5, 7, 11),
ϕ(p) = p − 1 for any prime p.

Question 54

What is Fermat’s Little Theorem?

Answer 54

If p is a prime number, a is any integer, then
a^p ≡ a (mod p).

Following from this we get, If p is a prime number, a a number relatively prime to p, then a^(p−1) ≡ 1 (mod p).

Question 55

What is Euler’s Theorem?

Answer 55

If n is any positive integer, a is relatively prime to n, then
a^ϕ(n) ≡ 1 (mod n).

Question 56

What is Big O Notation?

Answer 56

Let f(x) and g(x) be two functions. We say
f(x) = O(g(x))
if there is some constant C > 0, which does not depend on x, so that
|f(x)| ≤ Cg(x)
or possible this holds for x > x0 for some x0.

Question 57

What is the Algorithm for Addition?

Answer 57

Consider adding two 3-digit numbers by an algorithm. Say a3a2a1 +b3b2b1 and think how you would do this using pen and paper. We would first add a1 to b1 to get d1 with a carry c1 (which may be zero). Then we add a2, b2 and c1 to get the next digit of the sum d2 with another carry c2 (which may be zero). Finally we add a3, b3 and c2 to get the third digit d3 and then we have either a three digit answer, or a four digit answer if there is a further carry c3.
If we assume here that ”addition” is a single step, then this algorithm takes 3 steps. It should be clear that if we have two n digit numbers then addition of those numbers
would now require n steps. This algorithm is O(n).

Question 58

What is the Algorithm for Multiplicaiton?

Answer 58

Now consider multiplying two n-digit numbers, as an example let’s assume we have two 2-digit numbers, so we wish to multiply together a2a1 and b2b1. To do this we multiply in pairs a1b1, a2b1, a1b2 and a2b2 which is four steps, and then we add, with carry if necessary the resultant numbers which is another 4.
In general, for two n digit numbers the same process will require n^2 multiplications and 2n additions (plus carries). So multiplication is O(n^2 + n) = O(n^2).

Question 59

What is the Algorithm for Division?

Answer 59

Division is no worse than multiplication so is also O(n^2) for our purposes.
The most common reasoning for this is using Newton-Raphson to get better and better approximations. We want to solve for x in
1/x + a = 0.
We start with some first guess and then successive iterations given by xn+1 = xn −
f(xn)/f′(xn) where f(x) = 1/x−a. This gives that xn+1 = xn(2−axn) since f′(x) = −1/x^2,
so we are taking a sequence of multiplications each of which is therefore O(n^2).

Question 60

What is Binet’s formula?

Answer 60

We also proved Binet’s Formula, that if ϕ = (1 + √5)/2 and τ = (1 −√5)/2 then
f(n) = (ϕ^n − τ^n)/√5
and noted that as n → ∞ we have from the above formula that f(n) → ϕ^n/√5.

Question 61

How are the two numbers run with Euclid’s Algorithm related to its running time?

Answer 61

If a > b ≥ 0 and Euclid’s Algorithm takes k ≥ 1 steps to complete, then a ≥ f(k + 2) and b ≥ f(k + 1) where f(k) is the kth term of the Fibonacci sequence.

Question 62

What is a Primitive Root?

Answer 62

A number a is a primitive root modulo n if every number b coprime to a (i.e. hcf(a, b) = 1) is congruent to a power of a (mod n).
I.e. for every a ∈ Z coprime to n there is some integer k for which g^k ≡ a (mod n).

Question 63

How many primitive roots does a prime have?

Answer 63

If (Z/pZ)^×, p prime, has a primitive root, then it has precisely ϕ(p − 1) of them.

Question 64

What is the Discrete Logarithm Problem?

Answer 64

(The Discrete Logarithm Problem - DLP). Given a cyclic group G, a generator g for G and some element x of G, find n such that x = g^n. Or, given (Z/pZ)×, where p is prime, a ∈ (Z/pZ)× a primitive root, and some element x ∈ (Z/pZ)×, find a number n such that
x ≡ a^n (mod p).

Question 65

What is the Diffie Hellman Problem?

Answer 65

(The Diffie-Hellman Problem - DHP). Given a cyclic group G, a generator g for G and two elements g^a and g^b, compute g^ab. Or, given (Z/pZ)×, with p prime, a a primitive root, a^x (mod p) and a^y (mod p) for integers x and y, compute
a^xy (mod p).

Question 66

What is Clear and Cipher Text?

Answer 66

We call the original, readable message, the clear text. The same message that has been encoded in some way is called the cipher text.

Question 67

What is the Caesar’s Cipher?

Answer 67

The well-known Caesar’s Cipher (supposedly used by Julius Caesar) does this substitution by a simple shift of letters in the alphabet.
Then a Caesar Cipher is just replacing the letter corresponding to the number n with the letter corresponding to the number m = n + k (mod 26) for some k, called the key. The recipient of the message then simply does the reverse substitution n = m−k (mod 26).

Question 68

How does a numbers roots relate to its primality?

Answer 68

An integer n is prime iff the only solutions to the equation
x^2 ≡ 1 (mod n) are x ≡ ±1 (mod n).

Question 69

What is Wilson’s Theorem?

Answer 69

For an integer p > 1 we have
(p − 1)! ≡ −1 (mod p)
if and only if p is prime.