diff options
| -rw-r--r-- | bibliography.bib | 38 | ||||
| -rw-r--r-- | gust.tex | 773 |
2 files changed, 637 insertions, 174 deletions
diff --git a/bibliography.bib b/bibliography.bib new file mode 100644 index 0000000..b8aa8e3 --- /dev/null +++ b/bibliography.bib @@ -0,0 +1,38 @@ +@book{dummit-foote, + author={David S. Dummit and Richard M. Foote}, + title={Abstract Algebra}, + edition={3}, + publisher={John Wiley \& Sons, Inc.}, + year={2004} +} + +@book{gallian, + author={Joseph A. Gallian}, + title={Contemporary Abstract Algebra}, + edition={10}, + publisher={Taylor \& Francis Group, LLC}, + year={2021} +} + +@misc{wikipedia-ring, + author={{Wikipedia contributors}}, + title={Ring (mathematics)}, + howpublished={Web: \url{https://en.wikipedia.org/wiki/Ring_(mathematics)}}, + note={Accessed November 29, 2024}, + year={2024} +} + +@book{maunder, + author={C. R. F. Maunder}, + title={Algebraic Topology}, + publisher={Dover Publications, Inc.}, + year={1996} +} + +@misc{mathworld-ring, + author={Eric W. Weisstein}, + title={Ring}, + howpublished={Web: \url{https://mathworld.wolfram.com/Ring.html}}, + note={Accessed November 29, 2024}, + year={2024} +} @@ -8,11 +8,16 @@ \documentclass{montgomery} +\addbibresource{bibliography.bib} +\makeindex[intoc] + \DeclareMathOperator{\abs}{abs} +\newcommand{\normal}{\mathbin{\trianglelefteq}} + \begin{document} -\thispagestyle{empty} +\pagestyle{empty} \phantom{.} @@ -20,13 +25,9 @@ \begin{center} - {\huge Grand Unified Study Guide} - - {\Large (under construction)} - - \phantom{.} + {\huge\itshape\bfseries Grand Unified Study Guide} - \hrule + {\Large\itshape (under construction)} \vfill @@ -43,9 +44,9 @@ \phantom{.} \newpage -\thispagestyle{empty} -\frontmatter +\tableofcontents + \chapter*{Preface} This is intended to be a study guide for a number of classes I have taken. I attempt to cover all the topics listed for these in the syllabi at the universities where I took them (University of North Carolina Charlotte and University of South Carolina), although they are not necessarily presented in the same way. For example, I present topology before analysis and then cite a lot of facts from topology, even though a first-year course in analysis usually does not require such a long detour. @@ -54,264 +55,688 @@ There are exercises and examples interspersed throughout the text. The solutions Throughout this text, $\mathbb{N}$ denotes the non-negative integers, and $\mathbb{Z}_+$ denotes the positive integers. $\mathbb{Q}_+$ and $\mathbb{R}_+$ are the positive rationals and reals respectively. $\mathbb{Z}_\pm$, $\mathbb{Q}_\pm$, and $\mathbb{R}_\pm$ are the non-zero integers, rationals, and reals respectively. For any set $S$, we use $\mathcal{P}(S)$ for the power set of $S$. -What follows is a summary of each chapter and its prerequisites. Note that a chapter does not necessarily depend on each previous chapter. +It is not necessary to read the chapters in order. Each section begins with a list of other sections that should be read first. Sections without prerequisites are intended to be readable by students in their first year of a graduate mathematics program. -\begin{itemize} +\mainmatter +\pagestyle{headings} - \item \Cref{logic-chapter}: Logic +\chapter{Groups} - This chapter provides a very formal treatment of first-order logic and natural deduction up to G\"odel's completeness and incompleteness theorems. It is intended to be understandable by anyone who has (successfully) taken some proof-based course in mathematics. +\section{Definitions and basic properties} +\label{groups-section} - \item \Cref{set-theory-chapter}: Set Theory +\subsection*{Groups} - Here we develop the von Neumann--Bernays--G\"odel ($NBG$) set theory. For those already versed in set theory, this is a theory where every object is a class and sets are defined as those classes which are an element of some other class. The language of $NBG$ is a superset of the language of $ZFC$, and the statements which can be written in the language of $ZFC$ are true in $NBG$ if and only if they are true in $ZFC$. This chapter requires only \Cref{logic-chapter} as a prerequisite. +\begin{definition} + \index{group} + \index{identity!in a group|see {group}} + \index{inverse!in a group|see {group}} + A \textit{group} is a set $G$ along with an operation $\diamond : G^2 \to G$ satisfying: + \begin{itemize} + \item Associativity: for all $x, y, z \in G$, we have $(x \diamond y) \diamond z = x \diamond (y \diamond z)$. + \item Existence of identity: there is an $e \in G$ such that, for all $x \in G$, we have $x \diamond e = x$ and $e \diamond x = x$. + \item Existence of inverses: for each $x \in G$, there is an $x' \in G$ such that $x \diamond x' = e$. + \end{itemize} +\end{definition} - \item \Cref{algebra-chapter}: Algebra +\begin{definition} + \index{Abelian group} + A group $(G, \diamond)$ is \textit{Abelian} if we have $x \diamond y = y \diamond x$ for all $x, y \in G$. +\end{definition} - This covers some amount of group theory, ring theory, and linear algebra. The topics covered are intended to align with those a student would see in their first year of graduate school. Some of the statements from \Cref{set-theory-chapter} (in particular Zorn's lemma) are used here, but if you believe the statements you do not need to read \Cref{set-theory-chapter} or \Cref{logic-chapter} in detail. If you are content to believe the statements from \Cref{set-theory-chapter} that are used here, the prerequisites for this are the same as those for \Cref{logic-chapter}. +\begin{example} + Let $S$ be any set. Let $B(S)$ denote the set of bijections from $S$ to itself. Then, $S$ forms a group under composition. The identity is the identity function and the inverse of a bijection is its function inverse. This group is Abelian if and only if $S$ has no more than 2 elements. +\end{example} - \item \Cref{topology-chapter}: Topology +\begin{example} + $\mathbb{R}$ forms an Abelian group under addition. Here, the identity is $0$ and the inverse of a number is its negation. +\end{example} - This covers the parts of topology that I find interesting and don't require too much set theory. Topics discussed include the separation and countability axioms, metrizability, and compactness. The prerequisites for this section are the same as those for \Cref{logic-chapter}, plus the parts of \Cref{set-theory-chapter} about orders, ordinals, and cardinality. +\begin{example} + $\mathbb{R}_\pm$ forms an Abelian group under multiplication. Here, the identity is $1$ and the inverse of a number is its reciprocal. +\end{example} - \item \Cref{analysis-chapter}: Analysis, Part I +Some basic properties of groups follow. - We begin by developing the real numbers in $NBG$. \Cref{encoding-of-the-real-numbers-section} requires \Cref{set-theory-chapter} and \Cref{algebra-chapter}. If one is content to believe that the real numbers are a complete ordered field and is not interested in the details, then that section can be skipped. Only \Cref{topology-chapter} is required for the remaining sections, which discuss compactness, continuity, and differentiation specifically in $\mathbb{R}$ and $\mathbb{R}^n$. +\begin{theorem} + \label{group-basic-props} + % careful about renumbering in the enumerates - search for references to group-basic-props + Let $(G, \diamond)$ be a group with identity $e$. For each $x \in G$, let $x'$ be the inverse of $x$. + \begin{enumerate} + \item Let $x, y, z \in G$. If $x \diamond y = z \diamond y$, then $x = z$. + \item For all $x \in G$, we have $x' \diamond x = e$ (i.e.~$x = x''$). + \item Let $x, y, z \in G$. If $x \diamond y = x \diamond z$, then $y = z$. + \item Suppose $f \in G$ with $x \diamond f = x$ for all $x \in G$. Then, $f = e$. + \item Suppose $f \in G$ with $f \diamond x = x$ for all $x \in G$. Then, $f = e$. + \item Let $x, y \in G$ with $x \diamond y = e$. Then, $x = y'$ and $y = x'$. + \end{enumerate} + \begin{proof} + \begin{enumerate} + \item $x = x \diamond e = x \diamond y \diamond y' = z \diamond y \diamond y' = z \diamond e = z$. + \item $x' \diamond x \diamond x' = x' \diamond e = e \diamond x'$. Applying (a), we get $x' \diamond x = e$. + \item $y = e \diamond y = x' \diamond x \diamond y = x' \diamond x \diamond z = e \diamond e = z$. + \item $f = e \diamond f = e$. + \item $f = f \diamond e = e$. + \item $x = x \diamond e = x \diamond y \diamond y' = e \diamond y' = y'$ and $y = e \diamond y = x' \diamond x \diamond y = x' \diamond e = x'$. + \qedhere + \end{enumerate} + \end{proof} +\end{theorem} -\end{itemize} +Often the group operation will be represented by either $+$ or $\cdot$. In these two cases we define some special notation. + +If we have a group $(G, +)$, then we will write $0$ for the group identity, and $-x$ for the group inverse of an $x \in G$. For any $x, y \in G$, we will write $x - y$ for $x + -y$. We define $n \cdot x$ or $nx$ for $n \in \mathbb{Z}$ and $x \in G$ recursively: +\begin{gather*} + 0 \cdot x = 0x = 0\\ + n \cdot x = nx = (n - 1)x + x \text{ for } n > 0\\ + n \cdot x = nx = -(|n|x) \text{ for } n < 0. +\end{gather*} +If we have a group $(G, \cdot)$, then we will write $1$ for the group identity and $x^{-1}$ for the group inverse of an $x \in G$. We define $x^n$ for $n \in \mathbb{Z}$ and $x \in G$ recursively: +\begin{gather*} + x^0 = 1\\ + x^n = x^{n - 1} \cdot x \text{ for } n > 0\\ + x^n = (x^{|n|})^{-1} \text{ for } n < 0. +\end{gather*} -\tableofcontents +\begin{theorem} + \label{group-power-rules} + Let $(G, \cdot)$ be a group. Then, the following are true: + \begin{enumerate} + \item If $x \in G$ and $n, m \in \mathbb{Z}$, then $x^{n + m} = x^n x^m$. + \item If $x \in G$ and $n, m \in \mathbb{Z}$, then $x^{n \cdot m} = (x^{n})^m$. + \end{enumerate} + \begin{proof} + \begin{enumerate} + \item + If $m = 0$, then $x^{n + m} = x^n = x^n \cdot 1 = x^n x^m$. Let $m > 0$ and suppose that $x^{n + m - 1} = x^n x^{m - 1}$. Then $x^{n + m} = x^{n + m - 1} x = x^n x^{m - 1} x = x^n x^m$. By induction, $x^{n + m} = x^n x^m$ for all $m \ge 0$. -\mainmatter + If $m < 0$, then $x^n x^m = x^{n + m + |m|} x^m = x^{n + m} x^{|m|} x^m = x^{n + m} x^{|m|} (x^{|m|})^{-1} = x^{n + m}$. + \item + If $m = 0$, then $x^{n \cdot m} = x^0 = 1 = (x^n)^m$. Let $m > 0$ and suppose that $x^{n \cdot (m - 1)} = (x^n)^{m - 1}$. Then $x^{n \cdot m} = x^{n \cdot (m - 1) + n} = x^{n \cdot (m - 1)} x^n = (x^n)^{m - 1} x^n = (x^n)^m$. By induction, $x^{n \cdot m} = (x^n)^m$ for all $m \ge 0$. -\chapter{Logic} -\label{logic-chapter} + Observe that, for any $k \in \mathbb{Z}$, we have $x^k \cdot x^{-k} = x^{k + {-k}} = x^0 = 1$, so $x^{-k} = (x^k)^{-1}$. -\section{Propositional logic} + Then, if $m < 0$, we have $(x^n)^m = ((x^n)^{|m|})^{-1} = (x^{n \cdot |m|})^{-1} = x^{-(n \cdot |m|)} = x^{n \cdot m}$. + \qedhere + \end{enumerate} + \end{proof} +\end{theorem} -We begin this chapter with a discussion of propositional logic, also known as zeroth-order logic. I think the topics in this section will be familiar to those who have seen Boolean logic in an undergraduate computer science context. +For a group $(G, +)$, $x \in G$, and $n, m \in \mathbb{Z}$, those equations are: +\begin{itemize} + \item $(n + m)x = nx + mx$. + \item $(n \cdot m)x = m(nx)$. +\end{itemize} -We will first define the set of propositional formulae. There is an infinite set of propositional variables $\mathcal{L}_0 = \{P_1, P_2, P_3, \dots\}$, and a set of binary connectives $\mathcal{C} = \{{\land}, {\lor}, {\rightarrow}, {\leftrightarrow}\}$, which will not vary throughout this section. For now, propositional formula should be considered as nothing more than formal strings over the alphabet $\mathcal{L}_0 \cup \mathcal{C} \cup \{{\lnot}, {(}, {)}\}$. +\subsection*{Subgroups} \begin{definition} - For any integer $n > 0$, we let \[ - \mathcal{L}_n = \mathcal{L}_{n - 1} \cup \{(\lnot \phi) : \phi \in \mathcal{L}_{n - 1}\} \cup \{(\phi \diamond \chi) : \phi, \chi \in \mathcal{L}_{n - 1}, {\diamond} \in \mathcal{C}\}. - \] - We define the set of all \textit{propositional formulae} by \[ - \mathcal{L} = \bigcup_{n \in \mathbb{N}} \mathcal{L}_n. - \] + \index{subgroup} + Let $(G, +)$ be a group. A \textit{subgroup} of $G$ is a group on a subset $H \subseteq G$ with the operation being the restriction of $+$ to $H^2$. \end{definition} +A potentially subtle point here: recall that the operation in a group on $H$ goes from $H^2$ to $H$. Thus, we need $h_1 + h_2 \in H$ for all $h_1, h_2 \in H$ for $H$ to be a subgroup. + \begin{example} - The following are formulae: - \begin{itemize} - \item $(P_1 \land P_2)$ - \item $((P_1 \land P_2) \lor (P_1 \land P_3))$ - \item $(P_1 \rightarrow (P_2 \lor P_3))$ - \item $(\lnot (P_1 \rightarrow (\lnot P_2)))$ - \end{itemize} + $(\mathbb{Z}, +)$ is a subgroup of $(\mathbb{R}, +)$. +\end{example} + +\begin{example} + $(\mathbb{Q}_\pm, \cdot)$ is a subgroup of $(\mathbb{R}_\pm, \cdot)$. \end{example} -When one wants to prove something is true for all formulae, one often uses the following pattern: +Notice that if $(H, +)$ is a subgroup of $(G, +)$, then the $0$ from $G$ is the $0$ of $H$ by \cref{group-basic-props}(d) or \cref{group-basic-props}(e). Additionally, if $h \in H$, then the $-h$ from $G$ is the $-h$ of $H$ by \cref{group-basic-props}(f). \begin{theorem} - \label{formula-induction} - Let $\Gamma \subseteq \mathcal{L}$. Suppose that the following are true: + \label{subgroup-test} + Let $(G, +)$ be a group, and let $H \subseteq G$. Then, $H$ is a subgroup of $G$ if and only if both of the following are satisfied: \begin{itemize} - \item $\mathcal{L}_0 \subseteq \Gamma$. - \item If $\phi \in \Gamma$, then $(\lnot \phi) \in \Gamma$. - \item If $\phi, \chi \in \Gamma$ and $\diamond \in \mathcal{C}$, then $(\phi \diamond \chi) \in \Gamma$. + \item $H$ is nonempty. + \item For all $x, y \in H$, we have $x - y \in H$. \end{itemize} - Then, $\Gamma = \mathcal{L}$. \begin{proof} - We need to show that $\mathcal{L} \subseteq \Gamma$. We will show that $\mathcal{L}_n \subseteq \Gamma$ for all $n$ by inducting on $n$. - - Our base case is $\mathcal{L}_0 \subseteq \Gamma$, which we already assumed. + If $H$ is a subgroup, then $H$ is nonempty because it contains its inverse. For any $x, y \in H$, we have $-y \in H$, and $H$ is closed under $+$ so $x + -y \in H$. - For the inductive step, let $n > 0$ and suppose that we have $\mathcal{L}_m \subseteq \Gamma$ for all $m < n$. Let $\phi \in \mathcal{L}_n$. There are three cases: - \begin{itemize} - \item $\phi \in \mathcal{L}_{n - 1}$. By the induction hypothesis, we have $\phi \in \Gamma$. - \item $\phi = (\lnot \chi)$ for some $\chi \in \mathcal{L}_{n - 1}$. By the induction hypothesis, we have $\chi \in \Gamma$, and then by one of our assumptions, $(\lnot \chi) \in \Gamma$. - \item $\phi = (\chi \diamond \psi)$ for some $\chi, \psi \in \mathcal{L}_{n - 1}$ and $\diamond \in \mathcal{C}$. By the induction hypothesis, we have $\chi, \psi \in \Gamma$, and then by one of our assumptions, $(\chi \diamond \psi) \in \Gamma$. - \end{itemize} - In any case, $\phi \in \Gamma$, so $\mathcal{L}_n \subseteq \Gamma$. + On the other hand, suppose $H \subseteq G$ satisfies the two bullet points. Since $H$ is nonempty, we can take some $h \in H$ and then $0 = h - h \in H$. For any $h \in H$, we have $-h = 0 - h \in H$. For any $x, y \in H$, we have $x + y = x - {-y} \in H$. So, $H$ is closed under $+$. We have already shown that $H$ has the identity and inverse from $G$, and these still satisfy those roles when restricted to $H$. Finally, restricting $+$ to $H^2$ does not impact its associativity. So, $H$ is a group under $+$. \end{proof} \end{theorem} \begin{example} - Every formula has an equal number of $($ and $)$. + Let $(G, +)$ be a group and let $x \in G$. Consider $\left<x\right> = \{nx : n \in \mathbb{Z}\}$. This is a group. \begin{proof} - Let $f : \mathcal{L} \to \mathbb{N}$ map a formula $\phi$ to the number of $($ in $\phi$. Let $g : \mathcal{L} \to \mathbb{N}$ map a formula $\phi$ to the number of $)$ in $\phi$. Let $\Gamma = \{\phi \in \mathcal{L} : f(\phi) = g(\phi)\}$. + We have $x = 1x \in \left<x\right>$, so $\left<x\right>$ is nonempty. If we take two $y, z \in \left<x\right>$, we can write $y = nx$ and $z = mx$ for some $n, m \in \mathbb{Z}$. Then, using \cref{group-power-rules}, we get $y - z = nx - mx = nx + -1 \cdot mx = nx + (-m)x = (n - m)x \in \left<x\right>$. + \end{proof} +\end{example} + +\begin{definition} + \index{subgroup!generated by an element} + The group $\left<x\right>$ in the previous example is called the subgroup of $(G, +)$ \textit{generated by} $x$. +\end{definition} + +\begin{exercise} + What are $\left<1\right>$, $\left<-1\right>$, $\left<2\right>$, $\left<-2\right>$ in each of $(\mathbb{R}, +)$ and $(\mathbb{R}_\pm, \cdot)$? + \begin{solution} + In $(\mathbb{R}, +)$: + \begin{itemize} + \item $\left<1\right> = \left<-1\right> = \mathbb{Z}$. + \item $\left<2\right> = \left<-2\right> = \{2n : n \in \mathbb{Z}\}$. + \end{itemize} + In $(\mathbb{R}_\pm, \cdot)$: + \begin{itemize} + \item $\left<1\right> = \{1\}$. + \item $\left<-1\right> = \{1, -1\}$. + \item $\left<2\right> = \{2^n : n \in \mathbb{Z}\}$. + \item $\left<-2\right> = \{2^n, -2^n : n \in \mathbb{Z}\}$. + \qedhere + \end{itemize} + \end{solution} +\end{exercise} + +\begin{definition} + \index{order!of a group} + \index{order!of an element in a group} + Let $(G, +)$ be a group. The \textit{order} of $(G, +)$ is the cardinality of $G$ if that is finite, and ``$\infty$'' otherwise. We call $(G, +)$ a \textit{finite} group if its order is finite. For any $x \in G$, the \textit{order} of $x$ is the order of $\left<x\right>$. We denote the order of $G$ by $|G|$, and the order of $x$ by $|x|$. +\end{definition} - For every $\phi \in \mathcal{L}_0$, we have $f(\phi) = 0 = g(\phi)$, so $\phi \in \Gamma$. +\begin{exercise} + What are the orders of $1$, $-1$, $2$, $-2$ in $(\mathbb{R}, +)$ and $(\mathbb{R}_\pm, \cdot)$? + \begin{solution} + In $(\mathbb{R}, +)$, all of these have order $\infty$. - For every $\phi \in \Gamma$, we have $f((\lnot \phi)) = 1 + f(\phi) = g(\phi) + 1 = g((\lnot \phi))$, so $(\lnot \phi) \in \Gamma$. + In $(\mathbb{R}_\pm, \cdot)$, the order of $1$ is $1$, the order of $-1$ is $2$, and the orders of $2$ and $-2$ are $\infty$. + \end{solution} +\end{exercise} - For every $\phi, \chi \in \Gamma$ and $\diamond \in \mathcal{C}$, we have $f((\phi \diamond \chi)) = 1 + f(\phi) + f(\chi) = g(\phi) + g(\chi) + 1 = g((\phi \diamond \chi))$, so $(\phi \diamond \chi) \in \Gamma$. +\begin{theorem}[Lagrange's theorem] + \label{lagrange} + \index{Lagrange's theorem} + Let $H$ be a subgroup of a finite group $G$. Then, the order of $H$ divides the order of $G$. + \begin{proof} + Let $+$ stand for the operation in $G$. For each $g \in G$, define $g + H = \{g + h : h \in H\}$. I claim that the relation $\sim$ on $G$ defined by $g_1 \sim g_2$ if and only if $g_1 \in g_2 + H$ is an equivalence relation. + \begin{itemize} + \item For any $g \in G$, we have $0 \in H$ and $g = g + 0 \in g + H$, so $g \sim g$. + \item If $g_1 \sim g_2$, then there is an $h \in H$ with $g_1 = g_2 + h$. We get $g_2 = g_1 + -h$, so $g_2 \sim g_1$. + \item If $g_1 \sim g_2$ and $g_2 \sim g_3$, then there are $h_1, h_2 \in H$ with $g_1 = g_2 + h_1$ and $g_2 = g_3 + h_2$. We get $g_1 = g_3 + h_2 + h_1$, so $g_1 \sim g_3$. + \end{itemize} + So, $\sim$ partitions $G$. In particular, note that, given a fixed $g \in G$, we have $\{g' \in G : g' \sim g\} = g + H$. In other words, $\{g + H : g \in G\}$ partitions $G$. - Then, the theorem gives us $\Gamma = \mathcal{L}$. + Next, I claim that each of these sets is the same size. Given two $g_1, g_2 \in G$, let $f : g_1 + H \to g_2 + H$ be defined by $f(g) = g_2 + -g_1 + g$. We will show that $f$ is a well-defined bijection. + \begin{itemize} + \item If $g \in g_1 + H$, then there is an $h$ with $g = g_1 + h$. We have $f(g) = g_2 + -g_1 + g_1 + h = g_2 + h$, so $f(g) \in g_2 + H$. So, $f$ is well-defined. + \item For any $g \in g_2 + H$, there is some $h$ with $g = g_2 + h$. Then, $g_1 + h \in g_1 + H$, and $f(g_1 + h) = g_2 + -g_1 + g_1 + h = g_2 + h = g$. So, $f$ is surjective. + \item Given two $g, g' \in g_1 + H$ with $f(g) = f(g')$, we have $g_2 + -g_1 + g = g_2 + -g_1 + g'$, so $g = g'$. Then, $f$ is injective. + \end{itemize} + Next, observe that $0 + H = H$. We have partitioned $G$ into sets that each have the same size as $H$, so the order of $H$ divides the order of $G$. \end{proof} - In the future, we will not explicitly define a set $\Gamma$ of formulae with the property. We will just show that every formula in $\mathcal{L}_0$ has the property, if $\phi$ is a formula with the property then $(\lnot \phi)$ has the property, and if $\phi, \chi$ are formulae with the property and $\diamond \in \mathcal{C}$ then $(\phi \diamond \chi)$ has the property. -\end{example} +\end{theorem} -In particular, that example shows us that every formula has a finite length. +In particular, this means that the order of an element in a finite group divides the order of that group. \begin{exercise} - \label{start-and-end} - Show that, for every $\phi \in \mathcal{L}$, the first symbol in $\phi$ that is not a $($ is in $\mathcal{L}_0 \cup \{{\lnot}\}$, and the last symbol in $\phi$ that is not a $)$ is in $\mathcal{L}_0$. + Let $(G, +)$ be a group. Let $\mathcal{H}$ be a set of subgroups of $(G, +)$. Show that $\bigcap \mathcal{H}$ is a subgroup of $(G, +)$. \begin{solution} - Let $\phi \in \mathcal{L}_0$. Then, $\phi$ starts and ends with a symbol from $\mathcal{L}_0$ (namely $\phi$). + We use \cref{subgroup-test}. Each $H \in \mathcal{H}$ has $0 \in H$. Then, $0 \in \bigcap \mathcal{H}$, so $\bigcap \mathcal{H}$ is not empty. If $x, y \in \bigcap \mathcal{H}$, then $x, y \in H$ for each $H \in \mathcal{H}$. So, $x - y \in H$ for each $H \in \mathcal{H}$, which means $x - y \in \bigcap \mathcal{H}$. + \end{solution} +\end{exercise} - Let $\phi = (\lnot \chi)$, where $\chi \in \mathcal{L}$, and suppose the exercise is true for $\chi$. The first symbol in $\phi$ that isn't a $($ is $\lnot$, and the last symbol in $\phi$ that isn't a $)$ is the same as that of $\chi$. +\begin{definition} + \index{subgroup!generated by a set} + \index{generating set!for a group} + Let $(G, +)$ be a group. Given a set $S \subseteq G$, the \textit{subgroup generated by $S$} is the intersection of all subgroups of $G$ with $S$ as a subset. We denote this subgroup by $\left<S\right>$. If $\left<S\right> = G$, then we say that $S$ \textit{generates} $(G, +)$, or that $S$ is a \textit{generating set} for $(G, +)$. +\end{definition} - Let $\phi = (\chi \diamond \psi)$, where $\chi, \psi \in \mathcal{L}$ and $\diamond \in \mathcal{C}$, and suppose the exercise is true for $\chi$ and $\psi$. The first symbol in $\phi$ that isn't a $($ the same as that of $\chi$, and the last symbol in $\phi$ that isn't a $)$ is the same as that of $\psi$. +\begin{exercise} + Let $S$ be a subset of a group $(G, +)$. Let $S' = S \cup \{-s : s \in S\}$. Let $T$ be the set of finite sums of (not necessarily distinct) elements in $S'$, including the empty sum. For example, if $x, y \in S$, then $T$ has $0$, $x$, $x + y$, $x - y$, $x + x$, $-x + y + y$, etc. Show that $\left<S\right> = T$. + \begin{solution} + It is sufficient to show that $T$ is a subgroup of $(G, +)$ containing $S$ and that every subgroup of $(G, +)$ containing $S$ must contain $T$. + + It is clear that $S \subseteq T$, since each $x \in S$ can be viewed as the sum of just $x$. To show that $T$ is a subgroup, see that $0 \in T$ so $T$ is nonempty, and that if $x, y \in T$, then we have \begin{gather*} + x = x_1 + x_2 + \cdots + x_n,\\ + y = y_1 + y_2 + \cdots + y_m; + \end{gather*} + where each $x_i, y_i \in S'$, so + \begin{gather*} + x - y = x_1 + x_2 + \cdots + x_n - y_m - y_{m - 1} - \cdots - y_1 \in T. + \end{gather*} + Now let $H$ be a subgroup of $(G, +)$ with $S \subseteq H$. Since $H$ has to contain inverses for each element, we have $S' \subseteq H$, and since $0 \in H$ and $H$ is closed under the operation of the group, we get $T \subseteq H$. \end{solution} \end{exercise} +From the previous exercise we can see that, given a group $(G, +)$ and a $g \in G$, we have $\left<\{g\}\right> = \left<g\right>$. + +\begin{example} + $(\mathbb{Z}, +)$ is generated by $\{1\}$. Generating sets are not unique: $(\mathbb{Z}, +)$ is also generated by $\{2, 3\}$, since if a subgroup has both $2$ and $3$ then it must have $3 - 2 = 1$. +\end{example} + \begin{exercise} - \label{proper-more-open} - Show that, for every formula $\phi$, every nonempty proper initial substring of $\phi$ has more $($ than $)$. + Let $S$ be the set of bijections from $\mathbb{Q}$ to $\mathbb{Q}$. Show that the subgroup of $(S, \circ)$ generated by $\{x \mapsto qx : q \in \mathbb{Q}_\pm\} \cup \{x \mapsto x + q : q \in \mathbb{Q}\}$ is $\{mx + b : m \in \mathbb{Q}_\pm, b \in \mathbb{Q}\}$. \begin{solution} - If $\phi \in \mathcal{L}_0$, then $\phi$ has no nonempty proper substrings. + Let $A = \{x \mapsto qx : q \in \mathbb{Q}_\pm\}$, $B = \{x \mapsto x + q : q \in \mathbb{Q}\}$, $C = \{mx + b : m \in \mathbb{Q}_\pm, b \in \mathbb{Q}\}$. - Let $\phi = (\lnot \chi)$, where $\chi \in \mathcal{L}$, and suppose the exercise is true for $\chi$. A nonempty proper initial substring of $\phi$ is one of: - \begin{itemize} - \item $($ - \item $(\lnot$ - \item $(\lnot$ followed by a nonempty proper initial substring of $\chi$ - \item $(\lnot \chi$ - \end{itemize} - In each case we have more $($ than $)$. + $C$ is clearly nonempty. If we have $(x \mapsto m_1 x + b_1), (x \mapsto m_2 x + b_2) \in C$, then \begin{align*} + (x \mapsto m_1 x + b_1) \circ (x \mapsto m_2 x + b_2)^{-1} + & = (x \mapsto m_1 x + b_1) \circ \left(x \mapsto \frac{x - b_2}{m_2}\right)\\ + & = \left(x \mapsto m_1 \cdot \frac{x - b_2}{m_2} + b_1\right)\\ + & = \left(x \mapsto \frac{m_1}{m_2} x + b_1 - \frac{m_1 b_2}{m_2} \in C\right). + \end{align*} + So, $C$ is a subgroup of $(S, \circ)$. - Let $\phi = (\chi \diamond \psi)$, where $\chi, \psi \in \mathcal{L}$ and $\diamond \in \mathcal{C}$, and suppose the exercise is true for $\chi$ and $\psi$. A nonempty proper initial substring of $\phi$ is one of: - \begin{itemize} - \item $($ - \item $($ followed by a nonempty proper initial substring of $\chi$ - \item $(\chi$ - \item $(\chi \diamond {}$ - \item $(\chi \diamond {}$ followed by a nonempty proper initial substring of $\psi$ - \item $(\chi \diamond \psi$ - \end{itemize} - In each case we have more $($ than $)$. + Given an $(x \mapsto m x + b) \in C$, we can write $(x \mapsto m x + b) = (x \mapsto x + b) \circ (x \mapsto mx)$, so any subgroup of $(S, \circ)$ containing $A$ and $B$ must contain $C$. \end{solution} \end{exercise} -We will use a similar pattern when providing a definition that is parameterized by a formula. Implicit in this is that you can't get to the same formula in two different ways by applying those operations repeatedly. We prove that with the following theorem. +\subsection*{Homomorphisms} + +\begin{definition} + \index{homomorphism!between groups|see {group homomorphism}} + \index{isomorphism!between groups|see {group isomorphism}} + \index{group!homomorphism} + \index{group!isomorphism} + Given two groups $(G, +)$ and $(H, +)$, a \textit{group homomorphism} from $(G, +)$ to $(H, +)$ is a function $\theta : (G, +) \to (H, +)$ such that, for all $g_1, g_2 \in G$, we have $\theta(g_1 + g_2) = \theta(g_1) + \theta(g_2)$. A \textit{group isomorphism} is a group homomorphism that is also a bijection. Two groups are \textit{isomorphic} if there is a group isomorphism between them. +\end{definition} + +We will just call these \textit{homomorphisms} and \textit{isomorphisms} when it is clear from context that we mean the group kind. + +\begin{example} + The function $\theta : (\mathbb{R}, +) \to (\mathbb{R}_\pm, \cdot)$ defined by $\theta(x) = e^x$ is a homomorphism, since $e^{x + y} = e^x \cdot e^y$ for any $x, y \in \mathbb{R}$. The same function with codomain $(\mathbb{R}_+, \cdot)$ is an isomorphism. +\end{example} + +\begin{exercise} + Let $\theta : (G, +) \to (H, +)$ be a group homomorphism. Show the following: + \begin{enumerate} + \item $\theta(0) = 0$. + \item For all $g \in G$, we have $\theta(-g) = -\theta(g)$. + \item For all $g \in G$ and $z \in \mathbb{Z}$, we have $\theta(zg) = z \theta(g)$. + \end{enumerate} + \begin{solution} + \begin{enumerate} + \item $\theta(0) = \theta(0) + \theta(0) - \theta(0) = \theta(0 + 0) - \theta(0) = \theta(0) - \theta(0) = 0$. + \item $\theta(-g) = -\theta(g) + \theta(g) + \theta(-g) = -\theta(g) + \theta(g - g) = -\theta(g) + \theta(0) = -\theta(g)$. + \item We have $\theta(0g) = \theta(0) = 0 = 0\theta(g)$. For any $n > 0$, if we have $\theta((n - 1)g) = (n - 1)\theta(g)$, then we have $\theta(ng) = \theta((n - 1)g + g) = \theta((n - 1)g) + \theta(g) = (n - 1)\theta(g) + \theta(g) = n\theta(g)$. By induction, we have $\theta(zg) = z\theta(g)$ for all $z \ge 0$. If $z < 0$, then $\theta(zg) = \theta(-|z|g) = -\theta(|z|g) = -|z|\theta(g) = z\theta(g)$. + \qedhere + \end{enumerate} + \end{solution} +\end{exercise} + +\section{Factor groups, direct products and sums} +\label{group-factors-products} + +\begin{center} + \textit{Prerequisite: \cref{groups-section}} +\end{center} + +\subsection*{Factor groups} + +\begin{definition} + \index{normal!subgroup} + A subgroup $(N, +)$ of a group $(G, +)$ is called \textit{normal} in $(G, +)$ if, for all $g \in G$ and $n \in N$, we have $g + n - g \in N$. We denote this by $N \normal G$. +\end{definition} + +\begin{example} + Any subgroup of an Abelian group is normal, since $g + n - g = n$. +\end{example} + +\begin{example} + Let $(G, +)$ be any group. Let $N = \{g \in G : g + g = 0\}$. Then, $N$ is normal in $G$, since for any $g \in G$ and $n \in N$, we have $g + n - g + g + n - g = g + n + n - g = g - g = 0$, so $g + n - g \in N$. +\end{example} + +\begin{example} + Let $S$ be the set of bijections from $\mathbb{Q}$ to $\mathbb{Q}$. Let $T = \{x \mapsto qx : q \in \mathbb{Q}_\pm\}$. See that $T \subseteq S$. In particular, $(T, \circ)$ is a subgroup of $(S, \circ)$ by \cref{subgroup-test}: we certainly have $T$ nonempty, and for any $x \mapsto qx, x \mapsto rx \in T$, we have $(x \mapsto qx) \circ (x \mapsto rx)^{-1} = x \mapsto qr^{-1}x \in T$. This subgroup is not normal since for example $(x \mapsto x + 1) \circ (x \mapsto 2x) \circ (x \mapsto x + 1)^{-1} = x \mapsto 2x - 1 \not \in T$. +\end{example} \begin{theorem} - Let $\phi \in \mathcal{L}$. Then, exactly one of the following is true: - \begin{itemize} - \item $\phi \in \mathcal{L}_0$. - \item There is a $\chi \in \mathcal{L}$ with $\phi = (\lnot \chi)$. - \item There are $\chi, \psi \in \mathcal{L}$ and $\diamond \in \mathcal{C}$ with $\phi = (\chi \diamond \psi)$. - \end{itemize} - Furthermore: - \begin{itemize} - \item In the second case, there is a unique $\chi$ that works. - \item In the third case, there is a unique combination of $\chi, \psi, \diamond$ that works. - \end{itemize} + Let $(N, +) \normal (G, +)$. For each $g \in G$, let $g + N$ denote $\{g + n : n \in N\}$. Then, $\{g + N : g \in G\}$ forms a group under the operation $(g_1 + N) + (g_2 + N) = (g_1 + g_2) + N$ (and that operation is well-defined). \begin{proof} - We will show this for $\phi \in \mathcal{L}_n$ for each $n$ by induction on $n$. + First we show this new operation is well defined. Let $g_1, g_2, g_3, g_4 \in G$ with $g_1 + N = g_3 + N$ and $g_2 + N = g_4 + N$. We need to show that $(g_1 + g_2) + N = (g_3 + g_4) + N$. Let $g \in (g_1 + g_2) + N$. There is an $n \in N$ with $g = g_1 + g_2 + n = g_1 + g_2 + n - g_2 + g_2$. Since $N$ is normal in $G$, there is an $n' \in N$ with $g_2 + n - g_2 = n'$. So, $g = g_1 + n' + g_2$. Since $g_1 + N = g_3 + N$, there is an $n'' \in N$ with $g_1 + n' = g_3 + n''$. So, $g = g_3 + n'' + g_2 = g_3 + g_2 - g_2 + n'' + g_2$. Normality of $N$ in $G$ gives us an $n''' \in N$ with $-g_2 + n'' + g_2 = n'''$, so $g = g_3 + g_2 + n'''$. Finally, since $g_2 + N = g_4 + N$, there is an $n'''' \in N$ with $g_2 + n''' = g_4 + n''''$, so $g = g_3 + g_4 + n''''$, and therefore $g \in (g_3 + g_4) + N$. The same argument shows that anyone in $(g_3 + g_4) + N$ is in $(g_1 + g_2) + N$. - For the base case, let $\phi \in \mathcal{L}_0$. The first case is true, and since $\phi$ does not start with a $($, the second and third cases are not true. + Associativity is immediate. The identity is $0 + N$, and the inverse of a $g + N$ is $(-g) + N$. + \end{proof} +\end{theorem} - Now let $n > 0$ and $\phi \in \mathcal{L}_n$. There are three ways to be in $\mathcal{L}_n$: - \begin{itemize} - \item $\phi \in \mathcal{L}_{n - 1}$: apply the inductive hypothesis. - \item $\phi = (\lnot \chi)$ with $\chi \in \mathcal{L}_{n - 1}$: we are in the second case. We are not in the first case since $\phi$ is not a single symbol, and we are not in the third case since the $\chi$ of the third case would have to start with $\lnot$, which no formula does. Uniqueness of $\chi$ is immediate: if there are $\chi_1, \chi_2 \in \mathcal{L}$ with $(\lnot \chi_1)$ and $(\lnot \chi_2)$ the same string, then $\chi_1$ and $\chi_2$ are the same string. - \item $\phi = (\chi \diamond \psi)$ with $\chi, \psi \in \mathcal{L}_{n - 1}$ and $\diamond \in \mathcal{C}$: we are in the third case. We are not in the first case for same reason as before, and we are not in the second case since again $\chi$ would have to start with $\lnot$. For uniqueness, suppose we had $\chi_1, \chi_2, \psi_1, \psi_2 \in \mathcal{L}$ and $\diamond_1, \diamond_2 \in \mathcal{C}$ with $(\chi_1 \diamond_1 \psi_1)$ and $(\chi_2 \diamond_2 \psi_2)$ the same string. Then, one of $\chi_1$ and $\chi_2$ is an initial substring of the other. It cannot be a proper initial substring, because then \cref{proper-more-open} and the example after \cref{formula-induction} would contradict. Thus, $\chi_1 = \chi_2$. Then, $(\chi_1$ and $(\chi_2$ are the same string, and so ${} \diamond_1 \psi_1)$ and ${} \diamond_2 \psi_2)$ are the same string. Since $\diamond_1$ and $\diamond_2$ are both the first symbol of the same string, they are the same symbol. Then, $\psi_1)$ and $\psi_2)$ are the same string, so $\psi_1 = \psi_2$. \qedhere - \end{itemize} +\begin{definition} + \index{factor!group} + The group defined in the previous theorem is called the \textit{factor group} of $(G, +)$ modulo $N$, and is denoted $(G / N, +)$. +\end{definition} + +Note that without normality, the operation is not well defined. + +\begin{example} + Let $S$ be the set of bijections from $\mathbb{R}$ to $\mathbb{R}$ considered as a group under composition, and let $T = \{x \mapsto rx : r \in \mathbb{R}_\pm\}$. See that $T$ is a non-normal subgroup of $S$ (similar to the example above with $\mathbb{Q}$ instead of $\mathbb{R}$). + + Let $f, g, h : \mathbb{R} \to \mathbb{R}$ with \begin{gather*} + f(x) = \sqrt[3]{x^3 + 1},\\ + g(x) = \sqrt[3]{x^3 - 1},\\ + h(x) = 2x. + \end{gather*} + See that $f, g \in S$ and $h \in T$. We have \begin{gather*} + f \circ h \circ T = f \circ T,\\ + g \circ h \circ T = g \circ T; + \end{gather*} + but \begin{gather*} + (f \circ g) \circ T = (x \mapsto x) \circ T = T,\\ + (f \circ h \circ g \circ h) \circ T = (x \mapsto \sqrt[3]{64x^3 - 7}) \circ T \ne T. + \end{gather*} + So, an operation mapping $f \circ T$ and $g \circ T$ to $(f \circ g) \circ T$ for all $f, g \in S$ would not be well-defined. +\end{example} + +\begin{definition} + \index{kernel!of a group homomorphism} + Given two groups $(G, +)$ and $(H, +)$ and a homomorphism $\theta : (G, +) \to (H, +)$, we define the \textit{kernel} of $\theta$, denoted $\ker \theta$, as $\{g \in G : \theta(g) = 0\}$. +\end{definition} + +\begin{exercise} + Show that the kernel of a homomorphism is a normal subgroup of the homomorphism's domain. + \begin{solution} + Let $\theta : (G, +) \to (H, +)$ be a homomorphism. We know $\ker \theta$ is nonempty because e.g.~$0 \in \ker \theta$. If we have $x, y \in \ker \theta$, then $\theta(x - y) = \theta(x) - \theta(y) = 0 - 0 = 0$, so $x - y \in \ker \theta$. Then, \cref{subgroup-test} tells us that $\ker \theta$ is a subgroup of $G$. + + To show normality, let $g \in G$ and $k \in \ker \theta$. Then, $\theta(g + k - g) = \theta(g) + \theta(k) - \theta(g) = \theta(g) + 0 - \theta(g) = 0$, so $g + k - g \in \ker \theta$. + \end{solution} +\end{exercise} + +\begin{exercise} + Show that the image of a group under a homomorphism is a subgroup of the homomorphism's codomain. + \begin{solution} + We will use \cref{subgroup-test} again. Let $\theta : (G, +) \to (H, +)$ be a homomorphism. First, $\theta[G]$ is nonempty since e.g.~$\theta(0) = 0$ so $0 \in \theta[G]$. If $x, y \in \theta[G]$, then there are $z, w \in G$ with $\theta(z) = x$ and $\theta(w) = y$, and we get $\theta(z - w) = \theta(z) - \theta(w) = x - y$ so $x - y \in \theta[G]$. + \end{solution} +\end{exercise} + +\begin{theorem}[first isomorphism theorem for groups] + \index{first isomorphism theorem!for groups} + Let $\theta : (G, +) \to (H, +)$ be a group homomorphism. Then, $(G / {\ker \theta}, +)$ and $\theta[G]$ are isomorphic. + \begin{proof} + Let $\phi : (G / {\ker \theta}, +) \to (\theta[G], +)$ be defined by $\phi(g + \ker \theta) = \theta(g)$. To show $\phi$ is well-defined, let $g_1, g_2 \in G$ with $g_1 + \ker \theta = g_2 + \ker \theta$. Since $g_1 = g_1 + 0 \in g_1 + \ker \theta$, we also have $g_1 \in g_2 + \ker \theta$. Then, there is a $g_3 \in \ker \theta$ with $g_1 = g_2 + g_3$. Then, $\theta(g_1) = \theta(g_2 + g_3) = \theta(g_2) + \theta(g_3) = \theta(g_2)$. + + Next we will show that $\phi$ is a homomorphism. For any $x, y \in G$, we have $\phi((x + \ker \theta) + (y + \ker \theta)) = \phi((x + y) + \ker \theta) = \theta(x + y) = \theta(x) + \theta(y) = \phi(x + \ker \theta) + \phi(y + \ker \theta)$. + + Finally we need to show that $\phi$ is a bijection. For every $h \in \theta[G]$, there is a $g \in G$ with $\theta(g) = h$. Then, $\phi(g + \ker \theta) = h$, so $h$ is in the range of $\phi$. If we have $g_1, g_2$ with $\phi(g_1 + \ker \theta) = \phi(g_2 + \ker \theta)$, then $\theta(g_1) = \theta(g_2)$. In particular, that gives us $g_1 - g_2 \in \ker \theta$ and $g_2 - g_1 \in \ker \theta$, so $g_1 + \ker \theta = g_2 + \ker \theta$. \end{proof} \end{theorem} -That theorem allows us to recurse on formulae with no worries about well-definedness. By applying that theorem repeatedly, we uniquely decompose a formula into a tree. That tree must be finite, since at each non-terminal step the length strictly decreases and the length of a formula is finite. +\begin{example} + Consider the set $\mathbb{Q}^{\mathbb{Q}}$ of functions from $\mathbb{Q}$ to $\mathbb{Q}$. Define $+ : (\mathbb{Q}^{\mathbb{Q}})^2 \to \mathbb{Q}^{\mathbb{Q}}$ by $(f + g)(q) = f(q) + g(q)$. See that $(\mathbb{Q}^{\mathbb{Q}}, +)$ is a group. Let $T = \{f \in \mathbb{Q}^{\mathbb{Q}} : f(0) = 0\}$. Consider the function $\theta : (\mathbb{Q}^{\mathbb{Q}}, +) \to (\mathbb{Q}, +)$ defined by $\theta(f) = f(0)$. See that $\theta$ is a surjective homomorphism, and that $\ker \theta = T$. Then, $(T, +)$ is a normal subgroup of $(\mathbb{Q}^{\mathbb{Q}}, +)$, and the groups $(\mathbb{Q}^{\mathbb{Q}}/T, +)$ and $(\mathbb{Q}, +)$ are isomorphic by the theorem. +\end{example} + +\subsection*{Direct products} + +Let $(G, +)$ and $(H, +)$ be two groups. We can define a new group on the Cartesian product $G \times H$ with the operation $(g_1, h_1) + (g_2, h_2) = (g_1 + g_2, h_1 + h_2)$. This operation is associative since $+$ is associative in each of $(G, +)$ and $(H, +)$. The identity here is $(0, 0)$, and the inverse of $(g, h)$ is $(-g, -h)$. The following generalizes this to arbitrarily many groups. \begin{definition} - An \textit{assignment of truth values} is a function from $\mathcal{L}_0$ to $\{0, 1\}$. Given an assignment $\tau : \mathcal{L}_0 \to \{0, 1\}$, we extend $\tau$ to a $\hat{\tau} : \mathcal{L} \to \{0, 1\}$ by recursion: + \index{direct product!of groups} + Let $\Lambda$ be an index set. For each $\lambda \in \Lambda$, let $(G_\lambda, +)$ be a group. Then, we define the \textit{direct product} of $\{(G_\lambda, +)\}_{\lambda \in \Lambda}$, denoted $\bigotimes_{\lambda \in \Lambda} (G_\lambda, +)$, as the group on the Cartesian product $\prod_{\lambda \in \Lambda} G_\lambda$ with the operation $(x_\lambda)_{\lambda \in \Lambda} + (y_\lambda)_{\lambda \in \Lambda} = (x_\lambda + y_\lambda)_{\lambda \in \Lambda}$. In the case where $\Lambda$ is finite, we also denote $\bigotimes_{i = 1}^n (G_i, +)$ by $(G_1, +) \otimes (G_2, +) \otimes \cdots \otimes (G_n, +)$. +\end{definition} + +\begin{definition} + \index{canonical injection!into a direct product of groups} + Let $\{(G_\lambda, +)\}_{\lambda \in \Lambda}$ be a collection of groups. For each $\mu \in \Lambda$, we define the \textit{canonical injection} of $(G_\mu, +)$ into $\bigotimes_{\lambda \in \Lambda} (G_\lambda, +)$, denoted by $\iota_\mu$: + \begin{gather*} + \iota_\mu : (G_\mu, +) \to \bigotimes_{\lambda \in \Lambda} (G_\lambda, +),\\ + \iota_\mu(g) = \left(\begin{cases} g & \text{if } \lambda = \mu \\ 0 & \text{if } \lambda \ne \mu \end{cases}\right)_{\lambda \in \Lambda.} + \end{gather*} +\end{definition} + +Notice that each canonical injection is an injective homomorphism. + +\begin{definition} + \index{canonical projection!from a direct product of groups} + Let $\{(G_\lambda, +)\}_{\lambda \in \Lambda}$ be a collection of groups. For each $\mu \in \Lambda$, we define the \textit{canonical projection} of $\bigotimes_{\lambda \in \Lambda} (G_\lambda, +)$ onto $(G_\mu, +)$, denoted by $\pi_\mu$: + \begin{gather*} + \pi_\mu : \bigotimes_{\lambda \in \Lambda} (G_\lambda, +) \to (G_\mu, +),\\ + \pi_\mu((g_\lambda)_{\lambda \in \Lambda}) = g_\mu. + \end{gather*} +\end{definition} + +Notice that each canonical projection is a surjective homomorphism. + +\begin{exercise} + Let $\{(G_\lambda, +)\}_{\lambda \in \Lambda}$ be a collection of groups. Show that for each $\mu \in \Lambda$ we have \[ + \iota_\mu[G_\mu] \normal \bigotimes_{\lambda \in \Lambda} (G_\lambda, +). + \] + \begin{solution} + For any $n \in G_\mu$ and $(g_\lambda)_{\lambda \in \Lambda} \in \prod_{\lambda \in \Lambda} G_\lambda$, we have \[ + (g_\lambda)_{\lambda \in \Lambda} + \iota_\mu(n) - (g_\lambda)_{\lambda \in \Lambda} = \left(\begin{cases} g_\mu + n - g_\mu & \text{if } \lambda = \mu \\ g_\lambda + 0 - g_\lambda & \text{if } \lambda \ne \mu \end{cases}\right)_{\lambda \in \Lambda} = \iota_\mu(g_\mu + n - g_\mu). \qedhere + \] + \end{solution} +\end{exercise} + +\begin{exercise} + Let $(G_1, +)$ and $(G_2, +)$ be groups and consider the direct product $(G_1, +) \otimes (G_2, +)$. Show that $((G_1, +) \otimes (G_2, +)) / \iota_1[G_1]$ and $\iota_2[G_2]$ are isomorphic. + \begin{solution} + Consider the homomorphism $\iota_2 \circ \pi_2 : (G_1, +) \otimes (G_2, +) \to (G_1, +) \otimes (G_2, +)$. We can write $(\iota_2 \circ \pi_2)(g_1, g_2) = \iota_2(g_2) = (0, g_2)$. The kernel of this homomorphism is $\iota_1[G_1]$, and the range is $\iota_2[G_2]$. Apply the first isomorphism theorem to get what we want. + \end{solution} +\end{exercise} + +\section{Center and centralizers, Cauchy's theorem} +\label{cauchy-section} + +% in this section: +% center of a group +% centralizer of an element +% conjugacy classes of an element +% cauchy's theorem + +\section{Sylow's theorems} +\label{sylow-section} + +% in this section: +% sylow's theorems + +\chapter{Rings} +\label{rings-chapter} + +\section{Definitions and basic properties} +\label{rings-section} + +\begin{definition} + \index{ring} + A \textit{ring} is a set $R$ with two binary operations ${+}, {\cdot} : R^2 \to R$ satisfying the following: \begin{itemize} - \item If $\phi \in \mathcal{L}_0$, then $\hat{\tau}(\phi) = \tau(\phi)$. - \item If $\chi \in \mathcal{L}$ and $\hat{\tau}(\chi)$ has already been defined, then $\hat{\tau}((\lnot \chi)) = 1 - \hat{\tau}(\chi)$. - \item If $\chi, \psi \in \mathcal{L}$ and $\hat{\tau}(\chi)$ and $\hat{\tau}(\psi)$ have already been defined, then: - \begin{itemize} - \item $\hat{\tau}((\chi \land \psi)) = \min(\hat{\tau}(\chi), \hat{\tau}(\psi))$. - \item $\hat{\tau}((\chi \lor \psi)) = \max(\hat{\tau}(\chi), \hat{\tau}(\psi))$. - \item $\hat{\tau}((\chi \rightarrow \psi)) = \max(1 - \hat{\tau}(\chi), \hat{\tau}(\psi))$. - \item $\hat{\tau}((\chi \leftrightarrow \psi)) = 1 - \abs(\hat{\tau}(\chi) - \hat{\tau}(\psi))$. - \end{itemize} + \item Associativity of addition: for all $x, y, z \in R$, we have $(x + y) + z = x + (y + z)$. + \item Commutativity of addition: for all $x, y \in R$, we have $x + y = y + x$. + \item Existence of additive identity: there is a $0 \in R$ such that, for all $x \in R$, we have $x + 0 = x$. + \item Existence of additive inverses: for all $x \in R$, there is a $-x \in R$ such that $x + {-x} = 0$. + \item Associativity of multiplication: for all $x, y, z \in R$, we have $(x \cdot y) \cdot z = x \cdot (y \cdot z)$. + \item Left distributivity: for all $x, y, z \in R$, we have $x \cdot (y + z) = x \cdot y + x \cdot z$. + \item Right distributivity: for all $x, y, z \in R$, we have $(x + y) \cdot z = x \cdot z + y \cdot z$. \end{itemize} \end{definition} +Note that we do not require multiplication to be commutative, and we do not require the existence of a multiplicative identity or multiplicative inverses. Some sources (e.g.~\cite{wikipedia-ring}) do require the existence of a multiplicative identity, while others (e.g.~\cite{dummit-foote,gallian,maunder,mathworld-ring}) do not. + +\begin{definition} + \index{ring!with identity} + \index{nontrivial ring} + \index{trivial ring} + A ring $R$ is said to \textit{have identity} if we have the following additional property: + \begin{itemize} + \item Existence of multiplicative identity: there is a $1 \in R$ such that, for all $x \in R$, we have $x \cdot 1 = x$ and $1 \cdot x = 1$. + \end{itemize} + A ring with identity is called \textit{trivial} if $1 = 0$, and nontrivial otherwise. +\end{definition} + \begin{example} - The following table shows evaluations of $\hat{\tau}$ for different $\tau$'s: - \begin{center} - \begin{tabular}{ccc|ccc} - $\tau(P_1)$ & $\tau(P_2)$ & $\tau(P_3)$ & $\hat{\tau}((P_1 \land P_2))$ & $\hat{\tau}((\lnot P_3))$ & $\hat{\tau}(((P_1 \land P_2) \rightarrow (\lnot P_3)))$\\ - \hline - 0 & 0 & 0 & 0 & 1 & 1\\ - 0 & 0 & 1 & 0 & 0 & 1\\ - 0 & 1 & 0 & 0 & 1 & 1\\ - 0 & 1 & 1 & 0 & 0 & 1\\ - 1 & 0 & 0 & 0 & 1 & 1\\ - 1 & 0 & 1 & 0 & 0 & 1\\ - 1 & 1 & 0 & 1 & 1 & 1\\ - 1 & 1 & 1 & 1 & 0 & 0 - \end{tabular} - \end{center} + The integers form a ring with identity under the usual $+$ and $\cdot$. The even integers form a ring without identity under the same operations. The odd integers do not form a ring under the usual operations, since there is no additive identity. \end{example} -\begin{exercise} - For each of the eight rows above, find the values of: +\begin{definition} + \index{commutative ring} + A ring $R$ is called \textit{commutative} if we have the following additional property: + \begin{itemize} + \item Commutativity of multiplication: for all $x, y \in R$, we have $x \cdot y = y \cdot x$. + \end{itemize} +\end{definition} + +\begin{example} + The integers and the even integers are commutative rings, since multiplication of integers is commutative. For an example of a non-commutative ring, consider the set of $2 \times 2$ matrices with integer entries. One can verify that this forms a ring under the usual matrix addition and multiplication. This ring is not commutative: \[ + \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} + \cdot + \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} + = + \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} + \text{ but } + \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} + \cdot + \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} + = + \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}. + \] +\end{example} + +Oftentimes, we will not write $\cdot$ between members of a ring. For example, we can write the condition for a commutative ring as $xy = yx$ for all $x, y \in R$. + +Given a member $x$ of a ring $R$, we recursively define $nx$ and $x^n$ for $n \in \mathbb{Z}_+$ as follows: +\begin{gather*} + 1x = x\\ + x^1 = x\\ + nx = (n - 1)x + x \text{ for } n > 1\\ + x^n = x^{n - 1} \cdot x \text{ for } n > 1 +\end{gather*} +We further define $0x = 0$ and $(-n)x = -(nx)$ for $n \in \mathbb{Z}_+$, where the first $0$ is the integer $0$ and the second $0$ is the additive identity of the ring. + +For clarity, we only use these notations when the operations of the ring are denoted by $+$ and $\cdot$. There is no requirement that the operations of a ring be something we think of as addition and multiplication. + +We will now see some basic properties of rings. + +\begin{theorem} + Let $R$ be a ring. Then, the following are all true: \begin{enumerate} - \item $\hat{\tau}(((P_1 \land P_2) \lor (P_1 \land P_3)))$ - \item $\hat{\tau}((P_1 \rightarrow (P_2 \lor P_3)))$ - \item $\hat{\tau}((P_1 \rightarrow (P_2 \rightarrow P_1)))$ - \item $\hat{\tau}((P_1 \rightarrow (P_2 \rightarrow (P_1 \land P_2))))$ + \item For all $x \in R$, we have $0 + x = x$ and $-x + x = 0$. + \item Let $z \in R$. If $x + z = x$ for all $x \in R$, then $z = 0$. + \item Let $x, i \in R$. If $x + i = 0$, then $i = -x$. + \item Suppose $R$ has identity, and let $o \in R$. If $x \cdot o = x$ for all $x$ or $o \cdot x = x$ for all $x$, then $o = 1$. + \item Suppose $R$ has identity. Then, $R$ is trivial if and only if $R$ has exactly one element. + \item For all $x \in R$, we have $-(-x) = x$. \end{enumerate} + \begin{proof} + \begin{enumerate} + \item Just commute the addition and apply the definitions of $0$ and $-x$. + \item Let $z$ have that property. Then in particular $0 + z = 0$. But $0 + z = z$, so $z = 0$. + \item Since $x + i = 0$, we have $-x + x + i = -x$. But $-x + x + i = 0 + i = i$, so $i = -x$. + \item Let $o$ have that property. Then in particular either $1 \cdot o = 1$ or $o \cdot 1 = 1$. In either case we get $o = 1$. + \item If $R$ is trivial, then for any $x, y \in R$ we get $x = x \cdot 0 = 0 = y \cdot 0 = y$. If $R$ is not trivial, then $0$ and $1$ are two distinct elements. + \item $-x + x = x + -x = 0$, so $x = -(-x)$. + \qedhere + \end{enumerate} + \end{proof} +\end{theorem} + +\begin{definition} + \index{subring} + Given a ring $R$, a \textit{subring} of $R$ is a set $S \subseteq R$ such that $S$ forms a ring under the restrictions of the operations from $R$. +\end{definition} + +\begin{example} + The even integers are a subring of the integers. +\end{example} + +\begin{exercise} + \label{subring-test} + Let $R$ be a ring and $S \subseteq R$. Show that $S$ is a subring of $R$ if and only if all of the following conditions are satisfied: + \begin{itemize} + \item $0 \in S$. + \item For all $x, y \in S$, we have $x + -y \in S$. + \item For all $x, y \in S$, we have $x \cdot y \in S$. + \end{itemize} \begin{solution} - \begin{center} - \begin{tabular}{ccc|cccc} - $\tau(P_1)$ & $\tau(P_2)$ & $\tau(P_3)$ & (a) & (b) & (c) & (d)\\ - \hline - 0 & 0 & 0 & 0 & 1 & 1 & 1\\ - 0 & 0 & 1 & 0 & 1 & 1 & 1\\ - 0 & 1 & 0 & 0 & 1 & 1 & 1\\ - 0 & 1 & 1 & 0 & 1 & 1 & 1\\ - 1 & 0 & 0 & 0 & 0 & 1 & 1\\ - 1 & 0 & 1 & 1 & 1 & 1 & 1\\ - 1 & 1 & 0 & 1 & 1 & 1 & 1\\ - 1 & 1 & 1 & 1 & 1 & 1 & 1 - \end{tabular} - \end{center} + If $S$ is a subring of $R$, then the second and third bullets are obvious. For the first bullet, let $0_R$ denote the $0$ in $R$ and $0_S$ denote the $0$ in $S$. Then, $0_R = 0_S + -0_S \in S$ by the second bullet. In fact, $0_R = 0_S + -0_S = -0_S = 0_S$. + + Now suppose $S \subseteq R$ satisfies the three bullet points. For any $x, y \in S$, we have $-y = 0 + -y$, so $-y \in S$, and $x + y = x + -(-y)$, so $x + y \in S$. Then, $+$ and $\cdot$ have the right codomain when restricted to $S$. Associativity and commutativity of addition, associativity of multiplication, and both distributivities follow from $R$ being the corresponding property of $R$. We already know that the $0$ from $R$ is in $S$, and this acts like a $0$ in $S$. We also know that, for all $y \in S$, the $-y$ from $R$ is in $S$, and this acts like a $-y$ in $S$. \end{solution} \end{exercise} \begin{definition} - We say a formula $\phi \in \mathcal{L}$ is \textit{satisfied} by an assignment $\tau : \mathcal{L}_0 \to \{0, 1\}$ if $\hat{\tau}(\phi) = 1$. We say a formula $\phi \in \mathcal{L}$ is a \textit{tautology} if it is satisfied by every $\tau : \mathcal{L}_0 \to \{0, 1\}$, and a \textit{antilogy} if it is not satisfied by any $\tau : \mathcal{L}_0 \to \{0, 1\}$. + \index{ideal} + Given a ring $R$, an \textit{ideal} of $R$ is a set $I$ satisfying: + \begin{itemize} + \item $I$ is a subring of $R$. + \item Left closure: for all $r \in R$ and $x \in I$, we have $r \cdot x \in I$. + \item Right closure: for all $r \in R$ and $x \in I$, we have $x \cdot r \in I$. + \end{itemize} \end{definition} -\chapter{Set Theory} -\label{set-theory-chapter} +\begin{example} + The even integers are an ideal of the integers. For an example of a subring that is not an ideal, consider the $2 \times 2$ matrices of integers again. One can consider the subset of matrices where the right column is $0$. That subset will be a subring, but it will not be an ideal. +\end{example} + +\begin{definition} + \index{ring!homomorphism} + \index{ring!isomorphism} + \index{homomorphism!between rings|see {ring homomorphism}} + \index{isomorphism!between rings|see {ring isomorphism}} + Given two rings $R$ and $Q$, a \textit{ring homomorphism} from $R$ to $Q$ is a function $\theta : R \to Q$ such that, for all $r_1, r_2 \in R$, we have $\theta(r_1 + r_2) = \theta(r_1) + \theta(r_2)$, and $\theta(r_1 \cdot r_2) = \theta(r_1) \cdot \theta(r_2)$. A ring homomorphism that is also a bijection is called a \textit{ring isomorphism}. If there is a ring isomorphism between two rings, we say that those rings are \textit{isomorphic}. +\end{definition} -\chapter{Algebra} -\label{algebra-chapter} +We will sometimes just say a \textit{homomorphism} or an \textit{isomorphism} when it is clear from context that we mean the ring kind. -\chapter{Topology} -\label{topology-chapter} +\section{Direct products and sums, polynomial rings} -\chapter{Analysis, Part I} -\label{analysis-chapter} +You should read \cref{rings-section} first. -\section{Encoding of the real numbers} -\label{encoding-of-the-real-numbers-section} +% in this section: +% direct product and sum definitions +% polynomial rings as direct sums +% usc algebra qual, january 2013, #1(a) -\appendix +\chapter{Modules} -\chapter{Links to Qualifying Exam Problems} +\section{Definitions and basic properties} -\chapter{Solutions to Exercises} +You should read \cref{rings-section} first. \cref{groups-section} is referenced in some examples. + +\begin{definition} + \index{module} + \index{R-module@$R$-module|see {module}} + Given a ring $R$, an \textit{$R$-module} is a set $M$ with two binary operations $+ : M^2 \to M$ and $\cdot : R \times M \to M$ satisfying the following: + \begin{itemize} + \item Associativity of addition: for all $x, y, z \in M$, we have $(x + y) + z = x + (y + z)$. + \item Commutativity of addition: for all $x, y \in M$, we have $x + y = y + x$. + \item Existence of additive identity: there is a $0 \in M$ such that, for all $x \in M$, we have $x + 0 = x$. + \item Existence of additive inverses: for all $x \in M$, there is a $-x \in M$ such that $x + {-x} = 0$. + \item Distributivity over scalar addition: for all $x, y \in R$ and $z \in M$, we have $(x + y) \cdot z = x \cdot z + y \cdot z$. + \item Distributivity over module addition: for all $x \in R$ and $y, z \in M$, we have $x \cdot (y + z) = x \cdot y + x \cdot z$. + \item Associativity of scalar multiplication: for all $x, y \in R$ and $z \in M$, we have $(x \cdot y) \cdot z = x \cdot (y \cdot z)$. + \item Unitarity: If $R$ has identity, then for all $x \in R$ we have $1 \cdot x = x$. + \end{itemize} +\end{definition} + +This is typically (e.g.~\cite{dummit-foote}) called a \textit{left $R$-module}. One can define a similar structure with $\cdot : M \times R \to M$ and call that a \textit{right $R$-module}. Here, we never refer to right $R$-modules, so we will just call this an $R$-module. + +\begin{example} + Let $R$ be any ring and let $S$ be any set. Let $R^S$ denote the set of functions from $S$ to $R$. Define the operations as follows for any $f, g \in R^S$, $s \in S$, and $r \in R$: + \begin{gather*} + (f + g)(s) = f(s) + g(s)\\ + (r \cdot f)(s) = r \cdot f(s) + \end{gather*} + Then, $R^S$ forms an $R$-module with those operations. In particular, if $S$ is a finite set, then $R^S$ can be thought of as the length $|S|$ vectors with entries in $R$, and the operations are componentwise addition and scalar multiplication. +\end{example} + +\begin{example} + Any Abelian group (see \cref{groups-section}) is a $\mathbb{Z}$-module. The addition in the module is just the operation in the group, and the scalar multiplication is repeated addition (i.e.~$4 \cdot x = x + x + x + x$). +\end{example} + +\begin{example} + Any ideal of a ring is a module over that ring, with the operations inherited from the ring. +\end{example} + +\appendix + +\chapter{Solutions} \label{solutions-chapter} +\clearpage \solutions +\chapter{List of Qualifying Exam Problems} + +\section{University of South Carolina, Algebra} + +\begin{tabular}{ll} + \multicolumn{2}{c}{\textbf{January 2013}}\\[0.5\topsep] +\end{tabular} + +\backmatter + +\printindex + +\printbibliography[heading=bibintoc] \end{document} |