---
# System prepended metadata

title: Math 74 Definition List

---

#  Math 74 Definition List
**text and examples taken from lecture pdf slides**
<br>
KEY: <span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">Definition</span> | <span style="color:#FFFFFF; background-color: #49AEBA; padding: 8px;">Corollary</span> | <span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">Lemma</span> | <span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">Theorem</span> | <span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">Example</span> | <span style="color:#FFFFFF; background-color: #9381FF; padding: 8px;">Axiom</span>

<br>

## Week 5:
### Section 4.3 - *Inequalities*
<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Absolute Value*)</span>

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$
:::

<br>

<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #1**</span>

Let $a, b \in \mathbb{R}.$

Then \begin{equation} |ab| = |a| \cdot |b| \end{equation}

<br>![](https://i.imgur.com/wYXyDIf.png)
<br><br>

<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #2**</span>

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}

<br>![](https://i.imgur.com/4vOxur5.png)
<br><br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #1** (*Fundamental Theorem of Absolute Values*)</span>

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}

<br>![](https://i.imgur.com/RkSWmkg.png)
<br><br>


<span style="color:#FFFFFF; background-color: #49AEBA; padding: 8px;">**Corollary #1**</span>

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}

<br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #2**</span>

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}

<br>![](https://i.imgur.com/nM2FCth.png)
<br><br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #3** (*Reverse Triangle Inequality*)</span>

Let $a, b \in \mathbb{R}.$
Then \begin{equation} ||a| - |b|| \leq |a - b|. \end{equation}

<br>![](https://i.imgur.com/E9pNfxA.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #1**</span>

If $|x| \leq 1$ show \begin{equation} |x^2 + 2x -3| \leq 4|x-1|. \end{equation}

<br>![](https://i.imgur.com/EkKEl3W.png) ![](https://i.imgur.com/AlGeQ4k.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #2**</span>

Let $x \in \mathbb{R}.$
Show \begin{equation} 1 \leq \frac{4}{x(4-x)} \end{equation} whenever $|x - 1| < 1.$

<br>![](https://i.imgur.com/YOQ8aio.png) ![](https://i.imgur.com/13nuBRf.png)
<br><br>


<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #3**</span>

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}

<br>


<span style="color:#FFFFFF; background-color: #49AEBA; padding: 8px;">**Corollary #2**</span>

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}

<br>![](https://i.imgur.com/DD6DgPA.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #3**</span>

Let $a, b \in \mathbb{R}$ where $a > 2$ and \begin{equation} b = 1 + \sqrt{a-1}. \end{equation} Show \begin{equation} 2 < b < a. \end{equation}

<br>![](https://i.imgur.com/UFKSJCX.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #4**</span>

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}

<br>![](https://i.imgur.com/WFeCypA.png)
<br><br><br>


### Section 4.4, 4.5 - *Proofs on Sets*
<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #1**</span>

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}

<br>![](https://i.imgur.com/eAwmKhV.png)
<br><br>


<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #1**</span>

Let $A$ and $B$ be sets.
Then \begin{equation} A \hspace{3pt}\backslash\hspace{3pt} B = A \cap B^c. \end{equation}

<br>![](https://i.imgur.com/8ZQZ5CD.png)
<br><br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #1** (*Commutative*)</span>

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.

<br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #2** (*Associative*)</span>

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.

<br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #3** (*Distributive*)</span>

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}

<br>![](https://i.imgur.com/9RDUit3.png) ![](https://i.imgur.com/4sIKw2n.png)
<br><br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #4** (*De Morgan's Law*)</span>

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}

<br>![](https://i.imgur.com/yauYcpb.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #2**</span>

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}

<br>![](https://i.imgur.com/9Bbt4te.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #3**</span>

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}

<br>![](https://i.imgur.com/FYcfr3f.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #4**</span>

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}

<br>![](https://i.imgur.com/3W8mMdp.png) ![](https://i.imgur.com/jbIVJ4m.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #5**</span>

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}

<br><br><br>



### Section 5.1, 5.2 - *Counterexamples and Contradiction*
<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #1**</span>

Consider the statement: 
For all $n \in \mathbb{N},$ \begin{equation} 2^n + 1 \end{equation} is prime.

<br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #2**</span>

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.

<br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #3**</span>

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).$

<br>![](https://i.imgur.com/EIOsxqi.png)
<br><br>


<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Proof by Contradiction*)</span>

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.$

<br>![](https://i.imgur.com/ZgdV6UN.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #4**</span>

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}

<br>![](https://i.imgur.com/AGUtPgN.png)
<br>
:::warning
**Remark:**
Proof by contrapositive - you know where you are going
Proof by contradiction - who knows what is going to break
::::
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #5**</span>

Let $x \in \mathbb{Q^c}$ and $y \in \mathbb{Q}.$
Show \begin{equation} x + y \in \mathbb{Q^c}. \end{equation}

<br>![](https://i.imgur.com/tpgLE9Y.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #6**</span>

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}

<br>![](https://i.imgur.com/iNeZOGF.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #7**</span>

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.$

<br>![](https://i.imgur.com/dsqeecT.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #8**</span>

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.

<br>![](https://i.imgur.com/d3Ei0kY.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #9**</span>

Prove that \begin{equation} 2m + 5n^2 = 20 \end{equation} has no solution in the set of positive integers.

<br>![](https://i.imgur.com/T6KciIn.png)
<br><br><br><br>


## Week 6:
### Section 5.4, 5.5 - *Existence Proofs*
<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #1** (Mean Value Theorem)</span>

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}

<br>![](https://i.imgur.com/jcYYXIP.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #1**</span>

Let $a, b \in \mathbb{R}$ such that \begin{equation} a < x < b \end{equation}

<br>![](https://i.imgur.com/g03G6i6.png)
<br><br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #2** (Archimedean Ordering Property)</span>

Let $a, b > 0.$
If $a < b$ then there exists $n \in \mathbb{N}$ such that \begin{equation} b < na. \end{equation}

<br>![](https://i.imgur.com/OdaI0Gn.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #2**</span>

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}

<br>![](https://i.imgur.com/ZPqvxqa.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #3**</span>

Show that there exist irrational numbers $x$ and $y$ such that \begin{equation} x^y \end{equation} is rational.

<br>![](https://i.imgur.com/9k6Yphy.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #4**</span>

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}

<br>![](https://i.imgur.com/1ZgLTNZ.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #5**</span>

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}

<br>![](https://i.imgur.com/noffWuI.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #6**</span>

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}

<br>![](https://i.imgur.com/fT0O7Vw.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #7**</span>

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}

<br>![](https://i.imgur.com/gcDBKxt.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #8**</span>

Prove there is no $n \in \mathbb{N}$ such that \begin{equation} n^2 + n^3 = 100 \end{equation}

<br>![](https://i.imgur.com/UfLbBn9.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #9**</span>

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}

<br>![](https://i.imgur.com/tWKD8LD.png)
<br><br>


<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #10**</span>

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}

<br><br><br>


### Section X.0 - *Peano's Axioms*
<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Axiom*)</span>

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}
:::
<br>


<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #2** (*Successor Operator*)</span>

The **successor** of $0$ is defined as \begin{equation} {0++} \end{equation} and the successor of ${0++}$ is \begin{equation} {({0++})++}. \end{equation}

<br>


<span style="color:#FFFFFF; background-color: #9381FF; padding: 8px;">**Axiom #1**</span>

We have $0 \in \mathbb{N}.$

<br>


<span style="color:#FFFFFF; background-color: #9381FF; padding: 8px;">**Axiom #2**</span>

If $n \in \mathbb{N}$ then \begin{equation} {n++} \in \mathbb{N}. \end{equation}

<br>


<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #3**</span>

We define \begin{equation} 1 = {0++}, \hspace{8pt} 2 = {1++},\hspace{8pt} 3 = {2++} ... \end{equation}

<br>


<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #1**</span>

We have \begin{equation} 3 \in \mathbb{N}. \end{equation}

<br>![](https://i.imgur.com/eqgAOY7.png)
<br><br>


<span style="color:#FFFFFF; background-color: #9381FF; padding: 8px;">**Axiom #3**</span>

If $n \in \mathbb{N}$ then \begin{equation} {n++} \neq 0. \end{equation}

<br>


<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #2**</span>

We have \begin{equation} 4 \neq 0. \end{equation}

<br>![](https://i.imgur.com/QKspIOd.png)
<br><br>


<span style="color:#FFFFFF; background-color: #9381FF; padding: 8px;">**Axiom #4**</span>

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}

<br>


<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #3**</span>

We have \begin{equation} 6 \neq 2. \end{equation}

<br>![](https://i.imgur.com/QmS8GAP.png)
<br><br>


<span style="color:#FFFFFF; background-color: #9381FF; padding: 8px;">**Axiom #5** (*Principle of Mathematical Induction*)</span>

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.$

<br>![](https://i.imgur.com/cop1d99.png)
<br><br>


<span style="color:#FFFFFF; background-color: #9381FF; padding: 8px;">**Axiom #6** (*Infinity*)</span>

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

<br>![](https://i.imgur.com/cMP6l1e.png) ![](https://i.imgur.com/4CSrE4m.png) ![](https://i.imgur.com/Lmxdcqg.png)
<br><br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #1**</span>

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}.$

<br>![](https://i.imgur.com/jLqqIwa.png) ![](https://i.imgur.com/Ial82hN.png)
<br><br><br><br>


## Week 7:
### Section X.1 - *Addition and Ordering in $\mathbb{N}$*
<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem**</span> (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}$

<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Addition*)</span><br>
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}
:::
<br>

<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #1**</span><br>
Let $n \in \mathbb{N}.$

Then \begin{equation}n + 0 = n. \end{equation} <br>

<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #2**</span><br>
Let $m, n \in \mathbb{N}.$

Then \begin{equation}n + (m+\hspace{-2pt}+) = (n + m)+\hspace{-2pt}. \end{equation}<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #1** (*Commutativity*)</span><br>
Let $m, n \in \mathbb{N}.$

Then \begin{equation}n + m = m + n. \end{equation}<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #2** (*Associativity*)</span><br>
Let $a, b, c \in \mathbb{N}.$

Then \begin{equation}(a + b) + c = a+ (b + c). \end{equation}<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #3** (*Cancelation Law*)</span><br>
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.
:::
<br><br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #2** (*Positive Number*)</span><br>
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!
:::
<br><br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #4**</span><br>
Let $a, b \in \mathbb{N}.$

If $a$ is positive then \begin{equation}a + b\end{equation} is also positive.<br><br>

<span style="color:#FFFFFF; background-color: #49AEBA; padding: 8px;">**Corollary #1**</span><br>
Let $a, b \in \mathbb{N}.$

If \begin{equation}a + b = 0\end{equation} then $a = b = 0.$<br><br>

<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #3**</span><br>
Let $a \in \mathbb{N}$ be positive.

Then there exists exactly one number $b$ such that \begin{equation}b+\hspace{-2pt}+ = a. \end{equation}<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #3** (*Ordering of $\mathbb{N}$*)</span><br>
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}<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #4** (*Strict Ordering of $\mathbb{N}$*)</span><br>
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}<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #5**</span><br>
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}<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #6**</span><br>
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.
<br>

:::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.
:::
<br><br>

<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #4** (*Trichotomy of Addition*)</span><br>
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.
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #7** (*Trichotomy of Order of $\mathbb{N}$*)</span><br>
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.$
<br><br><br>

### Section X.2 - *Multiplication and Building $\mathbb{Z}$ from $\mathbb{N}$*

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Multiplication*)</span><br>
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}<br>

:::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}
:::
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #1** (*Commutativity*)</span><br>
Let $m, n \in \mathbb{N}.$

Then \begin{equation}n \times m = m \times n. \end{equation}
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #2**</span><br>
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.
<br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #3** (*Distributivity*)</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #4** (*Associativity*)</span><br>
Let $a, b, c \in \mathbb{N}.$

Then \begin{equation}(a \times b) \times c = a \times (b \times c). \end{equation}
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #5**</span><br>
Let $a, b, c \in \mathbb{N}.$

If $a < b$ and $c$ is positive then \begin{equation}ac < bc. \end{equation}
<br>

<span style="color:#FFFFFF; background-color: #49AEBA; padding: 8px;">**Corollary #1**</span><br>
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.
:::
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #2** (*$\mathbb{Z}$*)</span><br>
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}<br>

:::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}
::::
<br>


<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #1**</span><br>
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} 
<br>


<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #3** (*Addition and Multiplication in $\mathbb{Z}$*)</span><br>
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}<br>

:::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
::::
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #6** (*Addition is well defined on $\mathbb{Z}$*)</span><br>
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.<br><br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #4** (*Negation*)</span><br>
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.<br><br>

<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #2** (*Trichotomy of $\mathbb{Z}$*)</span><br>
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}.$
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #7**</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #5** (*Subtraction*)</span><br>
Let $x, y \in \mathbb{Z}.$

