Math 74 Definition List

# Math 74 Definition List **text and examples taken from lecture pdf slides** KEY: Definition | Corollary | Lemma | Theorem | Example | Axiom ## Week 5: ### Section 4.3 - *Inequalities* **Definition #1** (*Absolute Value*) Let $a \in \mathbb{R}.$ Then \begin{equation} |a| = \left\{ \begin{array}{ll} a, & \mbox{} a \geq 0 \\ -a, & \mbox{} a < 0 \end{array} \right. \end{equation} defines the **absolute value** of $x.$ :::warning **Remark:** The following are the same: 1. absolute value of $x$ 2. magnitude of $x$ 3. modulus of $x$ ::: **Lemma #1** Let $a, b \in \mathbb{R}.$ Then \begin{equation} |ab| = |a| \cdot |b| \end{equation} ![](https://i.imgur.com/wYXyDIf.png) **Lemma #2** Let $a \in \mathbb{R}$ and $M \geq 0.$ Then \begin{equation} |a| = M \end{equation} if and only if \begin{equation} a = M \hspace{8pt} \textrm{or} \hspace{8pt} a = -M. \end{equation} ![](https://i.imgur.com/4vOxur5.png) **Theorem #1** (*Fundamental Theorem of Absolute Values*) Let $a \in \mathbb{R}$ and $M \geq 0.$ Then \begin{equation} |a| \leq M \hspace{8pt} \textrm{if and only if} \hspace{8pt} -M \leq a \leq M. \end{equation} ![](https://i.imgur.com/RkSWmkg.png) **Corollary #1** Let $a \in \mathbb{R}$ and $M \geq 0.$ Then \begin{equation} |a| < M \hspace{8pt} \textrm{if and only if} \hspace{8pt} -M < a < M. \end{equation} **Theorem #2** For all $a, b \in \mathbb{R}$ we have 1. Positive Definite (a) $\hspace{2pt} |a| \geq 0$ (b) $\hspace{2pt} |a| = 0$ if and only if $a = 0$ 2. Symmetric \begin{equation} |a - b| = |b - a|. \end{equation} 3. Triangle Inequality \begin{equation} |a + b| \leq |a| + |b|. \end{equation} ![](https://i.imgur.com/nM2FCth.png) **Theorem #3** (*Reverse Triangle Inequality*) Let $a, b \in \mathbb{R}.$ Then \begin{equation} ||a| - |b|| \leq |a - b|. \end{equation} ![](https://i.imgur.com/E9pNfxA.png) **Example #1** If $|x| \leq 1$ show \begin{equation} |x^2 + 2x -3| \leq 4|x-1|. \end{equation} ![](https://i.imgur.com/EkKEl3W.png) ![](https://i.imgur.com/AlGeQ4k.png) **Example #2** Let $x \in \mathbb{R}.$ Show \begin{equation} 1 \leq \frac{4}{x(4-x)} \end{equation} whenever $|x - 1| < 1.$ ![](https://i.imgur.com/YOQ8aio.png) ![](https://i.imgur.com/13nuBRf.png) **Lemma #3** Let $a \in \mathbb{R}.$ If $a \in (0, 1)$ then \begin{equation} 0 < a^2 < a. \end{equation} If $a \geq 1$ then \begin{equation} a < a^2. \end{equation} **Corollary #2** Let $a \in \mathbb{R}.$ If $a \in (0, 1)$ then \begin{equation} 0 < a < \sqrt{a}. \end{equation} If $a \geq 1$ then \begin{equation} \sqrt{a} < a. \end{equation} ![](https://i.imgur.com/DD6DgPA.png) **Example #3** Let $a, b \in \mathbb{R}$ where $a > 2$ and \begin{equation} b = 1 + \sqrt{a-1}. \end{equation} Show \begin{equation} 2 ![](https://i.imgur.com/UFKSJCX.png) **Example #4** Let $a, b, c, d \in \mathbb{R}.$ Show \begin{equation} (ab + cd)^2 \leq (a^2 + c^2)(b^2 + d^2). \end{equation} ![](https://i.imgur.com/WFeCypA.png) ### Section 4.4, 4.5 - *Proofs on Sets* **Example #1** Consider \begin{equation} A = \{n \in \mathbb{Z} \hspace{3pt}|\hspace{3pt} n \equiv 1 \hspace{8pt}(\textrm{mod 2})\} \end{equation} Consider \begin{equation} B = \{n \in \mathbb{Z} \hspace{3pt}|\hspace{3pt} n \equiv 3 \hspace{8pt}(\textrm{mod 4})\} \end{equation} Show \begin{equation} B \subset A. \end{equation} ![](https://i.imgur.com/eAwmKhV.png) **Lemma #1** Let $A$ and $B$ be sets. Then \begin{equation} A \hspace{3pt}\backslash\hspace{3pt} B = A \cap B^c. \end{equation} ![](https://i.imgur.com/8ZQZ5CD.png) **Theorem #1** (*Commutative*) Let $A$ and $B$ be sets. Then \begin{equation} A \cup B = B \cup A \hspace{8pt}\textrm{and}\hspace{8pt} A \cap B = B \cup A. \end{equation} In other words, the union and intersection operators are commutative. **Theorem #2** (*Associative*) Let $A, B,$ and $C$ be sets. Then \begin{equation} A \cup (B \cup C) = (A \cup B) \cup C \end{equation} and \begin{equation} A \cap (B \cap C) = (A \cap B) \cap C. \end{equation} In other words, the union and intersection operators are associative. **Theorem #3** (*Distributive*) Let $A, B,$ and $C$ be sets. Then \begin{equation} A \cup (B \cup C) = (A \cup B) \cup (A \cup C) \end{equation} and \begin{equation} A \cap (B \cap C) = (A \cap B) \cap (A \cap C). \end{equation} ![](https://i.imgur.com/9RDUit3.png) ![](https://i.imgur.com/4sIKw2n.png) **Theorem #4** (*De Morgan's Law*) Let $A$ and $B$ be sets. Then \begin{equation} (A \cup B)^c = A^c \cap B^c \end{equation} and \begin{equation} (A \cap B)^c = A^c \cup B^c. \end{equation} ![](https://i.imgur.com/yauYcpb.png) **Example #2** Let $A, B,$ and $C$ be sets. Show \begin{equation} (A \hspace{3pt}\backslash\hspace{3pt} B) \cap (A \hspace{3pt}\backslash\hspace{3pt} C) = A \hspace{3pt}\backslash\hspace{3pt} (B \cup C). \end{equation} ![](https://i.imgur.com/9Bbt4te.png) **Example #3** Let $A, B,$ and $C$ be sets. Show \begin{equation} (A^c \cup (B^c \cap C))^c = (A \cap B) \cup (A \hspace{3pt}\backslash\hspace{3pt} C) \end{equation} ![](https://i.imgur.com/FYcfr3f.png) **Example #4** Let $A, B,$ and $C$ be sets. Show \begin{equation} A \times (B \hspace{3pt}\backslash\hspace{3pt} C) = (A \times B) \hspace{3pt}\backslash\hspace{3pt} (A \times C). \end{equation} ![](https://i.imgur.com/3W8mMdp.png) ![](https://i.imgur.com/jbIVJ4m.png) **Example #5** Let $A$ and $B$ be sets. Show \begin{equation} \mathcal{P}(A) \cup \mathcal{P}(B) \subset \mathcal{P}(A \cup B) \end{equation} but \begin{equation} \mathcal{P}(A \cup B) \not \subset \mathcal{P}(A) \cup \mathcal{P}(B) \end{equation} ### Section 5.1, 5.2 - *Counterexamples and Contradiction* **Example #1** Consider the statement: For all $n \in \mathbb{N},$ \begin{equation} 2^n + 1 \end{equation} is prime. **Example #2** Let $n \in \mathbb{N}.$ Consider the statement: If \begin{equation} \frac{n(n+1)}{2} \end{equation} is odd then \begin{equation} \frac{(n+1)(n+2)}{2} \end{equation} is odd. **Example #3** Consider the statement: There exists a number $x \in (0, \infty)$ such that \begin{equation} x \leq y \end{equation} for all $y \in (0, \infty).$ ![](https://i.imgur.com/EIOsxqi.png) **Definition #1** (*Proof by Contradiction*) Let $P(x)$ and $Q(x)$ be open sentences. Suppose we assume $Q(x)$ is false and $P(x)$ is true for all $x:$ \begin{equation} P(x) \wedge (\neg Q(x)). \end{equation} If the assumption leads to a contradiction we must have \begin{equation} P(x) \Rightarrow Q(x) \end{equation} for all $x.$ ![](https://i.imgur.com/ZgdV6UN.png) **Example #4** Let $x \in \mathbb{Q}$ and $y \in \mathbb{Q^c}$. If $x \neq 0$ show \begin{equation} xy \in \mathbb{Q^c}. \end{equation} ![](https://i.imgur.com/AGUtPgN.png) :::warning **Remark:** Proof by contrapositive - you know where you are going Proof by contradiction - who knows what is going to break :::: **Example #5** Let $x \in \mathbb{Q^c}$ and $y \in \mathbb{Q}.$ Show \begin{equation} x + y \in \mathbb{Q^c}. \end{equation} ![](https://i.imgur.com/tpgLE9Y.png) **Example #6** Let $x, y \in \mathbb{R}.$ Show if $x + y \geq 2$ then \begin{equation} x \geq 1 \hspace{8pt}\textrm{or}\hspace{8pt} y \geq 1. \end{equation} ![](https://i.imgur.com/iNeZOGF.png) **Example #7** Let $a \in \mathbb{R}.$ Assume that \begin{equation} a^n \in \mathbb{Q^c} \end{equation} for every $n \in \mathbb{N}.$ Show that \begin{equation} a^r \in \mathbb{Q^c} \end{equation} for any $r \in \mathbb{Q}$ with $r > 0.$ ![](https://i.imgur.com/dsqeecT.png) **Example #8** Assume $40$ coins are distributed among nine bags and each bag contains at least $1$ coin. Show that at least two bags have the same number of coins. ![](https://i.imgur.com/d3Ei0kY.png) **Example #9** Prove that \begin{equation} 2m + 5n^2 = 20 \end{equation} has no solution in the set of positive integers. ![](https://i.imgur.com/T6KciIn.png) ## Week 6: ### Section 5.4, 5.5 - *Existence Proofs* **Theorem #1** (Mean Value Theorem) Let $f$ : $[a,b] \rightarrow \mathbb{R}$ be continuous on $[a,b]$ and differentiable on $(a,b).$ Then there exists $c \in (a,b)$ such that \begin{equation} f'(c) = \frac{f(b) - f(a)}{b - a}. \end{equation} ![](https://i.imgur.com/jcYYXIP.png) **Example #1** Let $a, b \in \mathbb{R}$ such that \begin{equation} a < x ![](https://i.imgur.com/g03G6i6.png) **Theorem #2** (Archimedean Ordering Property) Let $a, b > 0.$ If $a < b$ then there exists $n \in \mathbb{N}$ such that \begin{equation} b < na. \end{equation} ![](https://i.imgur.com/OdaI0Gn.png) **Example #2** Let $a, b \in \mathbb{Q}.$ If $a < b$ show there exists $x \in \mathbb{Q^c}$ such that \begin{equation} a < x < b. \end{equation} ![](https://i.imgur.com/ZPqvxqa.png) **Example #3** Show that there exist irrational numbers $x$ and $y$ such that \begin{equation} x^y \end{equation} is rational. ![](https://i.imgur.com/9k6Yphy.png) **Example #4** Let $n \in \mathbb{N}.$ Show for $n \geq 8$ that there exist nonnegative integers $a$ and $b$ such that \begin{equation} n = 3a + 5b. \end{equation} ![](https://i.imgur.com/1ZgLTNZ.png) **Example #5** Let $a_1, a_2, ..., a_n \in \mathbb{R}.$ If \begin{equation} A = \frac{a_1 + a_2 + ... + a_n}{n} \end{equation} show there exists $j \in \{1, 2, ..., n\}$ such that \begin{equation} a_j \leq A. \end{equation} ![](https://i.imgur.com/noffWuI.png) **Example #6** Let $a_1, a_2, ..., a_n \in \mathbb{R}.$ If \begin{equation} A = \frac{a_1 + a_2 + ... + a_n}{n} \end{equation} must there exist $j \in \{1, 2, ..., n\}$ such that \begin{equation} a_j > A? \end{equation} ![](https://i.imgur.com/fT0O7Vw.png) **Example #7** Let $a_1, a_2, ..., a_n \in \mathbb{R}.$ Assume \begin{equation} A = \frac{a_1 + a_2 + ... + a_n}{n} \end{equation} and there exist $j \in \{1, 2, ..., n\}$ such that \begin{equation} a_j < A. \end{equation} Must there exist some term $a_k$ such that \begin{equation}A < a_k? \end{equation} ![](https://i.imgur.com/gcDBKxt.png) **Example #8** Prove there is no $n \in \mathbb{N}$ such that \begin{equation} n^2 + n^3 = 100 \end{equation} ![](https://i.imgur.com/UfLbBn9.png) **Example #9** Disprove the following: There exist odd integers $a$ and $b$ such that \begin{equation}4 \hspace{3pt}|\hspace{3pt} (3a^2 + 7b^2). \end{equation} ![](https://i.imgur.com/tWKD8LD.png) **Example #10** Assume statement \begin{equation}\textrm{"For all} \hspace{3pt} n \in \mathbb{N} \hspace{3pt} \textrm{we have} \hspace{3pt} P(n) \hspace{3pt} \textrm{true"} \end{equation} is known to have infinitely many counter examples. Show the following statement is false: \begin{equation} \textrm{"There exists a positive integer} \hspace{3pt}m\hspace{3pt} \textrm{such that for all} \hspace{3pt} n > M,\hspace{3pt} P(n)\hspace{3pt} \textrm{is true}." \end{equation} ### Section X.0 - *Peano's Axioms* **Definition #1** (*Axiom*) Let $P$ be a statement. If we assume, without proof that $P$ is true then $P$ is an **axiom**. :::warning **Remark:** We want to build our theory for the natural numbers from axioms. In this development we will assert $0 \in \mathbb{N},$ \begin{equation} \mathbb{N} = \{0, 1, 2, ...\} \end{equation} but our textbook defines \begin{equation} \mathbb{N} = \{1, 2, ...\}. \end{equation} ::: **Definition #2** (*Successor Operator*) The **successor** of $0$ is defined as \begin{equation} {0++} \end{equation} and the successor of ${0++}$ is \begin{equation} {({0++})++}. \end{equation} **Axiom #1** We have $0 \in \mathbb{N}.$ **Axiom #2** If $n \in \mathbb{N}$ then \begin{equation} {n++} \in \mathbb{N}. \end{equation} **Definition #3** We define \begin{equation} 1 = {0++}, \hspace{8pt} 2 = {1++},\hspace{8pt} 3 = {2++} ... \end{equation} **Lemma #1** We have \begin{equation} 3 \in \mathbb{N}. \end{equation} ![](https://i.imgur.com/eqgAOY7.png) **Axiom #3** If $n \in \mathbb{N}$ then \begin{equation} {n++} \neq 0. \end{equation} **Lemma #2** We have \begin{equation} 4 \neq 0. \end{equation} ![](https://i.imgur.com/QKspIOd.png) **Axiom #4** Let $m, n \in \mathbb{N}.$ If $n \neq m$ then we have \begin{equation} {n++} \neq {m++}. \end{equation} In other words, \begin{equation} {n++} = {m++} \hspace{6pt}\textrm{implies}\hspace{3pt} n = m. \end{equation} **Lemma #3** We have \begin{equation} 6 \neq 2. \end{equation} ![](https://i.imgur.com/QmS8GAP.png) **Axiom #5** (*Principle of Mathematical Induction*) Let $P(n)$ be any statement/property pertaining to $n \in \mathbb{N}.$ Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true $P({n++})$ is also true. Then $P(n)$ is true for every natural number $n.$ ![](https://i.imgur.com/cop1d99.png) **Axiom #6** (*Infinity*) There exists a set $\mathbb N$ where: 1. The elements are called natural numbers. 2. An object $0$ in $\mathbb{N}$ 3. An object ${n++}$ assigned to every natural number $n \in \mathbb{N}$ 4. The Peano axioms (Axioms 1-5) hold ![](https://i.imgur.com/cMP6l1e.png) ![](https://i.imgur.com/4CSrE4m.png) ![](https://i.imgur.com/Lmxdcqg.png) **Theorem #1** Suppose for each $n \in \mathbb{N}, f_n : \mathbb{N} \rightarrow \mathbb{N}$, and $c \in \mathbb{N}.$ Then we can assign a unique $a_n \in \mathbb{N}$ to each natural numbers, such that \begin{equation} a_0 = c \hspace{8pt} \textrm{and} \hspace{8pt} a_{n++} = f_n(a_n) \end{equation} for each $n \in \mathbb{N}.$ ![](https://i.imgur.com/jLqqIwa.png) ![](https://i.imgur.com/Ial82hN.png) ## Week 7: ### Section X.1 - *Addition and Ordering in $\mathbb{N}$* **Theorem** (From X.1) Suppose for each $n \in \mathbb{N}, \hspace{3pt} f_n : \mathbb{N} \rightarrow \mathbb{N}, \hspace{3pt} \textrm{and} \hspace{3pt} c \in \mathbb{N}.$ Then we can assign a unique $a_n \in \mathbb{N}$ to each natural numbers, such that \begin{equation} a_0 = c \hspace{3pt} \textrm{and} \hspace{3pt} a_{n++} = f_n(a_n) \end{equation} for each $n \in \mathbb{N}$ **Definition #1** (*Addition*) Let $m, in \in \mathbb{N}.$ We define \begin{equation} 0 + m = m. \end{equation} Assume we have inductively defined how to add $n$ to $m$: \begin{equation}n + m \in \mathbb{N}. \end{equation} We then define \begin{equation}(n+\hspace{-2pt}+) + m = (n + m)+\hspace{-2pt}+. \end{equation} :::warning **Remark:** Our addition operator $n + m$ is defined by incrementing $m$ to a total of $n$ times: \begin{eqnarray}1+3 &= (0+\hspace{-2pt}+) + 3 &= (0 + 3)+\hspace{-2pt}+ &= 3+\hspace{-2pt}+ = 4 \\ 2 + 3 &= (1+\hspace{-2pt}+) + 3 &= (1 + 3)+\hspace{-2pt}+ &= (3+\hspace{-2pt}+)+\hspace{-2pt}+ &= 4+\hspace{-2pt}+ &= 5 \\ 3 + 3 &= (2+\hspace{-2pt}+) + 3 &= (2 + 3)+\hspace{-2pt}+ &= 5+\hspace{-2pt}+ = 6. \end{eqnarray} So for general $m \in \mathbb{N},$ \begin{equation}1+m = m+\hspace{-2pt}+ \hspace{3pt} \textrm{and} \hspace{3pt} 2 + m = (m+\hspace{-2pt}+)+\hspace{-2pt}+. \end{equation} ::: :::danger **Warning:** We have not yet proved \begin{equation}3 + 8 = 3 + 8 \end{equation} ::: **Lemma #1** Let $n \in \mathbb{N}.$ Then \begin{equation}n + 0 = n. \end{equation} **Lemma #2** Let $m, n \in \mathbb{N}.$ Then \begin{equation}n + (m+\hspace{-2pt}+) = (n + m)+\hspace{-2pt}. \end{equation} **Theorem #1** (*Commutativity*) Let $m, n \in \mathbb{N}.$ Then \begin{equation}n + m = m + n. \end{equation} **Theorem #2** (*Associativity*) Let $a, b, c \in \mathbb{N}.$ Then \begin{equation}(a + b) + c = a+ (b + c). \end{equation} **Theorem #3** (*Cancelation Law*) Let $a, b, c \in \mathbb{N}.$ If \begin{equation}a + b = a + c \end{equation} then \begin{equation}b = c \end{equation} :::warning **Remark:** Cancelation is acting like a subtraction operator: We can remove unwanted, common terms from the sum. ::: **Definition #2** (*Positive Number*) Let $n \in \mathbb{N}.$ If $n \neq 0$ then $n$ is a **positive** number. :::warning **Remark:** We cannot define $a$ as positive whenever \begin{equation}a > 0 \end{equation} because we do not have a comparison operator! ::: **Theorem #4** Let $a, b \in \mathbb{N}.$ If $a$ is positive then \begin{equation}a + b\end{equation} is also positive. **Corollary #1** Let $a, b \in \mathbb{N}.$ If \begin{equation}a + b = 0\end{equation} then $a = b = 0.$ **Lemma #3** Let $a \in \mathbb{N}$ be positive. Then there exists exactly one number $b$ such that \begin{equation}b+\hspace{-2pt}+ = a. \end{equation} **Definition #3** (*Ordering of $\mathbb{N}$*) Let $m, n \in \mathbb{N}.$ If \begin{equation}n = m + a \end{equation} for some $a \in \mathbb{N}$ then $n$ is **greater than or equal to** $m$. We denote this by \begin{equation}n \geq m \hspace{8pt} \textrm{or} \hspace{8pt} m \leq n. \end{equation} **Definition #4** (*Strict Ordering of $\mathbb{N}$*) Let $m, n \in \mathbb{N}.$ If $n \geq m$ and $n \neq m$ the $n$ is **strictly greater than** $m$ and we denote this by \begin{equation}n > m \hspace{8pt} \textrm{or} \hspace{8pt} m < n. \end{equation} **Theorem #5** For $a, b, c \in \mathbb{N}$ we have: 1. (Reflexive) \begin{equation}a \leq a. \end{equation} 2. (Transitive) If $a \leq b$ and $b \leq c$ then \begin{equation}a \leq c. \end{equation} 3. (Anti-symmetric) If $a \leq b$ and $b \leq a$ then \begin{equation}a = b. \end{equation} **Theorem #6** For $a, b, c \in \mathbb{N}$ we have: 1. $a \leq b$ if and only if \begin{equation}a + c \leq b + c. \end{equation} 2. $a < b$ if and only if \begin{equation}a+\hspace{-2pt}+ \leq b. \end{equation} 3. $a < b$ if and only if \begin{equation}b = a + d \end{equation} for some $d \in \mathbb{N}$ which is positive. :::info **Question** Why did the previous proofs not require us to argue by induction? ::: :::warning **Remark:** The condition "$a < b$" if and only if $b = a + d$ for some $d \in \mathbb{N}$ which is positive." suggests the notation \begin{equation}a > 0 \end{equation} whenever $a$ is positive. ::: **Lemma #4** (*Trichotomy of Addition*) Let $a, b \in \mathbb{N}.$ Then one and only one of the following conditions hold: 1. $a = b.$ 2. $a = b + c$ for some $c$ positive. 3. $b = a + c$ for some $c$ positive. **Theorem #7** (*Trichotomy of Order of $\mathbb{N}$*) Let $a, b \in \mathbb{N}.$ Then one and only one of the following conditions hold: 1. $a = b.$ 2. $a < b.$ 3. $a > b.$ ### Section X.2 - *Multiplication and Building $\mathbb{Z}$ from $\mathbb{N}$* **Definition #1** (*Multiplication*) Let $m, n \in \mathbb{N}.$ We define \begin{equation}0 \times m = m. \end{equation} Assume we have inductively defined how to multiply $n$ to $m$: \begin{equation}n \times m \in \mathbb{N}. \end{equation} We then define \begin{equation}(n+\hspace{-2pt}+) \times m = (n \times m) + m. \end{equation} :::warning **Remark:** Our multiplication operator $n \times m$ is defined by adding up to $m$ a total of $n$ times: \begin{eqnarray}1 \times 3 &= (0+\hspace{-2pt}+) \times 3 &= (0 \times 3) + 3 = 3 \\ 2 \times 3 &= (1+\hspace{-2pt}+) \times 3 &= (1 \times 3) + 3 = 3 + 3 = 6 \\ 3 \times 3 &= (2+\hspace{-2pt}+) \times 3 &= (2 \times 3) + 3 = 6 + 3 = 9. \end{eqnarray} So for general $m \in \mathbb{N},$ \begin{equation}1 \times m = m \hspace{8pt} \textrm{and} \hspace{8pt} 2 \times m = m + m. \end{equation} ::: **Theorem #1** (*Commutativity*) Let $m, n \in \mathbb{N}.$ Then \begin{equation}n \times m = m \times n. \end{equation} **Theorem #2** Let $m, n \in \mathbb{N}.$ Then \begin{equation}n \times m = 0 \end{equation} if and only if \begin{equation}n = 0 \hspace{8pt} \textrm{or} \hspace{8pt} m = 0. \end{equation} In particular, if $n$ and $m$ are positive then \begin{equation}n \times m \end{equation} is positive. **Theorem #3** (*Distributivity*) Let $a, b, c \in \mathbb{N}.$ Then \begin{equation}a(b + c) = ab + ac \end{equation} and \begin{equation}(b + c)a = ba + bc. \end{equation} **Theorem #4** (*Associativity*) Let $a, b, c \in \mathbb{N}.$ Then \begin{equation}(a \times b) \times c = a \times (b \times c). \end{equation} **Theorem #5** Let $a, b, c \in \mathbb{N}.$ If $a < b$ and $c$ is positive then \begin{equation}ac < bc. \end{equation} **Corollary #1** Let $a, b, c \in \mathbb{N}.$ If $c$ is positive and \begin{equation}ac = bc \end{equation} then \begin{equation}a = b. \end{equation} :::warning **Remark:** Once again, cancellation is acting like a division operator: We can remove unwanted, common terms from the product ::: :::info **Problem** We want to define subtraction in $\mathbb{N}$ but \begin{equation}3 - 7 \notin \mathbb{N}. \end{equation} So we will extend the set $\mathbb{N}$ to allow for the inverse operator for addition to exist. ::: **Definition #2** (*$\mathbb{Z}$*) Let $a, b \in \mathbb{N}.$ An **integer** is of the form \begin{equation}a -\hspace{-4pt}- \hspace{3pt} b \end{equation} and the set of all integers is denoted by \begin{equation}\mathbb{Z}.\end{equation} :::warning **Remark:** Let $a, b, c, d \in \mathbb{N}.$ We say \begin{equation}a -\hspace{-4pt}- \hspace{3pt} b = c -\hspace{-4pt}- \hspace{3pt} d \end{equation} whenever $a + d = c + b.$ Notice that there are infinitely many ways to express $1$ as an element in $\mathbb{Z}:$ \begin{equation}"1" = 1 -\hspace{-4pt}- \hspace{3pt} 0 = 2 -\hspace{-4pt}- \hspace{3pt} 1 = \cdots \end{equation} :::: **Lemma #1** For $a, b, c, d, e, f \in \mathbb{N}$ we have: 1. (Reflexive) \begin{equation}a -\hspace{-4pt}- \hspace{3pt} b = a -\hspace{-4pt}- \hspace{3pt} b \end{equation} 2. (Symmetric) \begin{equation}a -\hspace{-4pt}- \hspace{3pt} b = c -\hspace{-4pt}- \hspace{3pt} d \hspace{8pt} \textrm{if and only if} \hspace{8pt} c -\hspace{-4pt}- \hspace{3pt} d = a -\hspace{-4pt}- \hspace{3pt} b \end{equation} 3. (Transitive) If \begin{equation}a -\hspace{-4pt}- \hspace{3pt} b = c -\hspace{-4pt}- \hspace{3pt} d \hspace{8pt} \textrm{and} \hspace{8pt} c -\hspace{-4pt}- \hspace{3pt} d = e -\hspace{-4pt}- \hspace{3pt} f \end{equation} then \begin{equation}a -\hspace{-4pt}- \hspace{3pt} b = e -\hspace{-4pt}- \hspace{3pt} f \end{equation} **Definition #3** (*Addition and Multiplication in $\mathbb{Z}$*) Let $a -\hspace{-4pt}- \hspace{3pt} b, c -\hspace{-4pt}- \hspace{3pt} d \in \mathbb{Z}.$ Then \begin{equation}(a -\hspace{-4pt}- \hspace{3pt} b) + (c -\hspace{-4pt}- \hspace{3pt} d) = (a+c) -\hspace{-4pt}- \hspace{3pt}(b+d) \end{equation} defines the sum of two integers. While the product of two integers is \begin{equation}(a -\hspace{-4pt}- \hspace{3pt} b) \times (c -\hspace{-4pt}- \hspace{3pt} d) = (ac + bd) -\hspace{-4pt}- \hspace{3pt}(ad + bc). \end{equation} :::danger **Warning:** There are infinitely many ways of representing an element of $\mathbb{Z}.$ We have to make sure that our notion of addition and multiplication is well defined: Addition and multiplication should **not** depend on ther representatives for the two integers :::: **Theorem #6** (*Addition is well defined on $\mathbb{Z}$*) Let $(a -\hspace{-4pt}- \hspace{3pt} b), (c -\hspace{-4pt}- \hspace{3pt} d) \in \mathbb{Z}.$ If \begin{equation}x = (a -\hspace{-4pt}- \hspace{3pt} b) \end{equation} then \begin{equation}x + (c -\hspace{-4pt}- \hspace{3pt} d) = (a -\hspace{-4pt}- \hspace{3pt} b) + (c -\hspace{-4pt}- \hspace{3pt} d) \end{equation} and \begin{equation}(c -\hspace{-4pt}- \hspace{3pt} d) + x = (c -\hspace{-4pt}- \hspace{3pt} d) + (a -\hspace{-4pt}- \hspace{3pt} b). \end{equation} A similar result holds for multiplication. **Definition #4** (*Negation*) Let $(a -\hspace{-4pt}- \hspace{3pt} b) \ in \mathbb{Z}$ and $n \in \mathbb{N}.$ The **negation** of $(a -\hspace{-4pt}- \hspace{3pt} b)$ is \begin{equation}-(a -\hspace{-4pt}- \hspace{3pt} b) = (b -\hspace{-4pt}- \hspace{3pt} a). \end{equation} If \begin{equation}n = (n -\hspace{-4pt}- \hspace{3pt} 0) > 0 \end{equation} then $-n$ is a **negative** integer. **Lemma #2** (*Trichotomy of $\mathbb{Z}$*) Let $x \in \mathbb{Z}.$ Then one and only one of the following conditions hold: 1. $x = 0.$ 2. $x = n$ for some positive $n \in \mathbb{N}.$ 3. $x = -n$ for some positive $n \in \mathbb{N}.$ **Theorem #7** For $x, y, z \in \mathbb{Z}$ we have: 1. (Commutativity) \begin{equation}x + y = y + x \end{equation} 2. (Associativity) \begin{equation}(x + y) + z = x + (y + z) \end{equation} 3. (Identity Element) \begin{equation}x+ 0 = 0 = 0 + x \end{equation} 4. (Inverse Element) \begin{equation}x + (-x) = (-x) + x = 0 \end{equation} **Definition #5** (*Subtraction*) Let $x, y \in \mathbb{Z}.$ Then \begin{equation}x - y = x + (-y) \end{equation} defines the **difference** between $x$ and $y$. **Theorem #8** For $x, y, z \in \mathbb{Z}$ we have: 1. (Commutativity) \begin{equation}xy = yx \end{equation} 2. (Associativity) \begin{equation}(xy)z = x(yz) \end{equation} 3. (Identity Element) \begin{equation}x \cdot 1 = x = 1 \cdot x \end{equation} 4. (Distributivity) \begin{equation}x(y + z) = xy + xz = (y + z)x \end{equation} **Theorem #9** Let $m, n \in \mathbb{Z}.$ Then \begin{equation}n \times m = 0 \end{equation} implies \begin{equation}n = 0 \hspace{8pt} \textrm{or} \hspace{8pt}m = 0 \end{equation} **Corollary #2** (*Multiplicative Cancelation in $\mathbb{Z}$*) Let $a, b, c \in \mathbb{Z}.$ If $c$ is nonzero and \begin{equation}ac = bc \end{equation} then \begin{equation}a = b. \end{equation} **Definition #6** (*Ordering of $\mathbb{Z}$*) Let $m, n \in \mathbb{Z}.$ If \begin{equation}n = m + a \end{equation} for some $a \in \mathbb{N}$ then $n$ is **greater than or equal to** $m$. We denote this by \begin{equation}n \geq m \hspace{8pt} \textrm{or} \hspace{8pt} m \leq n. \end{equation} **Definition #7** (*Strict Ordering of $\mathbb{Z}$*) Let $m, n \in \mathbb{Z}.$ If $n \geq m$ and $n \neq m$ then $n$ is **strictly greater than** $m$ and we denote this by \begin{equation}n > m \hspace{8pt} \textrm{or} \hspace{8pt} m < n. \end{equation} **Theorem #10** Let $a, b, c \in \mathbb{Z}.$ 1. $a < b$ if and only if \begin{equation}b - a \end{equation} is positive. 2. If $a < b$ then \begin{equation}a + c 0$ then \begin{equation}ac < bc \end{equation} **Theorem #11** Let $a, b, c \in \mathbb{Z}.$ 1. $a < b$ then \begin{equation}-b < -a \end{equation} 2. (Transitive) If $a < b$ and $b < c$ then \begin{equation}a < c. \end{equation} 3. (Trichotomy of Order) Exactly one of the following holds: \begin{equation}a < b, \hspace{8pt} a > b, \hspace{8pt} a = b. \end{equation} ## Week 8: ### Section 6.1 and 6.2 - Induction Proofs **Definition #1** (*Proof by Induction*) Let $P(n)$ be an open sentence over the set $\mathbb{N}.$ Suppose we show \begin{equation}P(1) \end{equation} is true and that whenever $k \in \mathbb{N}$ \begin{equation}P(k) \hspace{5pt} \textrm{implies} \hspace{5pt} P(k + 1). \end{equation} Then \begin{equation}P(n) \end{equation} is true for all $n \in \mathbb{N}.$ This yields a **proof by induction** of $P(n).$ **Example #1** Let $n \in \mathbb{N}.$ Show \begin{equation} 1 + 2 + . . . + (n - 1) + n = \frac{n(n + 1)}{2}. \end{equation} **Definition #2** (*Minimal Element*) Let $A \subset \mathbb{R}$ be nonempty. Suppose there exists $x \in A$ such that \begin{equation}x \leq y \end{equation} for all $y \in A$. Then $x$ is a **minimal element.** **Lemma #1** Let $A \subset \mathbb{N}$ be finite and nonempty. Then $A$ has a minimal element. **Theorem #1** (*Well Ordering Principle*) Let $A \subset \mathbb{N}$ be nonempty. Then $A$ has a minimal element, that is there exists $x \in A$ such that \begin{equation}x \leq y \end{equation} for all $y \in A.$ **Example #2** Let $n \in \mathbb{N}.$ Show \begin{equation}\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + .... + \frac{1}{\sqrt{n}} \geq \sqrt{n}. \end{equation} **Example #3** Let $n \geq 7.$ Show \begin{equation}n! > 3^{n}. \end{equation} **Theorem #2** Let $A$ be a set. If \begin{equation}|A| = n \end{equation} then \begin{equation}|\mathcal{P}(A)| = 2^{n}. \end{equation} ### Section 6.3 Strong Induction Proofs **Definition #1** (*Proof by Strong Induction*) Let $P(n)$ be an open sentence over the set $\mathbb{N}$. Suppose we show \begin{equation}P(1) \end{equation} is true and that whenever $k \in \mathbb{N}$ we have \begin{equation}P(1) \hspace{3pt} \textrm{and} \hspace{3pt} P(2) \hspace{3pt} \textrm{and} \hspace{3pt} \cdots \hspace{3pt} \textrm{and} \hspace{3pt} P(k) \hspace{3pt} \textrm{implies} \hspace{3pt} P(k + 1). \end{equation} Then \begin{equation} P(n) \end{equation} is true for all $n \in \mathbb{N}.$ This yields a **proof by strong induction** of $P(n).$ **Example #1** Define \begin{equation}a_n = 2^{n} - n2^{n - 1} \end{equation} for $n \in \mathbb{N}.$ Show $(a_n)$ satisfies \begin{eqnarray}a_n &=& 4(a_{n-1} - a_{n-2}) \\ a_0 &=& 1 \\ a_1 &=& 1. \end{eqnarray} **Example #2** Show that postage of 4 cents or more can be achieved by using only 2-cent and 5-cent stamps. :::warning **Claim #1** Every horse is grey. ::: ### Section 9.1, 9.2, and 9.3 - Relations **Definition** (*From 1.6 - Cartesian Product*) Let $X$ and $Y$ be sets. If $x \in X$ and $y \in Y$ then \begin{equation}(x, y) \end{equation} is an **ordered pair**. The set of all ordered pairs of $X$ and $Y$ is the **Cartesian Product** of $X$ and $Y$: \begin{equation}X \times Y = \{(x,y) \hspace{3pt} | \hspace{3pt} x \in X \hspace{3pt} \textrm{and} \hspace{3pt} y \in Y\}. \end{equation} :::danger **Warning:** We have sets $X$ and $Y$ such that \begin{equation}X \times Y \neq Y \times X. \end{equation} ::: **Definition #1** (*Relation*) Let $X$ and $Y$ be sets. Then $\mathcal{R} \subset X \times Y$ is a **relation** between sets $X$ and $Y$. If $(x, y) \in \mathcal{R}$ then $x$ is **related** to $y$ and we denote this as \begin{equation}x \mathcal{R} y. \end{equation} **Definition #3** (*Domain and Range*) Let $X$ and $Y$ be sets and $\mathcal{R}$ be a relation from $X$ to $Y$. The **domain** of $\mathcal{R}$ is \begin{equation}\textrm{dom}(\mathcal{R}) = \{x \in X \hspace{3pt} | \hspace{3pt} (x, y) \in \mathcal{R} \hspace{3pt} \textrm{for some} \hspace{3pt} y \in Y\} \end{equation} and the **range** of $\mathcal{R}$ is \begin{equation}\textrm{range}(\mathcal{R}) = \{y \in Y \hspace{3pt} | \hspace{3pt} (x, y) \in \mathcal{R} \hspace{3pt} \textrm{for some} \hspace{3pt} x \in X\} \end{equation} **Definition** (*From 1.5 - Partition*) Let $X$ be a set and $\mathcal{U}$ be a collection of nonempty subsets of $X$. If for every $x \in X$ we have one and only one set $A \in \mathcal{U}$ such that \begin{equation}x \in A \end{equation} then $\mathcal{U}$ is a **partition** of $X$. The sets in $\mathcal{U}$ are the **cells** of the partition. **Definition #4** (*Equivalence Relation*) Let $X$ be a set and $\mathcal{R}$ be a relation on $X$ and $x, y, z, \in X$. Suppose \begin{equation}x \hspace{3pt}\mathcal{R}\hspace{3pt} y \hspace{3pt} \textrm{and} \hspace{3pt} y \hspace{3pt}\mathcal{R}\hspace{3pt} z. \end{equation} and 1. (Reflexive) \begin{equation}x \hspace{3pt}\mathcal{R}\hspace{3pt} x \end{equation} 2. (Symmetric) \begin{equation}y \hspace{3pt}\mathcal{R}\hspace{3pt} x \end{equation} 3. (Transitive) \begin{equation}x \hspace{3pt}\mathcal{R}\hspace{3pt} z \end{equation} Then $\mathcal{R}$ is an **equivalence relation** on $X$. **Definition #5** (*Antisymmetric*) Let $X$ be a set, $\mathcal{R}$ be a relation on $X$, and $x, y \in X$. If $x \hspace{3pt}\mathcal{R}\hspace{3pt} y$ and $y \hspace{3pt}\mathcal{R}\hspace{3pt} x$ implies \begin{equation}x = y \end{equation} then $\mathcal{R}$ is **antisymmetric**. **Example #1** Determine whether each relation defined on the set of positive integers is reflexive, symmetric, antisymmetric, transitive. 1. $(x,y) \in \mathcal{R}$ if $xy = 1$. 2. $(x,y) \in \mathcal{R}$ if $x = y^2$. 3. $(x,y) \in \mathcal{R}$ if $x - y = 2$. :::info **Question:** So are **all** relations antisymmetric? ::: **Example #2** Prove that a relation $\mathcal{R}$ on a set $X$ is antisymmetric \begin{equation}\textrm{if and only if} \end{equation} for all $x, y \in X$, \begin{equation}(x, y) \in \mathcal{R} \hspace{3pt} \textrm{and} \hspace{3pt} x \neq y \hspace{3pt} \textrm{implies} \hspace{3pt} (y,x) \not \in \mathcal{R}. \end{equation} **Example #3** Prove or disprove the following: 1. If $\mathcal{R}$ is transitive, then $\mathcal{R}^{-1}$ is transitive. 2. If $\mathcal{R}$ and $\mathcal{S}$ are symmetric, then $\mathcal{R} \cap \mathcal{S}$ is symmetric. ## Week 9 ### Section 9.4 - Equivalence Relations **Definition** (*Equivalence Relation*) Let $X$ be a set and $\mathcal{R}$ be a relation on $X$ and $x, y, z, \in X$. Suppose \begin{equation}x \hspace{3pt}\mathcal{R}\hspace{3pt} y \hspace{3pt} \textrm{and} \hspace{3pt} y \hspace{3pt}\mathcal{R}\hspace{3pt} z. \end{equation} and 1. (Reflexive) \begin{equation}x \hspace{3pt}\mathcal{R}\hspace{3pt} x \end{equation} 2. (Symmetric) \begin{equation}y \hspace{3pt}\mathcal{R}\hspace{3pt} x \end{equation} 3. (Transitive) \begin{equation}x \hspace{3pt}\mathcal{R}\hspace{3pt} z \end{equation} **Example #1** Let $A, B, C \subset \{1, 2, 3\}.$ Determine if $A \hspace{3pt}\mathcal{R}\hspace{3pt} B$ defined by \begin{equation} A \cap B = \emptyset. \end{equation} is an equivalence relation on subsets of $\{1, 2, 3\}$. **Example #2** If $\mathcal{R}$ is an equivalence relation on a finite set $X$ and \begin{equation}|X| = |\mathcal{R}|,\end{equation} what must the relation look like? **Example #3** Let $X = \{1, 2, \cdots, 10\}$ and define a relation $\mathcal{R}$ on $X \times X$ by \begin{equation}(a, b) \hspace{3pt}\mathcal{R}\hspace{3pt} (c,d) \hspace{8pt} \textrm{if and only if} \hspace{8pt} a+d = b+c. \end{equation} Show $\mathcal{R}$ is a equivalence relation on $X \times X.$ **Example #4** Let $\mathcal{R}$ be a reflexive and transitive relation on the set $X$. Show that \begin{equation}\mathcal{R} \cap \mathcal{R}^{-1} \end{equation} is an equivalence relation on $X$. **Lemma #1** Let $X$ be a nonempty set, $a, b \in X,$ and $\mathcal{R}$ be an equivalence relation on $X$. Then $a \hspace{3pt}\mathcal{R}\hspace{3pt} b$ if and only if \begin{equation} [a] = \{x \in X \hspace{3pt}|\hspace{3pt} x \hspace{3pt}\mathcal{R}\hspace{3pt} a \} = \{x \in X \hspace{3pt}|\hspace{3pt} x \hspace{3pt}\mathcal{R}\hspace{3pt} b\} = [b] \end{equation} **Theorem #1** Let $X$ be a nonempty set and $\mathcal{R}$ be an equivalence relation on $X$. Then $\mathcal{R}$ generates a partition of X. The cells of the partition are of the form \begin{equation} [a] = \{x \in X \hspace{3pt}|\hspace{3pt} x \hspace{3pt}\mathcal{R}\hspace{3pt} a\} \end{equation} where $a \in X$. We call the cell $[a]$ an **equivalence class** of $\mathcal{R}$. **Definition** (*From 1.5 - Partition*) Let $X$ be a set and $\mathcal{U}$ be a collection of nonempty subsets of $X$. If for every $x \in X$ we have one and only one set $A \in \mathcal{U}$ such that \begin{equation}x \in A \end{equation} then $\mathcal{U}$ is a **partition** of $X$. The sets in $\mathcal{U}$ are the **cells** of the partition. **Theorem #2** Let $A$ be a nonempty set and $P$ be a partition of $X$. Then there exists an equivalence relation $\mathcal{R}$ on $X$ where the equivalence classes of $\mathcal{R}$ are precisely the sets in $P$. ### Section 9.5 and 9.6 - $\mathbb{Z}_n$ **Definition #1** (*Congruent Modulo n*) Let $a, b \in \mathbb{Z}$ with $n > 1.$ If \begin{equation} \frac{a - b}{n} \in \mathbb{Z} \end{equation} then $a$ is **congruent** to $b$ **modulo** $n$. We denote this as \begin{equation}a \equiv b \hspace{5pt} (\textrm{mod} \hspace{3pt} n) \end{equation} or say $a$ is **equivalent** to $b$ **modulo** $n$. **Example #1** Let $n \in \mathbb{N}$ where $n > 1$ and $a, b \in \mathbb{Z}.$ Show that $a \hspace{3pt} \mathcal{R} \hspace{3pt} b$ defined by \begin{equation}a \equiv b \hspace{5pt} (\textrm{mod} \hspace{3pt} n) \end{equation} forms an equivalence relation on $\mathbb{Z}$. **Definition #2** (*$\mathbb{Z}_n$*) Let $n \in \mathbb{N}$ where $n > 1$. Then \begin{equation} \mathbb{Z}_n = \{ [0], [1], [2], ..., [n - 1] \} \end{equation} is the set of **integers modulo** $n$. The elements of $\mathbb{Z}_n$ are the equivalence classes formed by \begin{equation}a \equiv b \hspace{5pt} (\textrm{mod} \hspace{3pt} n) \end{equation} :::warning **Remark:** We often define \begin{equation}\mathbb{Z}_n = \{ 0, 1, 2, ..., n - 1 \} \end{equation} and assume that the elements represent classes. So just like are construction of $\mathbb{Z}$ from $\mathbb{N} \times \mathbb{N}$, we need to prove that \begin{equation} 1 + 3 \hspace{5pt} \textrm{or} \hspace{5pt} [1] + [3] \end{equation} is well defined in $\mathbb{Z}_n$. ::: **Theorem #1** (*Addition and Multiplication is Well Defined in $\mathbb{Z}_n$*) Let $n \in \mathbb{N}$ where $n > 1$ and $a, b \in \mathbb{Z}_n$. If $x \in [a]$ and $y \in [b]$ then \begin{equation}xy \in [ab] \hspace{5pt} \textrm{and} \hspace{5pt} x + y \in [a + b]. \end{equation} **Example #2** Let $a, b \in \mathbb{Z}_8$. If \begin{equation}ab = 0 \end{equation} does it follow that $a = 0$ or $b = 0$? **Example #3** Let $a, b \in \mathbb{Z}_5$. If \begin{equation}ab = 0 \end{equation} does it follow that $a = 0$ or $b = 0$? **Definition #3** (*Multiplicative Inverse*) Let $n \in \mathbb{N}$ where $n > 1$ and $a, b \in \mathbb{Z}_n$. Then $b$ is the **multiplicative inverse** of $a$ if \begin{equation}ab =1 \end{equation} **Example #4** Find the multiplicative inverse of 3 in $\mathbb{Z}_7$ and in $\mathbb{Z}_5$. Does 3 have a multiplicative inverse in $\mathbb{Z}_6$? ### Section 10.1 - Functions and Preimages **Definition #1** (*Function*) Let $X$ and $Y$ be nonempty sets and $f$ be a relation from $X$ to $Y$. If for each $x \in X$ we have only one $y \in Y$ such that \begin{equation}(x, y) \in f \end{equation} then $f$ is a **function** from $X$ to $Y$. We denote this by \begin{equation}f : X \rightarrow Y \end{equation} and if $(x, y) \in f$ then we have say \begin{equation}f(x) = y. \end{equation} :::warning **Remark:** We denoting $f : X \rightarrow Y$ it is assumed that $X$ and $Y$ are nonempty sets. The function is called $f$. The term $f(x)$ is the value of the function at the position $x$. However, it is accepted in the world of mathematics to say \begin{equation}f(x) \end{equation} when you are talking about the function $f$. ::: **Definition #2** (*Domain, Codomain, and Range*) Let $f : X \rightarrow Y$. The set \begin{equation}f(X) = \{f(x) \hspace{3pt} | \hspace{3pt} x \in X\} \subset Y \end{equation} is the **range** of $f$, $X$ is the **domain** of $f$, and $Y$ is the **codomain** of $f$. **Definition #3** (*Function Equality*) Let $f : X \rightarrow Y$ and $g : Z \rightarrow Y.$ If \begin{equation}X = Z \hspace{5pt} \textrm{and} \hspace{5pt} f(x) = g(x) \end{equation} for all $x \in X$ then $f$ **equals** $g$. **Definition #4** (*Graph*) Let $f : X \rightarrow Y.$ Then \begin{equation} \{(x, f(x)) \hspace{3pt} | \hspace{3pt} x \in X \} \end{equation} is the **graph** of $f$.