Blogs, Mathematical Reasoning, MR Study Help

Bijective mappings

As we continue to look at proof, we will be working on showing that sets have different types properties. In this case, we will be looking at relations between sets.  In particular, we will show that a given relation is a bijective mapping.

Bijection

Here we let \(f:\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \to \mathbb{Z}\) be defined as \(f(m,n)=(5m+4n,4m+3n)\).   In order to show that \(f\) is bijection from \(\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}\) we will have to show that \(f\) is

  • a well-defined mapping,
  • a one-to-one, or injective, mapping,
  • a onto, or surjective, mapping.

Similar to the technique we used in Equivalence Relations and Partitions, we will focus one of these properties at a time so that we are not overwhelmed by everything that needs to be done.

Well-defined

In order to show that \(f\) is well-defined, we need to show that everything in the domain is mapped to exactly one thing in the range. That is, we will have to following.

Assume Show
\((m,n) \in \mathbb{Z} \times \mathbb{Z}\). \((5m+4n,4m+3n)\) is uniquely defined in \(\mathbb{Z} \times \mathbb{Z}\).
\(m,n \in \mathbb{Z}\) \(5m+4n\) and \(4m+3n\) are uniquely defined in \(\mathbb{Z}\).

Therefore, in order to show that \(f\) is well-defined, we just need to show that both \(5m+4n\) and \(4m+3n\) are both integers and are uniquely determined. However, this follows directly from the fact that the integers are defined to be closed under addition and multiplication. We are now ready to give our proof.

Proof

Let \((m,n) \in \mathbb{Z}\). Then \(m,n \in \mathbb{Z}\). Furthermore, since the integers are closed under addition and multiplication, this means that \(5m+4n, 4m+3n \in \mathbb{Z}\) and are uniquely defined. Hence, \((5m+4n, 4m+3n)\) is uniquely defined in \(\mathbb{Z} \times \mathbb{Z}\), so \(f\) is a well-defined mapping.

Onto

We will next try to show that \(f\) is onto. In order to show that \(f\) is onto, we must show that for anything in the co-domain, there exists something in the range that gets mapped to it. That is, we need to show that for every \((x,y)\) in the co-domain \(\mathbb{Z} \times \mathbb{Z}\), there exists a \((m,n)\) in the domain \(\mathbb{Z} \times \mathbb{Z}\) such that \(f(m,n)=(x,y)\). That is, we need to find \((m,n)\) with
\begin{align*}
f(m,n)&=(x,y) \\
(5m+4n,4m+3n)&=(x,y).
\end{align*}
Since these are ordered pairs, this means that we need both terms to be the same. Therefore, we need to solve the system of equations
\begin{align*}
5m+4n&=x \\
4m+3n&=y.
\end{align*}There are multiple techniques for solving systems of equations, including substitution, elimination by addition and matrices. While you may use any technique you like, we will be using matrices here. In order to create a matrix, we pull the coefficient off each of the variables on left and right so that each equation has an \(m,n,x\) and \(y\) in it. We then get
\[\begin{bmatrix}
5 & 4 & 1 & 0 \\
4 & 3 & 0 & 1
\end{bmatrix}\] Now that we have created our matrix, we will need to row reduce it so that we are left with the coefficients of \(m\) and \(n\) as \(1\) or \(0\). In order to do this we will first divide the first row by \(5\). This give us
\[\begin{bmatrix}
1 & \frac{4}{5} & \frac{1}{5} & 0 \\
4 & 3 & 0 & 1
\end{bmatrix}\] We will then subtract 4 times the first row from the second row and get
\[\begin{bmatrix}
1 & \frac{4}{5} & \frac{1}{5} & 0 \\
0 & -\frac{1}{5} & -\frac{4}{5} & 1
\end{bmatrix}\] Now, we can multiply the second row by \(-5\).
\[\begin{bmatrix}
1 & \frac{4}{5} & \frac{1}{5} & 0 \\
0 & 1 & 4 & -5
\end{bmatrix}\] Finally, we subtract \(\frac{4}{5}\) of the second row from the first row to get
\[\begin{bmatrix}
1 & 0 & -3 & 4 \\
0 & 1 & 4 & -5
\end{bmatrix}\]If we now convert this back into a system of equations, we will note that we need
\begin{align*}
m&=-3x+4y \\
n&=4x-5y.
\end{align*}We are now ready to prove that \(f\) is onto.

Proof

Let \((x,y) \in \mathbb{Z} \times \mathbb{Z}\). Now let \(m=-3x-4y\) and \(n=4x+5y\). Then note that, since the integers are closed under addition and multiplication, we have that \(m,n \in \mathbb{Z}\). Therefore, \((m,n) \in \mathbb{Z} \times \mathbb{Z}\). Now, note that
\begin{align*}
&f(m,n) \\
&=f(-3x+4y,4x-5y) \\
&=(5(-3x+4y)+4(4x-5y), 4(-3x+4y)+3(4x-5y)) \\
&=(-15x+20y+16x-20y, -12x+16y+12x-15y) \\
&=(x,y).
\end{align*}
Therefore, \(f\) is an onto function.

One-to-one