Then \begin{equation}x - y = x + (-y) \end{equation} defines the **difference** between $x$ and $y$.<br><br>


<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #8**</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #9**</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #49AEBA; padding: 8px;">**Corollary #2** (*Multiplicative Cancelation in $\mathbb{Z}$*)</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #6** (*Ordering of $\mathbb{Z}$*)</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #7** (*Strict Ordering of $\mathbb{Z}$*)</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #10**</span><br>
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 < b + c. \end{equation}
3. If $a < b$ and $c > 0$ then \begin{equation}ac <  bc \end{equation}
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #11**</span><br>
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}
<br><br><br>


## Week 8:
### Section 6.1 and 6.2 - Induction Proofs
<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Proof by Induction*)</span><br>
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).$
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #1**</span><br>
Let $n \in \mathbb{N}.$

Show \begin{equation} 1 + 2 + . . .  + (n - 1) + n = \frac{n(n + 1)}{2}. \end{equation}
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #2** (*Minimal Element*)</span><br>
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.**
<br>

<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #1**</span><br>
Let $A \subset \mathbb{N}$ be finite and nonempty. 

Then $A$ has a minimal element.
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #1** (*Well Ordering Principle*)</span><br>
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.$
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #2**</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #3**</span><br>
Let $n \geq 7.$

