PLP An introduction to mathematical proof

Recall that the only way an implication is false is if its conclusion is false while its hypothesis is true. So, \(P\implies (Q\land R)\) being false means that \(Q\land R\) is false while \(P\) is true. Note that \(Q\land R\) being false means that at least one of \(Q\) and \(R\) are false

Consider the second implication, \(\big((\neg Q)\land R\big) \implies (\neg P)\text{,}\) which is true. Since \(P\) is true, the conclusion of this implication, \(\neg P\) is false. But this means that the hypothesis, \((\neg Q)\land R\) is false, by modus tollens. More explicitly, if the hypothesis were true while the conclusion is false, then the implication is false, but if the hypothesis and conclusion are both false, then the implication is true. Therefore, at least one of \(\neg Q\) and \(R\) are false.

We have determined that at least one of \(Q\) and \(R\) are false, and at least one of \(\neg Q\) and \(R\) are false. In order for both of these conditions to be satisfied, \(R\) must be false. If \(R\) were true, then both \(Q\) and \(\neg Q\) would necessarily be false, which is impossible!

We cannot determine the truth value of \(Q\) from the information given. While \(P\) must be true and \(R\) must be false, \(Q\) can be true or false. We show how you can verify this:

Alternatively, we could determine the answer by analyzing the truth tables of the two implications.

The second and fourth rows are the only rows where the first implication is false, and the second true. In both these rows, \(P\) is true and \(R\) is false, so the truth values of these statements are determined. Since \(Q\) is true in the second row, but false in the fourth row, we cannot determine the truth value of \(Q\text{.}\) Either \(P\) is true, \(Q\) is true, and \(R\) is false, or \(P\) is true, \(Q\) is false, and \(R\) is false.

Since \(S\) is true, \(\neg S\) is false, and consequently the conclusion of the implication, \(Q\land (\neg S)\text{,}\) is false. But since the implication is true, its hypothesis \(R\lor(\neg P)\) must also be false. If the hypothesis were true while the conclusion were false, then the implication would be false.

Since \(R\lor(\neg P)\) is false, both \(R\) and \(\neg P\) are false. So \(R\) is false while \(P\) is true.

Finally, we use that \(P \iff \big(Q\lor (\neg S) \big) \) is true. Since \(P\) is true, \(Q\lor (\neg S) \) must also be true. But \(\neg S\) is false, so \(Q\) must be true.

We have deduced that \(P\) and \(Q\) are true while \(R\) is false.

Alternatively, we could solve this question by analyzing the truth tables of the implication and biconditional. We only include the rows where \(S\) is true, since this is given in the question.

The only row in which the implication and biconditional are true is row 2, so we look at this row to discern the truth values of \(P\text{,}\) \(Q\text{,}\) and \(R\text{:}\) \(P\) is true, \(Q\) is true, and \(R\) is false.

Notice that the second solution is really just a reordering of the steps given in the first question. Since the initial deductions we made from the biconditional being true and the implication being false were independent of each other, we could make these deductions in either order. The last solution is different: rather than making logical deductions from the information given, we use the truth table to look at every possible case for the truth values of \(P\text{,}\) \(Q\text{,}\) and \(R\text{,}\) and look for the cases where the conditions given in the question are satisfied.

We see that this is a conditional statement, and to prove it, we are going to assume that the hypothesis is true and show that the conclusion follows. This means that we assume that \(n\) is an even number and show that \(n^2+3n+5\) is odd.

This means that, we have an assumption and we need to understand what this assumption means by using the definitions and extracting useful expressions, i.e. structures we can work with.

In this question, since \(n\) is even, we know that \(n=2k\) for some \(k\in\mathbb Z\text{.}\) This is a nice structure and we can build upon it. Now, since we want to show that \(n^2+3n+5\) is odd, we can try to see what this expression is equal to given the assumption, \(n=2k\text{.}\)

We see that \(n^2+3n+5=(2k)^2+3(2k)+5=2(2k^2+3k+2)+1\text{.}\) Then, using the definition of even and odd, we see that \(n^2+3n+5\) is an odd number since \(2k^2+3k+2\in\mathbb{Z}\text{.}\) This is what we wanted to show.

Of course, we don’t need this much explanation in the actual proof. So, let’s clear this up and turn this into a nice proof.

Here, we are going to rely on the definitions again to get as much information as we can from our assumption. Since \(m\) and \(n\) are odd, we know that \(m=2k+1\) for some \(k\in\mathbb Z\) and \(n=2\ell+1\) for some \(\ell\in\mathbb Z\text{.}\) Using this structure, we can get a nice expression for \(mn\text{.}\)

We see that \(mn=(2k+1)(2\ell+1)=2(2k\ell+k+\ell)+1\text{.}\) Then, using the definition of even and odd functions, we see that \(mn\) is an odd number since \(2k\ell+k+\ell\in\mathbb{Z}\text{.}\) This is what we wanted to show. Let’s clean this up.

With this scratchwork we can write a formal proof to the statement, “the sum of two odd numbers is even.” The solutions to the remaining parts can be determined using the same logic: first, we’ll suppose that \(m\) and \(n\) are two integers whose parity is given. We can then write out \(m\) in the form \(2k\) if its even, or \(2k+1\) if its odd, and similarly for \(n\) (although we should be careful not to reuse the variable \(k\) in our expression for \(n\)). Using these expressions we can then obtain an expression for \(m+n\) or \(mn\text{.}\) Then we manipulate this expression so that it’s either in the form \(2p\) or \(2p+1\text{,}\) where \(p\) is an integer, to determine if it is even or odd.

This may look slightly harder then the previous questions since it involves \(5\) different variables and a conjunction (an “and”) statement. But, since this is a conditional statement, our strategy is going to be the same. We are going to assume the hypothesis to be true and show the conclusion.

So, we assume that \(n\mid a\) and \(n\mid b\text{.}\) This means that \(a=nk\text{,}\) and \(b=n\ell\) for some \(k,\ell\in\mathbb Z\text{.}\) Once we have these expressions, we can bo back and try to see what we wanted to prove again.

We see that we want to prove that \(n\mid (ax+by)\text{.}\) In other words, we want to prove \(ax+by=nm\) for some \(m\in\mathbb Z\text{.}\) Since we know that \(a=nk\text{,}\) and \(b=n\ell\text{,}\) we can write \(ax+by=nkx+n\ell y=n(kx+\ell y)\text{.}\) This is what we wanted to show. Let’s write this in a nice proof.

The hypothesis tells us that \(a=nk\) and \(a+1=n\ell\text{.}\) This means we can write \(1 = (a+1)-a = n\ell - nk = n(\ell-k)\text{.}\) But this means \(n \mid 1\text{.}\) This is the basis of our proof.

This is a conditional statement. To prove this, we need to assume that the hypothesis is true and show that the conclusion follows. This means that we assume \(3\mid a\) and \(2\mid a\) and show that \(6\mid a\text{.}\)

