Book: Chapter 2 and 3 (t.o.m. 3.5). Lecture: Monday, week 1.

Some answers are available.

The idea is that you should prepare these exercises at home, by yourself or with your group. If you have any questions, you can come to the exercise session and ask them to the assistants. (If you do not prepare in advance, there is little point in coming!)

Make sure you are comfortable with the following before you start the next exercises:

Chapter 2: 2.1, 2.2, 2.4, 2.13.

Chapter 3: 3.5, 3.7, 3.12, 3.14, 3.17, 3.19.

Now, please think about these.

1. Give an example of a function f : ℕ -> ℕ that is injective but not surjective. Explain why it is injective and why it is not surjective.

2. Give an example of a function g : ℕ -> ℕ that is surjective but not injective. Explain why it is surjective and why it is not injective.

3. Let A = {1,2,3,4,5}. Can you find a function f : A -> A that is injective but not surjective? Explain.

4. Which of the following set operations: union, intersection ("snitt"), difference are associative and/or commutative?

5. Find a bijection between the set of natural numbers ℕ and the cartesion product 𝔹 x ℕ between the booleans 𝔹 and ℕ. Now, find a bijection between ℕ and ℤ, showing that there are as many natural numbers as integer numbers ("heltal").

6. How many elements does A x B have, expressed in the number of elements of A and the number of elements in B? How many elements does A -> B have? What can you say about the number of elements in A U B and A ∩ B?

7. Give an example of an operator f : ℕ x ℕ -> ℕ that is associative but not commutative. Explain.

8. Give an example of an operator f : ℕ x ℕ -> ℕ that is commutative but not associative. Explain.

9. Do your operators have an identity? Why / why not?

10. For your operators above, can you find elements that are each other's inverse? Why / why not?

These exercises are for students who are looking for a challenge.

1*. Show that all rational numbers ℚ fit into the Hilbert hotel. So: Describe a way to fill up every room in the Hilbert hotel with a rational number from ℚ, and explain why every rational number has a room.

Hint: Do it first only for the positive rational numbers. Then adapt your method to include all rational numbers.

2*. Show that the real numbers ℝ do not fit into the Hilbert hotel.

Hint: Not even the real numbers from the interval [0,1) fit. Almost the exact argument we used for the functions ℕ -> ℕ works here.