Problem 15 - Book of Proof

Question

Use the method of proof by contradiction to prove the following statements. (In each case, you should also think about how a direct or contrapositive proof would work. You will find in most cases that proof by contradiction is easier.) If \(b \in \mathbb{Z}\) and \(b \nmid k\) for every \(k \in \mathbb{N},\) then \(b=0\).

Step-by-Step Solution

Answer

The initial statement 'If \(b\) is an integer and \(b\) doesn't divide any natural number \(k\), then \(b\) equals to zero.' is successfully proven by contradiction. If \(b\) didn't equal zero, that would mean it could divide itself, contradicting the assertion that \(b\) doesn't divide any natural number. Hence, \(b\) must be zero.

Step 1: Assume the Contradictory

Begin the proof by contradiction by assuming the opposite of what you want to prove. Here, we want to prove that if \(b\) doesn't divide any natural number \(k\), then \(b\) equals to zero, so let's assume \(b \neq 0\).

Step 2: Find a Contradiction

According to the division property, if \(b \neq 0\), \(b\) should divide itself. This leads to a contradiction because we initially stated that \(b\) doesn't divide any natural number \(k\), implied that \(b\) doesn't divide itself as well.

Step 3: Conclusion

Since our assumption led to a contradiction, the assumption must be false, hence, \(b\) must be equal to zero, proving the initial statement.

Key Concepts

Division Property

The division property in mathematics is a fundamental concept that helps us determine how one number can be divided by another without leaving a remainder. When we say "A divides B," noted as \( A \mid B \), it means there exists an integer \( C \) such that \( B = AC \). It is crucial when dealing with proofs and problems related to divisibility.

In the context of proof by contradiction, the division property plays a key role. We assume a statement and its negation cannot both be true. An application of this is in the given exercise, where we assume \( b eq 0 \). According to the division property, \( b \) should divide some numbers, even itself. Therefore, assuming \( b eq 0 \) but \( b mid k\) for all natural numbers \( k \), including itself, leads to a logical contradiction.

This contradiction invalidates our initial assumption, allowing us to conclude that \( b = 0 \). Understanding the division property is essential to recognize why certain assumptions create impossible scenarios in mathematical reasoning.

Natural Numbers

Natural numbers are the set of positive integers starting from 1 and continuing onwards: 1, 2, 3, and so forth. They do not include zero or negative numbers. These numbers are foundational in mathematics, particularly in number theory and proofs involving divisibility.

In our exercise, the concept of natural numbers is central. We are considering divisibility across all natural numbers \( k \). The statement \( b mid k \) for every \( k \in \mathbb{N} \) implies that \( b \) does not divide any of these numbers perfectly such that there is a remainder other than zero.

Understanding natural numbers aids in this contradiction proof. We can derive from this lack of divisibility that the factor that could divide \( k \) must itself be zero. Since this presumed fact leads us to an illogical conclusion when assuming \( b eq 0 \), it strengthens our final argument that indeed \( b = 0 \). Navigating proofs often involves deep comprehension of how natural numbers work within the statement and assumptions made.

Contrapositive Proof

A contrapositive proof is a method in logic used to demonstrate the truth of an implication, \( P \implies Q \). Instead of proving \( P \rightarrow Q \) directly, we show that the contrapositive \( eg Q \rightarrow eg P \) holds true. The appeal is in its often simpler logical construction.

For our specific problem, considering a contrapositive approach would involve demonstrating that if \( b eq 0 \) then there is some natural number \( k \) such that \( b \mid k \). This approach shares similarities with proof by contradiction, where instead of assuming \( eg Q \) to derive a contradiction, we directly prove \( eg Q \rightarrow eg P \).

The contrapositive proof is deeply intertwined with the proof by contradiction in terms of logical structure. It can often seem simpler because it avoids explicitly finding a contradiction, yet it implies the same result through a clear logical pathway. Thus, mastering contrapositive proof techniques enhances comprehension and versatility in tackling mathematical proofs like the one in the exercise.