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

Exercise for the break

Exercise Create referencenumber

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 Create referencenumber

Give examples of mappingsMDLD/mappings

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

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

Exercise Create referencenumber

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

Exercise Create referencenumber

How can we recognize by looking at the graphMDLD/graph (map) of a mapping

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

whether ${}f$ is injectiveMDLD/injective or surjective?MDLD/surjective

Exercise Create referencenumber

Which bijectiveMDLD/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?MDLD/inverse function

Exercise Create referencenumber

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 Create referencenumber

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.MDLD/injective

Exercise Create referencenumber

Is the mapping

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

injective?MDLD/injective Is it surjective?MDLD/surjective

Exercise Create referencenumber

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,MDLD/injective or not?

Exercise Create referencenumber

Determine the compositionsMDLD/compositions (mapping) ${}\varphi \circ \psi$ and ${}\psi \circ \varphi$ for the mappingsMDLD/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 Create referencenumber

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

Exercise Create referencenumber

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

Exercise * Create referencenumber

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

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

be mappingsMDLD/mappings with their compositionMDLD/composition

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

Show that if ${}g\circ f$ is injective,MDLD/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 Create referencenumber

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

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

is bijective.MDLD/bijective How does the inverse mappingMDLD/inverse mapping look?

Exercise Create referencenumber

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

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

===Exercise Exercise 2.16

change===

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

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

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

Exercise Create referencenumber

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

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

Exercise Create referencenumber

How can we visualize the graphMDLD/graph (map) 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 Create referencenumber

Let ${}F\colon L\rightarrow M$ denote a mapping.MDLD/mapping Show that taking preimagesMDLD/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 Create referencenumber

Let ${}F\colon L\rightarrow M$ be a mapping.MDLD/mapping Show that taking imagesMDLD/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 Create referencenumber

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

$F\colon L\longrightarrow M$

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

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

is surjective.MDLD/surjective

Exercise Create referencenumber

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

$F\colon L\longrightarrow M$

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

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

is injective.MDLD/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 Create referencenumber

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 compositionMDLD/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 Create referencenumber

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 injectiveMDLD/injective and whether ${}\Psi$ is surjective.MDLD/surjective

Exercise Create referencenumber

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 Create referencenumber

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) Create referencenumber

Determine the composite functionsMDLD/composite functions ${}\varphi \circ \psi$ and ${}\psi \circ \varphi$ for the functionsMDLD/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) Create referencenumber

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

Exercise (3 marks) Create referencenumber

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

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

be mappingsMDLD/mappings with their composite mappingMDLD/composite mapping

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

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

Exercise (3 marks) Create referencenumber

Consider the set ${}M=\{1,2,3,4,5,6,7,8\}$, and the mappingMDLD/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) Create referencenumber

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.MDLD/taking preimages

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

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

Exercise to give up

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

Exercise (8 marks) Create referencenumber

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)