   Go backward to 6.2 Counting Set ElementsGo up to 6 More on FunctionsGo forward to 6.4 Sequences and Series ## 6.3 Embedding Sets

We have introduced in Chapter Numbers a sequence of number domains and stated rather vaguely that each domain can be "embedded" into the successor domain such that the properties of the corresponding operations are preserved. This statement can be made more precisely by the following concept.

Definition 77 (Homomorphism) Let f: An -> A and f': Bn -> B. We call h a  homomorphism (Homomorphismus) from A to B (with respect to f and f') if, for every x0 in A, ..., xn-1 in A, h(f(x0, ..., xn-1)) = f'(h(x0), ..., f'(xn-1)):
 h: A ->hom(f,f') B : <=> h: A -> B /\ (exists n in N: f: An -> A /\  f': Bn -> B /\ (forall x in An: h(f(x0, ..., xn-1)) = f'(h(x0), ..., h(xn-1)))).
A  isomorphism (Isomorphismus) is a bijective homomorphism.
 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'.

Example
• Take h: N -> Z defined as (see Definition Integers)
h(x) := <x, 0>.
Then we have, for all x in N and y in N,
 h(x+Ny) = h(x) +Z h(y); h(x*Ny) = h(x) *Z h(y)
i.e., h is a homomorphism from N to Z (for the operations + and *).
• Take h: Z -> Q defined as (see Definition Rationals):
h(x) := x/1Z.
Then we have, for all x in Z and y in Z,
 h(x+Zy) = h(x) +Q h(y); h(x-Zy) = h(x) -Q h(y); h(x*Zy) = h(x) *Q h(y)
i.e., 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(x, y)) = length(x) + length(y)
i.e., "length" is a homomorphism from "List(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,
 (x + y)[a] = x(a) +R y(a) (x - y)[a] = x(a) -R y(a) (-x)[a] = -Rx(a) (x * y)[a] = x(a) *R y(a)
i.e., polynomial evaluation is a homomorphism from the set of polynomials to 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.,

N subset ' Z subset ' Q subset ' R subset ' C
where
A subset ' B : <=> exists h, B' subset B: h: A ->iso(OA,O'B) B'.
Here OA denotes the considered operations on A, O'B denotes the corresponding operations on B' and h: A ->iso(OA,O'B) B' states that h is an isomorphism between A and B for each operation pair.

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.

##### Another Construction of the Complex Numbers

Every element x+yi 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  polar coordinates (Polarkoordinaten), each point is represented by a pair <r, alpha > where r denotes the distance of the point from the origin and alpha denotes the angle to the horizontal axis: Thus we can define a "polar" variant of C
C' := R x [0,2pi[
assuming that angles are uniquely expressed in "radians" (i.e., pi = 180 o ).

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

 cartesian: C' -> C cartesian(z) = z0*cos(z1)+z0*sin(z1)i.
where "cos" and "sin" represent cosine and sine, respectively.

The other direction is a bit more complicated:

 polar: C -> C' polar(z) = (sqrt(z02+z12), alpha) where alpha= if z0 = 0 then if z1 > 0 then pi /2 else 3 pi /2 else let a = arctan(z1/z0): shift(if z0 >= 0 then a else pi -a)
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:
 shift: R -> [0,2 pi [ shift(a) := (such b: b in [0,2 pi [ /\  exists i in Z: a-b = 2 pi i)

One can now show

 cartesian o polar = 1C, polar o cartesian = 1C'
i.e., "cartesian" and "polar" are bijections.

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

x *C' y := <x0*y0, shift(x1+y1)>
We then have
 cartesian: C ->iso(*C, *C') C' polar: C' ->iso(*C', *C) C
i.e., C and C' are isomorphic with respect to their respective notions of multiplication.

Proof  We show that "cartesian" is a homomorphism with respect to multiplication:
forall x in C', y in C': cartesian(x *C' y) = cartesian(x) *C cartesian(y).
Take arbitrary x in C' and y in C'. We then have
 cartesian(x *C' y) = cartesian(x0y0, shift(x1+y1)) = x0y0cos(shift(x1+y1)) + (x0y0sin(shift(x1+y1)))i = (*) x0y0cos(x1+y1) + (x0y0sin(x1+y1))i.
(*) holds because of the definition of "shift" and because, for every x in R,
 sin(x+2 pi ) = sin(x), cos(x+2 pi ) = cos(x)
which we assume as granted knowledge.

We also have

 cartesian(x) *C cartesian(y) = (x0cos(x1) + x0sin(x1)i) *C (y0cos(y1) + y0sin(y1)i) = (x0y0cos(x1)cos(y1) - x0y0sin(x1)sin(y1)) + (x0y0cos(x1)sin(y1) + x0y0sin(x1)cos(y1))i = x0y0(cos(x1)cos(y1) - sin(x1)sin(y1)) + x0y0(cos(x1)sin(y1) + x0y0sin(x1)cos(y1))i
We assume the knowledge
 cos(x1+y1) = cos(x1)cos(y1) - sin(x1)sin(y1) sin(x1+y1) = cos(x1)sin(y1) + sin(x1)cos(y1)
as granted and are therefore done.

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.

Definition 78 (Complex Root)
 sqrt( ): (N x C') -> C' sqrtn(z) := .

Proposition 85 (Complex Roots) For every n in N>0 and z in C', the n-th roots of z are sqrt^n(z) and the n-1 values that have the same distance from the origin and their angle shifted by multiples of 2 pi /n:
 forall n in N>0, z in C': let r = sqrtn(z): (forall s in C': z = sn <=> exists i in N: s = ).

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 x C) -> C sqrtn(z) := cartesian(sqrtn(polar(z))).

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

 +C': (C' x C') -> C' x +C' y := polar(cartesian(x) +C cartesian(y)); -C': (C' x C') -> C' x -C' y := polar(cartesian(x) +C cartesian(y)).

Author: Wolfgang Schreiner
Last Modification: October 4, 1999   