% Created 2023-02-17 Fri 12:59 % Intended LaTeX compiler: pdflatex \documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage{graphicx} \usepackage{longtable} \usepackage{wrapfig} \usepackage{rotating} \usepackage[normalem]{ulem} \usepackage{amsmath} \usepackage{amssymb} \usepackage{capt-of} \usepackage{hyperref} \notindent \notag \usepackage{ dsfont } \usepackage{amsmath} \usepackage[a4paper,margin=1in,landscape]{geometry} \author{Lizzy Hunt} \date{\today} \title{Assignment Five} \hypersetup{ pdfauthor={Lizzy Hunt}, pdftitle={Assignment Five}, pdfkeywords={}, pdfsubject={}, pdfcreator={Emacs 28.2 (Org mode 9.6.1)}, pdflang={English}} \begin{document} \maketitle \setlength\parindent{0pt} \section{Section 3.2} \label{sec:org258154b} \subsection{Question One} \label{sec:orgf02bb85} \subsubsection{a} \label{sec:orgccb1c0c} \(a^2 - ab + ba - b^2\) \subsubsection{b} \label{sec:org9164b85} \(a^3 + ba^2 + 2a^2b + 2ab^2 + ab^2 + b^3\) \subsubsection{c} \label{sec:orgdaba485} (a) could be \(a^2 - b^2\) (b) could be \(a^3 + 3a^2b + 3ab^2 + b^3\) \subsection{Question Three} \label{sec:org4d02a16} \subsubsection{a} \label{sec:orgb743fca} \(\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}\) \subsubsection{b} \label{sec:org8300d7e} \begin{verbatim} >>> set(filter(lambda y: all([y**2 % 12 == y for x in range(12)]), range(12))) {0, 1, 4, 9} \end{verbatim} \subsection{Question Seven} \label{sec:org9152891} 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\) \subsection{Question Eight} \label{sec:org3ed31b0} Considering \(n,m \in T\) then \(n = xb, m = yb\) with \(x,y \in R\): \begin{enumerate} \item T is closed under multiplication: \(n \cdot m = xb \cdot yb = (x \cdot y)b\), which follows the rule. \item T is closed under subtraction: \(n - m = xb - yb = (x - y)b\), which also follows the rule. \end{enumerate} We also know \(T\) is not empty since it must have at least 0\textsubscript{R}. \subsection{Question Ten} \label{sec:orgc4efb36} \subsubsection{a} \label{sec:orgbc2ab9d} \(\bar{R} = {(0, 0), (1, 0), (2, 0)}\) \(\bar{S} = {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4)}\) \subsubsection{b} \label{sec:org564675e} Considering \(n, m \in \bar{R}\), then \(n = (x, 0_S), n = (y, 0_S)\) with \(x,y \in R\). \begin{enumerate} \item \(\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\). \item \(\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\). \end{enumerate} We also know that \(\bar{R}_0 = (0_R, 0_S) \in R \times S\) so \(\bar{R}\) is not empty. \subsubsection{c} \label{sec:org5905763} Considering \(n, m \in \bar{S}\), then \(n = (0_R, x), n = (0_R, y)\) with \(x,y \in S\). \begin{enumerate} \item \(\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\). \item \(\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\). \end{enumerate} We also know that \(\bar{S}_0 = (0_R, 0_S) \in R \times S\) so \(\bar{S}\) is not empty. \subsection{Question Thirteen} \label{sec:orgfc1192c} \subsubsection{a} \label{sec:orgdc9f5c9} Considering \(n, m \in S \cap T\), then \(n \in S\) and \(n \in T\), \(m \in S\) and \(m \in T\), therefore: \begin{enumerate} \item \(S \cap T\) is closed under multiplication as \(m \cdot n\) must also be in \(S \cap T\) \item \(S \cap T\) is closed under addition as \(m + n\) must also be in \(S \cap T\) \end{enumerate} Since \(S\) and \(T\) are both subrings of \(R\), \(0_R \in S \cap T\). \subsubsection{b} \label{sec:orgeb2e7d6} 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\). \subsection{Question Fifteen - TODO} \label{sec:org675f8a8} \subsection{Question Twenty-One} \label{sec:org0c713ff} \subsubsection{a} \label{sec:org6158430} 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\) \subsubsection{b} \label{sec:org4391edc} 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{Section 3.3} \label{sec:orgff5f7f5} \subsection{Question One} \label{sec:org08aff62} In the true nature of being a computer science student, automate something for 2 hours that you could've done in 20 minutes! \begin{verbatim} 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{verbatim} \subsubsection{Z\textsubscript{2} \texttimes{} Z\textsubscript{3} with bijection} \label{sec:orgcac27c3} \begin{verbatim} bijection = [0, 4, 2, 3, 1, 5] \end{verbatim} \begin{enumerate} \item Multiplication Tables \label{sec:org1f4aa9f} \begin{verbatim} make_cartesian_congruence_table(2, 3, mult_tup, bijection, '\odot') \end{verbatim} \begin{center} \begin{tabular}{lllllll} \(\odot\) & (0, 0) & (1, 1) & (0, 2) & (1, 0) & (0, 1) & (1, 2)\\[0pt] (0, 0) & (0, 0) & (0, 0) & (0, 0) & (0, 0) & (0, 0) & (0, 0)\\[0pt] (1, 1) & (0, 0) & (1, 1) & (0, 2) & (1, 0) & (0, 1) & (1, 2)\\[0pt] (0, 2) & (0, 0) & (0, 2) & (0, 1) & (0, 0) & (0, 2) & (0, 1)\\[0pt] (1, 0) & (0, 0) & (1, 0) & (0, 0) & (1, 0) & (0, 0) & (1, 0)\\[0pt] (0, 1) & (0, 0) & (0, 1) & (0, 2) & (0, 0) & (0, 1) & (0, 2)\\[0pt] (1, 2) & (0, 0) & (1, 2) & (0, 1) & (1, 0) & (0, 2) & (1, 1)\\[0pt] \end{tabular} \end{center} \item Addition Tables \label{sec:org807c598} \begin{verbatim} make_cartesian_congruence_table(2, 3, add_tup, bijection, '\oplus') \end{verbatim} \begin{center} \begin{tabular}{lllllll} \(\oplus\) & (0, 0) & (1, 1) & (0, 2) & (1, 0) & (0, 1) & (1, 2)\\[0pt] (0, 0) & (0, 0) & (1, 1) & (0, 2) & (1, 0) & (0, 1) & (1, 2)\\[0pt] (1, 1) & (1, 1) & (0, 2) & (1, 0) & (0, 1) & (1, 2) & (0, 0)\\[0pt] (0, 2) & (0, 2) & (1, 0) & (0, 1) & (1, 2) & (0, 0) & (1, 1)\\[0pt] (1, 0) & (1, 0) & (0, 1) & (1, 2) & (0, 0) & (1, 1) & (0, 2)\\[0pt] (0, 1) & (0, 1) & (1, 2) & (0, 0) & (1, 1) & (0, 2) & (1, 0)\\[0pt] (1, 2) & (1, 2) & (0, 0) & (1, 1) & (0, 2) & (1, 0) & (0, 1)\\[0pt] \end{tabular} \end{center} \end{enumerate} \subsubsection{Z\textsubscript{6}} \label{sec:orgbe8adf1} \begin{enumerate} \item Multiplication Tables \label{sec:orga98b12b} \begin{verbatim} make_normal_table(6, lambda a, b: a * b, '\odot') \end{verbatim} \begin{center} \begin{tabular}{rrrrrrr} \(\odot\) & 0 & 1 & 2 & 3 & 4 & 5\\[0pt] 0 & 0 & 0 & 0 & 0 & 0 & 0\\[0pt] 1 & 0 & 1 & 2 & 3 & 4 & 5\\[0pt] 2 & 0 & 2 & 4 & 0 & 2 & 4\\[0pt] 3 & 0 & 3 & 0 & 3 & 0 & 3\\[0pt] 4 & 0 & 4 & 2 & 0 & 4 & 2\\[0pt] 5 & 0 & 5 & 4 & 3 & 2 & 1\\[0pt] \end{tabular} \end{center} \item Addition Tables \label{sec:orgfcf7bde} \begin{verbatim} make_normal_table(6, lambda a, b: a + b, '\oplus') \end{verbatim} \begin{center} \begin{tabular}{rrrrrrr} \(\oplus\) & 0 & 1 & 2 & 3 & 4 & 5\\[0pt] 0 & 0 & 1 & 2 & 3 & 4 & 5\\[0pt] 1 & 1 & 2 & 3 & 4 & 5 & 0\\[0pt] 2 & 2 & 3 & 4 & 5 & 0 & 1\\[0pt] 3 & 3 & 4 & 5 & 0 & 1 & 2\\[0pt] 4 & 4 & 5 & 0 & 1 & 2 & 3\\[0pt] 5 & 5 & 0 & 1 & 2 & 3 & 4\\[0pt] \end{tabular} \end{center} \end{enumerate} \subsection{Question Two} \label{sec:org9540aed} \begin{verbatim} bijection = [0, 3, 2, 1] make_cartesian_congruence_table(2, 2, mult_tup, bijection, '\odot') \end{verbatim} \begin{center} \begin{tabular}{lllll} \(\odot\) & (0, 0) & (1, 1) & (1, 0) & (0, 1)\\[0pt] (0, 0) & (0, 0) & (0, 0) & (0, 0) & (0, 0)\\[0pt] (1, 1) & (0, 0) & (1, 1) & (1, 0) & (0, 1)\\[0pt] (1, 0) & (0, 0) & (1, 0) & (1, 0) & (0, 0)\\[0pt] (0, 1) & (0, 0) & (0, 1) & (0, 0) & (0, 1)\\[0pt] \end{tabular} \end{center} \begin{verbatim} bijection = [0, 3, 2, 1] make_cartesian_congruence_table(2, 2, add_tup, bijection, '\oplus') \end{verbatim} \begin{center} \begin{tabular}{lllll} \(\oplus\) & (0, 0) & (1, 1) & (1, 0) & (0, 1)\\[0pt] (0, 0) & (0, 0) & (1, 1) & (1, 0) & (0, 1)\\[0pt] (1, 1) & (1, 1) & (0, 0) & (0, 1) & (1, 0)\\[0pt] (1, 0) & (1, 0) & (0, 1) & (0, 0) & (1, 1)\\[0pt] (0, 1) & (0, 1) & (1, 0) & (1, 1) & (0, 0)\\[0pt] \end{tabular} \end{center} \subsection{Question Three} \label{sec:org421e770} \begin{enumerate} \item \(f\) is injective, since \(f(a) = f(b) \Rightarrow (a,a) = (b,b) \Rightarrow a = b\) \item \(f\) is surjective since every range element in \(R^*\), \((a,a)\) is mapped to \(a \in R\) by definition \item \(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)\) \end{enumerate} \subsection{Question Four} \label{sec:org1f8479a} \(f(1)f(3) = (2)(6) \equiv_{10} 2\) but \(f(3) = 6\) which doesn't hold the properties of homomorphism. \subsection{Question Five} \label{sec:orgeb656c3} Consider the given function: \begin{enumerate} \item \(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\) \item \(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 \item \(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)\), \end{enumerate} \subsection{Question Nine - TODO} \label{sec:org2f29e8e} \subsection{Question Eleven} \label{sec:org3e455ed} \subsubsection{b} \label{sec:org24734c1} \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} \subsubsection{d} \label{sec:orgc2ba394} \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} \subsection{Question Twelve} \label{sec:org95ce95e} \subsubsection{c} \label{sec:org77d2e96} 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)\). \subsubsection{d} \label{sec:org1c2b201} \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} \subsection{Question Thirteen} \label{sec:org57e2c18} \subsubsection{a} \label{sec:org7515001} 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))\). \subsubsection{b} \label{sec:orgfb2a3ab} 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))\). \subsection{Question Fifteen} \label{sec:org4046d12} Consider \(f: Z_4 \rightarrow Z_4 \ni f(x) = 0\), then 2 is a zero divisor, but 0 is not by definition. \subsection{Question Twenty One} \label{sec:org48d8cc7} \subsubsection{Lemma} \label{sec:org3598e64} 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\). \subsubsection{Proof} \label{sec:orgee74248} 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}\textsuperscript{*}. 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. \begin{enumerate} \item \(f\) is a bijection since we have an inverse \(x = 1 - f(x)\) \item \(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)\) \end{enumerate} \subsection{Question Twenty Four} \label{sec:org07a0b7a} \subsubsection{a} \label{sec:org897ff21} \begin{enumerate} \item 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)\). \item \(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. \item 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)\) \item 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\) \end{enumerate} \subsubsection{b} \label{sec:org92e2744} 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: \begin{enumerate} \item \(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\) \item \(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\) \item \(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)\) \end{enumerate} \end{document}