Title: Part IA / Numbers and Sets
Tags: Real_Numbers Sets_Functions_Relations Countability Counting_Induction Elementary_Number_Theory Division

Q: Definition. Injective function
A: \[(\forall x, y \in X) f(x) = f(y) \implies x = y\]
It hits everything at most once

Q: Definition. Surjective function
A: \[(\forall y \in Y)(\exists x \in X)f(x) = y\]
It hits everything at least once

Q: Definition. Bijective function
A: Both injective and surjective, hits everything exactly once

Q: Definition. Pre-image of function
A: If \(f:A \to B\) and \(V \subseteq B\) then \(f^{-1}(V) = {a \in A : f(a) \in V}\)

Q: Definition. Image of function
A: If \(f:A \to B\) and \(U \subseteq A\) then \(f(U) = {f(u): u \in U}\)
\(f(A)\) is the image of A

Q: Definition. Identitiy map
A: \(id_{A}:A \to A\) is defined as the map \(a \mapsto a\)

Q: Definition. Composition of functions
A: If \(f: X \to Y\) and \(G:Y \to Z\) then \(g \circ f: X \to Z\) is defined by \(g \circ f(x) = g(f(x))\)

Q: Definition. Right and left inverse of function
A: Left: Given \(f : A \to B\), a left inverse of f is a function \(g:B \to A\) such that \(g \circ f = id_A\)
Right: Given \(f : A \to B\), a right inverse of f is a function \(g:B \to A\) such that \(f \circ g = id_B\)

