## Transcribed Text

1 Functions (15 P.)
Prove or disprove the following statements.
a) (4) Given the family of sets N%a = {x 2 N| x mod a = 0} with a 2 N+. There exists a bijection
f : N%x ! N%y for any pair x, y 2 N+.
The set N%x is the set of all (positive) multiples of x. So the set can also be written as {x, 2x, 3x, 4x, 5x, . . . }.
The same goes for N%y = {y, 2y, 3y, 4y, 5y,... }.
Now, you only need to define an identity function, which maps x to y, 2x to 2y and so on. I’ll leave it
to you as a task to find this identity function and prove its bijectivity.
b) (4) The function
fn : Nn ! Nn
x 7! (xn + 1) mod n
is bijective with Nn = {x 2 N| x n} for every n 2 N+.
The set Nn are just all natural numbers less or equal to n. So, N5 = {0, 1, 2, 3, 4, 5}. The function
fn has the set Nn as domain and codomain. Since the set Nn is finite for any n 2 N+, the function
is either bijective or neither injective nor surjective (but never just one of the two). As a last hint: The
function is not bijective. I’ll leave it up to you, to find a respective counterexample.
c) (7) There exists a bijection f : N ! N ⇥ N
You can imagine N as dots on the number-line and N ⇥ N as a grid of dots in a 2D plane (only
covering the upper right). This grid is also indicated in Figure 1.
Figure 1: Illustrative idea of how N ⇥ N looks like
From here on, you just have to find a plausible way to order these points, like “this is the first one,
this is the second one, that’s the third one” and so on. If you can find such a mapping, you also have
to show it’s bijective, but that’s again a task left for you.
1

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.