# Homework 1

In the lectures this first week we will cover material from Chapter 1 of Computability and Logic, 5th ed.

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) = n3

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.

hh (hja) hi.is, January 6th, 2014.