I don't understand the explanation of Proof by Contradiction

You're getting caught up on the word assume. You can make a pretend world by assuming a proposition is true when it's actually false. You're essentially breaking math. So, in this pretend world, ¬(P(n)→Q(n)), but also (C∧¬C). Since math has to be consistent, there was something wrong with our assumption, therefore the negation must be true, hence (P(n)→Q(n)).


What I don't understand is this line: "$\ \neg (P(n) \to Q(n)) \to C \wedge \neg C$ , is true."

Phrased another way, we hope to demonstrate that indeed, it "is true" that the negation of what we hope to prove leads to a contradiction. Therefore, the negation of what we hope to prove is false. Therefore, what we hope to prove is true.

You hope to prove $P(n) \to Q(n)$. Assume the negation. If it is true that the negation implies a contradiction

$\ \neg (P(n) \to Q(n)) \to C \wedge \neg C$

then $\ \neg (P(n) \to Q(n))$ is false. Therefore $P(n) \to Q(n)$ is true and our proof is complete.

You claim that if we stopped, you would fill the gas tank. We did stop and yet here we are on the side of the highway, gas gauge on E. How do you explain that Karen?

A famous example of proof by contradiction is the proof for the infinitude of the prime numbers. We hope to prove there an infinite number of primes. By way of contradiction, assume there are a finite number of primes. Then there must be a largest prime. Multiply all the primes together and add one. This new number is larger than every prime, and leaves a remainder of one when divided by any prime. Since it is not divisible by any smaller prime, it must be itself prime. But it is larger than the largest prime. This is a contradiction. Therefore, it is not true that there are a finite number of primes.

(There are a finite number of primes) $\to$ (there is a largest prime) $\land$ (there is a prime larger than the largest prime)

Therefore, there are an infinite number of primes.


It is not said that $\neg(P\to Q)$ is true but rather that we would treat it as if it were.

Logically it is not at all “taken to be true”, we simply make the deduction of $C\wedge \neg C$ from $\neg( P\to Q)$ via reasoning and the validity of that statement is not considered to begin with. The language of “taking it to be false” is English (for “we will begin with the negation of the statement”).

Tags:

Logic

Discrete Mathematics

Proof Writing

Proof Verification

Related

Calculating the curvature of product manifold $\mathbb{S}^2 \times \mathbb{R}$ 1-Torus as finite dimensional $\mathbb{R}$-vector space is one dimensional, yet not isomorphic to $\mathbb{R}$ Prove that the area of the trangles are equal. Find $\lim\limits_{n \to \infty} \int_0^1 f_n(x) \, dx$ with $f_0(x) = x$ and $f_{n+1}(x) = \sin (\pi f_n(x))$ Contradiction in proof by contraposition and counterexample Proving that $a^2+b^2\neq 3c^2$ for any positive nonzero integers $a$, $b$, and $c$ If an integer is not sum of two cubes in integers, then the integer cannot be sum of two cubes modulo every integer. Prove that $A\cup B$ is connected. List all generators of the set $\{5^n\mid n \in \mathbb{Z}\}$ under multiplication. Show that there are infinitely many primes of the form $8n+1,8n+3,8n+5,8n+7$ How do you determine which representation of a function to use for Newton's method? Precise general statement of flat morphisms being "equidimensional"

Recent Posts