114 Theorems

From Mathsoc wiki

This page is far from complete! Can you help by adding anything to it (such as notes or links to useful sites)?

The following is a (wholly incomplete) list of theorems and questions that have come in the past few years in Donal O'Donovan's 114 exams. Many of these theorems can be found in Modern Algebra: An Introduction by John R. Durbin.

1 Mappings and Functions
- 1.1 A function has a left inverse if and only if it is one to one
- 1.2 A function has a right inverse if and only if it is onto
2 Groups
3 Equivalence and Congruence
4 More on Groups
5 Rings

[edit]

Mappings and Functions

[edit]

A function $f$ has a left inverse if and only if it is one to one

Let $f : S\rightarrow T$ have a left inverse, denoted $g : T\rightarrow S$ , and let $f(x_1) = f(x_2)$ for some $x_1, x_2\in S$ . Applying $g$ to both sides, we get $g(f(x_1)) = g(f(x_2))$ , which implies that $x_1 = x_2$ , as $g$ is a left inverse for $f$ .

Let $f : S\rightarrow T$ be a one to one mapping. Define $g : T\rightarrow S$ as follows: if there exists a $x\in S$ such that $f(x) = y$ , for some $y\in T$ , then let $g(y) = x$ . If there does not exists a $x\in S$ such that $f(x) = y$ , for some $y\in T$ , then map that $y$ to any point in S, say $x_0$ . As $f$ is one to one, the mapping $g$ is well defined. Thus, $g$ is a left inverse for $f$ .

[edit]

A function $f$ has a right inverse if and only if it is onto

[edit]

Groups

[edit]

Given any group, the identity and all inverses are unique

Let $e$ and $f$ be two identities for a group $(G, *)$ . By definition of an identity, $a*e = e*a = a$ and $a*f = f*a = a$ for all $a\in G$ . However, $f*e = f$ , as $e$ is an identity, and $f*e = e$ , as $f$ is an identity. Thus $e = f$ .

Let $a$ be an element of a group $G$ , and let $b$ and $c$ be inverses for $a$ . Thus, $b = b*e = b*(a*c) = (b*a)*c = e*c = c$ . Thus, $b = c$ .

[edit]

If $x^2 = e$ for all elements in a group $G$ , then $G$ is Abelian

Let $(G,*)$ be a group. We know that $x*x = e$ for all $x\in G$ . Thus, applying $x^{-1}$ to both sides, we get $x = x^{-1}$ . As $G$ is a group, as know that if $a,b\in G$ , then $a*b\in G$ , and also that $(a*b)^{-1}\in G$ . However $a*b = (a*b)^{-1} = (b^{-1}*a^{-1}) = b*a$ . Thus, as $a*b = b*a$ , $G$ is commutative, or Abelian.

[edit]

Any Permutation on a finite set can be written as a product of disjoint cycles

Let $\sigma$ be some permutation on a finite set $S$ , and denote $(\sigma\circ\sigma)(a)$ by $\sigma^{(2)}(a)$ . Picking any element in $S$ , say $x$ , we consider the set $S_x = \left \lbrace x, \sigma(x), \sigma^{(2)}(x), \sigma^{(3)}(x), \dots, \sigma^{(n)}(x), x \right \rbrace$ . As the set $S$ is finite, we know that $S_x$ must also be finite.

Now, we consider the element $y\in S$ such that $y\notin S_x$ , and the set $S_y = \left \lbrace y, \sigma(y), \sigma^{(2)}(y), \sigma^{(3)}(y), \dots, \sigma^{(m)}(y), y \right \rbrace$ . Again, as $S$ is finite, $S_y$ must be finite. Also, we know that $S_x$ and $S_y$ have no elements in common, because if they did, we would have $\sigma^{(k)}(y) = x$ for some k, which implies that $y\in S_x$ . Thus, the sets are disjoint.

We continue in this way, picking elements that we have not already chosen. As $S$ is finite, this process must finish. The sets we have made are now disjoint, and represent cycles of the permutation $\sigma$ .

[edit]

Equivalence and Congruence

[edit]

Isomorphism between Groups is an Equivalence Relation

We are asked to prove that the relation $G_1\sim G_2$ meaning $G_1\cong G_2$ is an equivalence relation.

Reflexive: Consider the bijective identity mapping $\iota (a) = a$ , for $a\in G_1$ . This mapping is clearly both one to one and onto. Note that $\iota(ab) = ab = \iota(a)\iota(b)$ , which implies that the operation is preserved. Thus, $G_1\cong G_1$ , and $G_1\sim G_1$ .

