axioms

[Class 15] Equality Axioms
  1. reflexivity of equality: ∀x[Equal(x,x)]
  2. subsitutivity of equality: if Equal($e_1$,$e_2$) is true for two function/constant/variable expressions $e_1$ and $e_2$, and $F_1$ is a formula and formula $F_2$ is the result of replacing some (but not necessarily all) occurences of expression $e_1$ in $F_1$ with $e_2$, then $F_1 \Leftrightarrow F_2$.
Note: So as not to go completely crazy, we will allow ourselves to write "$e_1 = e_2$" to mean "Equal($e_1$,$e_2$)" and "$e_1 \neq e_2$" to mean "¬Equal($e_1$,$e_2$)".

[Class 20] Ring Axioms A ring consists of a set of elements and two binary operators, which we call "$+$" and "$*$", that satisfy the following axioms.
  1. addition properties - you know all these! (note: can write informally as well as in first-order syntax)
    1. associative $\forall x,y,z[ (x+y)+z = x+(y+z) ]$
    2. commutative $\forall x,y[ x+y = y+x ]$
    3. additive identity $\exists x [ \forall y[ x + y = y ]]$ ← We proved this "x" is unique and decided to call it "0"
    4. additive inverse $\forall x[ \exists y[ x + y = 0 ] ]$ ← proved "y" is unique for each x and decided to call it "-x"
  2. multiplication properties - you know these too
    1. associative $\forall x,y,z[ (x*y)*z = x*(y*z) ]$
    2. commutative $\forall x,y[ x*y = y*x ]$ ← IMPORTANT! not required! Rings in which this holds are called "commutative rings"
    3. multiplicative identity - we have a constant called 1 such that $\forall x[ 1*x = x ]$ and $\forall x[ x*1 = x ]$ ← Note: if multiplication is commutative we only need the first one!
    4. multiplicative inverses are not required! 0 never has an inverse. Commutative rings in which all non-zero elements have a multiplicative inverse are called "fields".
  3. How multiplication and addition interact
    1. distributivity: $\forall a,b,c[a*(b+c) = a*b + a*c]$ and $\forall a,b,c[(b+c)*a = b*a + c*a]$ NOTE: if multiplication is commutative we only need the first kind!

[Class 21] Axioms for total order for rings
Restating the total ordering axioms using the "<" notation we have:
  1. $\forall x[x \nless x]$, i.e. no object is less than itself in the order [note: $a \nless b$ is short-hand for $\neg (a \lt b)$]
  2. $\forall x,y,z[x \lt y \wedge y \lt z \Rightarrow x \lt z]$, i.e. the ordering is transitive
  3. $\forall x,y[x=y \vee x \lt y \vee y \lt x]$, i.e. we have a total order
However, since the objects that are being "ordered" are elements of a ring, we want "$\lt$" to interact with $+$ and $*$ in the way we expect. Technically, we say that the order needs to be compatible with addition and multiplication in the ring. This means:
  1. $\forall x,y,z[x \lt y \Rightarrow x + z \lt y + z]$
  2. $\forall x,y,z[0 \lt z \wedge x \lt y \Rightarrow z*x \lt z*y]$

[Class 22] Induction axiom
Given a non-trivial ring with a total oder, the (weak) induction property is:
  1. If $P(\cdot)$ is a predicate on the ring and
    • $P(0)$, and
    • for all non-negative $n$, $P(n) \Rightarrow P(n+1)$
    then $P(n)$ holds for all for all non-negative $n$.

Definitions

Definition 0: [Class 02] A propositional variable (also called a boolean variable) is a variable that takes on only the values true or false.

Definition 1: [Class 02] A boolean function is a function for which all inputs are boolean-valued and the output is boolean-valued.

Definition 2: [Class 02] The standard operations in propositional logic (also called boolean operators) are:

not and or implication equivalence exclusive or

Definition 3: [Class 02] A propositional formula is defined by the following rules:
  1. Propositional variables are propositional formulas
  2. If $A$ is a propositional formula, $\neg(A)$ is a propositional formula.
  3. If $A$ and $B$ are propositional formulas and $\mbox{op}$ is a binary propositional operator, then $(A)\mbox{op}(B)$ is a propositional formula.
  4. Nothing else is a propositional formula.
