Construct a bijection f from N onto Z
Question
Construct a bijection f from N onto Z
Solution
Sure, let's construct a bijection f from the set of natural numbers N (which we'll take to include 0) onto the set of integers Z.
We want to map every natural number to an integer such that every integer is hit exactly once. One way to do this is to alternate between nonnegative and negative integers as we go through the natural numbers.
Here's a possible function:
f(n) = (-1)^(n+1) * ceil(n/2)
Let's break down how this function works:
-
The term (-1)^(n+1) alternates between 1 and -1 as n increases. It's 1 for odd n and -1 for even n.
-
The term ceil(n/2) is the smallest integer greater than or equal to n/2. This increases by 1 every two steps as n increases.
-
By multiplying these two terms together, we get a function that alternates between nonnegative and negative integers as n increases.
Here's how the function maps the first few natural numbers to integers:
f(0) = 0 f(1) = -1 f(2) = 1 f(3) = -2 f(4) = 2 f(5) = -3 f(6) = 3 ...
As you can see, every integer is hit exactly once by this function, so it's a bijection from N onto Z.
Similar Questions
5. Determine whether each of these functions from Z to Z is one-to-one (onto)a) f (n) = n − 1 b) f (n) = n2 + 1 c) f (n) = n3 d) 2nf n 6. Determine whether f : Z × Z → Z is onto ifa) f (m, n) = 2m − n b) f (m, n) = m2 − n2 c) f (m, n) = m + n + 1d) f (m, n) = |m| − |n| e) f (m, n) = m2 − 4 f) f (m, n) = m + n7. Determine whether each of these functions is a bijection from R to R.a) f (x) = −3x + 4 b) f (x) = −3x2 + 7 c) f (x) = (x + 1)/(x + 2) d) f (x) = x5 + 18. Let S = {−1, 0, 2, 4, 7}. Find f (S) ifa) f (x) = 1 b) f (x) = 2x + 1 c) 5xf x
If f:A→B is a bijective function and n(A)=6 then which of the following is not possible*Number of elements in range of f is 6n(A)=n(B)n(B)=6n(B)=8
6. Determine whether f : Z × Z → Z is onto ifa) f (m, n) = 2m − n b) f (m, n) = m2 − n2 c) f (m, n) = m + n + 1d) f (m, n) = |m| − |n| e) f (m, n) = m2 − 4 f) f (m, n) = m + n
Suppose T is an infinite set and t(1), t(2), . . . , t(n), . . . is an enu-meration of T . Show that T is countable by providing a bijection f : N →T , briefly explain why f is indeed injective and surjective
For each of the following functions, state whether it is injective, surjective, and/or bijective, and why.(a) The function f (n) = 2n, mapping from integers to integers.(b) The function q(ϕ), with codomain N≥0, which maps any formula of predicate logic to the number of quantifiersin that formula
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.