Go backward to 6.2 Counting Set ElementsGo up to 6 More on FunctionsGo forward to 6.4 Sequences and Series |

A

h:A->^{hom(f,f')}B: <=>h:A->B/\( existsninN:f:A^{n}->A/\f':B^{n}->B/\( forallxinA^{n}:h(f(x_{0}, ...,x_{n-1})) =f'(h(x_{0}), ...,h(x_{n-1})))).

h:A->^{iso(f,f')}B: <=>h:A->^{hom(f,f')}B/\h:A->^{bijective}B.

A homomorphism makes the following diagram commute:

In other words, it does not matter whether we first perform the operation
`f` in `A` and let `h` map the result to `B` or whether we
let `h` map the arguments of `f` to `B` and apply `f`' to
them. In this sense, `h` *embeds* `A` into `B` and their
operations are *structurally equal*. If `h` is an isomorphism, then
this embedding works in both directions: `A` and
`B` become "identical twins" that cannot be distinguished
by the behavior of `f` and `f`'.

- Take
`h`:**N**->**Z**defined as (see Definition*Integers*)`h`(`x`) := <`x`, 0>.`x`in**N**and`y`in**N**,

i.e.,`h`(`x`+_{N}`y`)= `h`(`x`) +_{Z}`h`(`y`);`h`(`x`*_{N}`y`)= `h`(`x`) *_{Z}`h`(`y`)`h`is a homomorphism from**N**to**Z**(for the operations + and *). - Take
`h`:**Z**->**Q**defined as (see Definition*Rationals*):`h`(`x`) :=`x`/1_{Z}.`x`in**Z**and`y`in**Z**,

i.e.,`h`(`x`+_{Z}`y`)= `h`(`x`) +_{Q}`h`(`y`);`h`(`x`-_{Z}`y`)= `h`(`x`) -_{Q}`h`(`y`);`h`(`x`*_{Z}`y`)= `h`(`x`) *_{Q}`h`(`y`)`h`is a homomorphism from**Z**to**Q**(for operations +, -, and *). - Take the domain "List(
`T`)" with functions "length" and "append" (see the Examples*length*and*append*).We have for all

`x`in List(`T`) and`y`in List(`T`)length(append(

i.e., "length" is a homomorphism from "List(`x`,`y`)) = length(`x`) + length(`y`)`T`)" to**N**with respect to "append" and +. - Take the set of polynomials. We have, for all
polynomials
`x`and`y`and`a`in**R**,

i.e., polynomial evaluation is a homomorphism from the set of polynomials to( `x`+`y`)[`a`]= `x`(`a`) +_{R}`y`(`a`)( `x`-`y`)[`a`]= `x`(`a`) -_{R}`y`(`a`)(- `x`)[`a`]= - _{R}`x`(`a`)( `x`*`y`)[`a`]= `x`(`a`) *_{R}`y`(`a`)**R**(for operations +, -, *).

As the previous example suggests, we have a homomorphism from each number
domain introduced in Chapter *Numbers* to its
successor. Actually, each domain is *isomorphic* to some subset of its
successor, i.e.,

whereNsubset 'Zsubset 'Qsubset 'Rsubset 'C

HereAsubset 'B: <=>existsh,B' subsetB:h:A->^{iso(OA,O'B)}B'.

**Logic Evaluator**
We demonstrate that (a finite subset of) **N** is isomorphic to a
subset of **Z**:

Isomorphisms are also useful to demonstrate the equivalence of different constructions as shown below.

Every element `x`+`y`i of **C** can be visualized as
a point in the plane whose *Cartesian coordinates (kartesische
Koordinaten)* are denoted by the real part and by the imaginary part of the
complex number, respectively:

In

Thus we can define a "polar" variant of

assuming that angles are uniquely expressed in "radians" (i.e., pi = 180C' :=Rx [0,2pi[

A translation from the new domain into the original one is given by

where "cos" and "sin" represent cosine and sine, respectively.

cartesian: C' ->Ccartesian( z) =z_{0}*cos(z_{1})+z_{0}*sin(z_{1})i.

The other direction is a bit more complicated:

where "arctan" is the inverse ("arcus") tangent. Since the inverse tangent does not determine the result uniquely, we have to make a case distinction and normalize the result by the following auxiliary function:

polar: C->C'polar( z) = (sqrt(z_{0}^{2}+z_{1}^{2}), alpha)wherealpha=ifz_{0}= 0thenifz_{1}> 0thenpi /2else3 pi /2elseleta= arctan(z_{1}/z_{0}):shift( ifz_{0}>= 0thenaelsepi -a)

shift: R-> [0,2 pi [shift( a) := (suchb:bin [0,2 pi [ /\existsiinZ:a-b= 2 pii)

One can now show

i.e., "cartesian" and "polar" are bijections.

cartesian o polar = 1 _{C},polar o cartesian = 1 _{C'}

We may define the following "multiplication" on **C**':

We then havex*_{C'}y:= <x_{0}*y_{0}, shift(x_{1}+y_{1})>

i.e.,

cartesian: C->^{iso(*C, *C')}C'polar: C' ->^{iso(*C', *C)}C

Take arbitraryforallxinC',yinC': cartesian(x*_{C'}y) = cartesian(x) *_{C}cartesian(y).

(*) holds because of the definition of "shift" and because, for every

cartesian( x*_{C'}y)= cartesian( x_{0}y_{0}, shift(x_{1}+y_{1}))= x_{0}y_{0}cos(shift(x_{1}+y_{1})) + (x_{0}y_{0}sin(shift(x_{1}+y_{1})))i= (*) x_{0}y_{0}cos(x_{1}+y_{1}) + (x_{0}y_{0}sin(x_{1}+y_{1}))i.

which we assume as granted knowledge.

sin( x+2 pi )= sin( x),cos( x+2 pi )= cos( x)

We also have

We assume the knowledge

cartesian( x) *_{C}cartesian(y)= ( x_{0}cos(x_{1}) +x_{0}sin(x_{1})i) *_{C}(y_{0}cos(y_{1}) +y_{0}sin(y_{1})i)= ( x_{0}y_{0}cos(x_{1})cos(y_{1}) -x_{0}y_{0}sin(x_{1})sin(y_{1})) +( x_{0}y_{0}cos(x_{1})sin(y_{1}) +x_{0}y_{0}sin(x_{1})cos(y_{1}))i= x_{0}y_{0}(cos(x_{1})cos(y_{1}) - sin(x_{1})sin(y_{1})) +x_{0}y_{0}(cos(x_{1})sin(y_{1}) +x_{0}y_{0}sin(x_{1})cos(y_{1}))i

as granted and are therefore done.

cos( x_{1}+y_{1})= cos( x_{1})cos(y_{1}) - sin(x_{1})sin(y_{1})sin( x_{1}+y_{1})= cos( x_{1})sin(y_{1}) + sin(x_{1})cos(y_{1})

We may also define corresponding notions of addition, subtraction, and
division in **C**' such that they are isomorphic to their counterparts in
**C**.

Consequently, we may operate in **C** or in **C**', whatever
is more convenient, and translate the results into the other direction.
In particular, if the computation of some operation is rather awkward in one
domain, it may be simpler to translate the arguments into the other domain,
perform the operation there, and translate the result back into the original
domain. This is in particular true for the computation of complex roots.

sqrt( ): ( NxC') ->C'sqrt ^{n}(z) := <sqrt^{n}(z_{0}),z_{1}/n>.

forallninN_{>0},zinC':letr= sqrt^{n}(z):( forallsinC':z=s^{n}<=>existsiinN:s= <r_{0}, shift(r_{1}+2 pii/n)>).

In other words, the `n`-th roots of a complex number are on the same
circle and have equal distance from each other as shown in the following
diagram for the cube root of <`r`, alpha >.

Since roots can be computed in **C**' most easily, one usually does not
bother to introduce this concept in **C** but simply defines:

sqrt(`): ( N_{>0}xC) ->Csqrt ^{n}(z) := cartesian(sqrt^{n}(polar(z))).

Vice versa, addition and subtraction are done more easily in **C** than in
**C**':

+ _{C'}: (C' xC') ->C'x+_{C'}y:= polar(cartesian(x) +_{C}cartesian(y));- _{C'}: (C' xC') ->C'x-_{C'}y:= polar(cartesian(x) +_{C}cartesian(y)).

Author: Wolfgang Schreiner

Last Modification: October 4, 1999