MATH661

1.Numbers

Exercise 1. Define one-to-one correspondences between the following sets of numbers:

$𝔼 = {n | n \in ℕ, n mod 2 = 0 .}$ , $𝕆 = {n | n \in ℕ, n mod 2 = 1 .}$

Solution. $f : 𝔼 \to 𝕆$ , $f (n) = n + 1$ is one-to-one.

$ℕ$ , $ℤ$

Solution. $f : ℕ \to ℤ$ , with $f$ defined by ${0 \to 0, 1 \to - 1, 2 \to 1, 3 \to - 2, 4 \to 2, \dots}$ is one possibility. Introducing $[x]$ as the integer part of $x \in ℚ$ , i.e. $[x] = n$ with $n ⩽ x < n + 1$ , $f$ can be expressed as

f (n) = {(- 1)}^{n mod 2} ([n / 2] + n mod 2)

In Julia $x \div y$ is integer division, so for $n \in ℕ$ $[n / 2] = n \div 2$ , and % is the modulo operator

∴	[4÷5 4÷4 4÷3 4÷2; 4%5 4%4 4%3 4%2]

$[\begin{array}{cccc} 0 & 1 & 1 & 2 \\ 4 & 0 & 1 & 0 \end{array}]$ (1)

∴	function f(n) q = n÷2; r = n%2; s = 1-2r; s(q+r) end

f

∴	N=10; [collect(0:N)'; f.(0:N)']

$[\begin{array}{ccccccccccc} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 0 & - 1 & 1 & - 2 & 2 & - 3 & 3 & - 4 & 4 & - 5 & 5 \end{array}]$ (2)

∴

$ℤ$ , $ℚ$

Solution. Construct a table and introduce diagonal traversal to obtain the positive rationals $p / q$ .

Figure 1. One-to-one mapping showing that $| ℚ | = | ℕ |$

From above deduce $| ℕ | = | 𝔼 | = | 𝕆 | = | ℤ | = | ℚ | = ℵ_{0}$ .

Exercise 2. Provide an example to show $| ℝ | > | ℕ |$ .

Exercise 3. Let $ℕ_{q} = {n | n . \in ℕ, n < 2^{q}}$ . Answer the following questions analytically. Also provide a Julia implementation.

Define a one-to-one correspondence $f : ℕ_{2 q} \to ℕ_{q} \times ℕ_{q}$
Let $f (m_{1}) = (n_{1}, p_{1})$ , $f (m_{2}) = (n_{2}, p_{2})$ . Assume $m_{1} + m_{2} \in ℕ_{2 q}$ . Express $f (m_{1} + m_{2})$ in terms of $n_{1}, n_{2}, p_{1}, p_{2}$ .
Assume $m_{1} \cdot m_{2} \in ℕ_{2 q}$ . Express $f (m_{1} \cdot m_{2})$ in terms of $n_{1}, n_{2}, p_{1}, p_{2}$ .

Exercise 4. Construct a one-to-one representation of the positions of atoms within an hexagonal lattice, $f : ℤ^{2} \to ℝ^{2}$ . Implement $f$ and $f^{- 1}$ as Julia functions. Use $f$ to construct a graphical representation of a two-dimensional hexagonal lattice.

Exercise 5. Construct a one-to-one representation of the positions of atoms within an hexagonal lattice, $f : ℤ^{3} \to ℝ^{3}$ . Implement $f$ and $f^{- 1}$ as Julia functions. Use $f$ to construct a graphical representation of a three-dimensional hexagonal lattice.

2.Approximation

Solution

∴	function MachEps(type) one=type(1.0); half=type(0.5); eps=one; while (one+halfeps != one) eps=halfeps; end return eps; end;

∴	[MachEps(Float32) eps(Float32) MachEps(Float64) eps(Float64)]

$[\begin{array}{cccc} 1.1920928955078125 e - 7 & 1.1920928955078125 e - 7 & 2.220446049250313 e - 16 & 2.220446049250313 e - 16 \end{array}]$ (3)

∴

Solution

The floating point axiom states $fl (x) ⊛ fl (y) = (x * y) (1 + ε)$ , with $| ε | ⩽ ϵ$ , leading to

ε = \frac{fl (x) ⊛ fl (y)}{x * y} - 1,

or in this case

ε = \frac{fl (π) \oplus fl (r)}{π + r} - 1 .

The operations in $ℝ$ are computed in Float64 in the following, with $r$ randomly chosen.

∴

function ErrPlot(n)
  pi32=Float32(pi); pi64=Float64(pi); half=Float64(0.5); one=Float64(1.0);
  rscale = 1.0e3*half; e32 = eps(Float32);
  r64=Float64.( rscale*(rand(n) .- half) );
  r32=Float32.(r64);
  result32 = pi32 .+ r32; result64 = pi64 .+ r64;
  ε = result32 ./ result64 .- one;
  rmin=minimum(r64); rmax=maximum(r64);
  clf(); plot(r32,ε,".",[rmin rmax],[e32 e32],"dg",[rmin rmax],[-e32 -e32],"dg");
  xlabel("r"); ylabel("ε"); title("Float32 addition error");
end;

∴	ErrPlot(1000); savefig(homedir()*"/courses/MATH661/images/E01Fig02.eps")

∴

Write Julia functions to compute $S_{n}$ , $T_{n}$ .

Solution

∴	function S(n) fact=1.0; sum=1.0; for k=2:n fact = k*fact; sum = sum + 1/fact; end return sum; end;

∴	function T(n) fact=1.0; for k=n:-1:2 fact=k*fact; end sum=0.0; for k=n:-1:1 sum = sum + 1/fact; fact = fact/k; end return sum; end;

∴

Determine if $S_{n} = T_{n}$ for all $n \in ℕ$ .

Solution

In $ℝ$ , indeed $S_{n} = T_{n}$ by commutativity (proof by induction). In $𝔽$ there must exist some $N$ such that for $n > N$ , $S_{n} \neq T_{n}$ as a consequence of the existence of machine epsilon. Verify by computation (note organization of computations to use Julia broadcasting and presentation of results in a single table)

∴	r=1:8; s=S.(r); t=T.(r); chk = s.==t; [r s t chk]

$[\begin{array}{cccc} 1.0 & 1.0 & 1.0 & 1.0 \\ 2.0 & 1.5 & 1.5 & 1.0 \\ 3.0 & 1.6666666666666667 & 1.6666666666666665 & 0.0 \\ 4.0 & 1.7083333333333335 & 1.7083333333333333 & 0.0 \\ 5.0 & 1.7166666666666668 & 1.7166666666666668 & 1.0 \\ 6.0 & 1.7180555555555557 & 1.7180555555555554 & 0.0 \\ 7.0 & 1.7182539682539684 & 1.7182539682539684 & 1.0 \\ 8.0 & 1.71827876984127 & 1.7182787698412698 & 0.0 \end{array}]$ (4)

∴

Determine if $| S_{n} - T_{n} | < ϵ$ ( $ϵ$ is machine epsilon). Is the floating point axiom verified?
Determine if $| S_{n} - T_{n} | < (n - 1) ϵ$ . Is the floating point axiom verified?

Number Approximation - Exercises

1.Numbers

2.Approximation

3.Successive approximations