Q: Theorem. The left inverse of f exists iff f is injective
A: If the left inverse g exists, then \(\forall a, a' \in A, f(a) = f(a') \implies g(f(a)) = g(f(a')) \implies a = a'\). Therefore f is injective
If f is injective, we construct a g defined as \[g: \begin{cases} a & \text{if }b \in f(A), \text{where }f(a) = b\\ \text{anything} & \text{otherwise} \end{cases}\]
Then g is a left inverse of f.

Q: Theorem. The right inverse of f exists iff f is surjective.
A: We have \(f(g(B)) = B\) since \(f \circ g\) is the identity function. Thus f must be surjective since its image is B.
If f is surjective, we can construct a g such that for each \(b \in B\), pick one \(a \in A\) with \(f(a) = b\), and put \(g(b) = a\).

Q: Definition. Inverse of function
A: An inverse of \(f\) is a function that is both a left inverse and a right inverse. It is written as \( f^{-1}: B \to A\). It exists iff f is bijective, and is necessarily unique.

Q: Definition. Reflexive relation
A: A relation R is reflexive if \[(\forall a)aRa\]

Q: Definition. Symmetric relation
A: A relation R is symmetric iff \[(\forall a, b)aRb \iff bRa\]

Q: Definition. Transitive relation
A: A relation R is transitive iff \[(\forall a, b, c) aRb \wedge bRc \implies aRc\]

Q: Definition. Equivalence relation
A: A relation is an equivalence relation if it is reflexive, symmetric and transitive
We write ~ instead of R

Q: Definition. Equivalence class
A: If ~ is an equivalence relation, then the equivalence class \([x]\) is the set of all elements that are related via ~ to \(x\).

Q: Definition. Partition of set
A: A partition of a set \(X\) is a collection of subsets \(A_{\alpha}\) of \(X\) such that each element of \(X\) is in exactly one of \(A_{\alpha}\)

Q: Theorem. If ~ is an equivalence relation on A, then the equivalence classes of ~ form a partition of A.
A: By reflexivity, we have \(a \in [a]\). Thus the equivalence classes cover the whole set. We must now show that for all \(a,b \in A \), either \([a] = [b]\) or \([a] \cap [b] = \emptyset\).
Suppose \([a] \cap [b] \neq \emptyset\). Then \(\exists c \in [a] \cap [b]\). So a~c, b~c. By symmetry, c~b. By transitivity, we have a~b. For all \(b' \in [b]\), we have b~b'. Thus by transitivity, we have a~b'. Thus \([b] \subseteq [a]\). By symmetry, \( [a] \subseteq [b]\) and \([a] = [b]\)

Q: Definition. Quotient map
A: The quotient map q maps each element in A to the equivalence class containing a, i.e. \(a \mapsto [a]\)

Q: Theorem. Division Algorithm
A: Given \(a,b \in \mathbb{Z}, b \neq 0,\) there are unique \(q,r \in \mathbb{Z}\) with \(a = qb + r\) and \(0 \leq r < b\)
Choose \(q = \max(q:qb \leq a)\). This maximum exists because the set off all q such that \(qb \leq a\) is finite. Now write r = a - qb. We have \(0 \leq r < b\) and thus q and r are found.
To show that they are unique, suppose that \(a = qb + r = q'b + r'\). We have \((q-q')b = (r'-r)\). Sunce both r and r' are between 0 and b, we have \(-b < r - r' < b\). However, r' - r is a multiple of b. Thus \(q - q' = r' - r = 0\). Consequently, \(q = q'\) and \(r = r'\)

Q: Theorem. Let \(a,b \in \mathbb{N}\). Then \((a,b)\) exists.
A: Let S = {\({ua + vb : u,v \in \mathbb{Z}}\)} be the set of all linear combinations of a,b.
Let d be the smallest positive member of S. Say \(d = xa + yb\). Hence \(c|a, c|b \implies c|d\).
By the division algorithm there exists \(q,r \in \mathbb{Z}\) with \(a = qd + r\) with \(0 \leq r < d\). Then \(r = a-qd = a(1-qx)-qyb\). Therefore r is a linear combination of a and b. Since d is the smallest positive member of S and \(0 \leq r < d\), we have r = 0 and thus \(d|a\). Similarly \(d|b\) and so \(d = (a,b)\).

Q: Theorem. Bézout's identity
A: Let \(a,b \in \mathbb{N}\) and \(c \in \mathbb{Z}\). Then there exists \(u,v \in \mathbb{Z}\) with \(c = ua + vb\) iff \((a,b)|c\)
Let \(d = (a,b)\). If c is a linear combination of a and b, then \(d|c\) because \(d|a\) and \(d|b\).
Suppose that \(d|c\). Let \(d = xa + yb\) and \(c = kd\). Then \(c = (kx)a + (ky)b\). Thus c is a linear combination of a and b.

Q: Theorem. If \(a|bc\) and \((a,b) = 1\), then \(a|c\)
A: From Euclid's algorithm, there exists integers \(u,v \in \mathbb{Z}\) such that \(ua + vb = 1\). So multiplying by c, we have \(uac + vbc = c\). Since \(a|bc, a|LHS\). So \(a|c\).

Q: Theorem. Fundamental Theorem of Arithmetic
A: Every natural number is expressible as a product of primes in exactly one way.
Let \(p_1 \dots p_k = q_1 \dots q_l\). We know that \(p_1 | q_1 \dots q_l\) so \(p_1 | q_i\) for some i. WLOG assume i = 1. Then \(p_1 = q_1\) since both are primes. Likewise we have \(p_2 = q_2\) and so on.

Q: Theorem. Pigeonhole Pirinciple
A: If we put \(mn+1\) pigeons into \(n\) pigeonholes, then some pigeonhole has at least \(m+1\) pigeons

Q: Definition. Indicator function
A: Let \(X\) be a set, for each \(A \subseteq X\), the indicator function of \(A\) is the function \(i_A:X \rightarrow \{0,1\}\)with \(i_A(x) = 1\) if \(x \in A\), 0 otherwise.

Q: Theorem. Inclusion-Exclusion Principle
A: Let \(A_i\) be subsets of a finite set \(X\), for \(1 \leq i \leq n\). Then \[|\overline{A}_1 \cap \dots \cap \overline{A}_n| = |X| - \sum_i |A_i| + \sum_{i<j} |A_i \cap A_j| - \cdots + (-1)^n|A_1 \cap \cdots A_n|\]Use indicator functions for proof.

Q: Definition. Partial order
A: A partial order on a set is a reflexive, antisymmetric and transitive relation.
Antisymetric: \(((aRb)\wedge(bRa) \iff a=b)\)
Example: \(a \leq b\)

Q: Definition. Total order
A: A total order is a partial order where \(\forall a \neq b\), exactly one of \(aRb\) or \(bRa\) holds

Q: Definition. Well-ordered total order
A: A total order is well-ordered if every non-empty subset has a minimal element.
If \(S \neq \emptyset\), then \(\exists m \in S\) such that \(x < m \implies x \notin S\).

Q: Theorem. The well-ordering principle is equivalent to the strong principle of induction.
A: First prove that well-ordering implies strong induction. Consider a proposition \(P(n)\). Suppose \(P(k)\) is true \(\forall k <n \) implies \(P(n)\).
Assume the contrary. Consider the set \(S = \{n \in \mathbb{N}: \neg P(n)\}\). Then S has a minimal element m. Since m is the minimal counterexample to P, \(P(k)\) is true for all \(k < m\). However this implies that \(P(m)\) is true, which is a contradiction. Therefore \(P(n)\) must be true for all n.
For other direction, let \(S \subseteq \mathbb{N}\). Suppose that \(S\) has no minimal element. We need to show that \(S\) is empty. Let \(P(n)\) be the statement \(n \notin S\)
Certainly \(1 \notin S\), or else it will be the minimal element. So \(P(1)\) is true. Suppose we know that \(P(k)\) is true for all \(k < n\). Now \(n \notin S\) or else it will be the minimal element. So \(P(n)\) is true. By strong induction, \(P(n)\) is true for all n, so S is empty.
If \(P(n)\) fails for some n, then there is a minimal counterexample \(m\). Then we try to show that this leads to a contradiction.

Q: Definition. Unit(modular arithmetic)
A: \(u\) is a unit if \(\exists v\) such that \(uv \equiv 1\mod m\).

Q: Theorem. Chinese Remainder Theorem
A: Let \((m,n) = 1\) and \(a,b \in \mathbb{Z}\). Then there is a unique solution modulo mn to the simultaneous congruences
\[\begin{cases} x \equiv a \mod m \\ x \equiv b \mod n \end{cases}\]
Since \((m,n) = 1\), \(\exists u,v \in \mathbb{Z}\) with \(um+vn = 1\). Then \(vn \equiv 1 \mod m\) and \(um \equiv 1 \mod n\). Put \(x = umb + vna\). So \(x \equiv a \mod m\) and \(x \equiv b \mod n\).
Show uniqueness by contradiction.

Q: Definition. Euler's Totient Function
A: We denote by \(\phi (n)\) the number of integers a, \(0 \leq a \leq m\), such that \((a,m) = 1\)
\(\phi (m) = m \prod_{p|m} (1 - 1/p)\)

Q: Theorem. Wilson's Theorem
A: \((p-1)! \equiv -1 \mod p\) if p is a prime
Proof from fact that \(\forall a :1 \leq a \leq p-1\), a is a unit as \((a,p) = 1\)

Q: Theorem. Fermat's Little Theorem
A: Let p be a prime. Then \(a^p \equiv a \mod p\) for all \(a \in \mathbb{Z}\). Equivalently, \(a^{p-1} \equiv 1 \mod p\) if \(a \neq 0 \mod p\)
If \(a \not \equiv 0 \mod p\) then a is a unit. So \(ax \equiv ay \mod p \iff x \equiv y\), so \(a, 2a, 3a \dots (p-1)a\) are distinct mod p and congruent to \(1,2,3, \dots p-1\) in some order. Hence \(a \cdot 2a \cdot 3a \cdots(p-1)a \equiv 1 \cdot 2 \cdot 3 \cdots p-1. \)So \(a^{p-1}(p-1)! \equiv (p-1)!\)

Q: Theorem. Fermat-Euler Theorem
A: Let a,m be coprime. Then \[a^{\phi (m)} \equiv 1 \mod m\]

Q: Theorem. RSA Encryption
A: Receiver thinks of two large primes p,q. Let \(n=pq\) and pick e coprime to \(\phi (n) = (p-1)(q-1)\). Work out d with \(de = 1 \mod \phi (n)\). Publish the pair (n,e).
Split message into numbers \(M < n\). Sender sends \(M^e \mod n\) to receiver.
Receiver computes \((M^e)^d = M^{k \phi (n) + 1} \equiv M \mod n\) by Fermat-Euler.

Q: Definition. Totally Ordered Field
A: A set F equipped with binary operations +, x and relation \(\leq\) is a totally ordered field if:
i) F is an additive abelian group with identity 0
ii) F\{0} is a multiplicative abelian group with identity 1
iii)Multiplication is distributed over addition: a(b+c) = ab + ac
iv) \(\leq\) is a total order
v)For any \(p,q,r \in \mathbb{R}\), if \(p \leq q\), then \(p+r \leq q+r\)
vi)For any \(p,q,r \in \mathbb{R}\), if \(p \leq q\), then \(pr \leq qr\)