Note: This definition does not allow for the constants true/false. In practice, we will sometimes allow them.

Definition 4: [Class 03] An assignment of true/false values to the propositional variables in a formula is called an interpretation. We often represent an interpretation as a function that maps variables to their true/false values under the interpretation.

Definition 5: [Class 03] Let $F$ be a propositional formula in the variables $x_1,\ldots,x_n$, and let $I$ be an interpretation (i.e. $I:=\{x_1=b_1,\ldots,x_n=b_n\}$, where "$b_j$" is the true/false value $x_j$ has been assigned). The evaluation of $F$ under $I$, denoted $eval(F,I)$ is
  1. if $F$ is the variable $x_j$, then the evaluation is $b_j$
  2. if $F$ is $\neg(A)$, then the evaluation is $\neg z$, where $z = eval(A,I)$
  3. if $F$ is $(A)\mbox{op}(B)$, then the evaluation is $y\ \mbox{op}\ z$, where $y = eval(A,I)$ and $z = eval(B,I)$
  4. $F$ can't be anything else!

Definition 6: [Class 03] Let $F$ be a propositional formula in the variables $x_1,\ldots,x_n$. The boolean function defined by $F$ is the function $f_F$ that maps $n$ boolean values to a single boolean value according to the rule $f_F(b_1,\ldots,b_n) = eval(F,\{x_1=b_1,\ldots,x_n=b_n\})$.

Definition 7: [Class 04] Formulas $F_1$ and $F_2$ are equivalent if, for every interpretation of the combined variables of $F_1$ and $F_2$, both formulas evaluate to the same thing.

Definition 8: [Class 06] Given propositional formula $F$ and interpretation $I$ for the variables appearing in $F$, $I$ is a model of $F$ if the evaluation of $F$ under $I$ produces the value $\text{true}$.

Definition 9: [Class 08] A propositional formula that is true under all possible interpretations is called a tautology. (A formula that is false under all possible interpretations is called a contradiction.)

Definition 10: [Class 13] A first-order formula consists of the syntactical pieces described below. Underlying them is the idea of a domain of discourse, which is the collection of what we call objects. The pieces are: Warning: We should also define syntax, i.e. how these pieces are allowed to be combined to produce a formula, but for this class we will not do that. I believe it is best for this class to leave that to our in-class discussions and experiences with examples.

Definition 11: [Class 13] An interpretation $I$ under which formula $F$ evalutates to true is called a model for $F$.

Definition 12: [HW 07] A ring is non-trivial if and only if $\exists x[ x \neq 0 ]$.

Definition 13: [Class 22] A ring is called the integers.

Definition 14: [Class 23] $n$ is even if and only if $\exists k[n=2*k]$.
Note: In full first order logic this would be written as $\forall n[\text{even}(n) \Leftrightarrow \exists k[n=2*k]]$.

Definition 15: [Class 23] $n$ is odd if and only if $\exists k[n=2*k+1]$.
Note: In full first order logic this would be written as $\forall n[\text{odd}(n) \Leftrightarrow \exists k[n=2*k+1]]$.

Definition 16: [Class 25] For two integers $a$ and $b$ we say $a$ divides $b$ (or $b$ is divisible by $a$) if and only if $a \neq 0$ and $\exists x[a*x = b]$. We will use the notation "$a|b$" to express that $a$ divides $b$. (Sorry for using the same symbol as we sometimes to mean "or".) Note that "divides" is a predicate, so $a|b$ gives a true/false value, like $a = b$ or $a \lt b$.

Definition 17: [Class 26] Given integers $a$ and $b$, with $b \neq 0$, the quotient and remainder are the unique integers $q$ and $r$, respectively, that satisfy $a = q*b + r$ and $0 \leq r \lt |b|$.

Definition 18: [HW 09] Integer $g$ is a common divisor of integers $a$ and $b$ if and only $g|a$ and $g|b$.

