# 抽象代数代考| RELATIONS AND OPERATIONS作业代写

Problem 1.

An equivalence relation $\mathcal{R}$ on a set $S$ effects a partition of $S$ and, conversely, a partition of $S$ defines an equivalence relation on $S$.

Proof .

Let $\mathcal{R}$ be an equivalence relation on $S$ and define for each $p \in S, T_{p}=[p]={x: x \in S, x \mathcal{R} p}$.
Since $p \in[p]$, it is clear that $S$ is the union of all the distinct subsets $T_{a}, T_{b}, T_{c}$, induced by $\mathcal{R}$. Now for any pair of these subsets, as $T_{b}$, and $T_{c}$ we have $T_{b} \cap T_{c}=\emptyset$ since, otherwise, $T_{b}=T_{c}$ by Problem 5. Thus, $\left{T_{a}, T_{b}, T_{c}, \ldots\right}$ is the partition of $S$ effected by $\mathcal{R}$.

Conversely, let $\left{T_{a}, T_{b}, T_{c}, \ldots\right}$ be any partition of $S$. On $S$ define the binary relation $\mathcal{R}$ by $p \mathcal{R} q$ if and only if there is a $T_{i}$ in the partition such that $p, q \in T_{i}$. It is clear that $\mathcal{R}$ is both reflexive and symmetric. Suppose $p \mathcal{R} q$ and $q \mathcal{R} r$; then by the definition of $\mathcal{R}$ there exist subsets $T_{j}$ and $T_{k}$ (not necessarily distinct) for which $p, q \in T_{j}$ and $q, r \in T_{k}$. Now $T_{j} \cap T_{k} \neq \emptyset$ and so $T_{j}=T_{k}$. Since $p, r \in T_{j}$, then $p \mathcal{R} r$ and $\mathcal{R}$ is transitive. This completes the proof that $\mathcal{R}$ is an equivalence relation.

Problem 2.

Diagram the partial ordering of $(a)$ the set of subsets of $S={a, b, c}$ effected by the binary relation $(\subseteq),(b)$ the set $B={2,4,5,8,15,45,60}$ effected by the binary relation ( ).

Proof .

These figures need no elaboration once it is understood a minimum number of line segments is to be used. for example, $\emptyset$ is not joined directly to ${a, b, c}$ since $\emptyset \subseteq{a, b, c}$ is indicated by the path $\emptyset \subseteq{a} \subseteq{a, b} \subseteq{a, b, c} .$

Problem 3.

Prove: Let the permutation $\alpha$ on $n$ symbols be expressed as the product of $r$ transpositions and also as the product of $s>r$ transpositions. Then $r$ and $s$ are either both even or both odd.

Proof .

Using the distinct symbols $x_{1}, x_{2}, x_{3}, \ldots, x_{n}$, we form the product
$$\begin{array}{r} A=\left(x_{1}-x_{2}\right)\left(x_{1}-x_{3}\right)\left(x_{1}-x_{4}\right) \cdots\left(x_{1}-x_{n}\right) \ \left(x_{2}-x_{3}\right)\left(x_{2}-x_{4}\right) \cdots\left(x_{2}-x_{n}\right) \ \cdots \cdots \cdots \cdots \cdots \cdot \cdots \cdot \ \left(x_{n-1}-x_{n}\right) \end{array}$$
A transposition $(u, v)$, where $u<v$, on $A$ has the following effect: (1) any factor which involves neither $x_{u}$ nor $x_{v}$ is unchanged, (2) the single factor $x_{u}-x_{v}$ changes sign, (3) the remaining factors, each of which contains either $x_{u}$ or $x_{v}$ but not both, can be grouped into pairs, $\left(x_{u}-x_{w}\right)\left(x_{v}-x_{w}\right)$ where $u<v<w$, $\left(x_{u}-x_{w}\right)\left(x_{w}-x_{v}\right)$ where $u<w<v$, and $\left(x_{w}-x_{u}\right)\left(x_{w}-x_{v}\right)$ where $w<u<v$, which are all unchanged. Thus, the effect of the transposition on $A$ is to change its sign.

Now the effect of $\alpha$ on $A$ is to produce $(-1)^{r} A$ or $(-1)^{s} A$ according as $\alpha$ is written as the product of $r$ or $s$ transpositions. Since $(-1)^{r} A=(-1)^{s} A$, we have $A=(-1)^{s-r} A$ so that $s-r$ is even. Thus, $r$ and $s$ are either both even or both odd.