PLP An introduction to mathematical proof

Pay close attention to notation! For part (h), this is an issue you would only come across if you are typing your math in a program such as LaTeX.

Try writing out the first few terms of each set.

Carefully determine what is the hypothesis and what is the conclusion of each implication, and then refer to the truth table of the implication.

What is the only situation in which an implication is false?

Is the conclusion of the implication true or false? What does that tell you?

You don’t have to use truth tables to determine the answer (although you could).

Think about what does being even mean and how we can use it.

Think about what being odd means and how we can use it.

Think about what it means for \(n\) to divide \(a\) and \(b\text{,}\) and how we can use that information.

Think about the divisors of 1 and how you might use that.

Think about how we can get from \(2\) and \(3\) to \(6\text{.}\)

Think about what it means for \(3\) to divide an integer and how we can use that information.

Try writing down different integer roots and check whether their product is also an integer root.

Try writing the inequality in a different way, the difference of squares might help.

Refer back to Exercise 2.7.5 and use Theorem 4.2.3.

What is the contrapositive of this statement?

What is the contrapositive of the statement?

What is the contrapositive of the statement?

Think carefully about the parity of \(n\text{.}\)

The ideas used in the solution of Exercise 3.5.8 may be useful.

Try proving by cases.

Think carefully about the contrapositive.

What is the contrapositive of the statement?

If we assume the hypothesis is true, then what do we know about \(q\text{?}\)

Expand the cubes and simplify the sum

Modular arithmetic makes this much easier.

You may want to look at cases for \(x\in\mathbb R\) to get rid of the absolute values.

Try sketching the function.

You can think about the division algorithm and cases for \(n\text{.}\) Also try factoring things.

Try to eliminate \(n\text{.}\) What does this tell you about \(k\text{?}\) What else do you know about \(k\text{?}\)

What can you say about \(a^2\) modulo 4 for all \(a \in \mathbb{Z}\text{?}\)

Try playing around with some simple functions.

If you are unsure if the statement is true or not, then explore its negation — it might be easier to understand.

Which primes are even?

Think carefully about the truth table of the implication. Also, negate carefully. Finally, be careful with your inequalities.

Be careful of the order of quantifiers; make sure you pick variables in the correct order.

Start with a few simple functions you know well. Sketch them and try to decide if they are type A or type B or neither. Also, you should write out the negations of these definitions; what does it mean if a function is not type A? what does it mean if it is not type B?

Can you bound \(\sin(1/x)\) by a simpler function?

Carefully negate the definition of convergence. Also, explore the first few terms of the sequence.

Split the sequence at some large \(N\text{,}\) so that when \(n\geq N\text{,}\) we know that \(a_n\) is really close to \(L\text{.}\) We can use this to bound \(|a_n|\) when \(n\geq N\text{.}\) That leaves us to bound only finitely many of the terms \(|a_n|\text{,}\) the terms for which \(n\lt N\text{.}\) While we cannot take the maximum of an infinite set of values, we can find the maximum of a finite set of values and it will be finite. See Exercise 7.3.16 which explores this point.

For part (c), the contrapositive can help. Also, see Exercise 4.3.1 (c).

For part (b), try some of the sequences we have seen that converge with the Euclidean distance, and see whether they converge under this new distance? Choosing your \(\epsilon \) satisfying \(0\lt \epsilon\lt 1\text{,}\) would be very useful in understanding the convergence of a sequence.

Write out the statement for \(n=k\) and \(n=k+1\) and try to work out how to make the left-hand side of the first statement look like the left-hand side of the second statement.

How can we get from \(z^{2n+1}\) to \(z^{2(n+1)+1}\text{?}\)

The sum \(\sum\limits_{k=1}^n k\) is a very standard result and is in the main text. You can use that result without proof.

Be careful when you expand \((n+1)^3 \) and \((n+1)^4 \text{.}\)

Factoring a cubic can be painful. Perhaps write down the cubics you need and then expand them out. This might help with some of the arithmetic.

Adding to the end of the series will get you intro trouble. Try adding to the beginning instead. You might have to think about that a little.

For (b) try integration by parts.

The proof of Result 7.2.18 works because \(5\) is a Fibonacci number. See how you might generalise what is happening in the proof.

Integrate by parts!

As a base case, consider \(n=0\) and \(n=1\text{.}\) This means that your inductive hypothesis can include both the \(n-1\) and \(n\) cases.

Shops will not be intimidated by excess purchasing power; even though you have lots of money, this fictional mathematical country does not allow you to overpay for an item.

Strong induction helps, as does the parity of the number.

You can simplify the analysis of the floor function by studying even and odd values separately.

Be careful as to how you can go from \(k=n+1\) stones to \(k\leq n\) stones in your inductive step and see whether different splittings change the calculations. Try playing this game with \(5\) or \(6\) stones to get a better understanding of how this works.

Revise the definition of set-differences and then try to make a small example.

You may need to use mathematical induction on the size of \(A\text{.}\)

Try some small examples of sets \(A,B\) to gain some intuition.

In order to prove that \(a\) is the supremum of a set \(S\text{,}\) it suffices to show that \(a\) is an upper bound for \(S\text{,}\) and that if \(b \lt a\text{,}\) then \(b\) is not an upper bound of the set. The latter statement may be rephrased as follows: if \(b \lt a\text{,}\) then there is some \(s\in S\) with \(s \gt b\text{.}\)