Q: Definition. Natural Numbers
A: A set \(\mathbb{N}\) is called natural numbers if it has a special element 0 and a map \(S: \mathbb{N} \rightarrow \mathbb{N}\).
i) \(\forall n \in \mathbb{N} :S(n) \neq 0\)
ii)For all \(n,m \in \mathbb{N}\), if \(S(n) = S(m)\), then \(n = m\)
iii)For any subset \(A \subseteq \mathbb{N}\), if \(0 \in A\) and \(n \in A \implies S(n) \in A\) then \(A = \mathbb{N}\)

Q: Definition. Integers
A: We define \(\mathbb{Z}\) to be the equivalence classes of \(\mathbb{N} \times \mathbb{N}\) under the equivalence relation \((a,b) \sim (c,d) \iff a + d = b + c\).
Intuitively (a,b) is a-b.
We write a for \([(a,0)]\) and -a for \([(0,a)]\) and define the operations by \[(a,b) + (c,d) = (a+c, b+d)\] \[(a,b)\times (c,d) = (ad +bc, ad+bd)\]

Q: Definition. Rationals
A: We define \(\mathbb{Q}\) to be the equivalence classes of \(\mathbb{Z} \times \mathbb{N}\) under the relation \((a,b) \sim (c,d) \iff ad=bc\)
We write \(\frac{a}{b}\) for \([(a,b)]\). We define \[(a,b) \times (c,d) = (ac,bd)\]\[(a,b) + (c,d) = (ad+bc, bd)\]

