As in previous cases, we start by expressing the conjecture as a conditional statement.
If m is irrational and n is rational, then m+n is irrational.
In this case, we must use proof by contradiction.
Remember that a contradiction is a compound proposition that is always false.
To give a proof by contradiction of a conditional statement (p->q), we assume that p and ¬q are both true and then arrive to a contradiction.
So, let’s assume that p (m is irrational and n is rational) is true and ¬q (m+n is rational, or is not the case that m+n is irrational) is also true.
n = a/b, where a and b are integers and b ≠ 0, by rational number definition
m+n = c/d, where c and d are integers and d ≠ 0, by rational number definition
m + a/b = c/d, substituting n in m+n=c/d
m= c/d – a/b = (cb – ad) / db
Because we know that the multiplication and addition/subtraction of integer numbers is also an integer, cb, ad, db, and cb-ad are integer numbers. So, we can conclude that m is rational by the definition of a rational number.
Therefore, we got a contradiction because we assumed that m is irrational ∎
Summary of steps:
- Transform the conjecture into a conditional statement.
- Assume p and ¬q are both true.
- Arrive to a contradiction.
In some cases, you must prove a simple proposition (instead of a conditional statement) using proof by contradiction.
In this case, you should find a proposition r such that p -> (r ∧¬r).
An example of that type of proof is the following exercise: Prove that √2 is irrational by giving a proof by contradiction. You can find the solution to this exercise in the textbook Discrete Mathematics and its Applications by Rosen.
Related posts:
- Use a direct proof to show that the sum of two even integers is even
- Use a direct proof to show that the sum of two odd integers is even
- Prove or disprove that the product of two irrational numbers is irrational
- Show that if n is an integer and n^3+5 is odd, then n is even using a proof by contraposition and a proof by contradiction
- Prove that if m and n are integers and mn is even, then m is even or n is even
