TÖL203F Algorithms, Logic and Complexity

Homework 1

The first homework will be slightly easier than usual, since it only covers the first lecture on monday January 6th.

Homework

1. Determine for each of the following statements whether it is true or false. Justify each case in a few words.
   1. {∅} ∈ {∅}
   2. {∅} ⊆ {∅}
   3. ∅ = {∅}
   4. ∅ ∈ {a}
   5. {a} ∈ {a}

2. Let A be a set and ℘(A) be the powerset of A.
   1. Let A be the set {1, 2, 3, 4, 5}. How many elements are in ℘(A)?
   2. If A is the empty set, then what is ℘(A)?
   3. Let A be the set {1, 2, 3}. Show the set ℘(℘(A)) (i.e. the power set of the power set of A)

3. Which of the following functions on the integers are one-to-one and which are onto (or both!):
   1. f(n) = 3n
   2. g(n) = 3 − n
   3. f(n) = n³

4. Let A be a set with m elements and B be another set with n elements.
   1. How many different functions are there from A to B?
   2. How many of those functions are one-to-one?
   3. When are there no one-to-one functions from A to B (i.e. what conditions do A and B have to fulfill for there to be one-to-one functions from A to B)?

5. Problem 1.2 on page 14 in the textbook.

Hand this homework in before 12:00 on friday January 10th.