Definition 19: [Class 27] For integer $n$, where $n > 1$, we define the integers mod $n$, often written as $\mathbb{Z}_n$, as the number system with elements $\{0,1,\ldots,n-1\}$ and Note: "mod $n$" after the integer sum/product guarantees the result is in $\{0,1,\ldots,n-1\}$.

Definition 20: [Class 29] The greatest common divisor of two integers $u$ and $v$, at least one of which is non-zero, is the largest positive number that divides both $u$ and $v$. We use the expression $\text{gcd}(u,v)$ denote the greatest common divisor.

Definition 21: [Class 30] A vector $\boldsymbol{v}$ of dimension $n$ over commutative ring $R$ is a a sequence of $n$ values from $R$. Generally we will write $\boldsymbol{v} = [v_1 \ldots v_n]$, in which case $\boldsymbol{v}$ is a row vector, or
$\boldsymbol{v} = \begin{bmatrix} v_1\\ \vdots\\ v_n \end{bmatrix}$
in which case $\boldsymbol{v}$ is a column vector. The $v_i$'s are called the components of the vector, and their order matters. So $v_i$ is the $i$th component of $\boldsymbol{v}$. An element of $R$ is called a scalar. So $\boldsymbol{v}$ is of type vector, but $v_i$ is of type scalar.

Definition 22: [Class 30] The set of all vectors of dimension $n$ over ring $R$ in which all non-zero elements have multiplicative inverses is called a vector space, and is denoted $R^n$.

Definition 23: [Class 30] The basic operations on vectors in vector space $R^n$ are:
scalar product: for scalar $a$ and vector $\boldsymbol{w}$, define $a \cdot \boldsymbol{w} = a\cdot[w_1 \ldots w_n] = [a\cdot w_1\ \ldots\ a\cdot w_n]$. Note: "scalar times vector gives vector"
vector addition: for vectors $\boldsymbol{u}$ and $\boldsymbol{v}$, define $\boldsymbol{u} + \boldsymbol{v} = [u_1+v_1\ \ u_2+v_2\ \ldots\ u_n+v_n]$. Note: "vector + vector gives vector"
dot product: for vectors $\boldsymbol{u}$ and $\boldsymbol{v}$, define $\boldsymbol{u} \cdot \boldsymbol{v} = u_1\cdot v_1\ + u_2\cdot v_2\ + \cdots + \ u_n\cdot v_n$. Note: "vector · vector gives scalar"

Definition 24: [HW 11] If $a_1,\ldots,a_n$ are elements of some ring $R$, and $x_1,\ldots,x_n$ are objects on which addition is defined and multiplication by elements of $R$ is defined, we call $$ a_1 \cdot x_1 + a_2\cdot x_2 + \cdots + a_n\cdot x_n $$ a linear combination of the $x_i$'s. We refer to the $a_i$'s as the coefficients in the linear combination.

Definition 25: [HW 11] The Euclidean norm of a vector $\boldsymbol{v}$ over the ring $\mathbb{R}$, denoted $||\boldsymbol{v}||_2$, is defined as $||\boldsymbol{v}||_2 = \sqrt{\boldsymbol{v}\cdot \boldsymbol{v}}$.

Definition 26: [Class 32] Matrix $M$ of dimension $m\times n$ (meaning $m$ rows and $n$ columns) over ring $R$ is the sequence of values $m_{1,1},\ldots m_{1,n},m_{2,1},\ldots, m_{m,n}$ from $R$. We typically write matrix $M$ as $$ \begin{bmatrix} m_{1,1} & m_{1,2} & \cdots & m_{1,n}\\ m_{2,1} & m_{2,2} & \cdots & m_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ m_{m,n} & m_{m,2} & \cdots & m_{m,n} \end{bmatrix} $$ By the row vectors of $M$ we mean the $m$ vectors $\boldsymbol{v_1},\ldots,\boldsymbol{v_m}$ where $\boldsymbol{v_i} = \begin{bmatrix}m_{i,1}& m_{i,2}&\ldots& m_{i,n}\end{bmatrix}$.
By the column vectors of $M$ we mean the $n$ vectors $\boldsymbol{w_1},\ldots,\boldsymbol{w_m}$ where $\boldsymbol{w_j} = \begin{bmatrix} m_{1,j}\\ m_{2,j}\\ \vdots\\ m_{m,j} \end{bmatrix}$.