Q: Definition. Least upper bound (supremum) and greatest lower bound(infimum)
A: For an ordered set \(X\), \(s \in X\) is a least upper bound for the set \(A \subseteq X\), denoted by \(s = \sup S\), if
i) s is an upper bound for S, i.e. for every \(x \in S\), we have \(x \leq s\)
ii) if t is any upper bound for S, then \(s \leq t\)
Greatest lower bound is the reverse.

Q: Definition. Real Numbers
A: The real numbers is a totally ordered field containing \(\mathbb{Q}\) that satisfies the least upper bound axiom

Q: Axiom. Least upper bound axiom
A: Every non-empty set of the real numbers that has an upper bound has a least upper bound

Q: Definition. Closed and open intervals
A: A closed interval \([a,b]\) with \(a \leq b \in \mathbb{R}\) is the set \({x \in \mathbb{R}: a \leq x \leq b}\)
An open interval \((a,b)\) with \(a \leq b \in \mathbb{R}\) is the set \({x \in \mathbb{R}: a < x < b}\)

Q: Theorem. Axiom of Archimedes
A: Given \(r \in \mathbb{R}\), there exists \(n \in \mathbb{N}\) with \(n>r\).
Prove by contradiction using least upper bound axiom

Q: Theorem. \(\mathbb{Q}\) is dense in \(\mathbb{R}\)
A: For \(r,s \in \mathbb{R}\), with \(r<s\), \(\exists q \in \mathbb{Q}\) with \(r<q<s\)
\(s-r>0\), by the Archimedian property we can find \(n \in \mathbb{N}\) such that \(n > \frac{1}{s-r} \implies 1+nr < ns\)
Again by Archimedean property \(\exists N \in \mathbb{N}\) such that \(N > sn\).
Let \(T = {k \in \mathbb{N}: \frac{k}{n}\geq s}\). T is not empty as \(N \in T\) so T has a minimal element m.
We know \(m \neq 1\) as \(\frac{1}{n} < s-r < s\) so let \(q = \frac{m-1}{n}\). Now \(q < s\) and if \(\frac{m-1}{n} < r\) then \(\frac{m}{n} < r+\frac{1}{n} < s\) so \(m \not \in T\) so there is a contradiction and \(r < q < s\)

Q: Definition. Dedekind cut
A: A Dedekind cut of \(\mathbb{Q}\) is a set of partition of \(\mathbb{Q}\) into L and R such that \[(\forall l \in L)(\forall r \in R)l<r\] and R has no minimum(this is arbitrary and could be replaced with L having no maximum)

