Injective Function
Understanding injective functions, commonly known as one-to-one functions, is essential when dealing with the concepts of function mapping in mathematics. An injective function ensures that each element in the domain maps to a unique element in the co-domain. In other words, no two distinct elements from the domain have the same image in the co-domain.
Let's make this clearer with an example: suppose we have two pairs of natural numbers \( (m_1, n_1) \) and \( (m_2, n_2) \). To qualify as injective, our function \(\varphi\) must have the property that if \(\varphi(m_1, n_1) = \varphi(m_2, n_2)\), then necessarily \(m_1 = m_2\) and \(n_1 = n_2\). In the context of our exercise, proving injectivity requires demonstrating that the function gives a distinct output for each distinct input pair from the natural numbers.
Surjective Function
A surjective function, also called an onto function, covers every element in the co-domain. To say a function is surjective means that every element in the function's co-domain is the output (image) of at least one input from the domain.
For the exercise at hand, we need to prove the surjectivity of the function \(\varphi\). This involves showing that for each natural number \(z\) in the co-domain \(\mathbb{N}\), there is at least one pair of numbers \( (m, n) \) from the domain \(\mathbb{N} \times \mathbb{N}\) such that \(\varphi(m, n) = z\). This ensures that every natural number is mapped to by the function, establishing its surjective nature.
Countably Infinite
When we describe a set as 'countably infinite,' we mean that it has infinite elements, but these elements can be counted in a sequence that pairs each element with exactly one natural number. Think of it as if you could list all the elements one by one without any left over, and that list could go on indefinitely.
In our exercise, we refer to the sets \(\mathbb{N}\) and \(\mathbb{N} \times \mathbb{N}\) as countably infinite. The goal of the exercise is to show that the pairing of natural numbers (which creates a new set, \(\mathbb{N} \times \mathbb{N}\)) still results in a set that is countably infinite.
Cardinality of Sets
The cardinality concept deals with the size of sets, allowing us to compare and measure them, even when they are infinite. A set's cardinality is essentially the number of elements within it. In finite sets, cardinality is the total count of distinct elements. But with infinite sets, cardinality helps us to understand different 'sizes of infinity'.
In the context of our discussion, by proving the given function \(\varphi\) is bijective, we are, in fact, establishing that the cardinality of \(\mathbb{N} \times \mathbb{N}\) and \(\mathbb{N}\) are the same, meaning they are equally infinite and can be paired one-to-one.
Natural Numbers
Natural numbers are the basic counting numbers starting from 1 and going upwards indefinitely (1, 2, 3, ...). They are the building blocks for more complex numbers and are used in everyday counting and simple transactions. The set of all natural numbers is denoted by \(\mathbb{N}\).
In our proof exercise, natural numbers are the elements being mapped from and onto. They are the domain and co-domain of our function \(\varphi\). Since natural numbers are countably infinite, they provide a perfect framework for demonstrating the concept of bijective functions and the equivalence in the 'size' of infinite sets.