Symmetric: Let $G_1\sim G_2$ . This means that $G_1\cong G_2$ , or that there exists a bijective mapping $\theta : G_1\rightarrow G_2$ such that $\theta (ab) = \theta (a)\theta(b)$ for all $a,b\in G_1$ . By theorem, every bijective mapping has an inverse, which is also bijective. Denote the inverse of $\theta$ by $\phi$ . Let $a,b\in G_1$ , and let $\phi(a) = x$ and $\phi(b) = y$ . Thus, $ab = \theta(x)\theta(y) = \theta(xy)$ , as $\theta$ is an isomorphism. This implies that $\phi(ab) = xy = \phi(a)\phi(b)$ . Thus, $G_2\cong G_1$ , and $G_2\sim G_1$ .

Transitive: Let $G_1\sim G_2$ and $G_2\sim G_3$ . Thus, there are isomorphisms $\theta: G_1 \rightarrow G_2$ , and $\phi:G_2\rightarrow G_3$ . Define $\psi = \phi\circ\theta$ . We wish to show that this is an isomorphism. Let $a,b\in G_1$ and denote $\theta(a) = x$ and $\theta(b) = y$ . Thus $\theta(ab) = \theta(a)\theta(b) = xy$ because $\theta$ is an isomorphism. Also $\phi(xy) = \phi(x)\phi(y)$ as $\phi$ is an isomorphism. Thus:

	$\psi(ab)$	$= \phi(\theta(ab))$
		$= \phi(xy)$
		$= \phi(x)\phi(y)$
		$= \phi(\theta(a)) \phi(\theta(b))$
		$= \psi(a)\psi(b)$

Thus, $G_1\cong G_3$ , and $G_1\sim G_3$ .

[edit]

Given an Equivalence Relation \sim on a set S, the set of Equivalence Classes form a Partition of S

Let $\sim$ be an equivalence relation on $S$ . If $a\in S$ , then $a\in [a]$ at least, as the relation is reflexive ( $a\sim a$ ). Thus, the union of all equivalence classes must be $S$ .

Now, we must show that all equivalence classes are either disjoint or equal. Consider the two equivalence classes $[a]$ and $[b]$ , where $[a]\cap[b]\neq\emptyset$ . Let $c$ be an element of $S$ such that $c\in[a]\cap[b]$ . If $x$ is any element in $[a]$ , we know that $a\sim x$ and $a\sim c$ , or $c\sim a$ , as the relation is symmetric. Thus, $c\sim x$ , as the relation is transitive. However, $b\sim c$ also, as $c\in [b]$ . Thus, $b\sim x$ , or $x\in [b]$ . In other words, all elements in $[a]$ are in $[b]$ , or $[a]\subseteq[b]$ . We can use the same argument on $[b]$ to show that $[b]\subseteq[a]$ . Thus, $[a] = [b]$ .

[edit]

The Division Algorithm

If $a$ and $b$ are integers with $b>0$ , there exists unique integers $q$ and $r$ such that $a = bq+r$ , with $0\leq r < b$ .

The Existence of $q$ and $r$ :Consider the set $S = \left\lbrace a-bt\;:\; t\in\mathbb{Z} \right\rbrace$ and let $S^\prime$ denote all the non-negative elements of $S$ We must show that $S^\prime$ is non-empty.

If $a \geq 0$ , then for $t = 0$ , we get $a - b\cdot 0 = a \geq 0$ which is an element of $S^\prime$ .
If $a<0$ , then for $t = a$ , we get $a - ba = a(1-b)$ which is positive as $b>0$ .

Thus, by the law of Trichotomy, $S^\prime$ is a non-empty set. Thus, as this set consists of positive elements, it must contain a least element, by the Least Integer Principle. Denote the least element by $r$ , and denote it's corresponding value of $t$ by $q$ . Thus, the integers $q$ and $r$ exist.

The Remainder Term $0\leq r < b$ : By choice of $S^\prime$ , $0\leq r$ , so it suffices to prove that $r<b$ . Assume the contrary, that $r\geq b$ . Consider the integer $a-b(q+1) = a-bq - b = r-b \geq 0$ as $r\geq b$ . Therefore, as it is non-negative, $a-b(q+1)\in S^\prime$ . But $a-b(q+1) = r - b < r$ . This contradicts the choice of $r$ as the lest element of $S^\prime$ . Thus, out original assumption that $r\geq b$ must be false. Therefore, $0\leq r < b$ .

The Uniquenss of $q$ and $r$ : Assume the contrary, that there exists integers $q^\prime$ and $r^\prime$ such that $a = bq^\prime + r^\prime$ with $0\leq r^\prime < b$ . Thus, $bq + r = bq^\prime + r^\prime$ and $b(q - q^\prime) = r - r^\prime$ . This implies that $b | (r - r^\prime)$ . But $0\leq r < b$ and $0\leq r^\prime < b$ , implying that $-b < r - r^\prime < b$ . As the only multiple of $b$ in this interval is $0$ , $r - r^\prime = 0$ and, as $b\neq 0$ , $q - q^\prime = 0$ .