The last property we need to show is that \(f\) is one-to-one. Here, we will assume that \(f(m,n)=f(x,y)\) and we will need to show that \(m,n)=(x,y)\). That is, we get that assume the following.
\begin{align*}
f(m,n)&=f(x,y) \\
(5m+4n,4m+3n) &=(5x+4y,4x+3y).
\end{align*}Since these are ordered pairs we get that each of the components must be the same, so we get that the following system of equations must be true.
\begin{align*}
5m+4n&=5x+4y \\
4m+3n&=4x+3y.
\end{align*}From this, we will need to derive that \(m=x\) and \(n=y\). Since we have a system of equations, the process for doing this is very similar to what we had when showing onto. That is, we can construct a coefficient matrix and row reduce it in order to arrive at an equivalent system of equations which will provide our proof. Instead of working through these calculations twice, we will now give our proof.

Proof

Let \((m,n),(x,y) \in \mathbb{Z} \times \mathbb{Z}\) such that \(f(n,m)=f(x,y)\). We then note that
\begin{align*}
(5m+4n,4m+3n)&=(5x+4y,4x+3y) \text{ so, } \\
5m+4n&=5x+4y \text{ and } \\
4m+3n&=4x+3y.
\end{align*}We will now use the coefficient matrices to find an equivalent system of equations through row operations. We now see that,
\[\begin{bmatrix}
5 & 4 & 5 & 4 \\
4 & 3 & 4 & 3
\end{bmatrix}\]We now take \(\frac{1}{5}\) times row one and plug it in for row one.\[\begin{bmatrix}
1 & \frac{4}{5} & 1 & \frac{4}{5} \\
4 & 3 & 4 & 3
\end{bmatrix}\]Next, we take \(-4\) times row one and add it to row two and get\[\begin{bmatrix}
1 & \frac{4}{5} & 1 & \frac{4}{5} \\
0 & -\frac{1}{5} & 0 & -\frac{1}{5}
\end{bmatrix}\]Next, we multiply row two by \(-5\) and place this in row two.\[\begin{bmatrix}
1 & \frac{4}{5} & 1 & \frac{4}{5} \\
0 & 1 & 0 & 1
\end{bmatrix}\]

Finally, we take \(-\frac{4}{5}\) times row two and add it to row one. This give us,\[\begin{bmatrix}
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1
\end{bmatrix}\]

Therefore, the original system of equations is equivalent to the system
\begin{align*}
m&=x \\
n&=y.
\end{align*}Therefore, \((n,m)=(x,y)\), so \(f\) is one-to-one.

Inverse

Note that in the process of showing that this mapping was one-to-one and onto, we ended up finding the inverse mapping of \(f\). If we recall that a function is bijective if and only if it is invertible, we could have shown that \(f\) was both one-to-one and onto all at once just by showing that an inverse function exists. While the above proof is valid, we will look at how this approach would have worked.When finding the inverse, we again would have to let \(f(n,m)=(x,y)\), then solve for \((n,m)\) in terms of \((x,y)\). Note that this is exactly what we did when showing that \(f\) was onto, so our inverse mapping would be \(g(x,y)=(-3x+4y,4x-5y)\).

We would note that this is a well-defined function from \(\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}\) because, for every \(x,y \in \mathbb{Z}\) we have that both \(-3x+4y\) and \(4x-5y\) are well-defined integers. The only thing left to do is show that these are inverse functions, so we are ready to prove that \(f\) is invertible.

Proof

Let \(f: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}\) be given by \(f(m,n)=(5m+4n,4m+3n)\). Then let \(g:\mathbb{Z} \times \mathbb{Z} \to \mathbb{Z} \times \mathbb{Z}\) be given by \(g(m,n)=(-3m+4n, 4m-5n)\). We note that these are both well-defined functions since the set of integers is closed under multiplication and addition.Furthermore, we have that
\begin{align*}
&f(g(m,n)) \\
&=f(-3m+4n,4m-5n) \\
&=(5(-3m+4n)+4(4m-5n),4(-3m+4n)+3(4m-5n)) \\
&=(-15m+20n+16m-20n, -12m+16n+12m-15n) \\
&=(m,n).
\end{align*}
We also have that
\begin{align*}
&g(f(m,n)) \\
&=g(5m+4n,4m+3n) \\
&=(-3(5m+4n)+4(4m+3n),4(5m+4n)-5(4m+3n)) \\
&=(-15m-12n+16m+12n,20m+16n-20m-15n) \\
&=(m,n).
\end{align*}
Hence, \(f\circ g=g \circ f =\iota\), so \(g=f^{-1}\). Furthermore, since \(f^{-1}\) exists, we have that \(f\) is invertible and is therefore one-to-one and onto. Thus, \(f\) is a bijection.

Conclusion

In this situation we wanted to show that a given relation between two sets was a well-defined bijective mapping. As we did so, we noted that there were multiple ways to do this. While any one of these is sufficient it is helpful to be able to see how to do both. If you can do this, then you have multiple options when trying to write your proofs.For more help with proofs, make sure to continue working on the other problems we have posted solutions for in Study Help.

If you find these helpful, make sure to let other people know about them so that they can get help as well.If you would like to learn more about matrices in particular and linear algebra in general, I will be teaching a linear algebra course over the summer. If you are a VCU student, I would love to have in you class, but even if you don’t take the class, feel free to read the posts and follow along with the class on the website.

1 thought on “Bijective mappings”

We'd love to hear your thoughts!

This site uses Akismet to reduce spam. Learn how your comment data is processed.