Definition 27: [Class 32] If $M$ is an $m\times n$ matrix with row vectors $\boldsymbol{r_1},\ldots,\boldsymbol{r_m}$, and $\boldsymbol{x}$ is column vector of dimension $n$, the matrix-vector product $M \cdot \boldsymbol{x}$ is the column vector of dimension $m$ whose $i$th component is $\boldsymbol{r_i}\cdot \boldsymbol{x}$. In other words: $$ M\cdot\boldsymbol{x} = \left[ \begin{array}{c} \boldsymbol{r_1}\cdot\boldsymbol{x}\\ \boldsymbol{r_2}\cdot\boldsymbol{x}\\ \vdots\\ \boldsymbol{r_m}\cdot\boldsymbol{x}\\ \end{array} \right] $$

Definition 28: [Class 33] Let $A$ be an $m\times n$ matrix with row vectors $\boldsymbol{r_1},\ldots, \boldsymbol{r_m}$. The elementary row operations are:
  1. replace $\boldsymbol{r_i}$ with $s\boldsymbol{r_i}$, where $s$ is a non-zero scalar
  2. swap row $i$ with row $j$
  3. replace $\boldsymbol{r_i}$ with $\boldsymbol{r_i} + s\boldsymbol{r_j}$, where $i\neq j$

Definition 29: [Class 34] The leftmost non-zero entry of a row in a matrix is called the pivot for that row. Matrix $A$ is said to be in row echelon form when the pivot for each row is to the right of the pivot for the row above it.

Definition 30: [Class 36] If $c$ is a scalar and $A$ is an $m\times n$ matrix, the scalar-matrix product $c\cdot A$ is defined as $$ c \cdot \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{bmatrix} = \begin{bmatrix} c\cdot a_{1,1} & c\cdot a_{1,2} & \cdots & c\cdot a_{1,n}\\ c\cdot a_{2,1} & c\cdot a_{2,2} & \cdots & c\cdot a_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ c\cdot a_{m,1} & c\cdot a_{m,2} & \cdots & c\cdot a_{m,n} \end{bmatrix}. $$

Definition 31: [Class 36] If $A$ and $B$ are $m\times n$ matrices, the matrix sum $A+B$ is defined as $$ \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{bmatrix} + \begin{bmatrix} b_{1,1} & b_{1,2} & \cdots & b_{1,n}\\ b_{2,1} & b_{2,2} & \cdots & b_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ b_{m,1} & b_{m,2} & \cdots & b_{m,n} \end{bmatrix} = \begin{bmatrix} a_{1,1}+b_{1,1} & a_{1,2}+b_{1,2} & \cdots & a_{1,n}+b_{1,n}\\ a_{2,1}+b_{2,1} & a_{2,2}+b_{2,2} & \cdots & a_{2,n}+b_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m,1}+b_{m,1} & a_{m,2}+b_{m,2} & \cdots & a_{m,n}+b_{m,n} \end{bmatrix}. $$

Definition 32: [Class 36] If $A$ is $m\times n$ matrix, and $B$ is $n\times k$ matrix (note: the number of columns in $A$ is the same as the number of rows in $B$), the matrix product $A\cdot B$ is the matrix of dimension $m\times k$ defined as $$ \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{bmatrix} \cdot \begin{bmatrix} b_{1,1} & b_{1,2} & \cdots & b_{1,k}\\ b_{2,1} & b_{2,2} & \cdots & b_{2,k}\\ \vdots & \vdots & \ddots & \vdots\\ b_{n,1} & b_{n,2} & \cdots & b_{n,k} \end{bmatrix} = \begin{bmatrix} c_{1,1} & c_{1,2} & \cdots & c_{1,k}\\ c_{2,1} & c_{2,2} & \cdots & c_{2,k}\\ \vdots & \vdots & \ddots & \vdots\\ c_{m,1} & c_{m,2} & \cdots & c_{m,k} \end{bmatrix} \text{, where } c_{i,j} = \begin{bmatrix}a_{i,1} & \cdots & a_{i,n}\end{bmatrix}\cdot \begin{bmatrix} b_{1,j}\\ \vdots\\ b_{n,j} \end{bmatrix} $$

