Exercises Week 1 - Sets and Functions
Preparation
Lecture: Monday, week 1.
Read: Lemurell and Jonasson Chapter 2 and 3 (t.o.m. 3.5).
Read: Lehman, Leighton, and Meyer: Chapter 4.1-4.3.
Basic Exercises from the Book
Make sure you are comfortable with the following before you start the exercises:
Lemurell and Jonasson: Chapter 2: 2.1, 2.2, 2.4, 2.13. Chapter 3: 3.5, 3.7, 3.12, 3.14, 3.17, 3.19.
Lehman, Leighton, and Meyer: Chapter 4: Problem 4.1 (powerset), 4.36 (compare domain and co-domain sizes).
Exercises
(1.) Give an example of a function \(f : \mathbb{N} \rightarrow \mathbb{N}\) 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 : \mathbb{N} \rightarrow \mathbb{N}\) 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 \rightarrow 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 \(\mathbb{N}\) and set of integers \(\mathbb{Z}\), showing that there are as many natural numbers as integer numbers ("heltal").
(6.) How many elements does \(A \times B\) have, expressed in the number of elements of A and the number of elements in B? How many elements does \(A \rightarrow B\) have? What can you say about the number of elements in \(A \cup B\) and \(A \cap B\)?
(7.) Give an example of an operator \(\star : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) that is associative but not commutative. Explain.
(8.) Give an example of an operator \(\star : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) 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?
Starred Exercises
These exercises are for students who are looking for a challenge.
(1*.) Show that all rational numbers \(\mathbb{Q}\) fit into the Hilbert hotel. So: Describe a way to fill up every room in the Hilbert hotel with a rational number from \(\mathbb{Q}\), 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 \(\mathbb{R}\) 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 \(\mathbb{N} \rightarrow \mathbb{N}\) works here.