[edit]

The Greatest Common Divisor

First, we shall prove the existence of such an integer, then that it is the largest such, and finally that it is unique. Note that this method in known as Euclid's Algorithm.

The Existence of $d$ : Consider the case that $b > 0$ . Apply the Division Algorithm, we get $a = bq_1 + r_1, 0\leq r_1 < b$ . Repeatedly applying the Division Algorithm, we get the following:

$b = r_1q_2 + r_2$		$0\leq r_2 < r_1$
$r_1 = r_2q_3 + r_3$		$0\leq r_3 < r_2$
$r_2 = r_3q_4 + r_4$		$0\leq r_4 < r_3$
	$\vdots$

As $r_1 > r_2 > r_3 \dots$ , and all these integer terms are greater than or equal to zero, we must eventually reach a remainder term that is equal to zero. Thus, for some $k$ :

$r_{k-2} = r_{k-1}q_k + r_k$	$0\leq r_k < r_{k-1}$
$r_{k-1} = r_kq_{k+1}$	$r_{k+1} = 0$

By the last line, $r_k \mid r_{k-1}$ . This implies that $r_k \mid r_{k-2}$ , $r_k \mid r_{k-3}$ , etc. Working our way upwards to the top, we see that $r_k \mid a$ and $r_k \mid b$ , as required.

The Largest such Integer: Let there exist an integer $c$ such that $c\mid a$ and $c\mid b$ . Thus, $c\mid r_1$ , as $r_1 = a - bq_1$ . Similarly, $c\mid r_2$ , as $r_2 = b - r_1q_2$ . Continuing like this, we eventually reach $c\mid r_{k-1}$ and $c\mid r_k$ , as required.

Note: If $b<0$ , we repeat the above, but using $-b$ instead of $b$ . Also, if $b=0$ , then $|a|$ suffices as the greatest common divisor.

Uniqueness of the Greatest Common Divisor: Denote the above divisor by $d$ . Let there exist another integer $d^\prime$ with the same properties. As $d$ is a greatest common divisor, $d^\prime\mid a$ , and $d^\prime \mid b$ , we have $d^\prime \mid d$ . Similarly, as $d^\prime$ is also a greatest common divisor, we have $d\mid d^\prime$ . As $d$ and $d^\prime$ are both positive integers, $d = d^\prime$ .

[edit]

The Fundamental Theorem of Arithmetic

All integers greater than 1 can be written as a product of prime powers and, except for the order in which this product is written, this factorisation is unique.

Lemma 1: If $a,b$ and $c$ are integers, with $\gcd(a,b) = 1$ and $a\mid bc$ , then $a\mid c$ .

Proof: There exist integers $m,n$ such that $am+bn = 1$ . Multiplying by $c$ , we get $c = amc+bnc$ . It is true that $a\mid amc$ . $As a\mid bc$ , is is true that $a\mid nbc$ . Thus $a\mid amc+bnc$ , or $a\mid c$ .

Lemma 2: If $p$ is a prime, and $p\mid a_1a_2\cdots a_n$ for integers $a_1,a_2,\dots a_n$ , then $p\mid a_i$ for some $i$ .

Proof: We shall prove this using induction on $n$ . The case for $n = 1$ is simple. Assume that $n>1$ . If $p\mid a_1a_2\cdots p_n$ , then $p\mid a_i$ for some $1\leq i\leq n$ . If $p\nmid a_1a_2\cdots a_n$ , then $\gcd(p,a_1,a_2,\dots , a_n) = 1$ , as p is prime. Thus, by Lemma 1 above, $p\mid a_{n+1}$ .

Factorisation: Let $S$ denote the set of all integers that cannot be factorised in such a way. This set is positive, as all elements are greater than 1. By the Least Integer Principle, this set contains a least element, denote it $n$ . $S$ contains no primes, and $1\neq S$ , by definition of $S$ . Thus $n$ can be factorised as $n = k_1k_2$ , where $k_1,k_2 \in \mathbb{N}$ . As $k_1$ and $k_2$ are positive integers, it is true that $1\leq k_1 < n$ and $1\leq k_2 < n$ . As $n$ is the least element of $S$ , $k_1,k_2\neq S$ . Thus, $k_1$ and $k_2$ can be written as a product of prime powers. However, as $n = k_1k_2$ , this implies that n can be written as a product of prime powers. Thus, $S = \emptyset$ .