Definition 33: [Class 36] The $i$th unit vector in vector space $R^n$, denoted $\boldsymbol{e_i}$, is the vector that is $1$ in its $i$th component and zero everywhere else. If it is not clear by context, we will specify whether it is a row or column vector.

Definition 34: [Class 36] The $n\times n$ identity matrix, denoted by $I_n$, is the matrix whose $i$th row is $\boldsymbol{e_i}$, the $i$th unit (row) vector. Note that this also means that the $i$th column is the $i$th unit (column) vector.

Definition 35: [Class 37] A function $T$ with inputs from vector space $R^n$ and outputs in vector space $R^m$ that satisfies
  1. $c\cdot T(\boldsymbol{u}) = T(c\cdot \boldsymbol{u})$
  2. $T(\boldsymbol{u}+\boldsymbol{v})=T(\boldsymbol{u}) + T(\boldsymbol{v})$
for any vectors $\boldsymbol{u}$, $\boldsymbol{u}$ in $R^n$ and scalar $c$ in $R$, is called a linear transformation.

Definition 36: [Class 41] Given real number $x$, the floor of $x$, denoted $\lfloor x \rfloor$, is the largest integer i such that $i \leq x$. The ceiling of x, denoted $\lceil x \rceil$, is the smallest integer i such that $x \leq i$. Examples: $\lfloor 2.5 \rfloor = 2$, $\lceil 2.5 \rceil = 3$, $\lfloor 7 \rfloor = 7$, $\lceil 7 \rceil = 7$.

Definition 37: [Class 42] The fibonacci sequence is defined by: $ f(n) = f(n-1) + f(n-2), \ \ f(0) = 0, f(1) = 1. $

Theorems

Theorem 0: [Class 04] If $f$ is a boolean function of $n$ inputs, then there is a propositional formula $F$ in the variables $x_1,\ldots,x_n$ such that $f_F$ is that function.

Theorem 1: [Class 05] In propositional logic, operators ∧, ∨, ⇔ and ⊕ are commutative, and operator ⇒ is not.

Theorem 2: [Class 05] In propositional logic, operators ∧, ∨, ⇔ and ⊕ are associative, and operator ⇒ is not.

Theorem 3: [Class 07] For any propositional formula, $F$, there is an equivalent propositional formula that only uses the operators $\wedge$, $\vee$ and $\neg$ (i.e. no $\Rightarrow$, $\oplus$, $\Leftrightarrow$).

Theorem 4: [Class 07] The $\wedge$ operator distributes with $\vee$, i.e. $a \wedge (b \vee c)$ is equivalent to $(a \wedge b) \vee (a \wedge c)$.

Theorem 5: [Class 07] The $\wedge$ operator distributes with $\oplus$, i.e. $a \wedge (b \oplus c)$ is equivalent to $(a \wedge b) \oplus (a \wedge c)$.

Theorem 6: [Class 15] ∀x,y[Equal(x,y) $\Rightarrow$ Equal(y,x)]. (Alternatively, ∀x,y[x=y $\Rightarrow$ y=x]) In other words, equality is symmetric.

Theorem 7: [Class 19] The additive identity is unique.

Theorem 8: [Class 19] The additive inverse is unique. I.e. ∀x,y,y'[x + y = 0 ∧ x + y' = 0 => y = y']

Theorem 9: [Class 19] $\forall x,y[ x + y = y \Rightarrow x = 0 ]$ , i.e. there are no part-time zeros.

Theorem 10: [Class 19] ∀z[z*0 = 0] and ∀z[0*z = 0]

