Abstract Algebra Learning Log - Preliminaries

Recently, I have been working on Abstract Algebra which has derived category theory and exposes its strong relation with computer science.

Brief Introduction

All these learning logs will be based on one online and free textbook (2019 Version), naming Abstract Algebra which is licensed under the GNU FDL.
This learning log is basically in two parts, one is my own understandings or complementions to some of the parts, another part is my own answers to part of the Exercises section in the end of the chapter. And succeeding learning logs will mainly based on this form too.
First part may contain works in the textbook itself, therefore, this series of posts is licensed under the GNU FDL either.

Understandings and complementions to textbook

Page 6, Proof of De Mogran's Laws

  1. \((A\cup{}B)'=A'\cap{}B'\)
    We define two statements, \(p\) and \(q\), representing \(x\in{}A\) and \(x\in{}B\) respectively.
    statement \(x\in{}(A\cup{}B)'\Leftrightarrow{}\neg{}(p\lor{}q)\Leftrightarrow{}(\neg{}p\land{}\neg{}q)\Leftrightarrow{}x\in{}(A'\cup{}B')\). (The relation between \(\neg{}(p\lor{}q)\) and \((\neg{}p\land{}\neg{}q)\) can be deduced by simply enumerating through all the possible values of \(p\) and \(q\), e.g. \(true\) or \(false\) for statements).
    Thus, \(\forall{}x\in{}(A\cup{}B)'\rArr{}x\in{}(A'\cap{}B')\rArr{}(A\cup{}B)'\supset{}A'\cap{}B'\). Conversely, we can prove \((A\cup{}B)'\subset{}A'\cap{}B'\).
    Therefore, \((A\cup{}B)'=A'\cap{}B'\). \(\square{}\)
  2. \((A\cap{}B)'=A'\cup{}B'\)
    Similarly, we can deduce it by using proposition logic. \(\square{}\)

\(\blacksquare{}\)

Page 12, Proof of implications between partition and relation

Theorem. Given an equivalence relation \(\thicksim{}\) on a set \(X\), the equivalence classes of \(X\) form a partition of \(X\), then there is an equivalence relation on \(X\) with equivalence classes \(X\). Conversely, if \(\mathcal{P}=\{x_{i}\}\) partition of a set \(X\), then there is an equivalence relation on \(X\) with equivalence classes \(X_{i}\).
\(Proof\). By using the reflective property, we have \(\forall{}x\in{}X, x\thicksim{}x\). Thus, \(x\thicksim{}[x]\) by the definition of the equivalence class. Therefore, the \([x]\not =\empty\).
Thus, \(\bigcup_{x\in{}X}[x]\).
Now, we should show \(\forall{}x,y\in{}X\), either \([x]\cap{}[y]=\empty{}\) or \([x]=[y]\).
Suppose \([x]\cap{}[y]\not = \empty\),
Then, \(\forall{}c\in{}[y], c\thicksim{}y\).
\[\begin{aligned} \because{}&x\thicksim{}y\\ \therefore{}&y\thicksim{}x\\ \therefore{}&c\thicksim{}x\\ \therefore{}&c\in{}[x]\\ \therefore{}&[y]\subset{}[x]\\ \end{aligned}\] Conversely, we can also show \([x]\subset{}[y]\) in the same way. Thus, the \([x]\) and \([y]\) are either disjoint or completely the same. \(\square\)
Now we need to show that given a partion on \(X\), we can construct a relation \(\thicksim\) on \(X\) such that partion \(\mathcal{P}\) is the equivalence classes of \(\thicksim{}\).
Suppose we have a relation \(\thicksim\). We define \(x\thicksim{}y\Leftrightarrow{}x\ and\ y\ are\ in\ the\ same\ part\ x_{i}\ of\ partition\ \mathcal{P}\). So we should show that the relation is equivalent.

  1. Reflectivity
    since \(\forall{}x\in{}X\), \(x\) will be in the same \(x_{i}\) as itself does, so it is trivial to prove.
  2. Symmetry
    \(x\thicksim{}y\Leftrightarrow{}x\ and\ y\ are\ in\ the\ same\ part\ x_{i}\ of\ partition\ \mathcal{P}\Leftrightarrow{}y\thicksim{}x\), since the order doesn't matter.
  3. Transitivity
    If \(x\thicksim{}y\), then \(x\) and \(y\) are in the same part. If \(y\thicksim{}z\), than \(z\) and \(y\) are in the same part. Thus \(x\) and \(z\) are in the same part, which is \(x\thicksim{}z\).

Thus relation \(\thicksim{}\) is equivalence relation. Since no element can be both in two parts, \([x]\cap{}[y]=\empty\) where \(x,y\in{}X\).
Now we need to prove the set of equivalence classes is the same as partition \(\mathcal{P}\).
If there is \([x]\not = x_{i}\) where \(x\in{}x_{i}\), then there must be some \(y\in{}x_{i}\) in other equivalence class or \(y\in{}[x]\) in other part of \(\mathcal{P}\). Both of which above have contradicted the definition of \(\thicksim{}\). And the \(\mathcal{P}\) will be the same as the set of equivalence classes. \(\square\)
\(\blacksquare\)

My Answers to part of Exercises section \(1.3\).

Disclaimer: this part is my own work to the section, thus no guarantees is provided in terms of correctness. You may use it neither as instruction or correct answer.

General solution to problems \(4\thicksim{}16\) except \(8\) and \(12\)

All the proof-based problems involving the equality of operation of set theory (limited to union and intersect only) can be proved by transforming both sides into statements and enumerating through all the possible values of single statements, which construct the left-hand-side or right-hand-side statement, to show that set on each side is a subset of the other. For example, Proof of De Morgan's laws.

Problem 12

\[\begin{aligned} (A\cup{}B)\times{}C&=\{(a,b):a\in{}(A\cup{}B),\ b\in{}C\}\\ &=\{(a,b):a\in{}A\ or\ a\in{}B,\ b\in{}C\}\\ &=\{(a,b):a\in{}A,\ b\in{}C\}\cup{}\{(a,b):a\in{}B,\ b\in{}C\}\\ &=(A\times{}C)\cup{}(B\times{}C)\\ \end{aligned}\]
\(\blacksquare\)

Problem 17

In order to let \(f\) be a mapping which is well-defined, we need to make sure that \(f(\frac{kp}{kq})=f(\frac{p}{q})\) where \(k\in{}\Z\) and \(k\not = 0\).

  1. Only if \(kp=q\) implies the above implication. Thus it isn't a mapping
  2. It is a mapping since it fulfills the requirement above.
  3. Only if \(p=q\) or \(k=1\). Not a mapping.
  4. It is a mapping.

Problem 22

(d) We have to show that \(g(a)=g(b)\rArr{}a=b\) in order to prove that \(g\) is one-to-one. Suppose \(g(a)=g(b)\). Since \(f\) is onto, there exists such \(a\) and \(b\) that \(a=f(\alpha{})\) and \(b=f(\beta{})\). So \(g(a)=g(b)\) can be written as \(g(f(\alpha))=g(f(\beta))\). Given \(g\circ{}f\) is one-to-one, we know that \(\alpha{}=\beta{}\). Thus \(a=f(\alpha{})=f(\beta{})=b\), resulting in \(g(a)=g(b)\rArr{}a=b\).
\(\blacksquare{}\)
(e) \[\begin{aligned} \forall{}&b\in{}B,g(b)\in{}C\\ \because{}&(g\circ{}f)\ is\ onto\\ \therefore{}&\exist{}a:g(b)=(g\circ{}f)(a)=g(f(a))\\ \because{}&g\ is\ one\text{-}to\text{-}one\\ \therefore{}&\forall{}b\in{}B,b=f(a) \end{aligned}\] \(\blacksquare{}\)

Problem 28

Suppose there is a element \(z\in{}X\) such that \(z\) is not related to anything. Then transitivity and symmetry hold but reflective holds since we need to have \((x,x)\in{}R,\forall{}x\in{}X\).
\(\blacksquare\)

Other parts I find not worth sharing or taking notes.
\(24.(b),\ 24.(c),\ 24.(d),\ 24.(e)\) remain unsolved.

References

I would prefer a quick and informal one rather than a formal one.

  1. Abstract Algebra
  2. Equivalence Class Question - Reddit

Special thanks

My math teacher.