Uniqueness of Prime Factorisation: For an integer $m$ , assume that $m = p_1p_2\cdots p_s = q_1q_2\cdots q_t$ , where $p_i$ and $q_j$ are primes for $1\leq i\leq s$ and $1\leq j\leq t$ . As $p_1\mid p_1p_2\cdots p_s$ , it is true that $p_1\mid q_1q_2\cdots q_t$ , and by Lemma 2 above $p_1\mid q_j$ for some $1\leq j\leq t$ . As $p_1$ and $q_j$ are prime, this implies that $p_1 = q_j$ . Thus $p_2p_3\cdots p_s = q_1q_2\cdots q_{j-1}q_{j+1}\cdots q_t$ . Continuing in this way, we can pair all of the primes on the left with one on the right. However, if we cancel all the primes on the left side of the equation, this would imply that 1 is equal to the product of primes, a contradiction. Thus, these two products must be equal, except possibly for the order in which they are written.

[edit]

More on Groups

[edit]

The Direct Product of two Groups is also a Group

Let (G, *) and $(H, \sharp)$ be two groups. The direct product of $G$ and $H$ is defined as $G\times H = \left \lbrace (g,h)\;:\;g\in G, h\in H \right \rbrace$ . We define the following operation on $G\times H$ : $(g_1, h_1)\star(g_2, h_2)$ = $(g_1* g_1, h_2\sharp h_2)$ . We must now verify the three properties of a Group.

Associative: Let $(g_1, h_1),(g_2, h_2),(g_3, h_3)\in G\times H$ . Note the following:

$(g_1,h_1)\star[(g_2,h_2)\star(g_3h_3)]$	$= (g_1,h_1)\star(g_2* g_3,h_2\sharp h_2)$
	$=(g_1* g_2* g_3, h_1\sharp h_2\sharp h_3)$
	$=((g_1* g_2*) g_3, (h_1\sharp h_2\sharp) h_3)$
	$=(g_1* g_2, h_1\sharp h_2)\star(g_3, h_3)$
	$=\left[ (g_1,h_1)\star(g_2,h_2)\right] \star(g_3,h_3)$

Thus, the operation is associative.

Identity: The identity for this operation is $(e_G, e_H)$ , where $e_G$ is the identiy in $G$ , and $e_H$ is the identity in $H$ . We check this by noting that $(g,h)\star(e_G, e_H) = (g* e_G, h\sharp e_H) = (g,h)$ and $(e_G, e_H)\star (g,h) = (e_G* g, e_H\sharp h) = (g,h)$ .

Inverses: The Inverse for an element $(g,h)$ is given by $(g^{-1}, h^{-1})$ . We check this by noting that:

$(g,h)\star(g^{-1}, h^{-1})$		$= (g* g^{-1}, h\sharp h^{-1})$
		$= (e_G, e_H)$
	and
$(g^{-1}, h^{-1})\star (g,h)$		$= (g^{-1}* g, h^{-1}\sharp h)$
		$= (e_G, e_H)$

[edit]

Lagrange's Theorem: The order of a Subgroup divides the order of the Group

Let $H$ be a subgroup of $G$ . We'll prove Lagrange's Theorem from the beginning.

Cosets: Let $a\sim b$ mean that $ab^{-1}\in H$ . This relation is an equivalence relation (check), as it is symmetric, reflexive and transitive. We note that the equivalence class of the element $a\in G$ can be represented as $[a] = Ha = \left \lbrace ha\;:\;h\in H \right \rbrace$ , called a right coset.

Lemma: We now must show that $|H| = |Ha|$ , for any element $a\in G$ . We do this by showing that there is a mapping between $H$ and $Ha$ that is both one to one and onto. Consider $\theta : H\rightarrow Ha$ given by $\theta(h) = ha$ . Assume that $\theta(h_1) = \theta(h_2)$ . Thus implies that $h_1a = h_2a$ , and applying $a^{-1}$ to both sides gives $h_1 = h_2$ . Thus, $\theta$ is one to one. Given any $ha$ , we can always find an element of $H$ that gets mapped to $ha$ , namely $\theta(h) = ha$ . Thus, $\theta$ is also onto. Therefore, there exists a mapping between $H$ and $Ha$ that is one to one and onto, meaning that $|H|=|Ha|$ .

Lagrange's Theorem: We know that the equivalence classes form a partition of the set. Thus, the cosets form a partition of the group $G$ . Therefore $Ha_1\cup Ha_2\cup\cdots\cup Ha_n = G$ . We also know that each equivalence class (coset) is disjoint, that they have no elements in common. Therefore, $|G| = |Ha_1\cup Ha_2\cup\dots\cup Ha_n| = |Ha_1|+|Ha_2|+\dots+|Ha_n|$ . But by lemma, all these cosets have the same order, namely $|Ha_i| = |H|$ . Thus, The above simplifies to $|G| = n|H|$ , where $n$ is the number of cosets of $H$ in $G$ .

