211L10Solutions

Lecture 10

1. Consider the partial functions defined below. Find the domain and the range of each of the functions.

• (a) The partial function f : N -> N is such that for every natural number n, f outputs k only when n = 2k where k is a natural number.

Domain: All even natural numbers Range: All even natural numbers greater than 2

• (b) The partial function f : Z . Z is such that for every integer n, if n <= 0, then f(n) = -n; if n > 5, then f(n) = n.

Domain: All integers less than 1 and greater than 5 Range: All natural number

• (c) The division function d : Q2 . Q, where d(n,m) = n m if m 6= 0.

2. Let f : A -> B be a partial function. We say that a function g : A -> B extends f if g is total and for every a . A it must be the case that g(a) = f(a) whenever f(a) is defined. Prove that every partial function f : A -> B can be extended if B != Ø.

Since B != Ø, there exists b from B. Define the function. g(a) is such that it is f(a) where f(a) is defined. Where f(a) is not defined, it is b.

3. Consider the function f : Z2 . Z2 defined as follows. For (x, y) . Z2: If both x and y are even or both x and y are odd then f(x, y) = (x, y+1); Otherwise f(x, y) = (x+1, y). Prove that f is a bijective function.

4. Let A and B be two finite sets. Show that there exists a bijective function f : A . B if and only if A and B have the same number of elements.

5. Let f : Z . Z be the function defined as: f(n) = (-1)n + n. Prove that f is a bijective function.

6. Let A be a set. Consider the set of all functions from A into {0, 1}. This set is denoted by 2A. Prove that there exists a bijective function from P(A) to 2^A. The power set of {1} has two elements. P({1})={{},{1}}. Let the function be that for every {1} the answer is 1, and 0 otherwise. This is injective because for each of the 0 and 1, there is only one input from the power set which gives each value. It is also surjective because for every element in 2^A there is an element from the power function which gives that element.

7. Give an example of a bijective function f from N to Z. An example of a bijective function from N to Z, is for the Element 0 in N, let this go to the element 0 in z. Let the first odd number in N equal the first negative number in Z and the first even number in N be the first positive number in Z. Continue for the second even number going to the second positive and the second odd number going on to the second negative number. There is a one-to-one correspondence as every element in Z has a unique corresponding element in N and every element in both sets is mapped.

8. Give an example of a bijective function from N to N^2.

(0,2) (1,2) (2,1)
(0,1) (1,1) (2,1)
(0,0) (1,0) (2,0)

The function where 0 maps to (0,0), 1 maps to (0,1), 2 maps to (1,1). 3 to (1,0) and so on in a spiral. Every element is mapped to a unique element on the opposite end of the function.

9. Prove that the composition of onto functions is onto. Let f:A->B, g:B->C.

If f is onto, then every element in B has a source in A. And since no element in A can go to more than one element in B, then B <= A. The same ca be said for g assuming g is also onto, where C <= B. Since C <= B <= A, C <= A. For every element in C there has to be a unique element in A for which the element in C is mapped to through the composition of onto functions.

10. Prove that the composition of injective functions is injective.

11. Draw transition diagrams of the transition functions presented in Tables 3 and 4.

12. Let E be an equivalence relation on N. The factor set defined by E is the set of all E- equivalence classes. Denote the factor set by N/E. Call a number n . N a representative if n is the minimal element in the equivalence class containing n. Prove that there exists a bijection between the factor set and the set of all representatives.