Question

Find a bijection \(f: \mathbb{N} \rightarrow \mathbb{Z}\). Hint: Find an \(f\) which maps even integers onto the positive integers and odd integers onto the negative integers.

Short answer

The function \(f\) defined by \(f(n) = n/2\) for even \(n\) and \(f(n) = -(n+1)/2\) for odd \(n\) is a bijection from \(\mathbb{N}\) to \(\mathbb{Z}\).

Step-by-step solution

Define the function \(f\)

First, we need to define the mapping function \(f: \mathbb{N} \rightarrow \mathbb{Z}\). From the given hint, we can have \(f(n) = n/2\) for even \(n\) and \(f(n) = -(n+1)/2\) for odd \(n\). This will map even integers in \(\mathbb{N}\) to positive integers in \(\mathbb{Z}\) and odd integers in \(\mathbb{N}\) to negative integers in \(\mathbb{Z}\).

Prove \(f\) is one-to-one (injective)

A function is injective if and only if every element in the domain maps to a unique element in the codomain. From the definition of \(f\), we can see that, for any distinct natural numbers \(n\) and \(m\) (\(n \neq m\)), \(f(n)\) will not equal to \(f(m)\) because if \(n\) is odd, then \(m\) is even and vice versa. Thus, \(f\) is an injective function.

Prove \(f\) is onto (surjective)

A function is surjective if every element in the codomain has a pre-imgae in the domain. From the definition of \(f\), it's clear that for any integer \(z\) in \(\mathbb{Z}\), we can find a corresponding natural number \(n\) in \(\mathbb{N}\). If \(z\) is positive, \(n=2z\) is even and \(f(n)=z\). If \(z\) is negative, \(n=-2z-1\) is odd and \(f(n)=z\). Hence, \(f\) is a surjective function.

Conclusion

Since \(f\) is both one-to-one (injective) and onto (surjective), it is indeed a bijection from \(\mathbb{N}\) to \(\mathbb{Z}\). Moreover, it satisfies the hint conditions with even integers in \(\mathbb{N}\) mapping to positive integers in \(\mathbb{Z}\) and odd integers in \(\mathbb{N}\) mapping to negative integers in \(\mathbb{Z}\).

Key concepts

Injective functions

An injective function, often referred to as a one-to-one function, is a type of mapping where each element of the domain is mapped to a unique element of the codomain. This means there are no two distinct elements in the domain that map to the same element in the codomain.
For a clearer understanding of injective functions, consider the following example:

• Imagine a classroom where each student has a unique ID number. In this scenario, if you know a student's ID, you can pinpoint exactly which student it belongs to, because no two students share the same ID.

To verify that a function is injective, you should ensure that if f(a) = f(b), then it must be true that a = b.
In our defined function, the distinct handling of natural numbers, whether odd or even, ensures that each number in the domain maps to a unique number in the codomain, thereby confirming its injectiveness.

Surjective functions

A surjective function, or onto function, covers the entire codomain. For a function to be surjective, every element in the codomain must be the image of at least one element from the domain.
In other words, there are no "unmapped" elements left in the codomain when the function is applied.

• Think of it like coloring a wall. A surjective function ensures that every spot on the wall gets covered exactly once by the paint.

In the solution exercise, the function is designed such that each integer in \(\mathbb{Z}\) is paired with precisely one number from \(\mathbb{N}\). By assigning even natural numbers to positive integers and odd natural numbers to negative integers, the function guarantees that every integer is hit, making the mapping surjective.

Natural numbers

Natural numbers, often denoted by \(\mathbb{N}\), are the set of positive integers starting from 1, and sometimes, they include 0 too. These are the numbers we use for counting and ordering.

• Examples include: 1, 2, 3, 4, 5, and so on.

Natural numbers are infinite, offering an endless supply of elements to work with in mathematical problems and functions.
In the given exercise, the idea is to map the infinitely growing list of natural numbers to all integers, positive and negative. Despite the infinite nature of \(\mathbb{N}\), ingenious mapping functions like the one defined, allow them to interact uniquely with other sets such as integers.

Integer mapping

Mapping integers, especially between infinite sets like the natural numbers \(\mathbb{N}\) and the integers \(\mathbb{Z}\), involves finding a function that appropriately pairs elements from one set to another.
The challenge lies in ensuring that all elements in the destination set (integers) are accounted for, creating a bijection where the function is both injective and surjective.

• In mathematics, bijection is a one-to-one and onto mapping, meaning that each element of a set pairs uniquely and exhaustively to elements in another set.

The function detailed in the exercise divides natural numbers into even and odd, pairing them systematically with integers such that:

• Even natural numbers map to positive integers
• Odd natural numbers map to negative integers

This even/odd strategy effectively covers all bases in the mapping challenge and ensures the successful construction of a bijection.