[edit]

Given two groups $G$ and $H$ , $G\times H \cong H\times G$

Let $(G,*)$ and $(H,\sharp)$ be groups. We know that $G\times H$ and $H\times G$ are also groups. We need to show that there exists a bijective mapping between $G\times H$ and $H\times G$ that preserves the operation. Define $\theta : G\times H \rightarrow H\times G$ by $\theta((g_1, h_1)) = (h_1, g_1)$ .

One to one: Let $\theta((g_1, h_1)) = \theta((g_2, h_2))$ . By \theta, this gives $(h_1, g_1)=(h_2, g_2)$ , or that $g_1 = g_2$ and $h_1 = h_2$ . Thus, $(g_1, h_1)=(g_2, h_2)$ . Thus, $\theta$ is one to one.

Onto: Given any $(h,g)\in H\times G$ , we know that $\theta((g,h)) = (h,g)$ . Thus, $\theta$ is onto.

The operation: We wish to show that $\theta((g_1, h_1)(g_2, h_2)) = \theta((g_1, h_1))\theta((g_2, h_2))$ . We know that:

$\theta((g_1, h_1)(g_2, h_2))$	$= \theta((g_1* g_2, h_1\sharp h_2))$
	$= (h_1\sharp h_2, g_1*g_2)$
	$= (h_1, g_1)(h_2, g_2)$
	$= \theta((g_1, h_1))\theta((g_2, h_2))$

[edit]

Quotient Groups

Given a normal subgroup $N$ of the group $G$ , we wish to show that the cosets of $N$ in $G$ form a group. Let $G/N$ denote the set of all cosets of $N$ in $G$ . Define the operation on $G/N$ : for all $Na, Nb\in G/N$ , let $(Na)(Nb) = Nab$ .

Well Defined: We must check that this operation is well defined. Let $Na_1 = Na_2$ , and $Nb_1 = Nb_2$ , where $a_1,a_2,b_1,b_2\in G$ . We must show that $(Na_1b_1)= (Na_2b_2)$ . By definition of cosets, we know that $Na_1 = Na_2$ implies that there exists some $n_1\in N$ such that $a_1 = n_1a_2$ . Similarly, $b_1 = n_2b_2$ . Bringing these two equations together gives $a_1b_1 = n_1a_2n_2b_2$ . From our definition of a normal group, we know that $gng^{-1}\in N$ for all $g\in G$ and $n\in N$ . Thus, we know that $a_2n_2a_2^{-1}\in N$ . This implies that there exists a $n_3\in N$ such that $a_2n_2a_2^{-1} = n_3$ , or that $a_2n_2 = n_3a_2$ . Thus, returning to the above, we get $a_1b_1 = n_1(a_2n_2)b_2 = n_1n_3a_2b_2$ . Again, by our definition of cosets, this implies that $Na_1b_1 = Na_2b_2$ .

Associativity: Let $Na,Nb,Nc\in G/N$ . Under our operation, we get:

$(Na)((Nb)(Nc))$	$= (Na)(Nbc)$
	$= Nabc$
	$= (Nab)(Nc)$
	$= ((Na)(Nb))(Nc)$

Thus, our operation is associative.

The Identity Element: Let $Ne$ be the identity element of $G/N$ , where $e$ is the identity element for $G$ . Thus, $(Na)(Ne)=Nae=Na$ and $(Ne)(Na) = Nea = Na$ . Thus, $Ne$ is the identity element.

Inverses: Let inverses in $G/N$ be defined as $(Na)^{-1} = Na^{-1}$ . Thus, $(Na)(Na^{-1}) = Naa^{-1} = Ne$ and $(Na^{-1})(Na) = Na^{-1}a = Ne$ . Thus, these inverses hold.

[edit]

Given any groups $G$ and $H$ and a homomorphism $\theta : G\rightarrow H$

$\ker\theta\triangleleft G$
$\theta(G)<H$
$G/\ker\theta\cong\theta(G)$

Part one - $\ker\theta\triangleleft G$ : We know that $\ker\theta = \left \lbrace g\in G\;:\;\theta(g) = e_H \right \rbrace$ , where $e_H$ is the identity in $H$ . We wish to show that $gng^{-1}\in\ker\theta$ , for all $g\in G$ and $n\in\ker\theta$ . Consider $\theta(gng^{-1})$ , where $g\in G$ and $n\in\ker\theta$ . As $\theta$ is a homomorphism, we know that $\theta(gng^{-1}) = \theta(g)\theta(n)\theta(g^{-1})$ . However, we know that $\theta(n)=e_H \mathrm{\;as\;} n\in\ker\theta$ . Also, we know that $\theta(g^{-1}) = \theta(g)^{-1}$ , as \theta is a homomorphism. Thus, $\theta(gng^{-1}) = \theta(g)\theta(n)\theta(g^{-1}) = \theta(g)e_H\theta(g)^{-1} = e_H$ . Thus, $\theta(gng^{-1})\in\ker\theta$ , or that $\ker\theta\triangleleft G$ .