This is “one of those questions” where our previous knowledge may be misleading. We may want to say that since \(6=3\cdot 2\text{,}\) then if \(a\) is divisible by \(2\) and \(3\text{,}\) it should be divisible by \(6\text{.}\) But this would be a wrong chain of implications. Even though the result is true in this instance, it may be wrong if we change the numbers a little. For example, if we change \(3\) by \(4\text{,}\) that is, “If \(4\mid a\) and \(2\mid a\text{,}\) then \(8\mid a\)”, even though the previous chain of implications doesn’t change, the result doesn’t follow anymore (for an example you can see the statement is false for \(a=4\) ).

It is always preferable to use the definitions and the results we have proven to prove these statements. Let’s see what we can do.

Assume \(3\mid a\) and \(2\mid a\text{,}\) that is, \(a=2k\) and \(a=3m\) for some \(k,m\in\mathbb Z\text{.}\) Since we want to show that \(6\mid a\text{,}\) we can multiply both sides of the equation \(a=2k\) by \(3\) and both sides of the equation \(a=3m\) by \(2\) and get \(3a=6k\) and \(2a=6m\text{.}\) Then, subtracting the second form the first, we get \(a=3a-2a=6k-6m=6(k-m)\text{,}\) which is the desired result. Now, we can write this nicely in a proof.

Alternatively, assuming \(a=2k\) and \(a=3m\) for some \(k,m\in\mathbb Z\text{,}\) we can try to show that \(m=2\ell\) for some \(\ell\in\mathbb Z\text{.}\) We can do this by writing, \(a=2k=3m\text{,}\) and hence, \(2k-2m=2(k-m)=m\text{.}\) Therefore \(a=3m=6(k-m)\text{,}\) and the result follows.

To prove this conditional statement, we are going to assume the hypothesis to be true and show that the conclusion follows. That means, we assume that \(3\mid (n-4)\) and show that \(3\mid (n^2-1)\text{.}\)

We see that assuming \(3\mid (n-4)\) means that \(n-4=3k\) for some \(k\in\mathbb Z\text{,}\) and under this assumption, we want to show that \(3\mid (n^2-1)\text{,}\) that is, \(n^2-1=3m\) for some \(m\in\mathbb Z\text{.}\) This suggests that if we have an expression on \(n\) we can simply calculate \(n^2-1\) and get the desired result (alternatively, we could try to find a connection between \((n-4)\) and \((n^2-1)\)).

Since we know that \(n-4=3k\) for some \(k\in\mathbb Z\text{,}\) we see that \(n=3k+4\text{.}\) Thus, we get \(n^2-1= (3k+4)^2-1=(9k^2+24k+16)-1= 3(3k^2+8k+5)\text{,}\) which is what we wanted to show. Of course, in a proof we don’t need this much explanation. Indeed, we can write this explanation nicely in a proof.

Now, assume that \(a\) and \(b\) are integer roots. This means that there are natural numbers \(k,\ell\) and integers \(m,n\) such that \(a^k=n\) and \(b^\ell=m\text{.}\) Now, we are going to do the same trick we did in the example above to make the powers “same” so that we can multiply the bases. We see \(a^{k\ell}=n^\ell\) and \(b^{\ell k}=m^k\text{.}\) Thus, \((ab)^{k\ell}=n^\ell m^k\text{,}\) which is the desired result, since \(n^\ell m^k\in\mathbb Z\text{.}\) Now, we can write this in a proof.

It is a common (and easy to make) mistake to apply any operation on an inequality and implicitly assuming that the operation keeps the order of the inequality. Namely, if \(f(x)\) is a function and we know \(x\lt y\text{,}\) we may want to say \(f(x)\lt f(y)\text{.}\) Unfortunately this is not always true, and we have to be careful. This reasoning would only be true if the function \(f\) is an increasing function in the given domain; and this question tells us that \(f(x)=\sqrt{x}\) is, indeed, an increasing function.

We see that what we want to prove in this question is a conditional statement. So, we can assume the hypothesis and try to show the conclusion. So, we assume \(x\gt y\) and try to show that \(\sqrt{x} \gt \sqrt{y}\text{.}\) Since we cannot simply take the square roots of both sides (because of the above argument), we need to find a different way to prove the conclusion.

We see that this is a conditional statement and as we did in the previous chapters, we can try direct proof where we assume the hypothesis and show the conclusion. That means, we assume that \(n^2+4n+5\) is odd and show that \(n\) is even.

This means that we assume \(n^2+4n+5=2k+1\) for some \(k\in\mathbb Z\) and show that \(n=2m\) for some \(m\in\mathbb Z\text{.}\) However, to get from \(n^2+4n+5=2k+1\) to showing that \(n\) is even will not an easy task. It would require us to take a square root, and so we would also need to understand the effect of taking square root on the parity of the number. Oof! That would be a whole other exercise.

Trying to prove this statement directly doesn’t make sense, and instead we’re going to prove this statement by its contrapositive; that way, we will end up with a statement about what happens when \(5\) does divide an integer, and we can directly use the definition of that.

The contrapositive of this statement is: If \(5\mid n\text{,}\) then \(5\mid n^2\text{.}\) We’ve had plenty of practice proving statements like this.

In this question we see that we have a conditional statement. Hence, we can assume the hypothesis and try to show the conclusion. In other words, we can assume \(5\nmid n\) or \(2\nmid n\) and try to show that \(10\nmid n\text{.}\) But, we we have seen before, whenever we have a hypothesis that is an “or”-statement, we may need to look at cases. Moreover, since each part of the hypothesis is of the form \(a\nmid b\text{,}\) we may need to look at cases for those as well. This means that if we want to prove this statement using direct proof and cases, it may get very long. Also, when we have lots of cases, the chances of making a mistake go up.

We see that this is a conditional statement. First let \(n,m\in\mathbb N\text{.}\) So, to prove the statement, we can assume the hypothesis, i.e. \(n \neq 1\) and \(n \neq 2\) and show that \(n\nmid m\) or \(n \nmid (m+2)\text{.}\) However, the assumption doesn’t give us much to work with. We can try to look at cases to create more structure to work with, but unfortunately, it is also not clear what those cases should be.

We see that this is a conditional statement. To prove it, we can assume that \(n^2+m^2\) is even and try to show that then \(n,m\) have the same parity, that is, \(n,m\) are both odd or both even. We know that \(n^2+m^2\) being even means that \(n^2+m^2=2k\) for some \(k\in\mathbb Z\text{.}\) We see that it may not be trivial to get from this assumption to the conclusion on \(n,m\text{.}\) It would require us to take square-roots or solve a quadratic or something like that. Urgh.

Here, we also see that these cases are almost the same since the conclusion is symmetric with respect to \(n,m\text{.}\) So, practically, we will only need to prove one of case, and the other will be proven very similarly. So, we can use “WLOG” and prove only one of the cases. But, whenever you want to use “WLOG”, you should always convince yourself that the cases are similar by doing both possibilities and seeing just how similar they are. Let’s see how we can make this work in a proof.

