previous up next
Go backward to 6.2 Counting Set Elements
Go up to 6 More on Functions
Go forward to 6.4 Sequences and Series
RISC-Linz logo

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'.


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
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
         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) := <sqrtn(z0), z1/n>.

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 = <r0, shift(r1+2 pi i/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 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

previous up next