Blogs, Mathematical Reasoning, MR Study Help

Proof by Contrapositive

In this post we will be proving that if \(10 \not| a\), then \(2 \not| a\) or \(5 \not|a\). For the following theorem we will be only assuming definitions and the lemma given to us. Anything else that is used will need to be proven.

Lemma

Let \(a,b \in \mathbb{Z}\). If \(2|ab\), then \(2|a\) or \(2|b\).

Using this lemma, prove the following with a proof by contrapositive.

Theorem

Let \(a \in \mathbb{Z}\). If \(10 \not| a\), then \(2 \not| a\) or \(5 \not| a\).

As we begin the process of writing the proof of the theorem, we first want to write down any information that will be useful. Such things would include:

  • The theorem and any lemma in terms of symbolic logic.
  • Definitions of any words used.
  • Anything we remember relating to the terms used.
  • A list of statements that are given.
  • A list of statements that need to be shown.

Symbolic Logic-Theorem

We begin by rewriting the theorem using symbolic logic. If you would like more help on turning sentences into symbolic logic, there is more available in the post Translating to symbolic logic and back.

For this problem, we first note that the variable is \(a \in \mathbb{Z}\). We then have the statements

  • \(p(a)=10 |a\),
  • \(q(a)=2 |a\),
  • \(r(a)=5 |a\).

We then note that the theorem will read \(\forall a \in \mathbb{Z}, \sim p(a) \rightarrow \sim q(a) \vee \sim r(a)\). In this case we will be using the fact that \(p \rightarrow q\) is equivalent to the statement \(\sim q \rightarrow \sim p\) to provide a proof. That is, we will need to show that whenever \(\sim(\sim q(a) \vee \sim r(a))\) is true, we must also have that \(\sim (\sim p(a))\) is true.

If we simplify these terms, we get
\begin{align*}
\sim(\sim q(a) \vee \sim r(a)) &=\sim \sim q(a) \wedge \sim \sim r(a) \\
&=q(a) \wedge r(a) \\
&=2|a \wedge 5|a,
\end{align*}
and \(\sim \sim p(a)=p(a)=10|a\). We, therefore, have to show that whenever \(2|a\) and \(5|a\) we also have that \(10|a\).

Symbolic Logic-Lemma

Again, we will do the same process for the lemma we just did for the theorem. In this case, we have variables \(a,b \in \mathbb{Z}\). The simple statements are \(p(a,b)=2|ab\), \(q(a,b)=2|a\), \(r(a,b)=2|b\). We then get that the lemma states \(\forall a,b \in \mathbb{Z}, p(a,b) \rightarrow q(a,b) \vee p(a,b)\). That is, if 2 divides a product of two terms, then it must divide at least one of the terms. We may assume this through the proof since it is given.

Definitions

As we read through these statements, there are a couple of things that need to be defined. When we do so, we will also try to write out any thing that we may know or think is equivalent.

  • \(\mathbb{Z}\) is the set of integers.
  • \(a | b\).
    • \(a\) divides \(b\).
    • \(b=ka\) for some integer \(k\).

Given and used

Now that we know what the theorem is saying, we want to list out what we are given, and what we need to show. We will also relate each of these to anything else we have, so that eventually we can move from one point to the other.

Given Must Show
\(2|a \wedge 5|a\) \(10|a \)
\(a=2k_{1} \wedge a=5k_{2}\) for \(k_{1},k_{2} \in \mathbb{Z}\) \(a=10k_{3}\) for \(k_{3} \in \mathbb{Z}\)
\(2k_{1}=a=5k_{2}\)
\(2|5k_{2}\)
\(2|5 \vee 2|k_{2}\) by Lemma
\(2|k_{2}\) since \(2 \not|5\)
\(k_{2}=2k_{4}\) for \(k_{4}\in \mathbb{Z}\)

After looking at what is implied by what is given, we have to find a way to connect the left to the right side. Here, we note that \(a=5k_{2}=5(2k_{4})\) since \(k_{2}=2k_{4}\). This then gives us that \(a=10k_{4}\), so \(10 |a\) as we wanted. Now, the only thing left to do is to give the formal proof.

Proof

Let \(a \in \mathbb{Z}\), \(2|a\) and \(5|a\). We then have that \(a=5k_{1}\) for some integer \(k_{1}\). Furthermore \(2|a=5k_{1}\), so \(2\) divides the product of \(5\) and \(k_{1}\). Since \(5\) is odd, we know that \(2 \not| 5\), so we must have that \(2|k_{1}\) by our lemma. Therefore \(k_{1}=2k_{2}\) for some integer \(k_{2}\).

We can now find that
\begin{align*}
a&=5k_{1} \\
&=5(2k_{2}) \\
&=10k_{2}.
\end{align*}
Therefore, \(10|a\) as desired.

Conclusion

Here the proof itself is actually quite short compared to everything that was needed to create the proof. As we try to come up with the proof, we spend a lot of time rewriting things so that we are absolutely sure what we are given and what we are trying to say. After all of this, there will always be a point where we need to make a connection between to ideas using our own creativity. The part we needed to see was that we had to use the given lemma. Note that, since the lemma was given, there was a good chance this would happen. Using this lemma, we were able to rewrite one of the terms so that we could get 2*5 together, which allowed us to show that 10 divided a.

I hope that you learned something about the process of writing proofs and that this will help you in your studies. For more help visit here. If you enjoyed the post or learned something, make sure to like it and share with anyone else that may need help on similar topics.

We'd love to hear your thoughts!

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