If we were to provide a direct proof of this statement, we’d have to start with the inequality \(x^3+5x\geq x^2+1\) which would be difficult, since we have a cubic term. Instead we’re going to prove this statement by its contrapositive; this will allow us to assume that \(x\leq 0\text{,}\) and from that we will know the sign of powers of \(x\text{.}\)

The contrapositive of this statement is: If \(x\leq 0\text{,}\) then \(x^3+5x \lt x^2+1\text{.}\) Notice that the right-hand side is positive, since \(x^2 \geq 0\text{.}\) At the same time, since \(x \leq 0\text{,}\) we know that \(x^3 \leq 0\) and \(5x \leq 0\text{.}\) So the left-hand side is non-positive. Thus we can write \(x^3+5x \leq 0 \lt x^2+1\text{.}\) And now we have everything we need for the proof.

Proving things directly looks difficult, so we look at the contrapositive: If \(a\) and \(b\) are consecutive, then \(a+b\) is odd. Now we can use the definition of consecutive to prove things.

We see that this is a conditional statement. This means that we can assume the hypothesis and then we try to show the conclusion. Hence, we assume that \(n=2k\) for some \(k\in\mathbb Z\text{,}\) and show that \(n=4m\) or \(n=4m+2\) for some \(m\in\mathbb Z\text{.}\) However, when we wrote \(n=2k\) for some \(k\in\mathbb Z\text{,}\) we have extracted all the information from our assumption and we still need more to finish the proof.

Proof by cases is a very useful tool in situations like these since it creates extra structure for us to work with.

In this question, if we pay a little closer attention to the conclusion of the statement, we see that we want to show is \(n=4m=2(2m)\) or \(n=2(2m+1)\) for some \(m\in\mathbb Z\text{.}\) Moreover, since \(k\in\mathbb Z\text{,}\) we know that \(k=2m\) or \(k=2m+1\) for some \(m\in\mathbb Z\text{,}\) which suggests that we can use cases to finish the proof.

We can also try to prove it directly by assuming \(3\mid 5a\text{,}\) that is, \(5a=3k\) for some \(k\in\mathbb Z\) and then manipulating this equation to show \(a=3n\) for some \(n\in\mathbb Z\text{.}\) Starting from \(5a=3k\text{,}\) add \(a\) to both sides to get \(6a=3k+a\text{.}\) Now subtract \(3k\) from both sides to get \(6a-3k=a\text{.}\) That is \(a=3(2a-k)\text{.}\) Since \(2a-k \in \mathbb Z\text{,}\) we have shown that \(3 \mid a\text{.}\) Let’s put everything together.

In order to show that \((n^2-1)(n^2+2n)\) is divisible by \(4\text{,}\) we need to show that \((n^2-1)(n^2+2n)=4k\) for some \(k\in\mathbb{Z}\text{.}\) This looks complicated, so we should split it into cases!

Since the polynomial is the product of two factors, it would be sufficient to show that both are even, or that one of them is divisible by 4. This suggests that we might get away with considering the parity of \(n\) — what happens when \(n\) is even, and when \(n\) is odd. Lets try that first.

We would like to prove the contrapositive, but first we need to figure out what the contrapositive statement is. Following the technical definition, we know that the contrapositive is If \(\neg\)(\(x\) or \(y\) is odd, but not both), then \(\neg\)(\(x+y\) is odd). But we would like to translate this into a statement that is easier to comprehend.

Putting these together, we get the contrapositive: If \(x\) and \(y\) have the same parity, then \(x+y\) is even.

We see that this is a conditional statement. So, to prove that we can assume the hypothesis and show the conclusion. That is, we assume that \(3\mid (n^2+4n+1)\) and try to show that \(n\equiv 1\mod 3\text{.}\) We see that our assumption means that \(n^2+4n+1=3m\) for some \(m\in\mathbb Z\text{.}\) From this assumption, we need to get to our conclusion on \(n\text{.}\) Even though it is not impossible, it will require factoring or taking the square root, and we may need to prove more statements about how those operations affect divisibility by \(3\text{.}\)

We see that this is a conditional statement. As we did before we can try to prove it directly by assuming the hypothesis and proving the conclusion. This means that we assume \(5\nmid m\) and show that \(m^2\equiv 1 \mod{5}\) or \(m^2\equiv -1 \mod{5}\text{.}\)

Since the hypothesis is \(5\nmid m\text{,}\) this suggests we may need to use cases to prove the result. Once we divide the proof into cases, the rest becomes quite straightforward.

Before attempting the question, we should think about what method of proof will be easiest to show. Based on the content of the chapter, it might be wise to consider a proof by contrapositive or a direct proof with cases.

The contrapositive statement is: If \(q^2 \not \equiv 1 \mod 3\text{,}\) then \(3\mid q\). This means that either \(q^2 \equiv 0 \mod 3\) or \(q^2 \equiv 2 \mod 3\text{.}\) Working through this problem would be difficult because we start with cases on \(q^2\) and we need to get information about \(q\) from there. For this reason, we look into another method of proof.

Now, we consider what a direct proof with cases might look like. If \(3 \nmid q\text{,}\) then when we divide \(q\) by \(3\text{,}\) we will have a remainder of \(1\) or \(2\text{.}\) This gives two very clear cases. It is also easier in general to start with information about \(q\) and work towards information about \(q^2\text{.}\) Because of this, we proceed directly using cases.

However, we are not allowed to use triangle inequality in this question. This means that we need to find a way to simplify the absolute values in the question. For that, we need to understand when the expressions \((x+4)\) and \((x-3)\) change signs. We see that these expressions change signs at \(x=-4\) and \(x=3\text{,}\) respectively.

It is quite common to think here to look at cases \(x\lt -4\text{,}\) \(x\geq 4\text{,}\) \(x\lt 3\text{,}\) and \(x\geq 3\text{.}\) However, this is not the most efficient way to divide this hypothesis into cases since even when we look at \(x\geq -4\text{,}\) we need to consider the sign of \(x-3\text{.}\) This means that within some of the cases, we may have extra cases to consider.

Instead, we can divide these into \(3\) cases: \(x\lt -4\text{,}\) \(-4\leq x\leq 3\text{,}\) and \(x\gt 3\text{.}\) This is more efficient since the expressions \((x+4)\) and \((x-3)\) do not change signs in the intervals \((-\infty,-4)\text{,}\) \([-4, 3]\text{,}\) and \((3,\infty)\text{.}\)

Let’s see how this works in the proof.

With this scrap work, we’re ready to write up the proof of the statement. Remember to be careful with the logic of the proof! We need to start by assuming the hypothesis, \(|x-1| \lt 1\text{,}\) and show the conclusion is true, that \(|x^2-1| \lt 3\text{.}\)

With this scrap work, we’re ready to write up the proof of the statement. But remember, we have to make sure that our logic flows in the correct direction. We must make sure our proof starts from the hypothesis, \(|x-2| \lt 1\text{,}\) and ends at the conclusion, \(|2x^2-3x-2| \lt 7\text{.}\)

