Proof by contradiction Definition and 58 Threads

I'm taking a look at intuitionistic propositional logic (IPL). Basically it exclude Double Negation Elimination (DNE) from the set of axiom schemas replacing it with Ex falso quodlibet: ⊥ → p for any proposition p (including both atomic and composite propositions). In IPL, for instance, the Law...

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 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...

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...