Go backward to 6.2 Counting Set Elements Go up to 6 More on Functions Go forward to 6.4 Sequences and Series

6.3 Embedding Sets

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

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

  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/1_Z.

  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

A subset ' B : <=> exists h, B' subset B: h: A ->^{iso(O_A,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.

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:

C' := R x [0,2pi[

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.

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)

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'

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

x *_C' y := <x₀*y₀, shift(x₁+y₁)>

cartesian: C ->iso(*C, *C') C'

polar: C' ->iso(*C', *C) C

forall x in C', y in C': cartesian(x *_C' y) = cartesian(x) *_C cartesian(y).

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.

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

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

cos(x1+y1)	=	cos(x1)cos(y1) - sin(x1)sin(y1)
sin(x1+y1)	=	cos(x1)sin(y1) + sin(x1)cos(y1)

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( ): (N x C') -> C'

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