Math 360, Fall 2021, Assignment 5

I was at the mathematical school, where the master taught his pupils after a method scarce imaginable to us in Europe. The proposition and demonstration were fairly written on a thin wafer, with ink composed of a cephalic tincture. This the student was to swallow upon a fasting stomach, and for three days following eat nothing but bread and water. As the wafer digested the tincture mounted to the brain, bearing the proposition along with it.

- Jonathan Swift, Gulliver's Travels

Read:

1. Section 3.

Carefully define the following terms, then give one example and one non-example of each:

1. Substructure (of a binary structure).
2. Unit (in a monoid).
3. $\mathcal{U}(M)$ (the group of units of a monoid $(M,\triangle)$).
4. Isomorphism (from one binary structure to another).
5. Isomorphic (binary structures).
6. Structural property.

Carefully state the following theorems (you do not need to prove them):

1. Theorem concerning the place of $\mathcal{U}(M)$ in the "hierarchy of niceness" (i.e. whether it is necessarily a semigroup, a monoid, a group, and/or an abelian group).

Solve the following problems:

1. Section 3, problems 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 17, 29, 30, 31, and 32.
2. (Rigid motions) Recall that $\mathbb{R}^n$ denotes the set of all ordered $n$-tuples of real numbers. Given two points $\vec{x}=(x_1,\dots,x_n)$ and $\vec{y}=(y_1,\dots,y_n)$, the distance between these points is given by the distance formula $d(\vec{x},\vec{y})=\sqrt{(x_1-y_1)^2+\dots+(x_n-y_n)^2}$. An isometry of $\mathbb{R}^n$ (also known as a rigid motion of $\mathbb{R}^n$) is a bijection $f:\mathbb{R}^n\rightarrow\mathbb{R}^n$ with the property that for any pair of points $\vec{x},\vec{y}\in\mathbb{R}^n$, one has $d(f(\vec{x}),f(\vec{y}))=d(\vec{x},\vec{y})$. For example, the function $f:\mathbb{R}^1\rightarrow\mathbb{R}^1$ given by $f((x_1))=(x_1+3)$ is an isometry, since it is bijective and $\sqrt{((x_1+3)-(y_1+3))^2}=\sqrt{((x_1-y_1)^2)}$. On the other hand, the motion $g((x_1))=(x_1^3)$ is not rigid even though it is bijective since, for instance, the points $(1)$ and $(2)$ lie at distance $1$ but their images under $g$ lie at distance $7$. Give as many examples as you can of rigid motions of $\mathbb{R}^2$, and then give examples of motions of $\mathbb{R}^2$ that are not rigid.
3. ($\mathrm{Iso}(\mathbb{R}^n)$) Let $\mathrm{Iso}(\mathbb{R}^n)$ denote the set of all isometries of $\mathbb{R}^n$. Prove that $\mathrm{Iso}(R^n)$ is a substructure of $(\mathrm{Fun}(\mathbb{R}^n,\mathbb{R}^n),\circ)$. (Hint: you only need to show that the composition of two isometries is an isometry. This is easier than it looks.)
4. (Challenge) Prove that $(\mathrm{Iso}(\mathbb{R}^n),\circ)$ is in fact a group. (Hint: it is relatively straightforward to show that this structure is associative and has an identity. Once that is done, it remains to show that the inverse of an isometry is again an isometry. Some cleverness is required for the last part, though once the proof is begun in the right way, it is quite short.)

--------------------End of assignment--------------------

Definitions:

1. Suppose $(S, \triangle)$ is a binary structure, and that $T \subseteq S$, and also: $\forall t_1, t_2 \in T, t_1 \triangle t_2 \in T$. Then $T$ is said to be a substructure of $(S, \triangle)$, and $(T, \triangle)$ can itself be regarded as a binary structure. Example: $\mathbb Z$ is a substructure of $(\mathbb R, +)$. $\mathbb Z$ is in fact "closed under $+$". Non-example: $\mathbb Z_{\geq 0}$ is not a substructure of $(\mathbb Z, -)$.
2. Suppose that $(M, \triangle)$ is a monoid. An invertible element of M is also said to be a unit of M.
3. Suppose that $(M, \triangle)$ is a monoid. An invertible element of M is also said to be a unit of M. Let $U(M)$ be the set of units of M. Example: $(M_{n}(\mathbb R), \cdot)$ is a monoid. $U(M_{n}(\mathbb R)) = \{A \in M_{n}(\mathbb R) | det(A) \neq 0 \}$.
4. Suppose $(S, \triangle), (T, \cdot)$ are binary structures. An isomorphism from $(S,\triangle )$ to $(T, \cdot)$ is a function $\phi : S \rightarrow T$ such that: 1. $\phi$ is injective; 2. $\phi$ is surjective; 3.$\phi (S_{1} \triangle S_{2}) = \phi (S_1) \cdot \phi (S_2)$.
5. Two binary structures are said to be isomorphic if there exist one isomorphism from one to the other. Example: $U(\mathbb Z, \cdot), (\mathbb Z_2, +_2)$.
6. A Property P is said to be structural if, whenever P is true of $(S, \triangle)$ and $(S, \triangle)$ is isomorphic to $(T, \cdot)$, P is also true of $(T, \cdot)$.