Theorem 11: [Class 19] For all $x$, $-x = -1*x$. [Note: it is also true that $-x = x*-1$, though we don't prove the second version here.]

Theorem 12: [HW 07] In a non-trivial ring, $0 \neq 1$.

Theorem 13: [Class 21] (Negation & Order) In a ring with a total order, for any $x$ we have: if $0 \lt x$ then $-x \lt 0$; if $x \lt 0$ then $0 \lt -x$.

Theorem 14: [Class 21] (Trichotemy Law) In a ring with a total order, for any $x$, exactly one of $x \lt 0$, $x = 0$, $0 \lt x$ is true.

Theorem 15: [Class 22] In a non-trivial ordered ring, $0 \lt 1$. Note: These are not the integers "0" and "1". These are the additive indentity and multiplicative identity in whichever ring we are talking about.

Theorem 16: [Class 22] there is no "<" relation for the boolean ring that satisfies the axioms of an ordered ring.

Theorem 17: [Class 22] (Gap theorem) For any non-negative integer $x$, $x \lt 1 \Rightarrow x = 0$.
Note: Read this as "the only non-negative integer less than 1 is 0".

Theorem 18: [Class 22] (Gaps everywhere) For any integers $x$ and $k$, if $x \lt k$, then $x = k-1$ or $x \lt k-1$.

Theorem 19: [Class 23] (Generating Positive Integers) Every non-negative integer $k$ is equal to the sum of 0 and some number of ones - i.e. $0 + 1 + 1 + \cdots + 1$.

Theorem 20: [HW 08] (no zero divisors) Over the integers, if $x*y = 0$ then $x = 0$ or $y = 0$.

Theorem 21: [HW 08] (Removing common factors) Over the integers, if $a*b = a*c$ then $a = 0$ or $b = c$.

Theorem 22: [Class 24] Zero is not odd.

Theorem 23: [Class 24] No integer is both even and odd.

Theorem 24: [Class 24] Every integer is either even or odd (but, by the previous theorem, not both!).

Theorem 25: [Class 25] For any integers $u$, $v$ and $w$, if $u|v$ then $u|(v*w)$.

Theorem 26: [Class 25] (Divisors are smaller) For positive integers $a$ and $b$, $a|b$ implies $a \leq b$.

Theorem 27: [Class 26] (Correctness of div) The division algorithm meets is specifications, i.e. given $a\geq 0$ and $b > 0$, calling $\text{div}(a,b)$ returns values $q$,$r$ such that $a = q*b+r$ and $0\leq r \lt b$.

Theorem 28: [Class 26] (Uniqueness of quotient and remainder) For any two non-negative integers $a$ and $b$, where $b \neq 0$, there are unique integers $q$ and $r$, called the quotient and remainder, such that $ a = q*b + r $ and $0 \leq r \lt b$.

Theorem 29: [HW 09] For any $a$, $b$, $x$, $y$, if $g$ is a common divisor of $a$ and $b$, $g|(x*a + y*b)$.

Theorem 30: [Class 27] The integers mod $n$, ie. $\mathbb{Z}_n$, is a commutative ring.

Theorem 31: [Class 27] Let $n$ be an integer greater than 1. If $x_1$ and $y_1$ are integers with the same remainder mod $n$, i.e. their quotients and remainders satisfy $x_1 = q_1 n + r_1$ and $y_1 = q'_1 n + r_1$, and $x_2$ and $y_2$ are integers with the same remainder mod $n$, i.e. their quotients and remainders satisfy $x_2 = q_2 n + r_2$ and $y_2 = q'_2 n + r_2$, then
  1. $x_1 + x_2$ and $y_1 + y_2$ have the same remainders mod $n$
  2. $x_1 * x_2$ and $y_1 * y_2$ have the same remainders mod $n$
  3. $-x_1$ and $-y_1$ have the same remainders mod $n$

Theorem 32: [Class 27] Assume $n$ is an arbitrary but fixed integer greater than 1. Let +, unary - and * have their usual meaning over the integers, but define new operators +', -' and *' where $a +' b = (a + b) \bmod n$, $a *' b = (a * b) \bmod n$ and $-'a = (-a) \bmod n$. Let $G$ and $H$ be fully parenthesized expressions in +,-,*,+',-',*' which, if they differ at all, differ only in whether or not operators have an apostrophe ( $'$ ) after them. [E.g. $H = -5 + (3*'8)$ and $G = -'5 + (3*8)$.] The numbers resulting from evaluating $G$ and $H$ have the same value mod $n$.

Theorem 33: [Class 28] If $x$ and $n$ have a common divisor $g$ such that $1 \lt g$, then $x$ has no multiplicative inverse mod $n$.

Theorem 34: [Class 29] The Euclidean algorithm is correct, i.e. it meets its input/output specifications.

Theorem 35: [HW 10] Let $a$ be an integer such that $2|a*a$, then $a$ is even.

Theorem 36: [HW 10] There is no $p/q$ such that $(p/q)*(p/q) = 2$. Note that we can express this as: there are no integers $p,q$ where $q > 0$ and $\text{gcd}(p,q) = 1$ such that $p*p = 2*q*q$.

Theorem 37: [Class 31] The following properties of the basic vector operations hold in any vector space $R^n$:
  1. vector addition is commutative and associative
  2. dot product is commutative, but dot product is *not* associative!
  3. $a\cdot\boldsymbol{u} + a\cdot\boldsymbol{v} = a\cdot(\boldsymbol{u} + \boldsymbol{v})$ where $a$ is scalar and $\boldsymbol{u}$ and $\boldsymbol{v}$ are vectors
  4. $(a\cdot b)\cdot \boldsymbol{u} = a\cdot (b\cdot \boldsymbol{u})$ where $a$ and $b$ are scalars and $\boldsymbol{u}$ is a vector
  5. $a\cdot (\boldsymbol{u}\cdot \boldsymbol{v}) = (a\cdot \boldsymbol{u})\cdot \boldsymbol{v} = \boldsymbol{u}\cdot (a\cdot \boldsymbol{v})$ where $a$ is scalar and $\boldsymbol{u}$ and $\boldsymbol{v}$ are vectors
  6. $(\boldsymbol{u} + \boldsymbol{v})\cdot \boldsymbol{w} = \boldsymbol{u}\cdot \boldsymbol{w} + \boldsymbol{v}\cdot \boldsymbol{w}$, where $\boldsymbol{u}$, $\boldsymbol{v}$ and $\boldsymbol{w}$ are vectors

Theorem 38: [Class 33] Let $A$ be an $m\times n$ matrix, and let $A'$ be the same matrix after performing one elementary row operation, then
   $\boldsymbol{x}$ is a solution to $A\cdot \boldsymbol{x}=\boldsymbol{0}$ if and only if $\boldsymbol{x}$ is a solution to $A'\cdot \boldsymbol{x}=\boldsymbol{0}$.

Theorem 39: [Class 35] Let $A$ be an $m\times n$ matrix and $\boldsymbol{b}$ an $n$-dimensional column vector. Vector $\boldsymbol{u}$ is a solution to $A\cdot\boldsymbol{x}=\boldsymbol{b}$ if and only if the column vector $\boldsymbol{u'} = [u_1,\ldots,u_n,-1]$ is a solution to $[A|\boldsymbol{b}]\cdot\boldsymbol{x}=\boldsymbol{0}$.

Theorem 40: [Class 36] If $A$ and $B$ are $m \times n$ matrices, and $c$ and $d$ are scalars, then
  1. $c\cdot (d\cdot A) = (c\cdot d)\cdot A$
  2. matrix addition is commutative and associative
  3. $c\cdot(A + B) = c\cdot A + c\cdot B$

Theorem 41: [Class 36] If $A$ and $B$ are $m \times n$ matrices and $\boldsymbol{v}$ is a vector, $(A + B)\cdot \boldsymbol{v} = A\cdot\boldsymbol{v} + B\cdot\boldsymbol{v}$.

Theorem 42: [Class 36] If $A$ is an $n\times n$ matrix, then $I_n\cdot A = A$.

Theorem 43: [Class 37] A function $T$ with inputs from vector space $R^n$ and outputs in vector space $R^m$ is a linear transformation if and only if there is an $m\times n$ matrix $A$ over $R$ such that for any $\boldsymbol{u}$ in $R^n$, $T(\boldsymbol{u}) = A\boldsymbol{u}$.

Theorem 44: [Class 42] If $f_1(x)$ and $f_2(x)$ are solution functions of Ⓑ, then any linear combination of $f_1$ and $f_2$, i.e. $sf_1(x)+tf_2(x)$ for constants $s$ and $t$, is a solution of Ⓑ.

Christopher W Brown