Determine which formulas below define surjections from N x N to N,and reason why

Question

Determine which formulas below define surjections from N x N to N,and reason why.

A) f(a, b) = a + b
B) f(a, b) = ab
C) f(a, b) = ab(b + 1)/2
D) f(a, b) = (a + 1)b(b + 1)/2
E) f(a, b) = ab(a + b)/2

Explanation / Answer

We need to show that for any y in N, there is some pair (a, b) in Nx N with f(a, b) = y. a) for any y, f(0, y) = y, so surjective. b) for any y, f(1, y) = y, so surjective. c) for any y, f(y, 1) = y, so surjective. d) for any y > 0, f(y - 1, 1) = y, and f(0, 0) = 0, sosurjective. e) We will prove that there is no pair (a, b) with f(a, b) =5. Suppose there were such a pair. Then ab(a + b) =10. Clearly neither a nor b can be 0, for then the product onthe left would be 0. So, a, b and a + b are divisors of10. The only choices for a, b, and a + b are among 1, 2, 5,10. The only choice for a and b among these divisors thatmakes a + b also a divisor is a = b = 1. But then the productab(a + b) is only 2. So f(a, b) = 5 is impossible. Thusf is not surjective in this case.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.