InitHEADmain

1 files changed, 315 insertions, 0 deletions

diff --git a/Homework/math4310/alg_structures_assn_5.org b/Homework/math4310/alg_structures_assn_5.org
new file mode 100644
index 0000000..78b0957
--- /dev/null
+++ b/Homework/math4310/alg_structures_assn_5.org
@@ -0,0 +1,315 @@
+#+TITLE: Assignment Five
+#+AUTHOR: Lizzy Hunt
+#+STARTUP: entitiespretty fold inlineimages
+#+LATEX_HEADER: \notindent \notag \usepackage{ dsfont } \usepackage{amsmath} \usepackage[a4paper,margin=1in,landscape]{geometry}
+#+LATEX: \setlength\parindent{0pt}
+#+OPTIONS: toc:nil
+
+* Section 3.2
+** Question One
+*** a
+$a^2 - ab + ba - b^2$
+*** b
+$a^3 + ba^2 + 2a^2b + 2ab^2 + ab^2 + b^3$
+*** c
+(a) could be $a^2 - b^2$
+
+(b) could be $a^3 + 3a^2b + 3ab^2 + b^3$
+
+** Question Three
+*** a
+$\begin{smallmatrix}
+0 & 0 \\
+0 & 0 \\
+\end{smallmatrix}$, $\begin{smallmatrix}
+1 & 0 \\
+0 & 1 \\
+\end{smallmatrix}$, $\begin{smallmatrix}
+1 & 0 & 0 \\
+0 & 1 & 0 \\
+0 & 0 & 1 \\
+\end{smallmatrix}$, $\begin{smallmatrix}
+0 & 0 & 0 \\
+0 & 0 & 0 \\
+0 & 0 & 0 \\
+\end{smallmatrix}$
+*** b
+\begin{verbatim}
+>>> set(filter(lambda y: all([y**2 % 12 == y for x in range(12)]), range(12)))
+{0, 1, 4, 9}
+\end{verbatim}
+
+** Question Seven
+S is closed under multiplication:
+$i \in S, j \in S \Rightarrow i \cdot j = n1_R \cdot m1_R = (nm)1_R$.
+
+S is closed under subtraction:
+$i \in S, j \in S \Rightarrow i - j = n1_R - m1_R = (n-m)1_R$
+
+** Question Eight
+Considering $n,m \in T$ then $n = xb, m = yb$ with $x,y \in R$:
+
+1. T is closed under multiplication: $n \cdot m = xb \cdot yb = (x \cdot y)b$, which follows the rule.
+2. T is closed under subtraction: $n - m = xb - yb = (x - y)b$, which also follows the rule.
+
+We also know $T$ is not empty since it must have at least 0_R.
+
+** Question Ten
+*** a
+$\bar{R} = {(0, 0), (1, 0), (2, 0)}$
+
+$\bar{S} = {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)}$
+
+*** b
+Considering $n, m \in \bar{R}$, then $n = (x, 0_S), n = (y, 0_S)$ with $x,y \in R$.
+
+1. $\bar{R}$ is closed under multiplication: $n \cdot m = (x, 0_S) \cdot (y, 0_S) = (x \cdot y, 0_S)$ and $x \cdot y \in R$, so thus $n \cdot m \in R \times S$.
+2. $\bar{R}$ is closed under subtraction: $n - m = (x, 0_S) - (y, 0_S) = (x - y, 0_S)$ and $x - y \in R$, so thus $n - m \in R \times S$.
+
+We also know that $\bar{R}_0 = (0_R, 0_S) \in R \times S$ so $\bar{R}$ is not empty.
+
+*** c
+Considering $n, m \in \bar{S}$, then $n = (0_R, x), n = (0_R, y)$ with $x,y \in S$.
+
+1. $\bar{S}$ is closed under multiplication: $n \cdot m = (0_R, x) \cdot (0_R, y) = (x \cdot y, 0_S)$ and $x \cdot y \in S$, so thus $n \cdot m \in R \times S$.
+2. $\bar{S}$ is closed under subtraction: $n - m = (0_R, x) - (0_R, y) = (0_R, x - y)$ and $x - y \in R$, so thus $n - m \in R \times S$.
+
+We also know that $\bar{S}_0 = (0_R, 0_S) \in R \times S$ so $\bar{S}$ is not empty.
+
+** Question Thirteen
+*** a
+Considering $n, m \in S \cap T$, then $n \in S$ and $n \in T$, $m \in S$ and $m \in T$, therefore:
+
+1. $S \cap T$ is closed under multiplication as $m \cdot n$ must also be in $S \cap T$
+2. $S \cap T$ is closed under addition as $m + n$ must also be in $S \cap T$
+
+Since $S$ and $T$ are both subrings of $R$, $0_R \in S \cap T$.
+
+*** b
+No, consider $S$ being the integer multiples of 8 and $T$ being the integer multiples of 3 being subrings of $\mathds{Z}$ (proof of these being subrings is in
+Question Six of Section 3.1 in Assignment Four), then $n \in S$ with $n = 8$ and $m \in T$ with $m = 3$ then $n + m = 11 \notin S \cup T$.
+
+** Question Fifteen - TODO
+
+** Question Twenty-One
+*** a
+From $ab = ac \Rightarrow ab - ac = 0_R \Rightarrow a(b - c) = 0_R$, we know $b-c$ is equivalent to $0_R$ since we're given that $a$ is a non-zero element.
+
+$b-c = 0_R \Rightarrow b = c$
+
+*** b
+From $ba = ca \Rightarrow ba - ca = 0_R \Rightarrow (b - c)(a) = 0_R$ we come to the same conclusion as (a)
+
+$b-c = 0_R \Rightarrow b = c$
+
+* Section 3.3
+** Question One
+In the true nature of being a computer science student, automate something for 2 hours that you could've done in 20 minutes!
+#+BEGIN_SRC python :session "cct" :results none
+  cartesian_prod = lambda zn, zm: list([(i, j) for i in range(zn) for j in range(zm)])
+  mult_tup = lambda a, b, zn, zm: ((a[0] * b[0]) % zn, (a[1] * b[1]) % zm)
+  add_tup = lambda a, b, zn, zm: ((a[0] + b[0]) % zn, (a[1] + b[1]) % zm)
+  empty_table = lambda col, row, symbol: [[symbol] + [str(x) for x in col]] + [[str(x)] + [0 for i in range(len(col))] for x in row]
+
+  def make_cartesian_congruence_table(zn, zm, op, mapping, symbol):
+    cp = cartesian_prod(zn, zm)
+    mapped_cp = [cp[mapping[i]] for i in range(len(cp))]
+    table = empty_table(mapped_cp, mapped_cp, symbol)
+    for i in range(len(cp)):
+      for j in range(len(cp)):
+        table[i+1][j+1] = str(op(mapped_cp[i], mapped_cp[j], zn, zm))
+    return table
+
+  def make_normal_table(n, op, symbol):
+    table = empty_table(list(range(n)), list(range(n)), symbol)
+    for i in range(n):
+      for j in range(n):
+        table[i+1][j+1] = str(op(i, j) % n)
+    return table
+#+END_SRC
+
+*** Z_2 \times Z_3 with bijection
+#+BEGIN_SRC python :session "cct" :results none
+  bijection = [0, 4, 2, 3, 1, 5]
+#+END_SRC 
+
+**** Multiplication Tables
+#+BEGIN_SRC python :session "cct" :results table
+  make_cartesian_congruence_table(2, 3, mult_tup, bijection, '\odot')
+#+END_SRC 
+
+| \odot      | (0, 0) | (1, 1) | (0, 2) | (1, 0) | (0, 1) | (1, 2) |
+| (0, 0) | (0, 0) | (0, 0) | (0, 0) | (0, 0) | (0, 0) | (0, 0) |
+| (1, 1) | (0, 0) | (1, 1) | (0, 2) | (1, 0) | (0, 1) | (1, 2) |
+| (0, 2) | (0, 0) | (0, 2) | (0, 1) | (0, 0) | (0, 2) | (0, 1) |
+| (1, 0) | (0, 0) | (1, 0) | (0, 0) | (1, 0) | (0, 0) | (1, 0) |
+| (0, 1) | (0, 0) | (0, 1) | (0, 2) | (0, 0) | (0, 1) | (0, 2) |
+| (1, 2) | (0, 0) | (1, 2) | (0, 1) | (1, 0) | (0, 2) | (1, 1) |
+
+**** Addition Tables
+#+BEGIN_SRC python :session "cct" :results table
+  make_cartesian_congruence_table(2, 3, add_tup, bijection, '\oplus')
+#+END_SRC 
+
+| \oplus     | (0, 0) | (1, 1) | (0, 2) | (1, 0) | (0, 1) | (1, 2) |
+| (0, 0) | (0, 0) | (1, 1) | (0, 2) | (1, 0) | (0, 1) | (1, 2) |
+| (1, 1) | (1, 1) | (0, 2) | (1, 0) | (0, 1) | (1, 2) | (0, 0) |
+| (0, 2) | (0, 2) | (1, 0) | (0, 1) | (1, 2) | (0, 0) | (1, 1) |
+| (1, 0) | (1, 0) | (0, 1) | (1, 2) | (0, 0) | (1, 1) | (0, 2) |
+| (0, 1) | (0, 1) | (1, 2) | (0, 0) | (1, 1) | (0, 2) | (1, 0) |
+| (1, 2) | (1, 2) | (0, 0) | (1, 1) | (0, 2) | (1, 0) | (0, 1) |
+
+*** Z_6
+**** Multiplication Tables
+#+BEGIN_SRC python :session "cct" :results table
+  make_normal_table(6, lambda a, b: a * b, '\odot')
+#+END_SRC 
+
+| \odot | 0 | 1 | 2 | 3 | 4 | 5 |
+| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
+| 2 | 0 | 2 | 4 | 0 | 2 | 4 |
+| 3 | 0 | 3 | 0 | 3 | 0 | 3 |
+| 4 | 0 | 4 | 2 | 0 | 4 | 2 |
+| 5 | 0 | 5 | 4 | 3 | 2 | 1 |
+
+**** Addition Tables
+#+BEGIN_SRC python :session "cct" :results table
+  make_normal_table(6, lambda a, b: a + b, '\oplus')
+#+END_SRC 
+
+| \oplus | 0 | 1 | 2 | 3 | 4 | 5 |
+|  0 | 0 | 1 | 2 | 3 | 4 | 5 |
+|  1 | 1 | 2 | 3 | 4 | 5 | 0 |
+|  2 | 2 | 3 | 4 | 5 | 0 | 1 |
+|  3 | 3 | 4 | 5 | 0 | 1 | 2 |
+|  4 | 4 | 5 | 0 | 1 | 2 | 3 |
+|  5 | 5 | 0 | 1 | 2 | 3 | 4 |
+
+** Question Two
+#+BEGIN_SRC python :session "cct" :results table
+  bijection = [0, 3, 2, 1]
+  make_cartesian_congruence_table(2, 2, mult_tup, bijection, '\odot')
+#+END_SRC
+
+| \odot      | (0, 0) | (1, 1) | (1, 0) | (0, 1) |
+| (0, 0) | (0, 0) | (0, 0) | (0, 0) | (0, 0) |
+| (1, 1) | (0, 0) | (1, 1) | (1, 0) | (0, 1) |
+| (1, 0) | (0, 0) | (1, 0) | (1, 0) | (0, 0) |
+| (0, 1) | (0, 0) | (0, 1) | (0, 0) | (0, 1) |
+
+#+BEGIN_SRC python :session "cct" :results table
+  bijection = [0, 3, 2, 1]
+  make_cartesian_congruence_table(2, 2, add_tup, bijection, '\oplus')
+#+END_SRC
+
+| \oplus     | (0, 0) | (1, 1) | (1, 0) | (0, 1) |
+| (0, 0) | (0, 0) | (1, 1) | (1, 0) | (0, 1) |
+| (1, 1) | (1, 1) | (0, 0) | (0, 1) | (1, 0) |
+| (1, 0) | (1, 0) | (0, 1) | (0, 0) | (1, 1) |
+| (0, 1) | (0, 1) | (1, 0) | (1, 1) | (0, 0) |
+
+** Question Three
+1. $f$ is injective, since $f(a) = f(b) \Rightarrow (a,a) = (b,b) \Rightarrow a = b$
+2. $f$ is surjective since every range element in $R^*$, $(a,a)$ is mapped to $a \in R$ by definition
+3. $f(a) + f(b) = (a, a) + (b, b) = (a + b, a + b) = f(a + b)$ and $f(a)f(b) = (a, a) \cdot (b, b) = (ab, ab) = f(ab)$
+
+** Question Four
+$f(1)f(3) = (2)(6) \equiv_{10} 2$ but $f(3) = 6$ which doesn't hold the properties of homomorphism.
+
+** Question Five
+Consider the given function:
+1. $f$ is injective, since $f(a) = f(b) \Rightarrow$ $\begin{smallmatrix} 0 & 0 \\ 0 & a \end{smallmatrix}$ = $\begin{smallmatrix} 0 & 0 \\ 0 & b \end{smallmatrix}$ $\Rightarrow a = b$
+2. $f$ is surjective, since every range element $\begin{smallmatrix} 0 & 0 \\ 0 & a \end{smallmatrix}$ has an element in $\mathds{R}$, $a$, such that $f(a) =$ $\begin{smallmatrix} 0 & 0 \\ 0 & a \end{smallmatrix}$ by definition
+3. $f(a) + f(b) =$ $\begin{smallmatrix} 0 & 0 \\ 0 & a \end{smallmatrix}$ + $\begin{smallmatrix} 0 & 0 \\ 0 & b \end{smallmatrix}$ = $\begin{smallmatrix} 0 & 0 \\ 0 & (a + b) \end{smallmatrix}$ = $f(a + b)$,
+   and $f(a) \cdot f(b) =$ $\begin{smallmatrix} 0 & 0 \\ 0 & a \end{smallmatrix}$ \cdot $\begin{smallmatrix} 0 & 0 \\ 0 & b \end{smallmatrix}$ = $\begin{smallmatrix} 0 & 0 \\ 0 & (a \cdot b) \end{smallmatrix}$ = $f(a \cdot b)$,
+   
+** Question Nine - TODO
+
+** Question Eleven
+*** b
+\begin{verbatim}
+>>> f = lambda x: 3 * x
+>>> list(filter(lambda x: f(x * x) != (f(x) * f(x)), range(0, 20, 2)))
+[2, 4, 6, 8, 10, 12, 14, 16, 18]
+\end{verbatim}
+*** d
+\begin{verbatim}
+>>> k = lambda x: 0 if x == 0 else (x ** -1)
+>>> list(filter(lambda x: k(x * x) != (k(x) * k(x)), range(0, 20)))
+[5, 10, 13, 19]
+\end{verbatim}
+** Question Twelve
+*** c
+Not a homomorphism. Just from reducing $f(x + x)$ we find $f(x + x) \neq f(x) + f(x)$:
+
+\begin{equation*}
+f(x + x) = \dfrac{1}{(x + x)^2 + 1} = \dfrac{1}{4x^2 + 1}
+\end{equation*}
+
+\begin{equation*}
+f(x) + f(x) = \dfrac{1}{x^2 + 1} + \dfrac{1}{x^2 + 1} = \dfrac{2}{x^2 + 1}
+\end{equation*}
+
+Thus $f(x + x) \neq f(x) + f(x)$.
+*** d
+\begin{verbatim}
+>>> import numpy as np
+>>> h = lambda x: [[-x, 0], [x, 0]]
+>>> list(filter(lambda x: not np.array_equiv(h(x * x), np.dot(h(x), h(x))), range(0, 20))
+[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
+\end{verbatim}
+** Question Thirteen
+*** a
+If $r \in R$ then $(r, 0_S) \in R \times S$, and $f((r, 0_S)) = r$, so every range element has a domain element mapping to it.
+
+For some $a = (r, m) \in R \times S$ and $b = (t, v) \in R \times S$ then $f((r, m)) + f((t, v)) = r + t = f((r + t, v + m))$, and
+$f((r, m)) \cdot f((t, v)) = r \cdot t = f((r \cdot t, v \cdot m))$.
+
+*** b
+If $s \in S$ then $(0_R, s) \in R \times S$, and $f((0_R, s)) = s$, so every range element has a domain element mapping to it.
+
+For some $a = (r, m) \in R \times S$ and $b = (t, v) \in R \times S$ then $f((r, m)) + f((t, v)) = m + v = f((r + t, m + v))$, and
+$f((r, m)) \cdot f((t, v)) = m \cdot v = f((r \cdot t, m \cdot v))$.
+
+** Question Fifteen
+Consider $f: Z_4 \rightarrow Z_4 \ni f(x) = 0$, then 2 is a zero divisor, but 0 is not by definition.
+
+** Question Twenty One
+*** Lemma
+We assume a multiplicative identity $x$ exists in $\mathds{Z}^{*}$:
+
+$b \odot x = b \Rightarrow b + x - bx = b \Rightarrow x - bx = 0 \Rightarrow x(1-b) = 0$ and $1-b \neq 0 \forall b \in \mathds{Z}^{*}$ so $x = 0$.
+
+which is verified by:
+
+$0 \odot b = 0 + b - 0 \cdot b = b$ and $b \odot 0 = b + 0 - b \cdot 0 = b$.
+
+*** Proof
+
+Consider $f : \mathds{Z}^{} \rightarrow \mathds{Z}^{*}$ to be the isomorphism we so desire, then by Theorem 3.10,
+f(1 \in \mathds{Z}) = 0 \in \mathds{Z}^{*}.
+
+Therefore, f(2) = f(1 + 1) = f(1) \oplus f(1) = -1, f(3) = f(2 + 1) = -1 \oplus f(1) = -2.
+
+$f : \mathds{Z}^{} \rightarrow \mathds{Z}^{*} \ni f(x) = 1 - x$ seems to fit the bill nicely.
+
+1. $f$ is a bijection since we have an inverse $x = 1 - f(x)$
+2. $f(a \oplus b) = 1 - (a \oplus b) = 1 - (a + b - 1) = (1 - a) + (1 - b) = f(a) + f(b)$ and
+   $f(a \odot b) = 1 - (a \odot b) = 1 - (a + b - ab) = (1-a) \cdot (1-b) = f(a) \cdot f(b)$
+
+** Question Twenty Four
+*** a
+1. By the usual coordinate addition we know that $a, b \in R \Rightarrow a + b \in R$ and is associative, commutative, and the additive identity is $(0, 0)$.
+2. $R$ is closed under multiplication: $a, b \in R \Rightarrow a = (c, d) \wedge b = (e, f) \Rightarrow a \cdot b = (ce, de)$ and since $c, d, e, f \in \mathds{R}$ then $(ce, de) \in \mathds{R} \times \mathds{R}$ by definition.
+3. Multiplication is associative: $a, b, c \in R \Rightarrow a = (d, e) \wedge b = (f, g) \wedge c = (h, i) \Rightarrow (a \cdot b) \cdot c = (df, ef) \cdot (h, i) = (dfh, efh)$ and $a \cdot (b \cdot c) = (d, e) \cdot (fh, gh) = (dfh, efh)$
+4. Multiplication is distributive: $a, b, c \in R \Rightarrow a = (d, e) \wedge b = (f, g) \wedge c = (h, i) \Rightarrow a(b + c) = (e, f) \cdot (f + h, g + i) = (ef + eh, ff + fh) = (ef, ff) + (eh, fh) = a \cdot b + a \cdot c$
+   and $a, b, c \in R \Rightarrow a = (d, e) \wedge b = (f, g) \wedge c = (h, i) \Rightarrow (a + b) \cdot c = (d + f, e + g) \cdot (h, i) = (dh + fh, eh + gh) = (dh, eh) + (fh, gh) = a \cdot c + b \cdot c$
+*** b
+Consider the function $f: R \rightarrow M(\mathds{R})$ is an isomorphism, such that $f((a, b)) =$ $\begin{smallmatrix} a & 0 \\ b & 0 \end{smallmatrix}$, then:
+1. $f$ is surjective since every element in the range has a domain element $\begin{smallmatrix} a & 0 \\ b & 0 \end{smallmatrix} = y \ni f((a, b)) = y$
+2. $f$ is injective since $f((c, d) = x) = f((e, f) = y) \Rightarrow$ $\begin{smallmatrix} c & 0 \\ d & 0 \end{smallmatrix}$ = $\begin{smallmatrix} e & 0 \\ f & 0 \end{smallmatrix}$ $\Rightarrow c = e \wedge d = f \Rightarrow x = y$
+3. $f((c, d) = x) + f((e, f) = y) \Rightarrow$ $\begin{smallmatrix} c & 0 \\ d & 0 \end{smallmatrix}$ + $\begin{smallmatrix} e & 0 \\ f & 0 \end{smallmatrix}$ = $\begin{smallmatrix} c + e & 0 \\ d + f & 0 \end{smallmatrix}$
+   $= f(x + y)$, and $f((c, d) = x) \cdot f((e, f) = y) \Rightarrow$ $\begin{smallmatrix} c & 0 \\ d & 0 \end{smallmatrix}$ $\cdot$ $\begin{smallmatrix} e & 0 \\ f & 0 \end{smallmatrix}$ = $\begin{smallmatrix} ce & 0 \\ de & 0 \end{smallmatrix}$
+   $= f(x \cdot y)$
+