We start with some scratchwork. We are asked to prove an inequality involving absolute values. Often, the triangle inequality can be helpful in these types of situations. Recall that the triangle inequality states: For any \(a,b\in \mathbb{R}\text{,}\) \(|a+b|\leq |a|+|b|\text{.}\) Following the hint, we would like to show that \(-|x-y|\leq |x|-|y|\) and \(|x|-|y|\leq |x-y|\text{.}\)

We rearrange the triangle inequality and attempt to get the formula \(|x|-|y|\leq |x-y|\) (the other formula can be obtained similarly).

The statement as written is false, which we can see by looking at the value of the function for a negative point in the domain, say \(x=-1,\) and then at a positive point in the domain, say \(y=1\text{.}\) Then \(x\leq y\) but \(f(-1)=-1\lt 1=f(1)\text{.}\) So \(f\) is not decreasing on all of \(\mathbb{R} - \{0\}\text{.}\) We will not run into this issue if we instead restrict the domain of the function to \((0,\infty)\text{.}\)

Let’s rewrite the statement as this: Let \(f:(0,\infty)\to\mathbb{R}\) be defined by \(f(x)=1/x\text{.}\) Then \(f\) is decreasing.

We are going to take \(0\lt x\lt y\) and we want to show that \(1/x\gt 1/y\text{.}\) To do this start from \(x\lt y\) and then divide both sides by \(xy\) (which is strictly positive). This gives \(1/y \lt 1/x\) as required. Notice that this argument fails precisely when \(xy\) is negative, and that happens when \(x\) and \(y\) have opposite signs - exactly as we saw in our counter-example above.

We see that this statement is a universal statement. Since we don’t have any information on \(n\) other than being an integer, we see that we don’t really have a useful assumption on \(n\text{.}\) For example, if \(n\) were even, then we could say \(n=2m\) for some \(m\in\mathbb Z\text{.}\) But in this question, \(n\) is just an integer, which is a broad assumption without much structure.

One strategy to create such structure is to divide our assumption into cases. This may create extra steps, but eventually may help us have “something” that we can work with. In this example, since we are trying to prove a statement on divisibility by \(3\text{,}\) it would make sense to look at cases that makes use of division algorithm and divisibility by \(3\text{.}\)

Even though this result looks counter-intuitive, it is indeed true.

We are going to use proof by contrapositive. We see that the expression \(\forall a,b\in\mathbb Z\) is not a part of the conditional statement, and therefore we see that the contrapositive of the statement is:

Looking at the contrapositive still doesn’t sound like the right thing to do since we are trading a “\(3\) divides (blah)” type of statement as the hypothesis of the conditional statement, with two “\(3\) doesn’t divide (blah)” type of statement that are connected with “or”. This may seem like it will make our assumption more complicated. But, by looking at the contrapositive, we now have an assumption on simpler building blocks, \(a\) and \(b\text{,}\) instead of the their complicated, complex, counterpart \(a^2+b^2\text{.}\) Since we now have “\(3\nmid a\) or \(3\nmid b\)”, it also suggests that we look at cases.

Since these two cases, \(3\nmid a\) and \(3\nmid b\text{,}\) are very similar we will will make the proof a little shorter by using “without loss of generality”. To make it shorter still, we will contract “without loss of generality” to “WLOG”. Note that one should always be careful using WLOG since it is easy to introduce errors by assuming two cases are very similar when, in fact, there are subtle differences between them.

Once we assume, WLOG that \(3\nmid a\text{,}\) this will introduce \(2\) new cases. Then, within those cases, we may still need to have some extra cases for the choices of \(b\text{.}\) We want to mention that this is quite standard to have cases within cases, within cases, within cases, within…

The converse of the statement is:

While the negation of this statement is:

We can test some values of \(n\text{,}\) \(a\text{,}\) and \(b\) to see if the converse or its negation is true. Suppose \(n=4\text{.}\) We can factor \(n=2\cdot 2\text{.}\) This means is we take \(a=b=2\text{,}\) then \(n=ab\) and so \(n\mid ab\text{.}\) But \(4\nmid 2\text{,}\) so \(n\nmid a\) and \(n\nmid b\text{.}\) Therefore we see that the converse of the original statement is false. Now we write up a formal disproof.

We’ll try to construct a pair of function \(f,g\) so that \(f+g\) is odd, but one of them, say \(f\text{,}\) is even. We can test the result by look at some simple odd and even functions. An example of an odd function is \(y=x\text{,}\) and an example of an even function is \(y=x^2\text{.}\) Let’s suppose that \(f(x)=x^2\text{,}\) which is even. We want to choose \(g\) so that \(f+g=x\text{,}\) an odd function. Then we can take \(g(x)=x-f(x)=x-x^2\text{.}\) Also, we can show that \(g\) is neither even nor odd; \(g(2)=-2\) but \(g(-2)=-6\text{.}\)

Now we can write up the formal proof.

We need to show the following:

For any \(\epsilon \gt 0\text{,}\) there is some \(\delta \gt 0\) so that whenever \(0 \lt |x-1| \lt \delta\text{,}\) we have \(|x^2-1| \lt \epsilon\text{.}\)

With this scratchwork, we’re ready to write up the proof.

Now we can write up the formal proof.

So take \(\epsilon = \dfrac{1}{2}\text{,}\) and then for any \(N \in \mathbb{N}\text{,}\) so that \(n \gt N\text{,}\) set \(n = \max\{N,2\}+1\) and we can make the proof work.

So we can now write up the proof.

We know one of the following is true: either \((a_n)_{n\in\mathbb{N}} \) is not increasing, or it is increasing. We will use these two cases to prove the contrapositive statement. In the first case, when \((a_n)_{n\in\mathbb{N}} \) is not increasing, the conclusion (that \((a_n)_{n\in\mathbb{N}} \) is bounded or not increasing) is automatically satisfied. Therefore we may focus on the second case, when \((a_n)_{n\in\mathbb{N}} \) is increasing. We need to show that the sequence is bounded (then the conclusion, \((a_n)_{n\in\mathbb{N}} \) is bounded or not increasing, will be true).

By assumption, we know that \(\displaystyle\lim_{n\to\infty}a_n\neq+\infty\text{.}\) By definition, this means there is some \(C\gt0\) such that for any \(n\in\mathbb{N}\text{,}\) there’s some \(m\geq n\) with \(a_m\lt C\text{.}\) But since \((a_n)_{n\in\mathbb{N}} \) is increasing, we know that \(a_n\leq a_m\lt C\text{.}\) While it’s not necessarily true that \(a_n\leq a_m\) for all \(n\text{,}\) since \(m\) depends on \(n\text{,}\) we do know that \(a_n\lt C\) for all \(n\text{.}\) Moreover, we also know that \(a_n\geq a_1\) for all \(n\in\mathbb{N}\text{,}\) as \(a_n\) is increasing. Combining these inequalities to get \(a_1\leq a_n\lt C\text{,}\) we can show that \(|a_n|\) is bounded, as desired.