Theorems:

1. Suppose $(M, \triangle)$ is a monoid. Then $U(M)$ is a substructure. Also, $(U(M), \triangle)$ is a group.

Book Problems:

1. $(S,\triangle )$ to $(T, \cdot)$ is a function $\phi : S \rightarrow T$ such that: 1. $\phi$ is injective, suppose that $\phi (x) = \phi (y)$ in $T$, then $x = y$ in $S$; 2. $\phi$ is surjective, $\phi$ is onto $T$, $y \in T$, there exists $x \in S$ such that $\phi (x) = y$; 3.$\phi (S_{1} \triangle S_{2}) = \phi (S_1) \cdot \phi (S_2)$.
2. Yes. if $(-a) = (-b) \in \mathbb Z$, then $a = b \in \mathbb Z$; for each $a \in \mathbb Z, \exists (-a) \in \mathbb Z$, $\phi (a + b) = -(a+b), \phi (a) + \phi (b) = (-a)+(-b)=-(a+b), \phi (a + b) == \phi (a) + \phi (b)$
3. Yes. $2a == 2b \rightarrow a ==b$, $\forall 2a \in \mathbb Z, \exists a \in \mathbb Z$, $2(a+b) = 2a+2b$.
4. NO. $(a+b) + 1 \neq (a+1) + (b+1)$.
5. Yes.
6. No. $4 = 4, 2 \neq -2$.
7. Yes.
8. No. $ 1 = 1, \{(1,1), (1,2)\} \neq \{(2,5), (1,3) \}$.
9. Yes.
10. Yes.
11. 17. (a). $a * b = a \cdot b -(a + b)$; (b) $a * b = a \cdot b + (a + b)$
12. 29. Suppose $(S, *)$ is commutative and $\phi : S \rightarrow T$ is an isomorphism. We need to show that $(T, \triangle)$ is communicative. $\forall t_1, t_2 \in T$, need to show that $t_1 \triangle t_2 == t_2 \triangle t_1$. Because $\phi$ is surjective, we find $s_1, s_2 \in S$ such that $\phi (s_1) = t_1$ and $\phi (s_2) = t_2$. $t_1 \triangle t_2 = \phi (s_1) \triangle \phi (s_2) = \phi (s_1 * s_2) = \phi (s_2 * s_1) = \phi (s_2) \triangle \phi (s_1) = t_2 \triangle t_1$.
13. 30. Suppose $(S, *)$ is associative and $\phi : S \rightarrow T$ is an isomorphism. We need to show that $(T, \triangle)$ is associative. $\forall t_1, t_2, t_3 \in T$, need to show that $t_1 \triangle (t_2 \triangle t_3) == (t_1 \triangle t_2) \triangle t_3$. Because $\phi$ is surjective, we find $s_1, s_2, s_3 \in S$ such that $\phi (s_1) = t_1, \phi (s_2) = t_2$ and $\phi (s_3) = t_3$. $t_1 \triangle (t_2 \triangle t_3) = \phi (s_1) \triangle (\phi (s_2) \triangle \phi (s_3)) = \phi (s_1) \triangle \phi (s_2*s_3) = \phi (s_1 * (s_2 * s_3)) = \phi ((s_1 * s_2) * s_3) = \phi (s_1*s_2) \triangle \phi (s_3) = (\phi (s_1) \triangle \phi (s_2)) \triangle \phi (s_3) = (t_1 \triangle t_2) \triangle t_3$
14. 31. Suppose $(S, *)$, for each $c \in S$, the equation $x * x = c$ has a solution $x$ in $S$, and $\phi : S \rightarrow T$ is an isomorphism. We need to show that $(T, \triangle)$, for each $k \in S$, the equation $y \triangle y = k$ has a solution $y$ in $T$. $\forall t_1 \in T$, need to show that $\exists t_2 \in T, t_2 \triangle t_2 = t_1$. Because $\phi$ is surjective, we find $s_1, s_2 \in S$ such that $\phi (s_1) = t_1, \phi (s_2) = t_2$. $s_1 = s_2 * s_2, \phi (s_1) = t_1 = \phi (s_2 * s_2) = \phi (s_2) \triangle \phi (s_2) = t_2 \triangle t_2$.
15. 32. Suppose $(S, *)$, for each $b \in S$, the equation $b * b = b$ has a solution $b$ in $S$, and $\phi : S \rightarrow T$ is an isomorphism. We need to show that $(T, \triangle)$, for each $k \in S$, the equation $k \triangle k = k$ has a solution $k$ in $T$. $\forall t_1 \in T$, need to show that $t_1 \triangle t_1 = t_1$. Because $\phi$ is surjective, we find $s_1 \in S$ such that $\phi (s_1) = t_1$. $s_1 = s_1 * s_1, \phi (s_1) = t_1 = \phi (s_1 * s_1) = \phi (s_1) \triangle \phi (s_1) = t_1 \triangle t_1$.

