Math 205a Fall Term 2002

Assignment 1

1. Form the negation of the following statements:

(i) ∀x ∈ A ∃ y ∈ B : (x, y) ∈ G . (ii) ∀x ∈ A ∃! y ∈ B : (x, y) ∈ G . (iii) ∃ y ∈ B : (x, y) ∉ G ∀x ∈ A . (iv) ∀n ∈ ℕ ∃ m ∈ ℕ : m ≥ n and m is prime.

2. Let A, B be non-empty sets. Then G ⊂ A × B determines a map f_{G} : A → B , x ↦ y iff

(x, y) ∈ G , (x, ỹ) ∈ G ⇒ y = ỹ.

If this is the case, then

dom(f) := {x ∈ A | ∃ y ∈ B with (x, y) ∈ G} , the domain of f , im(f) := {y ∈ B | ∃ x ∈ A with (x, y) ∈ G} , the range of f .

For x ∈ dom(f) we write y = f_{G}(x) if (x, y) ∈ G. Use quantifiers to describe the following:

(i) The map is one-to-one. (ii) The map is onto. (iii) The map is bijective. (iv) G̃ = {(y, x) ∈ B × A | (x, y) ∈ G} defines a set. What is fG̃ when it exists?

3. Let ℕ_{m} := {1, 2, …, m − 1, m}. How many maps f : ℕ_{m} → ℕ_{n} are there for m, n ∈ ℕ? How many are the bijections among them? [Consider the cases m < n , m = n , m > n separately.] Is the set map(ℕ, ℕ) := {f : ℕ → ℕ | f is a map} countable? What about map_{b}(ℕ, ℕ) := {f : ℕ → ℕ | f is a bijection}? Justify your answers.

4. In class we proved that ℕ × ℕ is countable. Can you construct a bijective map φ : ℕ → ℕ×ℕ explicitly? Also prove the more general statement that M × N is countable if M and N are and conclude that ℕ^{m} is countable for any m ∈ ℕ.

The Homework is due Friday, October 11