This particular distance function is known as the “discrete distance” or the “discrete metric”. Proving (a) is straight-forward by case analysis with either \(x=z\) or \(x \neq z\text{.}\)

Now, (b) looks like a complicated question since the distance that is given in the definition is not the standard distance function (where the distance between two points is defined as the absolute value of their difference). It also forces the reader to parse a new definition carefully and rework their understanding of the topic at hand.

Now, let’s try to see how we can prove this statememt.

First, we see that this is a conditional statement. This means that we can start by assuming the hypothesis and trying to show the conclusion. That is, assume that \((x_n)_{n\in\mathbb{N}}\) converges to \(L\text{,}\) and try to show that the set \(\set{ n\in\mathbb{N}: x_n\neq L }\) is finite.

Since \((x_n)_{n\in\mathbb{N}}\) converges to \(L\text{,}\) we know that

Hence, since this is true for all \(\forall \epsilon\gt 0\text{,}\) we know that this should also work for \(\epsilon=1/2\) (any \(\epsilon\) strictly between \(0\) and \(1\) would work here). So, for \(\epsilon=1/2\text{,}\) we should be able to find an \(N_\epsilon\in\mathbb N\text{,}\) such that \(\forall n\gt N_\epsilon\text{,}\) we have \(D(x_n,L)\lt \epsilon=1/2\text{.}\)

Now, if we recall that the distance function \(D\) only takes values \(0\) or \(1\text{,}\) this means that \(D(x_n,L)=0\lt\epsilon=1/2\lt 1\text{.}\)

We see that this is what we needed to show, since this means that \(\forall n\gt N_\epsilon\text{,}\) we have \(x_n=L\text{.}\) So the only \(x_n \neq L\) must occur for \(n \leq N_\epsilon\text{,}\) and that is a finite set.

Let’s clean this up and write in a proof.

Since we want to show that the inequality \(n!\gt 3^n\) is true for all \(n\geq 7\text{,}\) we can try to understand how it behaves for any natural number. We can do that by starting to look at the statement for different values of \(k\in\mathbb N\text{,}\) and try to develop a pattern.

We want to prove this statement by induction. As written, we want to prove something about all \(m\in\mathbb{N}\text{,}\) with \(m\) even. In order to prove this by induction, however, we need reformulate the statement into something that we want to prove for all natural numbers instead. We can do this by writing \(m=2n\) for \(n\in\mathbb{N}\text{.}\) Then we need to prove that \(8\) divides \(3^{2n}-1\text{.}\) We can prove this by induction on \(n\text{.}\)

Now we can write the formal proof up:

Now we can write the formal proof up:

Now we’re ready to write up the proof.

Now we can write the formal proof.

The base case of our induction will be \(n=2\text{.}\) For this part, we’ll need to show that the sum of two rational numbers is rational. For the inductive step, we’ll suppose that any sum of \(k\) rational numbers is rational, and we need to show that if \(x_1,x_2,\dots,x_{k+1}\in\mathbb{Q}\text{,}\) then their sum lies in \(\mathbb{Q}\text{.}\) The inductive hypothesis tells us that \(x_1+x_2+\dots+x_k\in\mathbb{Q}\text{.}\) But then \(x_1+x_2+\dots+x_k+x_{k+1}\) is really the sum of two rational numbers, and hence rational itself, as we already proved this in the base case.

Here we see that we have a statement we want to show is true for all \(n\in\mathbb N\text{.}\) In the previous chapters we have seen that to show such statements we assume that \(n\in\mathbb N\) and try to show the conclusion. Moreover, since the hypothesis is broad, we would probably need to look at cases. But, in this question, it is not clear what the cases should be. Instead, we can also apply mathematical induction. We see that this equation doesn’t seem to give us a formula, but instead gives us two expressions. However, we know what the right hand side is equal to.

In this question we want to prove that an inequality is true for all \(n\in\mathbb N\text{.}\) This suggests that induction may be a good method. However, in general, proving inequalities using induction may be a little harder than proving equalities or formulas. The reason for that is the fact that to prove the inductive step, we may need to manipulate the inequality, add or subtract terms, etc. We should also be very careful to make sure that our logic flows correctly in the proof of the inductive step; start from the assumption and reach the conclusion.

As scratchwork, we want to try to break the \(n+1\) case into something involving the previous cases.

Since we can write the \((n+1)^{\text{st}}\) case in terms of the \(n^{\text{th}}\) and \((n-1)^{\text{st}}\) cases, we should make sure to have two consecutive cases (e.g. \(n=0,1\)) in the base case.

Notice that we are able to use an induction argument with two parts to the base case, since this allows us to have two parts to the inductive hypothesis. Another way of proving this is to notice that for the \(n+1\) case we need to reference more than just the previous case, so we can use proof by strong induction.

This question tell us that from a natural number \(n\text{,}\) we can divide out the biggest possible power of \(3\text{,}\) say \(3^m\text{,}\) so that \(3\nmid \left( \frac{n}{3^m} \right)\text{.}\) Since this is a statement that should hold for all natural numbers, induction may be useful method to use. But, because of the nature of the problem, i.e. since we are trying to factor out as many powers of \(3\) as possible, we see that it may be hard to get from \(n=k\) to \(n=k+1\text{,}\) but it may be easier to get from \(n=\frac{(k+1)}{3}\) to \(n=k+1\) assuming that \(\frac{(k+1)}{3}\in\mathbb Z\text{.}\) This suggests that we may need to use strong induction rather than regular induction.

We want to prove this statement by induction on \(n\text{.}\) Since \(a_0\) and \(a_1\) are not given by the recurrence relation, we’ll prove that the formula is satisfied for \(n=0\) and \(n=1\) in the base case. When \(n\geq 2\text{,}\) we have to use the recurrence relation \(a_n = a_{n-1}+6a_{n-2}\) to prove that the formula holds. We can do this by plugging in the formula for \(a_{n-1}\) and \(a_{n-2}\text{.}\) Consequently, for the inductive hypothesis, we need to rely on the statement for \(n-1\) and \(n-2\text{,}\) not just \(n-1\text{.}\) Therefore we need to use strong induction.

This is a good use of induction methods since induction takes care of that “keep going till…” portion of the process.

Now, we may want to use regular induction in this question. If we think about how we can prove the inductive step, to get from \(n\) to \(n+1\text{,}\) we would assume \(n=c_m2^m+c_{m-1}2^{m-1}+\cdots+c_12+c_0\) for some \(m\geq 0\) and constants \(c_0,c_1,c_2,\dots, c_m\in\set{0,1} \text{.}\) Then, we see \(n+1=c_m2^m+c_{m-1}2^{m-1}+\cdots+c_12+c_0+1\text{.}\) But then, we have to have \(2m\) different cases depending on whether or not \(c_i\) is \(0\) or not, for \(0\leq i\leq m\text{.}\) We see that this has a very similar “keep going till...” type of problem. Instead, we can use strong induction and the fact that every natural number is even or odd.