Show \begin{equation}n! > 3^{n}. \end{equation}
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #2**</span><br>
Let $A$ be a set.

If \begin{equation}|A| = n \end{equation} then \begin{equation}|\mathcal{P}(A)| = 2^{n}. \end{equation}
<br><br>

### Section 6.3 Strong Induction Proofs
<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Proof by Strong Induction*)</span><br>
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).$
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #1**</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #2**</span><br>
Show that postage of 4 cents or more can be achieved by using only 2-cent and 5-cent stamps.
<br>

:::warning
**Claim #1**
Every horse is grey.
:::
<br><br>

### Section 9.1, 9.2, and 9.3 - Relations
<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition** (*From 1.6 - Cartesian Product*)</span><br>
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}
:::
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Relation*)</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #3** (*Domain and Range*)</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition** (*From 1.5 - Partition*)</span><br>
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.
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #4** (*Equivalence Relation*)</span><br>
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$.
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #5** (*Antisymmetric*)</span><br>
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**.
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #1**</span><br>
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?
:::
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #2**</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #3**</span><br>
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.
<br><br><br><br>

## Week 9 
### Section 9.4 - Equivalence Relations
<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition** (*Equivalence Relation*)</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #1**</span><br>
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\}$.
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #2**</span><br>
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?
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #3**</span><br>
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.$
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #4**</span><br>
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$.
<br>

