数学代写|MATH5330 Abstract Algebra

Not all problems on Induction require induction. 0.16 is better proven on the basis of the division algorithm (p. 20, Lemma 2.1). Of course this algorithm is known to you from elementary school: If $n$ is any integer and $d$ a positive integer then $d$ goes a certain number of times evenly into $n$, say $q$ many times. That is, $n=q \cdot d+r$ where for the remainder $r$ one has that $0 \leq r<d$. $q$ is called the quotient.
Like 27 divided by 4 has remainder $r=3$ and quotient $q=6: 27=6 \cdot 4+3$; while $-27=(-7) \cdot 4+1$ shows that $q=-7, r=1$.
Use the division algorithm in order to show that any list of $k$ consecutive integers contains a member that is divisible by $k$. Use this in order to prove 0.16 .
You may have to spend some time in order to figure out what went wrong in the proof that all horses are the same color.

For the time being, you can skip section 5 . This example will be better understood after we have covered rings (Section 16, Exercises 16.16, 16.17):
For any set $X$ one has that the powerset $P(X)$ of $X$ is a boolean ring where addition is the symmetric difference: $+=\nabla$ and multiplication is the intersection: $\cdot=\cap$, zero is the empty set: $0=\emptyset$ and one is the whole set $1=X$.

Problem 2.13 requires some thought. It is optional.
A product term is defined recursively as follows:

1. $p=a$ is a product where $a$ is any element of the group $\mathbf{G}$.
2. If $p_1$ and $p_2$ are products, then $p=\left(p_1 \cdot p_2\right)$ is a product.
3. All products are obtained that way.
   For any two elements $a, b$ one has that $p=(a \cdot b)$ is a product. For three elements $a, b, c$ there are two possibilities to form a product of these elements without changing the order: $((a \cdot(b \cdot c))$ and $((a \cdot b) \cdot c)$. By associativity, both products have the same value.

The complexity of a product is the number of dots in it. $p=a$ has complexity 0 . If $p$ has complexity $n$ and $q$ complexity $m$ then $(p \cdot q)$ has complexity $n+m+1$. A product is a string of parenthesis (left and right), elements of $\mathbf{G}$ and dots. However such strings have to be constructed according to the rules 1 . and 2 . They have to be well-formed.
If, read from left to right, the elements in a product are $a_1, a_2, \ldots, a_n$ then the product $p=p\left(a_1, a_2, \ldots, a_n\right)$ has complexity $n-1$.Given a list $a_1, a_2, \ldots, a_n$ of elements, the normal product $n\left(a_1, a_2, \ldots, a_n\right)$ of these elements is defined recursively by

$n\left(a_n\right)=a_n$

$n\left(a_1, a_2, \ldots, a_n\right)=\left(a_1 \cdot n\left(a_2, \ldots, a_n\right)\right)$
The claim of 2.13 now is
$$
p\left(a_1, \ldots, a_n\right)=n\left(a_1, \ldots, a_n\right)
$$
for any product $p\left(a_1, \ldots, a_n\right)$.Prove this by induction over the complexity of the product. 2.12 is a preparation for the general proof. Notice that for 2.12 and 2.13 , only associativity is used.

Comments: For the multiplicative monoid of $n \times n$-matrices one has that a left-inverse of a matrix $A$ is automatically a right-inverse, thus an inverse.
This is proven in linear algebra and related to the
Theorem The linear homogeneous system $A X=0$ of $n$ equations in $n$ unknowns has only the trivial solution if and only if $A X=B$ has for every $B$ (exactly) one solution. Here $A$ is an $n \times n$ matrix and $X$ and $B$ are $n \times 1$ matrices.
For the monoid of maps on a set $X$ one has that the $\operatorname{map} f: S \rightarrow S$ has a left inverse $g: S \rightarrow S$, that is $g \circ f=i d_S$ for some $g$, if and only if $f$ is injective, that is $f\left(x_1\right)=f\left(x_2\right)$ iff $x_1=x_2$. And $f$ has a right inverse $h: S \rightarrow S$, that is $f \circ h=i d s$ for some $h$, if and only if $f$ is surjective, that is for every $y \in S$ there is some $x$ such that $f(x)=y$. It now follows::
Theorem If a map $f: S \rightarrow S$ has a left as well a right inverse, then it has a unique inverse, which is the inverse map $f^{-1}$ of $f$
$$
f(x)=y \Leftrightarrow f^{-1}(y)=x
$$
For maps on finite sets $S$ one has that $f: S \rightarrow S$ is injective if and only $f$ is surjective. Why?
Exercise Let $S=\mathbb{N}$ and $f: n \mapsto 2 n$. Find a left inverse $g$ and demonstrate that it is not a right inverse and that there are many left inverses for $f$. Now let $f: n \mapsto d(n)$, where $d(n)$ is the number of prime divisors of $n$. Find a right inverse $g$ and demonstrate that it is not a left inverse and that there are many right inverses for $f$.