Linear algebra (Osnabrück 2024-2025)/Part I/Exercise sheet 2

Exercise for the break

Exercise

Give examples of mappings

\varphi ,\psi \colon \mathbb {N} \longrightarrow \mathbb {N} ,

such that ${}\varphi$ is injective, but not surjective, and ${}\psi$ is surjective, but not injective.

Exercises

Exercise

Rules for functions/From school/Exercise

Exercise

How can we recognize by looking at the graph of a mapping

f\colon \mathbb {R} \longrightarrow \mathbb {R}

whether ${}f$ is injective or surjective?

Exercise

Which bijective functions ${}f\colon \mathbb {R} \rightarrow \mathbb {R}$ (or between subsets of ${}\mathbb {R}$ ) do you know from school? What is the name of the inverse function?

Exercise *

Let ${}L,M,N$ be sets and let

f:L\longrightarrow M{\text{ and }}g:M\longrightarrow N

be functions with their composition

g\circ f\colon L\longrightarrow N,x\longmapsto g(f(x)).

Show that if ${}g\circ f$ is injective, then also ${}f$ is injective.

In the following exercises about the power set, it might be helpful to think of the interpretation where ${}G$ is the set of people in the course and ${}M={\mathfrak {P}}\,(G)$ is the set of possible parties (with respect to the guests). For exercise, one might think at ${}A=$ ladies in the course, ${}B=$ gentlemen in the course.

Exercise

Power set/Complement/Bijection/Exercise

Exercise

Power set/Indicator function/Bijection/Exercise

Exercise

Set/Disjoint union/Bijection of the power sets/2/Exercise

Exercise

Sets/M,N,L/Map(MxN,L) and Map(M,Map(N,L))/Bijection/Exercise

Exercise

Graph (mapping)/R and R^2/Imagination/Exercise

Exercise

Mapping/Take preimage/Exercise

Exercise

Mapping/Take image/Exercise

Exercise

Mapping/Injective and preimage surjective/Exercise

Exercise

Mapping/Surjective and preimage injective/Exercise

The idea of the following exercises came from http://jwilson.coe.uga.edu/emt725/Challenge/Challenge.html, also have a look at http://www.vier-zahlen.bplaced.net/raetsel.php .

Exercise

We consider the mapping

\Psi \colon \mathbb {N} ^{4}\longrightarrow \mathbb {N} ^{4}

which assigns to a four tuple ${}(a,b,c,d)$ the four tuple

(\vert {b-a}\vert ,\vert {c-b}\vert ,\vert {d-c}\vert ,\vert {a-d}\vert ).

We denote by ${}\Psi ^{n}$ the ${}n$ -th fold composition of ${}\Psi$ with itself.

Compute
$\Psi (6,5,2,8),\,\Psi ^{2}(6,5,2,8),\,\Psi ^{3}(6,5,2,8),\,\Psi ^{4}(6,5,2,8)\,...,$

until the result is the zero tuple ${}(0,0,0,0)$ .
Compute
$\Psi (1,10,100,1000),\,\Psi ^{2}(1,10,100,1000),\,\Psi ^{3}(1,10,100,1000),\,\Psi ^{4}(1,10,100,1000)\,...,$

until the result is the zero tuple ${}(0,0,0,0)$ .
Show ${}\Psi ^{4}(0,0,n,0)=(0,0,0,0)$ for every ${}n\in \mathbb {N}$ .

Exercise

We consider the mapping

\Psi \colon \mathbb {N} ^{4}\longrightarrow \mathbb {N} ^{4}

which assigns to a four tuple ${}(a,b,c,d)$ the four tuple

(\vert {b-a}\vert ,\vert {c-b}\vert ,\vert {d-c}\vert ,\vert {a-d}\vert ).

Determine whether ${}\Psi$ is injective and whether ${}\Psi$ is surjective.

Exercise

We consider the mapping

\Psi \colon \mathbb {N} ^{4}\longrightarrow \mathbb {N} ^{4}

which assigns to a four tuple ${}(a,b,c,d)$ the four tuple

(\vert {b-a}\vert ,\vert {c-b}\vert ,\vert {d-c}\vert ,\vert {a-d}\vert ).

Show that for any initial value ${}(a,b,c,d)$ , after finitely many iterations this map reaches the zero tuple.

Exercise

We consider the mapping

\Psi \colon \mathbb {N} ^{4}\longrightarrow \mathbb {N} ^{4}

which assigns to a four tuple ${}(a,b,c,d)$ the four tuple

(\vert {b-a}\vert ,\vert {c-b}\vert ,\vert {d-c}\vert ,\vert {a-d}\vert ).

Find an example of a four tuple ${}(a,b,c,d)$ with the property that all iterations ${}\Psi ^{n}(a,b,c,d)$ for ${}n\leq 25$ do not yield the zero tuple. Check your result on http://www.vier-zahlen.bplaced.net/raetsel.php .

We will later deal with the question on how it is with real four tuples, see in particular exercise.

Hand-in-exercises

Exercise ( marks)

Determine the composite functions ${}\varphi \circ \psi$ and ${}\psi \circ \varphi$ for the functions ${}\varphi ,\psi \colon \mathbb {R} \rightarrow \mathbb {R}$ , defined by

\varphi (x)=x^{4}+3x^{2}-2x+5\,\,{\text{  and }}\,\,\psi (x)=2x^{3}-x^{2}+6x-1.

Exercise ( marks)

Show that there exists a bijection between ${}\mathbb {N}$ and ${}\mathbb {Z}$ .

Exercise (3 marks)

Let ${}L,M,N$ be sets and let

f:L\longrightarrow M{\text{ and }}g:M\longrightarrow N

be functions with their composite

g\circ f\colon L\longrightarrow N,x\longmapsto g(f(x)).

Show that if ${}g\circ f$ is surjective, then also ${}g$ is surjective.

Exercise (3 marks)

Consider the set ${}M=\{1,2,3,4,5,6,7,8\}$ and the function

\varphi \colon M\longrightarrow M,x\longmapsto \varphi (x),

defined by the following table

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$
${}\varphi (x)$	${}2$	${}5$	${}6$	${}1$	${}4$	${}3$	${}7$	${}7$

Compute ${}\varphi ^{1003}$ , that is the ${}1003$ -rd composition (or iteration) of ${}\varphi$ with itself.

Exercise Mapping/Take preimage/Complete assignment/Exercise

Mapping/Take preimage/Complete assignment/Exercise

Exercise to give up

Please hand in solutions to the following exercise directly to the lecturer.

Exercise (10 marks)

We consider the mapping

\Psi \colon \mathbb {N} ^{4}\longrightarrow \mathbb {N} ^{4}

which assigns to a four tuple ${}(a,b,c,d)$ the four tuple

(\vert {b-a}\vert ,\vert {c-b}\vert ,\vert {d-c}\vert ,\vert {a-d}\vert ).

Find an example of a four tuple ${}(a,b,c,d)$ with the property that all iterations ${}\Psi ^{n}(a,b,c,d)$ for ${}n\leq 25$ do not yield the zero tuple. Check your result on http://www.vier-zahlen.bplaced.net/raetsel.php .

<< \| Linear algebra (Osnabrück 2024-2025)/Part I \| >> PDF-version of this exercise sheet Lecture for this exercise sheet (PDF)