<span style="color:#FFFFFF; background-color: #FFBCB5; padding: 8px;">**Lemma #1**</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #1**</span><br>
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}$.
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition** (*From 1.5 - Partition*)</span><br>
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.
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #2**</span><br>
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$.
<br><br>

### Section 9.5 and 9.6 - $\mathbb{Z}_n$
<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Congruent Modulo n*)</span><br>
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$.
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #1**</span><br>
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}$.
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #2** (*$\mathbb{Z}_n$*)</span><br>
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$.
:::
<br>

<span style="color:#FFFFFF; background-color: #7EA563; padding: 8px;">**Theorem #1** (*Addition and Multiplication is Well Defined in $\mathbb{Z}_n$*)</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #2**</span><br>
Let $a, b \in \mathbb{Z}_8$.

If \begin{equation}ab = 0 \end{equation} does it follow that $a = 0$ or $b = 0$?
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #3**</span><br>
Let $a, b \in \mathbb{Z}_5$.

If \begin{equation}ab = 0 \end{equation} does it follow that $a = 0$ or $b = 0$?
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #3** (*Multiplicative Inverse*)</span><br>
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}
<br>

<span style="color:#FFFFFF; background-color: #AFD2E9; padding: 8px;">**Example #4**</span><br>
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$?
<br><br>

### Section 10.1 - Functions and Preimages
<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #1** (*Function*)</span><br>
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$.
:::
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #2** (*Domain, Codomain, and Range*)</span><br>
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$.
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #3** (*Function Equality*)</span><br>
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$.
<br>

<span style="color:#FFFFFF; background-color: #B5446E; padding: 8px;">**Definition #4** (*Graph*)</span><br>
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$.