Q: Definition. Sequence
A: A sequence is a function \(\mathbb{N} \rightarrow \mathbb{R}\). If a is a sequence, we usually write \(a_1, a_2, \dots \). To emphasize it is a sequence we write the sequence as \((a_n)\)

Q: Definition. Limit of sequence
A: The sequence \((a_n)\) tends to \(l \in \mathbb{R}\) as n tends to infinity if and only if \[(\forall \varepsilon > 0)(\exists N \in \mathbb{N})(\forall n \geq N)|a_n - l|<\varepsilon\]

Q: Definition. Convergence of sequence
A: The sequence \((a_n)\) converges if there exists an l such that \(a_n \rightarrow l\). The sequence diverges if it doesn't converge

Q: Theorem. Every bounded monotonic sequence converges
A: The set \({a_n:n \geq 1}\) is bounded and non-empty, so it has a supremum \(l\) by least upper bound axiom.
Given any \(\varepsilon > 0\), \(l - \varepsilon\) is not an upper bound of \(a_n\). So \(\exists N : a_N \geq l - \varepsilon\). Since \(a_n\) is increasing(assumed WLOG), we know that \(l \geq a_m \geq a_N > l - \varepsilon\) for all \(m \geq N\). So \(\exists N\) such that \(\forall n \geq N\), \(|a_n - l|<\varepsilon\). So \(a_n \rightarrow l\)

Q: Theorem. Every sequence has a monotonic subsequence
A: Call a point a peak if \((\forall m \geq k)a_m \leq a_k\). If there are infinitely many peaks, then they form a decreasing subsequence. If there are only finitely many, \(\exists N\) such that no \(a_n\) with \(n>N\) is a peak. Pick \(a_{N_1}\)with \(N_1 > N\). Then pick \(a_{N_2}\) with \(N_2 > N_1\)and \(a_{N_2} > a_{N_1}\) as \(a_{N_1}\) is not a peak ad infinitum. Then we have a monotonic subsequence.

Q: Definition. Series and partial sums
A: Let \((a_n)\) be a sequence. Then \(s_m = \sum_{n=1}^m a_n\) is the mth partial sum of \((a_n)\).
We write \(\sum_{n=1}^{\infty} a_n = \lim_{m \rightarrow \infty} s_m\) if the limit exists

Q: Definition. Irrational number
A: Numbers in \(\mathbb{R} \setminus \mathbb{Q}\)are irrational

Q: Definition. Periodic number
A: A decimal is periodic if after a finite number \(l\) of digits, it repeats in blocks of k for some k

Q: Definition. Algebraic and transcendental numbers
A: An algebraic number is a root of a polynomial with integer coefficients.
A number is transcendental if it is not algebraic.

Q: Proposition. A number is periodic iff it is rational
A: Clearly a periodic number is rational.
For other direction let \(x \in \mathbb{Q}\). Suppose \(x = \frac{p}{2^c 5^d q}\) with \((q,10) = 1\). Then \(10^{max(c,d)}x = \frac{a}{q} = n + \frac{b}{q}\) for some \(a,b,n \in \mathbb{Z}\) and \(0 \leq b < q\). However, since \((q,10) = 1\), \(10^{\phi (q)} \equiv 1 \mod q\) by Fermat-Euler. So \(10^{\phi (q)} - 1 = kq\).
\[\frac{b}{q} = \frac{kb}{kq} = \frac{kb}{999\dots 9} = kb \left(\frac{1}{10^{\phi (q)}} + \frac{1}{10^{2\phi (q)}} + \cdots\right)\]
Since \(kb < kq < 10^{\phi (q)}\), write \(kb = d_1 d_2 \dots d_{\phi (q)}\). So \(\frac{b}{q} = 0.d_1 d_2 \dots d_{\phi(q)}d_1 d_2 \dots\)and x is periodic.

Q: Lemma. If \(f : [n] \rightarrow [n]\) is injective, then f is bijective
A: Perform induction on n. It is true for n = 1. For n>1, let \(j = f(n)\). Then define \(g:[n] \rightarrow [n]\) by \[g(j) = n, g(n) = j, g(i) = i \text{ otherwise}\]Then g is a bijection. So the map \(g \circ f \) is injective. It fixes n so the map \(h :[n-1] \rightarrow [n-1]\) by \(h(i) = g \circ f(i)\) is well-defined and injective. So h is bijective. So \(g \circ f\) is bijective. So f is bijective.