The sets \(F\) and \(G\) may look like regular sets in \(\mathbb R^2\text{,}\) but we see that in both cases, the second item of each ordered pair is given as a function of the first coordinate. This suggests that \(F\) and \(G\text{,}\) indeed, can be seen as representing the graphs of the functions \(f(x)=x^2-3x+2\) and \(g(x)=x+2\) respectively. So, finding the intersection of these sets is the same as finding the intersection of these two graphs. Let’s see how that works in the proof.

At a first glance, this statement looks like a true statement. It is because it sounds like it is saying: “if I remove elements of \(C\) from \(B\) and then add them back again, I get back to \(B\)”. But unfortunately it is not exactly what it says. What it says is: “if I remove all elements of \(C\) from \(B\) and add all the elements of \(C\) to it, then you get back to \(B\)”. Now, we see that this doesn’t have to be true since the set \(C\) may contain element that were not in \(B\) in the first place. So those elements wouldn’t have been removed when we took the difference, and would be added on top when we took the union. So, as long as the set \(C\) has an element that is not in \(B\text{,}\) we will have a counterexample. Let’s see how we can create such a counterexample for this statement.

We want to prove that \(\set{x^a \st a\in\mathbb{Q} }=\set{ y^a\st a\in\mathbb{Q} }\) given that \(x, y \in\mathbb{R}\) and \(k \in\mathbb N\) satisfying, \(x,y \gt 0\) and \(x^k = y\text{.}\) At first glance it may look like a difficult question since it has many variables. But, we can simplify this statement and have a better intuition by choosing certain values of \(x\) and \(y\text{.}\)

We can now write this neatly up as a proof.

We see that this is a “prove or disprove” question. This means that we need to figure out whether it is true or not.

The statement claims that every element that is both in the sets \(\set{x \in\mathbb{Z} : m\mid x}\) and \(\set{x \in\mathbb{Z} : n\mid x}\) must be in \(\set{x \in\mathbb{Z} : mn\mid x}\) as well. In other words, if a number is a multiple of \(m\) and also is a multiple of \(n\text{,}\) then it is also a multiple of \(mn\text{.}\) This statement doesn’t really sound right since \(m\) can itself be a multiple of \(n\text{,}\) and thus, the hypothesis wouldn’t give us any more information other than the number being a multiple of \(m\) (since it automatically becomes a multiple of \(n\) in that situation). This also suggests that we find a counterexample to this statement. Moreover, this suggest what kind of a counterexample would work. Let’s see how we can create a counterexample.