Part two - $\theta(G)<H$ : To show that $\theta(G)$ is a subgroup of $H$ , we need to show that $\theta(G)\neq\emptyset$ , inverses exist in $\theta(G)<H$ and that $\theta(G)<H$ is closed under the operation. We know that $\theta(e_G) = (e_H)$ , and thus $\theta(G)\neq\emptyset$ . If we let $\theta(g)^{-1} = \theta(g^{-1})$ , we can see that inverses exist. Finally, we note that as $\theta$ is a homomorphism, that $\theta(a)\theta(b) = \theta(ab)\in\theta G$ , for all $a,b\in G$ .

Part Three - $G/\ker\theta\cong\theta(G)$ : Let $\ker\theta = N$ for convenience, and consider the mapping $\phi : G/N\rightarrow\theta(G)$ defined as $\phi(Na) = \theta(a)$ . We must show that this mapping is bijective and that it preserves the operation. Letting $\phi(Na_1) = \phi(Na_2)$ , we get $\theta(a_1) = \theta(a_2)$ , thus $\phi$ is one to one. Given any $\theta(a)$ , we note that $\phi(Na) = \theta(a)$ , and so $\phi$ is onto. Finally, we must show that $\phi$ preserves the operation. Consider $\phi((Na)(Nb)) = \phi(Nab) = \theta(ab) = \theta(a)\theta(b) = \phi(Na)\phi(Nb)$ , as $\theta$ is a homomorphism.

[edit]

Cayley's Theorem: Every groups is isomorphic to a permutation group on its set of elements:

Let $G$ be a group. Given $a\in G$ , define $\lambda_a : G\rightarrow$ G by $\lambda_a(x)=ax$ , for all $x\in G$ . This mapping is clearly one to one and onto and thus $\lambda_a \in \mathrm{Sym}(G)$ where $\mathrm{Sym}(G)$ is the set of all bijective mappings from $G$ to $G$ . Now, consider the mapping $\theta : G\rightarrow \mathrm{Sym}(G)$ by $\theta(a) = \lambda_a$ for all $a\in G$ . We will show that $\theta$ is bijective and that it preserves the operation.

One to one: Let $\theta(a) = \theta(b)$ . This means that $\lambda_a(x) = \lambda_b(x)$ for all $x\in G$ . Letting $x = e$ , where $e$ is the identity in $G$ , we get $\lambda_a(e) = \lambda_b(e)$ , or $ae=be$ which implies that $a=b$ . Thus, $\theta$ is one to one.

Onto: Given any $\lambda_a$ with $a\in G$ , we note that $\theta(a) = \lambda_a$ , and thus $\theta$ is also onto.

The Operation: Remember that composition is the operation on $\mathrm{Sym}(G)$ . Note that for all $a,b,x\in G$ , $\theta(ab) = \lambda_{ab}(x) = abx = a(bx) = a(\lambda_b(x)) = \lambda_a(\lambda_b(x)) = (\lambda_a\circ\lambda_b)(x) = \theta(a)\circ\theta(b)$ . Thus, the operation is preserved.

[edit]

Rings

[edit]

The Direct product of any two Rings is also a Ring

Let $R$ and $S$ be rings. We note that from our work on groups that $R\times S$ is a group under the addition operation. It is easily shown that $R\times S$ is also Abelian. Thus, we need only prove that the distributive laws hold, and that multiplication is associative. Note that we define ( $a,b)(c,d) = (ac,bd)$ for all $(a,b),(c,d)\in R\times S$ .

The Distributive Laws: Let $(r_1, s_1), (r_2, s_2), (r_3, s_3)\in R\times S$ . Thus:

$(r_1,s_1)(r_2+r_3, s_2+s_3)$	$= (r_1(r_2+r_2), s_1(s_2+s_3))$
	$= (r_1r_2+r_1r_3, s_1s_2+s_1s_3)$
	$= (r_1r_2,s_1s_2)+(r_1r_3, s_1s_3)$
	$= (r_1,s_1)(r_2,s_2)+(r_1,s_1)(r_3,s_3)$

The same is true for the other distributive law.

Associativity of Multiplication: Let $(r_1, s_1), (r_2, s_2), (r_3, s_3)\in R\times S$ . Note the following:

