What is Proof by contradiction: Definition and 57 Discussions
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.
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...
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...
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...
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##...
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...
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...
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...
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...
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...
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...
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##...
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##...
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...
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...
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...
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.
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...
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...
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...
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...
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...
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...
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?
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...
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...
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...
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.
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...
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...
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...
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)...
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...
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...
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...
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 [Broken] 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...
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...
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...
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...
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:
|...
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...
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)\}...
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...
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...
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...
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...
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...
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 =...
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...
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...