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

Exercise for the break

Exercise

We want to realize as many bijective mappings as possible from the fingertips of the left hand to the fingertips of the right hand, by letting the corresponding (according to the assignment) fingertips touch each other.

1. Realize the "natural“ bijection.
2. Realize those bijections, where two adjacent fingertips swap their natural counterparts, and where the other three fingertips touch their natural counterparts (adjacent transposition).
3. Realize those bijections, where two fingertips swap their natural counterparts, and where the other three fingertips touch their natural counterparts (transposition).
4. Realize those bijections, where exactly two fingertips touch their natural counterparts.
5. Realize those bijections, where exactly one fingertip touches its natural counterpart.
6. Realize those bijections, where no fingertip touches its natural counterpart.

Exercises

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.

Exercise

What functions (and their defining rules) do you know from school?

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

1. Let ${}H$ be the set of all (alive or dead) people. Study the mapping

   $\varphi \colon H\longrightarrow H$

   that assigns to every person the mother, with respect to injectivity and surjectivity.

2. What is the meaning of the composition ${}\varphi ^{3}$?
3. How does it look when we take the same mapping but, in the domain, restricted to the set ${}E$ of all only children, and, in the codomain, restricted to the set ${}M$ of all mothers?
4. Be a bit hairsplitting and argue (referring to evolution or religion) that the mapping in (1) is not well-defined.

Exercise

A function

$f\colon \mathbb {R} \longrightarrow \mathbb {R} ,x\longmapsto f(x),$

is called strictly increasing if for all ${}x_{1},x_{2}\in \mathbb {R}$ satisfying ${}x_{1}<x_{2}$, also ${}f(x_{1})<f(x_{2})$ holds. Show that a strictly increasing function ${}f$ is injective.

Exercise

Is the mapping

$\mathbb {Q} _{\geq 0}\longrightarrow \mathbb {Q} _{\geq 0},x\longmapsto x^{2},$

injective? Is it surjective?

Exercise

Is the mapping

$\varphi \colon \mathbb {N} _{+}\times \mathbb {N} _{+}\longrightarrow \mathbb {N} _{+}\times \mathbb {N} _{+}\times \mathbb {N} _{+},(a,b)\longmapsto (a+b,ab,a^{b}),$

injective, or not?

Exercise

Determine the compositions ${}\varphi \circ \psi$ and ${}\psi \circ \varphi$ for the mappings ${}\varphi ,\psi \colon \mathbb {R} \rightarrow \mathbb {R}$ that are defined by

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

Exercise

Let ${}L,M,N$ be sets, let ${}F\colon L\rightarrow M$ and ${}G\colon M\rightarrow N$ denote surjective mappings. Show that the composition ${}G\circ F$ is also surjective.

Exercise

Let ${}L,M,N$ be sets, let ${}F\colon L\rightarrow M$ and ${}G\colon M\rightarrow N$ denote injective mappings. Show that the composition ${}G\circ F$ is also injective.

Exercise *

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

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

be mappings 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 all possible parties (with respect to the guests). For Exercise 2.16 , one might think of ${}A=$ ladies in the course, ${}B=$ gentlemen in the course.

Exercise

Let ${}G$ be a set, and ${}{\mathfrak {P}}\,(G)$ its power set. Show that the mapping

${\mathfrak {P}}\,(G)\longrightarrow {\mathfrak {P}}\,(G),T\longmapsto \complement T,$

is bijective. How does the inverse mapping look?

Exercise

Let ${}G$ be a set. Define a bijection between

${\mathfrak {P}}\,(G)\,\,{\text{ and }}\,\,\operatorname {Map} \,{\left(G,\{0,1\}\right)}.$

Exercise

Let ${}G$ be a set, which is given as a disjoint union

${}G=A\uplus B\,.$

Define a bijection between the power set ${}{\mathfrak {P}}\,(G)$ and the product set ${}{\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B)$.

Exercise

Let ${}M,N,L$ denote sets. Define a bijection between

$\operatorname {Map} \,{\left(M\times N,L\right)}\,\,{\text{ and }}\,\,\operatorname {Map} \,{\left(M,\operatorname {Map} \,{\left(N,L\right)}\right)}.$

Exercise

How can we visualize the graph of a mapping

$\varphi \colon \mathbb {R} ^{2}\longrightarrow \mathbb {R} ,$

and the graph of a mapping

$\varphi \colon \mathbb {R} \longrightarrow \mathbb {R} ^{2}?$

Exercise

Let ${}F\colon L\rightarrow M$ denote a mapping. Show that taking preimages

${\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(L),T\longmapsto F^{-1}(T),$

fulfills the following properties (for arbitrary subsets ${}T,T_{1},T_{2}\subseteq M$):

1. ${}F^{-1}(T_{1}\cap T_{2})=F^{-1}(T_{1})\cap F^{-1}(T_{2})\,,$

2. ${}F^{-1}(T_{1}\cup T_{2})=F^{-1}(T_{1})\cup F^{-1}(T_{2})\,,$

3. ${}F^{-1}(M\setminus T)=L\setminus F^{-1}(T)\,.$

Exercise

Let ${}F\colon L\rightarrow M$ be a mapping. Show that taking images

${\mathfrak {P}}\,(L)\longrightarrow {\mathfrak {P}}\,(M),S\longmapsto F(S),$

satisfies the following properties (for arbitrary subsets ${}S,S_{1},S_{2}\subseteq L$):

1. ${}F(S_{1}\cap S_{2})\subseteq F(S_{1})\cap F(S_{2})$,
2. ${}F(S_{1}\cup S_{2})=F(S_{1})\cup F(S_{2})$,
3. ${}F(L\setminus S)\supseteq F(L)\setminus F(S)$.

Show by examples that the inclusions in (1) and (3) might be strict.

Exercise

Let ${}L$ and ${}M$ denote sets, and let

$F\colon L\longrightarrow M$

be a mapping. Show that ${}F$ is injective if and only if taking preimages

${\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(L),T\longmapsto F^{-1}(T),$

is surjective.

Exercise

Let ${}L$ and ${}M$ denote sets, and let

$F\colon L\longrightarrow M$

be a mapping. Show that ${}F$ is surjective if and only if taking preimages

${\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(L),T\longmapsto F^{-1}(T),$

is injective.

The idea of the following exercises came from http://jwilson.coe.uga.edu/emt725/Challenge/Challenge.html, also take 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}$

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

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

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

3. Show that ${}\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}$

that 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}$

that 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 {Q} _{\geq 0}^{4}\longrightarrow \mathbb {Q} _{\geq 0}^{4}$

that assigns to a four-tuple of nonnegative rational numbers ${}(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 after finitely many iterations, this mapping yields the zero-tuple.

We will later deal with the question of how this mapping behaves with respect to real four-tuples; see in particular Exercise 23.16 .

Hand-in-exercises

Exercise (3 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 (3 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 mappings with their composite mapping

$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 mapping

$\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 (5 marks)

Let ${}L$ and ${}M$ denote sets. We consider the mapping

$\Psi \colon \operatorname {Map} \,{\left(L,M\right)}\longrightarrow \operatorname {Map} \,{\left({\mathfrak {P}}\,(M),{\mathfrak {P}}\,(L)\right)},f\longmapsto f^{-1},$

which assigns to a mapping the mapping given by taking preimages.

a) Show that ${}\Psi$ is injective.

b) Suppose ${}L\neq \emptyset$. Show that ${}\Psi$ is not surjective.

Exercise to give up

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

Exercise (8 marks)

We consider the mapping

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

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