$(r_1,s_1)[(r_2,s_2)(r_3s_3)]$	$= (r_1,s_1)(r_2 r_3,s_2 s_2)$
	$=(r_1 r_2 r_3, s_1 s_2 s_3)$
	$=((r_1 r_2) r_3, (s_1 s_2) s_3)$
	$=(r_1 r_2, s_1 s_2)(r_3, s_3)$
	$=\left[ (r_1,s_1)(r_2,s_2)\right] (r_3,s_3)$

[edit]

Given two rings $R$ and $S$ , $R\times S \cong S\times R$

Let $R$ and $S$ be rings. We know that $R\times S$ and $S\times R$ are also rings. We need to show that there exists a bijective mapping between $R\times S$ and $R\times S$ that preserves the operations. Define $\theta : R\times S \rightarrow S\times R$ by $\theta((r_1, s_1)) = (s_1, r_1)$ .

One to one: Let $\theta((r_1, s_1)) = \theta((r_2, s_2))$ . By $\theta$ , this gives ( $s_1, r_1)=(s_2, r_2)$ , or that $r_1 = r_2$ and $s_1 = s_2$ . Thus, $(r_1, s_1)=(r_2, s_2)$ . Thus, $\theta$ is one to one.

Onto: Given any $(s,r)\in S\times R$ , we know that $\theta((r,s)) = (s,r)$ . Thus, $\theta$ is onto.

The operations: To show that the operations are preserved, we wish to show that $\theta((r_1, s_1)+(r_2, s_2)) = \theta((r_1, s_1))+\theta((r_2, s_2))$ and $\theta((r_1, s_1)(r_2, s_2)) = \theta((r_1, s_1))\theta((r_2, s_2))$ . However, we know from our works on groups that both of these must be true.

[edit]

Quotient Rings

Given an Ideal $I$ of the ring $R$ , we wish to show that the cosets of $I$ in $R$ form a ring. Let $R/I$ denote the set of all cosets of $I$ in $R$ , under the operation addition. Define the operations on $R/I$ : for all $(I+a), (I+b)\in R/I$ , let $(I+a)+(I+b) = (I+(a+b))$ and $(I+a)(I+b) = (I+(ab))$ .

Well Defined: From our work on groups, we know that the operation of addition holds. Thus, we need only check properties involving multiplication. We must check that multiplication is well defined. Let $(I+a_1) = (I+a_2)$ , and $(I+b_1) = (I+b_2)$ , where $a_1,a_2,b_1,b_2\in R$ . We must show that $(I+a_1b_1)= (I+a_2b_2)$ . By definition of cosets, we know that $(I+a_1) = (I+a_2)$ implies that there exists some $n_1\in I$ such that $a_1 = n_1+a_2$ . Similarly, $b_1 = n_2+b_2$ . Bringing these two equations together gives

$a_1b_1$	$= (n_1+a_2)(n_2+b_2)$
	$= n_1n_2+n_1b_2+a_2n_2+a_2b_2$

From our definition of an ideal, we know that $ar\in I$ and $ra\in I$ for all $r\in R$ and $a\in I$ . Thus, we know that $n_1n_2,n_1b_2,a_2n_2 \in I$ . This implies that there exists some $n_3\in I$ such that $n_1n_2+n_1b_2+a_2n_2 = n_3$ . Thus, returning to the above, we get $a_1b_1 = n_1n_2+n_1b_2+a_2n_2+a_2b_2 = n_3+a_2b_2$ . Again, by our definition of cosets, this implies that $(I+a_1b_1) = (I+a_2b_2)$ .

Associative: Let $(I+a),(I+b),(I+c)\in R/I$ . Under our operation, we get:

$(I+a)((I+b)(I+c))$	$= (I+a)(I+(ab))$
	$= (I+abc)$
	$= (I+ab)(I+c)$
	$= ((I+a)(I+b))(I+c)$

Thus, our operation is associative.

The Distributive Laws: Let $(I+a),(I+b),(I+c)\in R/I$ . Thus,

$(I+a)[(I+b)+(I+c)]$	$=(I+a)[(I+(b+c))]$
	$= (I+a(b+c))$
	$= (I+(ab+ac))$
	$= (I+ab)+(I+ac)$
	$= (I+a)(I+b)+(I+a)(I+c)$

The other distributive law is similar.

[edit]

Given any rings $R$ and $S$ and a homomorphism $\theta : R\rightarrow S$

$\ker\theta \mathrm{\;is\;an\;ideal\;of\;} R$
$\theta(R)<S$
$R/\ker\theta\cong\theta(R)$