Other Problems:

1. Grid Motions: $f(x) = (x + a), \forall a \in \mathbb R$; Not: $f(x) = (ax^{b}), \forall a, b \in \mathbb R, a \cdot b \neq 1$.
2. According to $Fun$, if $Iso(\mathbb R^{n}$ is from $\mathbb R^{n}$ to itself, then $Iso(\mathbb R^{n}) \in Fun(\mathbb R^{n}, \mathbb R^{n})$. We need to prove that $\forall f, g \in Iso(\mathbb R^{n}), f(x) \circ g(x) \in Iso(\mathbb R^{n})$. We know that for $f(x), x \in Iso(\mathbb R^{n}), g \in Iso(\mathbb R^{n})$, we can set $x = g$, so that $f(g)(x) \in Iso(\mathbb R^{n})$. According to composition we know that $f \circ g = f(g)(x) \in Iso(\mathbb R^{n})$. $Iso(\mathbb R^{n}) \in Fun(\mathbb R^{n}, \mathbb R^{n}) \wedge \forall f, g \in Iso(\mathbb R^{n}), f \circ g \in Iso(\mathbb R^{n})$, it is a substructure.
3. Function composition is associative; identity: $f(x) = x$; Inverse of $f(x)$ is $f^{-1}(x)$. For example, $f(x) = x + 3$, then $x = f^{-1}(x) + 3, f^{-1}(x) = x - 3$. The inverse of the function which we get by switching f(x) and x is $f^{-1}(x)$, and we know $f \circ f^{-1} = f^{-1} \circ f = x$, now we need to prove that all $f^{-1}(x) \in Iso(\mathbb R^{n})$. By definition, if $f(x) \in Iso(\mathbb R^{n}), \sqrt{(f(x_1) - f(y_1))^{2}} = \sqrt{(x_1 - y_1)^{2}}$, because $f \circ f^{-1} = f^{-1} \circ f = x$, $f \circ f^{-1}(x_1) = f^{-1} \circ f (x_1) = x_1, f \circ f^{-1}(y_1) = f^{-1} \circ f(y_1) = y_1$, therefore, $\sqrt{f(f^{-1}(x_1)) - f(f^{-1}(y_1))^{2}} = \sqrt{(x_1 - y_1)^{2}} \rightarrow \sqrt{(f(x_1) \circ f^{-1}(x_1) - f(y_1) \circ (f^{-1}(y_1))^{2}} = \sqrt{(x_1 - y_1)^{2}} \rightarrow \sqrt{(f^{-1}(x_1) \circ f(x_1) - f^{-1}(y_1) \circ f^(y_1))^{2}} = \sqrt{(x_1 - y_1)^{2}}$, $\sqrt{f^{-1}(f(x_1)) - f^{-1}(f^(y_1))^{2}} = \sqrt{(x_1 - y_1)^{2}}$, $\sqrt{f^{-1}(x_1) - f^{-1}(y_1)^{2}} = \sqrt{(x_1 - y_1)^{2}}$, $f^{-1}(x) \in Iso(\mathbb R^{n})$.