We see that this is a `prove or disprove’ question. This means that we need to figure out whether it is true or not.

The statement claims that every element of \(\set{x \in\mathbb{Z} : mn\mid x}\) is an element of \(\set{x \in\mathbb{Z} : m\mid x}\) and \(\set{x \in\mathbb{Z} : n\mid x}\text{.}\) In other words, every multiple of \(mn\) is a multiple of \(m\) and also a multiple of \(n\text{.}\) We can easily tell that this statement is true. So, we need to prove it.

Of course, we should be extra careful around statements that we can “easily” decide are true. Sometimes they are very deceptive. As a general rule, we should avoid using words like “easily” when we do mathematics.

We see that since we are dealing with power sets in this question, we may not be able to use Venn diagrams to determine the set equality. This means that to see whether we want to prove or disprove the statement, we need to understand what the statement claims.

We can see that the statement says: “intersection of the power sets of \(A\) and \(B\) is the power set of their intersection”. In other words, it says that every set that is both a subset of \(A\) and \(B\) must be a subset of their intersection AND a subset of their intersection must be a subset of both \(A\) and \(B\text{.}\) This makes more sense. We can tell now that this statement is true. So, we can try to prove it.

We can see that the statement says: “the union of the power sets of \(A\) and \(B\) is the power set of their union”. In other words, it claims that every set that is a subset of \(A\) or \(B\) must be a subset of their union and every subset of the union must be a subset of \(A\) or \(B\text{.}\) We can tell that the first part of the statement is indeed true, that is, every set that is a subset of \(A\) or \(B\) must be a subset of their union. But, second part of the statement doesn’t sound right, since the union of two sets can be “bigger” than both sets. This would create a problem since we can simply take the union of these two sets as the “subset” of the union, i.e. the element of the power set of the union. This suggests that we should be able to create a counterexample as long as \(A\cup B\neq A\) and \(A\cup B\neq B\text{.}\) Let’s see how we can create a counterexample.

Let \(A\) be a set. We can check the statement for some numbers to see whether it works for, at least, sets with small sizes. This may also give us some ideas as to how to prove it for any size set.

We see that if \(A=\emptyset\text{,}\) then \(\pow{A}=\set{\emptyset}\text{.}\) This means that \(|\pow{A}|=1=2^0\text{.}\)

Now, assume that \(|A|=1\text{,}\) e.g. \(A=\set{1}\text{.}\) Then, we see that \(\pow{A}=\set{\emptyset, \set{1}}\text{.}\) Thus, \(|\pow{A}|=2=2^1\text{.}\)

Similarly, assume \(|A|=2\text{,}\) e.g. \(A=\set{1,2}\text{.}\) Then, we see that \(\pow{A}=\set{\emptyset, \set{1}, \set{2}, \set{1,2}}\text{.}\) Thus, \(|\pow{A}|=4=2^2\text{.}\)

Finally, if \(|A|=3\text{,}\) e.g. \(A=\set{1,2,3}\text{.}\) Then, we see that

\(\pow{A}=\set{\emptyset, \set{1}, \set{2}, \set{3}, \set {1,2},\set{1,3}, \set{2,3}, \set{1,2,3}}\text{.}\) Thus, \(|\pow{A}|=8=2^3\text{.}\)

This suggests that the stamement may, indeed, be true, and since it is a statement on the size of \(A\text{,}\) induction may be a useful tool.

This suggests that when we add an element to a set, we double its power set’s size, since every subset that contains \(3\) is a subset, \(B\text{,}\) of \(\set{1,2}\) union \(\set{3}\text{.}\)

Both statements are false. In the first case, notice that the empty set is an element of every power set. This means that the empty set is in the left-hand side, but not in the right-hand side.

The second statement is a little harder to disprove. Think about what happens when \(A\) and \(B\) have some, but not all, elements in common. For example, \(A = \set{1,2}\) and \(B = \set{2,3}\text{,}\) so that \(A-B = \set{1}\text{.}\) Then \(\set{1,2} \) is in the left-hand side, but not in the right-hand side. We can simplify this counter-example a little further, since we don’t actually need “\(3\)” to make it work.

The hint suggests that this relation says for the nonempty set \(E\text{,}\) \(q\in E\text{,}\) and \(A,B\in\mathcal P(E)\text{,}\) \(A\rel B\) if \(q\) is in both of them or in neither of them. This observation immediately suggests that the relation is reflexive and symmetric. Moreover, we see that if \(A\rel B\) and \(B\rel C\text{,}\) then we see that \(q\) is in all three sets \(A, B\text{,}\) and \(C\text{;}\) or in none of them. In either case, we see that \(A\rel C\text{.}\) Thus, the relation should be transitive too.

For the first part, we first realize the relation \(R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} : n\mid (a-b)\}\) is nothing but the congruence modulo \(n\) relation. Moreover, we see that if \(R\) is not sparse than there are \(a,b\in\mathbb Z\) such that \(a\equiv b \pmod n\) and either \(a\equiv (b+1) \pmod n\) or \((a+1)\equiv b \pmod n\text{.}\) Since these cases are symmetric with respect to \(a\) and \(b\text{,}\) WLOG, we can assume that \(a\equiv (b+1) \pmod n\text{.}\) Then, we see that \(n\mid (b-a)\) and \(n\mid ((b+1)-a)\text{,}\) that is \(n\mid ((b-a)+1)\text{.}\) Therefore, as the hint suggested, we get \(n=1\) (since \(n\in\mathbb N\)). We can also see that if \(n=1\text{,}\) then the congruence relation cannot be sparse, since every element will be related to every nonzero element.

This final observation is also going to be useful in the second part, since we know that the relation \(R = \{(a,b) \in \mathbb{Z} \times \mathbb{Z} : 1\mid (a-b)\}=\mathbb Z\times \mathbb Z\) is an equivalence relation, and it is not sparse.

Now, we can write this nicely as a proof.

Now, strictly speaking we have shown that if \(\phi\) is a function, then we have \(b \mid 6, b\mid a\text{.}\) We can also readily show that when \(b \mid 6, b \mid a\) then \(\phi\) is a function.

We see that for any values of \(a\) and \(b\) this function \(f(x) = x^2+ax+b\) is a quadratic function. This means that we wouldn’t expect the function to be injective or surjective. Moreover, we see that we can complete the square and get \(f(x)=\left(x+\frac{a}{2}\right)^2+\left(b-\frac{a^2}{4}\right)\text{.}\) This tells us the minimum of the function (which we can use to show that the function is not surjective) and also the vertex of the graph of the function (which we can use to show that the function is not injective).

We see that the condition in the question tells us that \(f(n)\leq n\) for all \(n\in\mathbb N\) and that \(f\) is an injective function. If we want to understand the function, we see that for large \(n\in\mathbb N\text{,}\) say \(n=1000000\text{,}\) we have \(f(1000000)\leq 1000000\text{.}\) This tells us that \(f(1000000)\) has \(1000000\) different options. If we also want to consider that \(f\) is an injective function, it may not be clear as to which of those options \(f(1000000)\) can take.

Instead, we can try to understand what happens to \(f\) when \(n\in\mathbb N\) is small. This will give us fewer options for \(f(n)\) and maybe we can even figure out some values of \(f\text{.}\)

Now, if we check \(n=1\text{,}\) we see \(f(1)\leq 1\text{.}\) Since \(f:\mathbb N \rightarrow \mathbb N\text{,}\) this tells us that \(f(1)=1\text{.}\) Similarly, if we check \(n=2\text{,}\) we see that \(f(2)\leq 2\text{.}\) This means that \(f(2)=1\) or \(f(2)=2\text{.}\) But, since \(f\) is injective, we see that \(f(2)\neq 1\text{.}\) Thus \(f(2)=2\text{.}\)

This suggests that if we keep going like this, we will end up with \(f(n)=n\text{.}\) But, we also realize that if we want to “keep going like this”, we need to apply induction. Moreover, since we want to know something about the values of the function at any point to be able to determine the next one since we want to make sure that the function is injective, we may need strong induction.

When we look at the relation defined in the question, we can easily see that it is reflexive (since equality is reflexive), and symmetric (since equality is symmetric). Moreover, if \((x,y)\rel (s,t)\) and \((s,t)\rel (a,b)\text{,}\) we see that \(x^2+y^2=s^2+t^2=a^2+b^2\text{.}\) Therefore it also is a transitive relation. As we can see, trying to show that this relation is an equivalence relation is not too hard to show.

This means that \(f\) defines a function.

This gives us the result we wanted. Now, we can write the proof.

In this question, we can try to show that \(f\) is an injective and surjective function, and conclude that \(f\) has an inverse, and calculate the inverse afterwards.

However, if we know what the inverse of \(f\) should look like, call it a new function \(g\text{,}\) we can check whether \(g\) is a right and also a left inverse of \(f\text{.}\) If so, using Lemma 10.6.3 and Lemma 10.6.4, we can conclude that \(f\) is bijective and moreover \(g\) is its inverse.

We can find what the inverse of \(f\) should look like quite easily in this question. We see that \(f\) takes even numbers to odd numbers and the odd numbers to even numbers. For example, \(f(5)=5+7=12\text{.}\) This means that if we want to find, \(g\text{,}\) the inverse of \(f\) we should have \(g(12)=5=12-7\) (since we added \(7\) to \(5\) to get \(12\)), that is \(g(n)=n-7\) for \(n\) even. Similarly for \(n\) even, we see that \(f(n)=-n+3\text{,}\) so we must have \(g(-n+3)=n=-((-n+3)-3)\text{,}\) that is, \(g(n)=-n+3\) for \(n\) odd. Now, we can check whether this function \(g\) is the right- and the left-inverse of \(f\text{.}\)

Proof by contradiction can be a useful tool for proving statements where we want to show the non-existence of an object satisfying certain conditions. This is because when we assume for a contradiction that such an object exists, then we would have some structure we can work with and, hopefully, get a contradiction with our prior assumptions or knowledge.

We’ll try to prove the statement by contradiction, by assuming that both \(a\) and \(b\) are odd. Using the definition of \(a\) and \(b\) being odd, we can prove that \(a^2+b^2=4n+2\) for some \(n\in\mathbb Z\text{.}\) Since \(c^2=a^2+b^2\text{,}\) this implies that \(c^2\) is even, and so \(c\) is even. (The contrapositive of this statement is given in Result 3.2.10) But then \(4\) will divide \(c^2\text{.}\) This contradicts the equation \(c^2=a^2+b^2=4n+2\text{,}\) which implies that \(c^2\) is not divisible by \(4\text{.}\)

In order to prove the statement by contradiction, we need to assume that there is some \(k\in\mathbb{Z}\) so that \(ak\equiv1\mod{n}\text{,}\) and then show that this leads to a contradiction, implying that the statement must be true. From the equation \(ak\equiv1\mod{n}\text{,}\) we know that \(n\mid (ak-1)\text{.}\) From here we can show that \(\gcd(a,n)\mid 1\text{.}\) This contradicts that \(\gcd(a,n)\gt 1\text{.}\)

Since we are trying to show that there are no integers satisfying , it may be useful to use proof by contradiction.

Then, if we can show that there is no integer \(y\) satisfying \(y^2\equiv 3 \pmod 4\text{,}\) we would get our contradiction. Moreover, we see that if \(y\) is even, then \(y^2\equiv 0 \pmod 4\) and if \(y\) is odd, then \(y^2\equiv 1 \pmod 4\text{.}\) Therefore, we have our contradiction.

Notice that we could also consider the four classes of \(y \pmod 4\text{,}\) but it will give the same result, just with more work.

This is a good proof-by-contradiction question. We’ll assume that \(\sqrt[3]{25}\) is rational, write it as a simple fraction, and then show that we get a contradiction.

Let’s assume the conclusion is false, that is, that \(rx\) is rational. Then we can write \(rx=p/q\) and \(r=m/n\) for integers \(p,q,m,n\text{.}\) Using this, we can show that \(x\) is rational, which is a contradiction. However, when we write the proof up, we need to be careful to always show that our denominators are non-zero

We’ll prove this by contradiction by first assuming that there are some \(a,n\in\mathbb N\) satisfying the equation. Writing \(a^2=7^n-35\text{,}\) we can show that \(a^2\) is divisible by \(7\text{.}\) By Euclid’s lemma, this implies that \(7\mid a\text{.}\) Then \(7^2\mid a^2\text{.}\) Notice that \(7\mid 35\text{,}\) but \(7^2\nmid 35\text{.}\) If we also had \(7^2\mid 7^n\text{,}\) then that would imply \(7^2\) divides \(35=7^n-a^2\text{,}\) which is a contradiction. So we have a contradiction in the case \(n\geq 2\text{.}\) Now we just need to show that the case \(n=1\) also leads to a contradiction. In this case, we have the equation \(a^2+35=7\text{.}\) This is impossible, since \(a^2+35\geq 35\text{.}\)

We can leverage this reasoning into a direct proof too. We leave that to the reader.

We know that we can use this function to show that \(\mathbb N\times\mathbb N\) is denumerable, if it is a bijective function. That is, if the function is bijective, then we can conclude that \(|\mathbb N|=|\mathbb N\times\mathbb N|\text{,}\) which implies that \(\mathbb N\times\mathbb N\) is denumerable. But, if the function is not bijective, this wouldn’t give us any more information, since just because \(f\) is not bijective wouldn’t imply \(|\mathbb N|\neq|\mathbb N\times\mathbb N|\text{.}\)

We actually saw that if we have two denumerable sets \(A, B\text{,}\) then \(A\times B\) is also denumerable. We proved it using a diagonalisation argument (see Result 12.2.6). Applying this result to \(A=B=\mathbb N\text{,}\) we can immediately see that \(\mathbb N\times \mathbb N\) is, indeed, denumerable.

So, assuming that we can show \(f\) is bijective, this question suggests that we could also show that \(\mathbb N\times \mathbb N\) is denumerable directly by finding a bijective function from \(\mathbb N\times\mathbb N\) to \(\mathbb N\text{.}\)

The hints suggests that we think about a bijection from \((0,\infty)\) to \(\mathbb R\text{.}\) We see that the easiest of such function is \(f(x)=\log(x)\text{.}\) But, we also realize that the set given to us is not \((0,\infty)\text{,}\) but \((-\infty, -\sqrt{29})\text{.}\) This may look like a big problem, but it is a problem we can easily overcome. First observe that we can take \(g(x)=\log(-x)\text{,}\) instead of \(f\text{,}\) it becomes a bijective function (at least intuitively, we need to show that such changes preserve bijectivity) from \((-\infty,0)\) to \(\mathbb R\text{.}\) Then, we can finalize our construction by shifting \(g\) by \(\sqrt{29}\) to the left, i.e. by defining \(h(x)=\log(-x-\sqrt{29})\text{.}\) This function, \(h\text{,}\) should be a bijection from \((-\infty, -\sqrt{29})\) to \(\mathbb R\text{.}\)

Now, of course, we need to show that \(h\) is indeed a bijection. We can do this either by showing that it is injective and surjective, or by showing that it has both a left and a right inverse. Since we know how to find the inverse of the \(\log\) function, the second way may be easier.

Question 13 in Section 10 suggests that we should be able to construct a bijective function \(g: S\to\pow{N}\) (as done in that question) implying that \(S\) is uncountable.

Unfortunately, this argument fails when at least one of the sets is infinite, since we cannot talk about the “sizes” of infinite sets. So what we need to, instead, is to use the actual definition of two sets having equal cardinalities. That is, we know that \(|A|=|B|\) and \(|C|=|D|\) means that there exist two bijective functions \(f: A\to B\) and \(g: C\to D\text{.}\)

We see that if we only want to show that these two sets are equinumerous, our best choice would be to use The Cantor-Schröder-Bernstein theorem. We can do that by finding two injective functions:

But, in this question, we want to find an explicit bijection from \((0,\infty)\) to \((0,\infty)-\set{1}\text{.}\) The problem with such bijections is that it generally feels almost trivial since the two sets are almost identical. This gives the impression that we should be just take the identity function, or a tiny variation of it to get the bijection.

However, this idea fails when we realize that our bijection should send 1 to an element in \((0,\infty)-\set{1} \text{,}\) call it \(y_1\text{.}\) But then \(y_1\in (0,\infty)\) and thus should go to another element in the codomain (different than itself), call it \(y_2\text{.}\) Then, this \(y_2\) should go to another element, and that should go to another, and so on. This means that we cannot take a simple variation of the identity function here, we may need to make a more drastic change to account for this “snowball” effect.

The simplest way to handle this situation is by defining a function that sends \(1\) to \(2\text{,}\) \(2\) to \(3\text{,}\) \(3\) to \(4\text{,}\) and so on, very similar to “Hilbert’s Hotel Problem”. As for elements that are not natural numbers, we can just send them to themselves.

We saw in Exercise 12.7.12 that if \(A_1, A_2, B_1, B_2\) are any nonempty sets satisfying \(A_1\cap A_2=\emptyset\) and \(B_1\cap B_2=\emptyset\text{,}\) and that \(|A_1|=|B_1|\) and \(|A_2|=|B_2|\text{,}\) then we have \(|A_1\cup A_2|=|B_1\cup B_2|\text{.}\) The idea in the proof relied on the fact that since \(|A_1|=|B_1|\) and \(|A_2|=|B_2|\text{,}\) there are bijections \(f:A_1\to B_1\) and \(g: A_2\to B_2\text{.}\) Using these functions, we could construct a piecewise function \(h:A_1\cup A_2 \to B_1\cup B_2\) that turned out to be a bijection as well.

We can see this result as a specific example to this question, where our partitions for the sets \(A=A_1\cup A_2\) and \(B=B_1\cup B_2\) are given as

Then, we see that \(F:P\to Q\text{,}\) defined as \(F(A_1)=B_1\text{,}\) and \(F(A_2)=B_2\) is a bijection from \(P\) to \(Q\text{,}\) and moreover \(|A_1|=|B_1|\) and \(|A_2|=|B_2|\text{.}\)

This suggests that if we have partitions with more sets in them, we should be able to construct a bijection in a very similar piecewise manner. Also, since sets in a partition are mutually disjoint, and that their union gives the entire set, such a construction would still work.