Part one - $\ker\theta$ is an ideal of $R$ : We know that $\ker\theta = \left \lbrace r\in R\;:\;\theta(r) = 0_S \right \rbrace$ , where $0_S$ is the zero in $S$ . We already know from our work on groups that $\ker\theta$ is a subgroup of the additive group of $R$ . Thus, we note that $\theta(ar) = \theta(a)\theta(r) = 0\theta(r) = 0$ and $\theta(ra) = \theta(r)\theta(a) = \theta(r)0 = 0$ . Thus, $\ker\theta$ is an ideal of $R$ .

Part two - $\theta(R)<S$ : As we know that $\theta(R)$ is a subgroup of $S$ , we need only show that $\theta(R)$ is closed with respect to multiplication. Let $r_1, r_2\in R$ . Thus, $\theta(r_1r_2) = \theta(r_1)\theta(r_2)\in\theta(R)$ . Thus, $\theta(R)$ is closed with respect to multiplication.

Part Three - $R/\ker\theta\cong\theta(R)$ : Let $\ker\theta = N$ for convenience, and consider the mapping $\phi : R/I\rightarrow\theta(R)$ defined as $\phi(I+a) = \theta(a)$ . We must show that this mapping is bijective and that it preserves the operation. Letting $\phi(I+a) = \phi(I+b)$ , we get $\theta(a) = \theta(b)$ , thus $\phi$ is one to one. Given any $\theta(a)$ , we note that $\phi(I+a) = \theta(a)$ , and so $\phi$ is onto. Finally, we must show that $\phi$ preserves the operations. We know from group theory that addition is preserved. Thus, consider

$\phi((I+a)(I+b)) = \phi(I+(ab)) = \theta(ab) = \theta(a)\theta(b) = \phi(I+a)\phi(I+b)$ , as $\theta$ is a homomorphism.

Retrieved from "http://www.maths.tcd.ie/~mathsoc/wiki/114_Theorems"

Categories: Stub | Group I courses | Mathematics courses

114 Theorems

From Mathsoc wiki

Contents

Mappings and Functions

A function $f$ has a left inverse if and only if it is one to one

A function $f$ has a right inverse if and only if it is onto

Groups

Given any group, the identity and all inverses are unique

If $x^2 = e$ for all elements in a group $G$ , then $G$ is Abelian

Any Permutation on a finite set can be written as a product of disjoint cycles

Equivalence and Congruence

Isomorphism between Groups is an Equivalence Relation

Given an Equivalence Relation \sim on a set S, the set of Equivalence Classes form a Partition of S

The Division Algorithm

The Greatest Common Divisor

The Fundamental Theorem of Arithmetic

More on Groups

The Direct Product of two Groups is also a Group

Lagrange's Theorem: The order of a Subgroup divides the order of the Group

Given two groups $G$ and $H$ , $G\times H \cong H\times G$

Quotient Groups

Given any groups $G$ and $H$ and a homomorphism $\theta : G\rightarrow H$

Cayley's Theorem: Every groups is isomorphic to a permutation group on its set of elements:

Rings

The Direct product of any two Rings is also a Ring

Given two rings $R$ and $S$ , $R\times S \cong S\times R$

Quotient Rings

Given any rings $R$ and $S$ and a homomorphism $\theta : R\rightarrow S$

current page

other pages

personal

Search

114 Theorems

From Mathsoc wiki

Contents

Mappings and Functions

A function has a left inverse if and only if it is one to one

A function has a right inverse if and only if it is onto

Groups

Given any group, the identity and all inverses are unique

If for all elements in a group , then is Abelian

Any Permutation on a finite set can be written as a product of disjoint cycles

Equivalence and Congruence

Isomorphism between Groups is an Equivalence Relation

Given an Equivalence Relation \sim on a set S, the set of Equivalence Classes form a Partition of S

The Division Algorithm

The Greatest Common Divisor

The Fundamental Theorem of Arithmetic

More on Groups

The Direct Product of two Groups is also a Group

Lagrange's Theorem: The order of a Subgroup divides the order of the Group

Given two groups and ,

Quotient Groups

Given any groups and and a homomorphism

Cayley's Theorem: Every groups is isomorphic to a permutation group on its set of elements:

Rings

The Direct product of any two Rings is also a Ring

Given two rings and ,

Quotient Rings

Given any rings and and a homomorphism

current page

other pages

personal

Search

A function $f$ has a left inverse if and only if it is one to one

A function $f$ has a right inverse if and only if it is onto

If $x^2 = e$ for all elements in a group $G$ , then $G$ is Abelian

Given two groups $G$ and $H$ , $G\times H \cong H\times G$

Given any groups $G$ and $H$ and a homomorphism $\theta : G\rightarrow H$

Given two rings $R$ and $S$ , $R\times S \cong S\times R$

Given any rings $R$ and $S$ and a homomorphism $\theta : R\rightarrow S$