Abstract Algebra: Theory and Applications

Let $\mathbb{R}$ be the universal set and suppose that

Then

Other relations between sets often hold true. For example,

To see that this is true, observe that

If $A=\{x,y\}\text{,}$ $B=\{1,2,3\}\text{,}$ and $C=\mathrm{\varnothing }\text{,}$ then $A\times B$ is the set

and

Let $f(x)=x^2$ and $g(x)=2x+5\text{.}$ Then

and

In general, order makes a difference; that is, in most cases $f\circ g\ne g\circ f\text{.}$

Sometimes it is the case that $f\circ g=g\circ f\text{.}$ Let $f(x)=x^3$ and $g(x)=\sqrt[3]{x}\text{.}$ Then

and

Given a $2\times 2$ matrix

we can define a map $T_A:{\mathbb{R}}^2\to {\mathbb{R}}^2$ by

for $(x,y)$ in ${\mathbb{R}}^2\text{.}$ This is actually matrix multiplication; that is,

Maps from ${\mathbb{R}}^n$ to ${\mathbb{R}}^m$ given by matrices are called linear maps or linear transformations.

Suppose that $S=\{1,2,3\}\text{.}$ Define a map $\pi :S\to S$ by

This is a bijective map. An alternative way to write $\pi$ is

For any set $S\text{,}$ a one-to-one and onto mapping $\pi :S\to S$ is called a permutation of $S\text{.}$

The natural logarithm and the exponential functions, $f(x)=\ln x$ and $f^{-1}(x)=e^x\text{,}$ are inverses of each other provided that we are careful about choosing domains. Observe that

and

whenever composition makes sense.

Suppose that

Then $A$ defines a map from ${\mathbb{R}}^2$ to ${\mathbb{R}}^2$ by

We can find an inverse map of $T_A$ by simply inverting the matrix $A\text{;}$ that is, $T_A^{-1}=T_{A^{-1}}\text{.}$ In this example,

hence, the inverse map is given by

It is easy to check that

Not every map has an inverse. If we consider the map

given by the matrix

then an inverse map would have to be of the form

and

for all $x$ and $y\text{.}$ Clearly this is impossible because $y$ might not be $0\text{.}$

Given the permutation

on $S=\{1,2,3\}\text{,}$ it is easy to see that the permutation defined by

is the inverse of $\pi \text{.}$ In fact, any bijective mapping possesses an inverse, as we will see in the next theorem.

Let $p\text{,}$ $q\text{,}$ $r\text{,}$ and $s$ be integers, where $q$ and $s$ are nonzero. Define $p/q\sim r/s$ if $ps=qr\text{.}$ Clearly $\sim$ is reflexive and symmetric. To show that it is also transitive, suppose that $p/q\sim r/s$ and $r/s\sim t/u\text{,}$ with $q\text{,}$ $s\text{,}$ and $u$ all nonzero. Then $ps=qr$ and $ru=st\text{.}$ Therefore,

Since $s\ne 0\text{,}$ $pu=qt\text{.}$ Consequently, $p/q\sim t/u\text{.}$

Suppose that $f$ and $g$ are differentiable functions on $\mathbb{R}\text{.}$ We can define an equivalence relation on such functions by letting $f(x)\sim g(x)$ if $f^{\prime }(x)=g^{\prime }(x)\text{.}$ It is clear that $\sim$ is both reflexive and symmetric. To demonstrate transitivity, suppose that $f(x)\sim g(x)$ and $g(x)\sim h(x)\text{.}$ From calculus we know that $f(x)-g(x)=c_1$ and $g(x)-h(x)=c_2\text{,}$ where $c_1$ and $c_2$ are both constants. Hence,

and $f^{\prime }(x)-h^{\prime }(x)=0\text{.}$ Therefore, $f(x)\sim h(x)\text{.}$

Let $A$ and $B$ be $2\times 2$ matrices with entries in the real numbers. We can define an equivalence relation on the set of $2\times 2$ matrices, by saying $A\sim B$ if there exists an invertible matrix $P$ such that $PA{P}^{-1}=B\text{.}$ For example, if

then $A\sim B$ since $PA{P}^{-1}=B$ for

Let $I$ be the $2\times 2$ identity matrix; that is,

Then $IA{I}^{-1}=IAI=A\text{;}$ therefore, the relation is reflexive. To show symmetry, suppose that $A\sim B\text{.}$ Then there exists an invertible matrix $P$ such that $PA{P}^{-1}=B\text{.}$ So

Finally, suppose that $A\sim B$ and $B\sim C\text{.}$ Then there exist invertible matrices $P$ and $Q$ such that $PA{P}^{-1}=B$ and $QB{Q}^{-1}=C\text{.}$ Since

the relation is transitive. Two matrices that are equivalent in this manner are said to be similar.

Let $r$ and $s$ be two integers and suppose that $n\in \mathbb{N}\text{.}$ We say that $r$ is congruent to $s$ modulo $n\text{,}$ or $r$ is congruent to $s$ mod $n\text{,}$ if $r-s$ is evenly divisible by $n\text{;}$ that is, $r-s=nk$ for some $k\in \mathbb{Z}\text{.}$ In this case we write $r\equiv s(\mathrm{mod}n)\text{.}$ For example, $41\equiv 17(\mathrm{mod}8)$ since $41-17=24$ is divisible by $8\text{.}$ We claim that congruence modulo $n$ forms an equivalence relation of $\mathbb{Z}\text{.}$ Certainly any integer $r$ is equivalent to itself since $r-r=0$ is divisible by $n\text{.}$ We will now show that the relation is symmetric. If $r\equiv s(\mathrm{mod}n)\text{,}$ then $r-s=-(s-r)$ is divisible by $n\text{.}$ So $s-r$ is divisible by $n$ and $s\equiv r(\mathrm{mod}n)\text{.}$ Now suppose that $r\equiv s(\mathrm{mod}n)$ and $s\equiv t(\mathrm{mod}n)\text{.}$ Then there exist integers $k$ and $l$ such that $r-s=kn$ and $s-t=ln\text{.}$ To show transitivity, it is necessary to prove that $r-t$ is divisible by $n\text{.}$ However,

and so $r-t$ is divisible by $n\text{.}$

If we consider the equivalence relation established by the integers modulo $3\text{,}$ then

Notice that $[0]\cup [1]\cup [2]=\mathbb{Z}$ and also that the sets are disjoint. The sets $[0]\text{,}$ $[1]\text{,}$ and $[2]$ form a partition of the integers.