Q: Corollary. If A is a set and \(f: A \rightarrow [n]\) and \(g: A \rightarrow [m]\) are both bijections, then m=n.
A: WLOG assume \( m \geq n\) . Let \(h: [n] \rightarrow [m]\) with \(h(i) = i\), which is injective. Then the map \(h \circ f \circ g^{-1} : [m] \rightarrow [m]\) is injective. Then by the lemma this is surjective. So h must be surjective. So \(n \geq m\). Hence n=m.

Q: Definition. Finite set and cardinality of set
A: The set A is finite if there exists a bijection \(A \rightarrow [n]\) for some \(n \in \mathbb{N}_0\). Then cardinality or size of A, written as \(|A|\), is n.

Q: Lemma. Let \(S \subseteq \mathbb{N}\). Then either S is finite or there is a bijection \(g : \mathbb{N} \rightarrow S\)
A: If \(S \neq \emptyset\), by the well-ordering principle there is a least element \(s_1 \in S\). If \(S \setminus \{s_1\} \neq \emptyset\), it has a least element \(s_2\). And so on. If at some the process stops then \(S = \{s_1, s_2, \dots, s_n\}\), which is finite. Otherwise the map \(g: \mathbb{N} \rightarrow S\) given by \(g(i) = s_i\) is well-defined and is an injection. It is also a surjection because if \(k \in S\), then k is a natural number and there are at most k elements of S less than k. So k will be mapped to \(s_i\) for some \(i \leq k\)

Q: Definition. Countable set
A: A set \(A\) is countable is \(A\) is finite or there is a bijection between \(A\) and \(\mathbb{N}\). A set is uncountable if it is not countable

Q: Theorem. A countable union of countable sets is countable
A: Let I be a countable index set and for each \(\alpha \in I\), let \(A_{\alpha}\) be a countable set. We need to show that \(\bigcup_{\alpha \in I} A_{\alpha}\) is countable. We need to contruct an injection \(h:\bigcup_{\alpha \in I} A_{\alpha} \rightarrow \mathbb{N} \times \mathbb{N}\) because this is countable. We know that I is countable. So there exists an injection \(f: I \rightarrow \mathbb{N}\). For each \(\alpha \in I\), there exists an injection \(g_{\alpha}:A_{\alpha} \rightarrow \mathbb{N}\).
Pick \(k : \bigcup_{n\in \mathbb{N}}A_n \to \mathbb{N} , x \mapsto 2^i3^j\), where \(x = a_j^i\) for the least i s.t. \(x \in A_i\)

Q: Theorem. The set of algebraic numbers in countable
A: Let \(\mathcal{P}_k\) be the set of polynomials of degree k with integer coefficients. Then \(a_kx^k + a_{k-1}x^{k-1} + \cdots + a_0 \mapsto (a_k, a_{k-1}, \dots, a_0)\) is an injection \(\mathcal{P}_k \rightarrow \mathbb{Z}^{k+1}\). Since \(\mathbb{Z}^{k+1}\) is countable, so is \(\mathcal{P}_k\).
Let \(\mathcal{P}\) be the set of all polynomials with integer coefficients. Then clearly \(\mathcal{P} = \bigcup \mathcal{P}_k\). This is a countable union of countable sets. So \(\mathcal{P}\) is countable.
For each polynomial \(p \in \mathcal{P}\), let \(R_p\) be the set of its roots. Then \(R_p\) is finite and thus countable. Hence \(\bigcup_{p \in \mathcal{P}} R_p\), the set of all algebraic numbers, is countable.

Q: Theorem. The set of real numbers \(\mathbb{R}\) is uncountable.
A: Cantor's diagonal argument.

Q: Theorem. Let A be a set. There is no surjection from \(A \to \mathcal{P}(A)\)
A: Suppose \(f:A \to \mathcal{P}(A)\) is surjective. Let \(S = \{a\in A: a \not \in f(a)\}\). f is surjective so \(\exists s \in A:f(s) = S\). However \(s\in S \implies s \not \in S\) and \(s \not \in S \implies s \in S\). Contradiction.