Formal MethodsHomework Assignment 13, Part 2Due Wednesday, May 9, 20071. Which of the following relations are functions?(a) f = {(x, y) ⊆ R × R : y =√x2+ 1}.This is a function. For each real number, x, there is exactly one real number y such thaty =√x2+ 1. For suppose that x, y1, and y2are real numbers such that y1=√x2+ 1 =y2. Then by simple transitivity of equality, we get that y1= y2.(b) g = {(m, n) ⊆ Z+× Z+: m divides n}.This is not a function. For example, (2, 2) and (2, 4) both belong to g, since 2|2 and 2|4.(c) h = {(m, n) ⊆ Z × Z : m + n is even }.This is not a function. For example, (0, 0) and (0, 2) both belong to h since 0 + 0 = 0and 0 + 2 = 2 are even.2. Define A = {A ⊆ Z : A is nonempty and finite }. If A ∈ A, define f(A) to be the sum of theelements of A. For example, if A = {1, 3, 6}, then f(A) = 10. Note that f ⊆ A × Z.(a) What is the domain of f?The domain of f is A. We can form the sum of any finite set of integers and get anotherinteger. That is, if A ∈ A, then since A is finite and nonempty, |A| = n, where n is apositive integer. Then if the elements of A are a1, a2, . . . , an, we can computef(A) =nXi=1ai,and since each ai∈ Z, i = 1, 2, . . . , n, f(A) ∈ Z.(b) What is the range of f?The range of f is Z. For each n ∈ Z, {n} ∈ A and f({n}) = n.(c) Is f one-to-one? Explain your answer.No, f is not one-to-one. For example, {0} and {−1, 1} both belong to A, but f({0}) =0 = f({−1, 1}).3. f ⊆ {1, 2, 3, 4} × {1, 2, 3, 4} is a function with domain {1, 2, 3, 4}. If f is symmetric, andf(1) = 4, what are the possibilities for f? (Write down the ordered pairs that belong to f.)Since f (1) = 4, and f is symmetric, we must have that f(4) = 1. Since the domain of f is{1, 2, 3, 4}, we only need to specify f (2) and f(3). First observe that we can’t have f (2) = 1,for then by symmetry, we’d have f (1) = 2, and f wouldn’t be a function. Similar reasoning1shows that f(2) 6= 4, and f(3) /∈ {1, 4}. So the possibilities are f(2) = 2 and f(2) = 3. Iff(2) = 2, then we must have f(3) = 3, for if f(3) = 2, then by symmetry, we’d have f(2) = 3,and f wouldn’t be a function. If f(2) = 3, then by symmetry, we must have f(3) = 2.To summarize, the possibilities for f aren 1 2 3 4f(n) 4 2 3 1f(n) 4 3 2 14. Suppose f and g are functions. Suppose also that• Dom(f) = Dom(g), and• f(x) = g(x), for all x ∈ Dom(f).Prove that f = g.Proof. We need to show that for each (x, y) ∈ f, (x, y) ∈ g, and, conversely, for each(x, y) ∈ g, (x, y) ∈ f. So suppose (x, y) ∈ f, i.e., f(x) = y. Then x ∈ Dom(f), and sinceDom(f) = Dom(g), x ∈ Dom(g). Furthermore, since f(x) = g(x) for all x ∈ Dom(f ), wemust have that g(x) = f(x) = y. So (x, y) ∈ g. The converse is similar.5. Suppose that f ⊆ X ×Y is a one-to-one function. Prove that f−1is also a function.Proof. Suppose that f is one-to-one. We need to see that f−1is a function. So we need tosee that if (y, x1), and (y , x2) belong to f−1, then x1= x2. By definitionf−1= {(y, x) ∈ Y × X : (x, y) ∈ f}.So if (y, x1) and (y, x2) belong to f−1, then both (x1, y) and (x2, y) belong to f. But f isone-to-one. So whenever (x1, y) and (x2, y) belong to f, x1= x2. Thus, if f is one-to-one,then f−1is a
View Full Document