If you want to show instead that \(S\) has no maximum, prove that any \(s\in S\) is not an upper bound of the set. That is, for any \(s\in S\text{,}\) there is some \(t\in S\) with \(t \gt s\text{.}\)

Suppose we are trying to prove that \(a\) is the least upper bound of a set \(S\text{.}\) Then we need prove that the two defining properties of the supremum hold for \(a\text{.}\) In order to prove the statement “if \(b\) is an upper bound for \(S\text{,}\) then \(a\leq b\text{,}\)” it may be easier to show the contrapositive, “if \(b \lt a\text{,}\) then \(b\) is not an upper bound for \(S\text{.}\)” In order to prove that contrapositive, we need to show that for any \(b \lt a\text{,}\) there is some \(s\in S\) so that \(s \gt b\text{.}\) Then \(b\) will not be an upper bound for \(S\text{,}\) by definition.

For any \(\epsilon\text{,}\) we know that \(a-\epsilon\) is not an upper bound of the set \(\{a_n:n\in\mathbb{N}\}\text{.}\)

You can first look at the relation \(R\) for \(E=\set {1,2,3,4}\text{,}\) and \(q=1\) to understand the relation better. Also, recall that \(\overline{A}\cap \overline{B}=\overline{A\cup B}\text{.}\)

Try looking at examples of relations on a small set, like \(A=\{1,2,3\}\text{.}\)

For part (a), try looking at examples of relations on a small set, like \(A=\{1,2,3\}\text{.}\)

Try some simple examples on small sets. Also, modus-tollens might help.

For the first part, the result in Exercise 3.5.7 will be useful.

Remember that every element of the set \(R\) is the intersection of two elements of \(P\) and \(Q\text{.}\) Also, read the definition of partitions carefully.

For the second part, start by finding the invertible elements in \(\mathbb Z_6\)

Try using Bézout’s identity.

Try modifying the proof of Euclid’s lemma 9.5.9.

The question asks for the range, not the codomain.

Remember that a function has to give a valid output for every valid input — why does this tell you about the \(y\)-values?

How do we show that two sets are equal?

Completing squares may help with the answer (to be honest, completing squares will help you with almost everything quadratic functions related, cherish it).

Also, try choosing some small \(a,b\) values and sketch the function.

Can you determine \(f(n)\) for small \(n\in\mathbb N\text{?}\)

This is a good example as to why when we want to determine whether a function is injective and/or surjective, we shouldn’t only look at `what kind’ of a function it is, but also consider the domain and the codomain of the function as well.

Remember, a function is not just a formula!

For one side of the implication, think about how we can express the surjectivity in terms of the codomain and the range.

Think how an integer factors.

To show that an integer is zero, one can show that it is small and divisible by a bigger integer.

Be careful, the symbol \(f^{-1}\) denotes the preimage not the inverse-function. It only denotes the inverse-function when the function is bijective.

Also, see Theorem 10.3.6 and its proof.

Be careful, the symbol \(f^{-1}\) denotes the preimage not the inverse-function. It only denotes the inverse-function when the function is bijective.

Also, see Theorem 10.3.6 and its proof.

To show that two functions with same domains and codomains are different, it suffices to show that there is a single point at which they differ. To show that they are the same, you must show they are equal on every point of the domain.

Try to construct counterexamples on small sets (eg. \(\{1,2,3\}\)) rather than on \(\mathbb{R}\text{.}\)

Two functions are equal when they are equal at all points in their domains.

Your observations from part (b) can be helpful in solving part (c).

Observe that \(f\) takes even numbers to odd numbers and odd numbers to even numbers. Considering that, what should the inverse of \(f\) look like?

Also - there are some very handy lemmas in Section 10.6.

If \(a\) were to satisfy both congruences, then we get 2 equations. Combining them helps.

Remember that \(1\) is not divisible by very many integers!

Modular arithmetic can really help with problems like this since they take all the infinite possible integers down to a small finite set of equivalence classes. Consider the equation modulo \(4\text{.}\)

Try adapting the proof of Result 11.1.2.

Please observe that \(25\mid 5^3\text{.}\)

Euclid and the prime-ness of 5 also help.

Prove this by contradiction, but negate the statement carefully. Then, to get more information, Bézout’s identity could be very useful.

What would the equation look like if \(x\) were a rational number?

If \(A\) were to have a maximum, what is the difference between \(\sqrt{2}\) and that? It is not a rational number, but how can we use it to make a rational number that is still in \(A\text{?}\)

What would happen if the function weren’t strictly increasing or decreasing?

Your answers for (d) or (f) may depend on (a).

Can you think of a bijection from \((0,\infty)\) to \(\mathbb R\) How can we use that function in this question?

Question 13 in Section 10 may be useful.

Try sketching the graph of potential bijections from \((0,1)\) to \(\mathbb{R}\text{.}\)

The sets do not have to be finite.

The explicit bijection in the proof of {Result 12.5.2} may be useful.

For part (a), try to define an injection from each set to the other; you can then use Cantor-Schröder-Bernstein 12.5.1 to infer there is a bijection between the sets. For the function from \((0,1)\times(0,1)\) to \((0,1)\text{,}\) consider the decimal representation of elements in \((0,1)\text{.}\)

Remember that the sets \(A\) and \(B\) may be infinite!