Proof by contradiction Definition and 57 Threads

In logic and mathematics, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Proof by contradiction is also known as indirect proof, proof by assuming the opposite, and reductio ad impossibile.

View More On Wikipedia.org
Recent contents Top users
  1. J

    Clarification on Proof by Contradiction

    This is more a general question that this problem spurred and this is what I came up with. I do not feel it is acceptable but would like clarification moving forward. My text states the format for proof by contradiction is as follow; Proposition: P PF: Suppose ~P. ...a little math and...
  2. M

    Proof by contradiction - any non-zero number divided by itself is 1

    Proof by contradiction (for some reason the LaTeX code is not working for me. Sorry) Lets assume that A, B, and C are non-zero real numbers; A = B ; and C is not equal to 1. A/ B = C A = B x C But BxC could be equal to B, if and only if C =1 Also, could you recommend a book where I...
  3. malawi_glenn

    Help with a proof regarding convergent sequence (proof by contradiction)

    Ok I am trying to brush up my real analysis skills so that I can study some topology and measure theory at some point. I found this theorem in my notes, that is proven by using proof by contradiction. However, I have a hard time understanding what the contradiction really is... Here is the...
  4. C

    Indirect Proof Proof verification: sequence a_n=(−1)^n does not converge

    Theorem: Show that the sequence ## a_n = (-1)^n ## for all ## n \in \mathbb{N}, ## does not converge. My Proof: Suppose that there exists a limit ##L## such that ## a_n \rightarrow L ##. Specifically, for ## \epsilon = 1 ## there exists ## n_0 ## s.t. for all ## n > n_0## then ##|(-1)^n-L|<1##...
  5. R

    Use proof by contradiction to show there is no rational number such that....

    Homework Statement Use proof by contradiction to show there is no rational number r for which r^3+r+1 = 0 Homework EquationsThe Attempt at a Solution Assume there is a rational number r for which r^3+r+1=0. Then r = (a/b) with a,b ∈ℤ and b ≠ 0, and a/b is in lowest terms Then a/b is a root...
  6. R

    Is my proof by contradiction valid?

    Homework Statement If 3n+2 is odd, then n is odd Homework EquationsThe Attempt at a Solution assume 3n+2 is even, show n is odd 3n+2 = 2f => 3n+3 = 2f + 1 => 3(n+1) = 2f+1 so 3*(n+1) is odd form. Only odd*odd gives you another odd, so n+1 is odd. That means n is even. We have a...
  7. U

    Proof by Contradiction: Converse of A(n) Holds for All n ∈ Z

    Homework Statement “If n = 3q + 1 or n = 3q + 2 for some q ∈ Z, then n 2 = 3t + 1 for some t ∈ Z.” Use proof by contradiction to show that the converse of A(n) is true for all n ∈ Z. For the proof by contradiction, on the answer sheet provided they have assumed n^2 = 3t+1 but n != 3q+1 and n...
  8. Mr Davis 97

    Proof by Contradiction: Showing a ≤ b when a ≤ b1 for every b1 > b

    Homework Statement Let ##a,b \in \mathbb{R}##. Show if ##a \le b_1## for every ##b_1 > b##, then ##a \le b##. Homework EquationsThe Attempt at a Solution We will proceed by contradiction. Suppose that ##a \le b_1## for every ##b_1 > b##, and ##a > b##. Let ##b_1 = \frac{a+b}{2}##. We see that...
  9. Derek Hart

    Proving ƒ(x) is the Identity Function

    Homework Statement I have been going through a textbook trying to solve some of of these with somewhat formal proofs. This is a former Putnam exam question. (Seemingly the easiest one I have attempted, which worries me). Consider a polynomial function ƒ with real coefficients having the...
  10. e2m2a

    A Circular reasoning and proof by Contradiction

    I need to understand something about proof by contradiction. Suppose there is an expression "a" and it is known to be equal to expression "b". Furthermore, suppose it is conjectured that expression "c" is also equal to expression "a". This would imply expression "c" is equal to expression...
  11. M

    I Is the negation of the statement in the book correct too?

    Hello. I'm currently studying about natural numbers and I encountered the theorem of definition by recursion: This states: Let ##H## be a set, let ##e \in H## and let ##k: H \rightarrow H## be a function. Then there is a unique function ##f: \mathbb{N} \rightarrow H## such that ##f(1) = e##...
  12. D

    Linear Algebra with Proof by Contradiction

    This is a linear algebra question which I am confused. 1. Homework Statement Prove that "if the union of two subspaces of ##V## is a subspace of ##V##, then one of the subspaces is contained in the other". The Attempt at a Solution Suppose ##U##, ##W## are subspaces of ##V##. ##U \cup W##...
  13. D

    Contradiction Method: Proving Statements Through Contradiction and Supposition

    Proof by contradiction starts by supposing a statement, and then shows the contradiction. 1. Homework Statement Now, there is a statement ##A##. Suppose ##A## is false. It leads to contradiction. So ##A## is true. My question: There are two statements ##A## and ##B##. Suppose ##A## is true...
  14. Battlemage!

    I Can you use proof by contradiction in the midst of induction

    In the process of doing a proof by induction, can you use a contradiction to show that if P(k) holds then P(k+1) must hold? What I mean is, after establishing that P(0) holds, can I assume that P(k) holds and that P(k+1) does not, and show that a contradiction arises, and thus conclude that if...
  15. pjgrah01

    Can b be an integer if it does not divide k for every natural number k?

    Homework Statement Prove by contradiction that if b is an integer such that b does not divide k for every natural number k, then b=0. Homework EquationsThe Attempt at a Solution I know that proof by contradiction begins by assuming the false statement: If b is an integer such that b does not...
  16. T

    MHB Prime numbers proof by contradiction

    For prime numbers, $a$, $b$, $c$, $a^2 + b^2 \ne c^2$. Prove this by contradiction. So, I get that $a^2 = c^2 - b^2 = (c - b)(c +b)$ And I get that prime numbers are the product of 2 numbers that are either greater than one, or less than the prime numbers. But I'm unsure how to go from here.
  17. lordianed

    Prove that no such functions exist

    Homework Statement Prove that there do not exist functions ##f## and ##g## with the following property: $$(\forall x)(\forall y)(f(x+y) = g(x) - y)$$ Homework Equations NA The Attempt at a Solution Here is some information I have found out about ##f## and ##g## if we suppose they exist: ##f(x...
  18. M

    Proof by contradiction and function

    Homework Statement Problem 1 Assuming that the people in D and C all have KTP (Citizen ID in my country) IDs, let: D = {x |x is the KTP ID of a student in your Basic Calculus class}, C = {y |y is the KTP ID of the biological father/mother of a student in your Basic Calculus class}, and f : D...
  19. Keen94

    Is the argument sound? Yes, the argument is sound.

    Homework Statement Suppose that a and b are nonzero real numbers. Prove that if a< 1/a < b < 1/b then a<-1. Homework Equations Givens: a and b are nonzero real numbers, a< 1/a < b < 1/b, and a≥-1. Goal: Arrive at a contradiction.The Attempt at a Solution Scratch work: First establish whether...
  20. T

    Proof by Contradiction: Showing x <= n Leads to a Contradiction

    Homework Statement lets say i have an int n that is greater than 2. I know n!-1 = xk where x and k are integers I must show that x <= n leads to a contradiction The Attempt at a Solution i assume x = n n!-1 =nk (n-1)! -1/n = k it seems to me that because of the 1/n k would not be an integer...
  21. Calculuser

    Understanding Proof by Contradiction in Advanced Calculus

    I was studying the first chapter "Sets and Structures" of the "A Course in Advanced Calculus - Robert S. Borden". I faced a difficulty at the part of the proof of contradiction. I got confused at what this B= \{x \in A : x \not\in f(x) \} is and how it's true that If~y \in A ~\text{is such...
  22. tomwilliam2

    Proof by contradiction for simple inequality

    Homework Statement I'm trying to show that if ##a \approx 1##, then $$-1 \leq \frac{1-a}{a} \leq 1$$ I've started off trying a contradiction, i.e. suppose $$ \frac{|1-a|}{a} > 1$$ either i) $$\frac{1-a}{a} < -1$$ then multiply by a and add a to show $$1 < 0$$ which is clearly...
  23. Z

    Proving Negative Real Numbers Using Contradiction

    Prove by contradiction that a real number that is less than every positive real number cannot be positive having troubles with this could someone give me a small hint to get started?
  24. M

    Proving n^2 is Divisible by 4: Contradiction Method

    Homework Statement Hello Guys, can you check my proof. Problem statement: Let n be an integer such that n2 is even. Prove that n2 is divisible by 4. Proof by contradiction: Suppose n2 is not divisible by 4, thus n is odd. Such that n=2p+1, and n2=4p2+4p+1. Factoring out 2 we have...
  25. Y

    Proof by Contradiction: Showing x ≤ 1 for x∈ℝ+ and t∈T

    Homework Statement Please check that the proof is correct or not. Let ℝ+ = {x\inℝ: x>0} and T = {x\inℝ: 0<x<1}. Let x∈ℝ+ and t∈T Prove: If x\leq xt then x\leq 1. * You may assume any common properties of log(x) as well as : if 0<a\leq b then log(a) ≤ log(b) Any help is appreciated...
  26. C

    Can Proof by Contradiction Be Validated through Logical Equivalences?

    Homework Statement Prove that if x^2 + y = 13 and y \neq 4 , then x \neq 3 .Homework Equations N.A.The Attempt at a Solution The proof itself is simple enough: suppose x^2 + y = 13 and y \neq 4 . Suppose for the sake of contradiction that x = 3 . Then \begin{align*} (3)^2 + y &= 13...
  27. P

    MHB Understanding Proof by Contradiction in Logic and Mathematics

    Is this how proof by condraction works? Say we want to prove A-> B. We prove by showing the statement 'A and not B' implies some statement C which is false (since it contradicts a known fact). Therefore, anything which implies C must itself be false, so 'A and not B' is false. I.e. A implies B.
  28. K

    Proving: Proof by Contradiction

    I'm reading through a text's proof on proof by contradiction. But it makes inexplicable jumps and doesn't appear to use some of the things brought up. Here's the theorem and proof in the text (shortened with comment). \mbox{Theorem: If } \Sigma \cup \{\lnot P\} \vdash \{Q\} \mbox{ and...
  29. A

    Proving √n Irrational: A Proof by Contradiction

    The problem reads as follows: Let n be a positive integer that is not a perfect square. Prove that √n is irrational. I understand the basic outline that a proof would have. Assume √n is rational and use a proof by contradiction. We can set √n=p/q where p and q are integers with gcd(p,q)=1...
  30. H

    Proof by Contradiction || Prove that an equation can never be a square number

    Homework Statement Prove that for any integer n n^2+n+1, can never be a square number. Homework Equations None. The Attempt at a Solution We could put the equation to a^2, (where a^2 is a square number) and solve for n and show that n can not be an integer. I tried quadratic...
  31. C

    Proof by contradiction for statement of the form P->(Q and R)

    Say I have a statement like this: P implies (Q1 and Q2). If I wanted to prove this by contradiction, I would assume P and not(Q1 and Q2)=[(not Q1) or (not Q2)] both hold, and try to find a contradiction. My question is... Am I done if I find a contradiction while assuming P and [(not Q1)...
  32. T

    Divisibility rules and proof by contradiction

    I posted this in the number theory forum to no success... so I figured maybe the homework help people would have some input Let x,y,z be integers with no common divisor satisfying a specific condition, which boils down to 5|(x+y-z) and 2*5^{4}k=(x+y)(z-y)(z-x)((x+y)^2+(z-y)^2+(z-x)^2) or...
  33. A

    Justifying Proof by Contradiction

    It seems to me (though I would be *extremely* glad to be proven wrong here) that in mathematics we often blindly assume that the theorems we attempt to prove/disprove are either true or false. Such an assumption is implicit in every proof by contradiction. We eliminate the possibility of the...
  34. C

    How Many Cases Do I Need to Consider for Proof by Contradiction?

    Homework Statement Suppose I want to prove the following statement by contradiction: P \longrightarrow (Q \land Z) Homework Equations If (Q \land Z) is false, then either: (i) Q is false and Z is true; (ii) Q is true and Z is false; (iii) Q and Z are false. The Attempt at a...
  35. X

    Can I prove the statement if n^2 is odd, then n must be odd by contradiction?

    I never understand the proof by contradiction, because somewhere in the middle I always lost myself. In this https://www.physicsforums.com/showthread.php?t=523874 there's an example of proof by contradiction. We assume that if n^2 is odd than n is odd. This means that if n^2 is even, n...
  36. P

    Proving Statements by Contradiction: Understanding the Logic Behind It

    Hi, I have a question about proofs by contradiction in general. Without getting into the mathematical details, suppose we had the statement: For every (condition A), B is true. If we want to prove this by contradiction, we want to assume the negation of this statement, and then prove it to...
  37. I

    Is At Least One of a or b Even in the Pythagorean Theorem?

    Homework Statement If a,b and c are integers and a2+b2=c2, then at least one of a and b is even. [b]2. Contradiction statement There exist an integer a,b,c such that a2+b2=c2 and a or b is odd The Attempt at a Solution I am not sure if my contradiction statement is correct...
  38. M

    This is the contradiction that proves that l = m.

    Prove: If f approaches l near a and f approaches m near a, then l = m. ...Im skipping to the end of the proof... " to comlete the proof a particular ε>0 has to be choses for which the two conditions |f(x) - l|< ε and |f(x) - m|< ε cannot both hold if l=/=m." if l=/=m so that |l - m|> 0...
  39. S

    How to do a delta-epsilon proof by contradiction?

    Homework Statement Prove that lim x→1 of x2 does not equal 1+10-10. You could use a proof by contradiction. (It is question 2.b here) Homework Equations δ-ε proofs! The Attempt at a Solution Given ε > 0, there is some number δ > 0 such that if: |x - a | < δ |x - 0 | < δ |x| < δ Then: |...
  40. S

    Discrete Math: Proof by contradiction

    Homework Statement Using contradiction, prove that for every four positive real numbers c, d, e and f, at least one of c, d, e, f is greater than or equal to the average of c, d, e, f. Homework Equations I don't believe that there are any relevant equations for this problem. I do know that...
  41. D

    Proving the proof by contradiction method

    Proving the "proof by contradiction" method This can get a little bit fundamental or "axiomatic", if you will. Let's say we can describe sets by prescribing a fixed property P on objects of a certain type, and claiming that a set is a collection of objects satisfying P; i.e. A = \{x : P(x)\}...
  42. G

    Proof by contradiction - For any integer n, n^2 - 2 is not divisible by 4.

    Homework Statement Just as the title said, I need to prove: For any integer n, n2 - 2 is not divisible by 4 by the method of proof by contradiction. Homework Equations (Relevant by division into cases) Even numbers = 2k for some integer k Odd numbers = 2m+1 for some integer m...
  43. B

    Proof by contradiction - polynomials and infinite primes

    Homework Statement Two Questions: 1. Prove, by contradiction, that if a and b are integers and b is odd,, then -1 is not a root of f(x)= ax^2+bx+a. 2. Prove, by contradiction, that there are infinitely many primes as follows. Assume that there only finite primes. Let P be the largest...
  44. T

    Using negation of an for all statment in a proof by contradiction.

    So if I want to prove. A=>B for all x. Does the following work? Suppose for contradiction, B is not true for all x, that is, there exists at least one x such that B is not true. In particular, assume that B is true for x=c and B isn't true for all other x. If I arrive at a...
  45. srfriggen

    Is Dividing an Irrational Number by a Rational Number Always Irrational?

    Homework Statement "Prove that when an irrational number is divided by a nonzero rational number, the resulting number is irrational" The Attempt at a Solution By contradiction: Prove that when an irrational number is divided by a nonzero rational number, the resulting number is...
  46. M

    Proving Infinite Solutions for sin(x)=b in R using Contradiction Method

    Homework Statement I want to practice proofs by contradiction I am trying to prove that sin(x)=b has infinite distinct solutions in R for every b in [-1,1] Homework Equations The Attempt at a Solution assume it has finite amount of solutions called set Z let k be in real number...
  47. B

    Proving 13 + 2√6 is an Irrational Number with Proof by Contradiction

    Homework Statement Prove or disprove the statement: 13 + 2√6 is an irrational number Given that √6 is irrational Homework Equations Rational number = p/q where p and q are integers The Attempt at a Solution Assume that 13 + 2√6 is a rational number Rational number =...
  48. G

    Proof By Contradiction Exercises

    Hi guys, I am looking to find some exercises, preferably online to practice Mathematical Proof by Contradiction. I have just finished my A-levels in the UK doing Maths and Further Maths and very little is done in the way of mathematical proof. The is only a single chapter on proof by...
  49. R

    Proof by Contradiction and Contraposition

    Homework Statement For any integer n, let A(n) be the statement: "If n=4q+1 or n=4q+3 for some q \in Z, then n is odd." (a) Write down the contrapositive of A(n). (b) Is the contrapositive of A(n) true for all n \in N? Give brief reasons. (c) Use proof by contradiction to show that...
  50. S

    Proof by Contradiction: Explanations and Examples in JPG and Doc Formats

    1.the qustion is proof by contradiction is in the jpg file 2. the format of the solution is in the attachement doc.
Back
Top