For questions about contradictions, and proof by contradiction.

learn more… | top users | synonyms

2
votes
2answers
131 views

Proof by Contradiction on prime numbers [duplicate]

Prove using contradiction that any prime number greater than $3$ is of the form $6n \pm 1$. Thanks for any help
0
votes
3answers
52 views

Other method show that $ A(x)=x^2+x+1=0$ has a zeros in $\mathbb{R}$ but why this contradiction?

Let $ A(x)=x^2+x+1$ be a quadratic polynomial equation and $ x \in\mathbb{R}$. It is well known that $ A(x)=x^2+x+1=0$ hasn't a roots in $\mathbb {R}$ , we choose another way to solve this equation ...
3
votes
2answers
57 views

Finding flaw in proof

This is one of the problem I have been working on Velleman's How to prove book: Incorrect Theorem. Suppose F and G are families of sets. If ∪F and ∪G are ...
0
votes
1answer
21 views

Can you use proof by contradiction inside simple induction?

During a proof using simple induction, I assumed P(k) is true. Now in order to show P(k+1) is true using P(k), can I do a proof by contradiction on P(k+1) and say P(k) would be wrong if P(k+1) is ...
0
votes
3answers
27 views

For every integer m, 2 divides m, and 4 doesn't divide m, there are no integers, x and y that satisfy x^2 + 3y^2 = m.

For every integer m, 2 divides m, and 4 doesn't divide m, there are no integers, x and y that satisfy x^2 + 3y^2 = m. Use a contradiction (assume the negation is true) Is my negation of the ...
2
votes
5answers
626 views

How to prove that there are infinitely many primes without using contradiction

How can I prove that there are infinitely many primes without using contradiction? I know the proof that is (not) by Euclid saying there are infinitely many primes. It assumes that there is a ...
0
votes
2answers
41 views

Prove $\forall a,b \in \mathbb{Z}, 18a + 6b \ne 1$

Prove $\forall a,b \in \mathbb{Z}, 18a + 6b \ne 1$ Is there a way to do this using proof by contradiction without using mod?
1
vote
3answers
40 views

Prove $\forall a,b \in \mathbb{Z}$, $a^2 -4b - 3 \ne 0$ using proof by contradiction

Prove $\forall a,b \in \mathbb{Z}$, $a^2 -4b - 3 \ne 0$ I want to do a proof by Contradiction. I know that this can be figured out using Rational root theorem by subbing in (1, -1, 3, -3), but I am ...
4
votes
3answers
84 views

Prove $x^5 + x^4 + x^3 + x^2 + 1 = 0$ has no rational solution

Prove $x^5 + x^4 + x^3 + x^2 + 1 = 0$ has no rational solution I want to prove it by Proof by Contradiction, but I am not sure how to proceed with the proof.
-2
votes
1answer
33 views

What means $A \subsetneq X$ with A ~ X? [closed]

How it is possible to have a subset A, which is $\neq$ to X and at the same time they have an equivalence relation ~? When $A \subset X$ therefore a $\in$ A is also a $\in$ X. With A ~ X ...
0
votes
1answer
19 views

A question about proof by contradiction

$1$. Claim: $\varnothing$ is an antichain. $Proof$: Suppose $\varnothing$ is not an antichain. Then $\exists$ a pair $x, y \in \varnothing$ such that $x$ and $y$ are comparable. Contradiction: ...
0
votes
2answers
46 views

How do I prove this using proof by contradiction

There is a set a set $S$ of numbers. i.e. $(s_1, s_2, s_3, s_4, s_5, ..., s_n)$. The average of the numbers in the set is $N$. How do I prove that at least one of the numbers in the set is greater ...
2
votes
1answer
72 views

1.Why is this proof of “$\sqrt{2}$ is irrational” titled as “Proof by infinite descent”?2. Do I understand it correctly?

I am reading this wikipedea article on the proof of irrationality of $\sqrt{2}$. It uses the principle of infinite descent. I understand it as: We assume $\sqrt{2}=\dfrac pq$, where $p$ and $q$ are ...
5
votes
1answer
132 views

Understanding the proof of “$\sqrt{2}$ is irrational” by contradiction.

I have some difficulties in understanding the proof of "$\sqrt{2}$is irrational" by contradiction. I am reading it in 10th class(in India) Mathematics book( available online, here ) This is the ...
0
votes
4answers
87 views

For every $x \in [\frac{\pi}{2},\pi]$, $\sin(x)+\cos(x)\geq 1$. Prove rigorously by contradiction.

For every $x \in [o,\frac{\pi}{2}]$, $\sin(x)+\cos(x)\geq 1$. How do you prove this rigorously by contradiction? I understand you start by assuming that $\sin(x)+ \cos(x)<1$ and prove this is a ...
0
votes
2answers
18 views

Proof by contradiction how to show is properly

For every $x \in \left[\pi/2,\pi\right]\,,\ \sin\left(x\right) − \cos\left(x\right) \geq 1$. I have drawn the graph and can clearly see that A is true however how do I prove it correctly.
0
votes
1answer
65 views

prove pigeonhole problem using contradiction

I'm trying to prove this pigeonhole problem: Given that fact that $\lceil x \rceil < x + 1$, give a proof by contradiction that if $n$ items are placed in $m$ boxes then at least one box must ...
0
votes
2answers
76 views

prove by contradicition that there does not exist a constant $c$, such that for all integers $n \geq1$, $(n+1)^2 - n^2 < c$

First thing I did was simplify the above to $2n-1 < c$, from there I changed the simplified expression to $2n-1 \geq c$ and tried to make that contradict with $n \geq 1$. the problem being that I ...
4
votes
1answer
132 views

Proof by counter example of optimal solution for Coin Changing problem (no nickels)

I'm a tutoring a student whose working on the classical coin changing problem. For those who are unfamiliar with problem or the greedy algorithm used for it. The goal is find the fewest number coins ...
1
vote
2answers
107 views

Proof Question using Proof By Contradiction, irrationality of $a + \sqrt[b]{5}$

I answered this question but am not quite sure if i did what was correct. If anything is wrong please point it out, thanks. Question:Prove that any number of the form $a + \sqrt[b]5$ is irrational, ...
0
votes
1answer
39 views

Prove using a proof by contradiction: There is no smallest positive real number

Prove using a proof by contradiction: There is no smallest positive real number Let us assume the contraction: There is a smallest positive real number. How do I continue?
1
vote
3answers
116 views

Show that there are no positive integer solutions to x^2 + x + 1 = y^2.

I'm trying to prove that $x^2 + x + 1 = y^2$ has no integer solution, but I'm having a lot of trouble. So far I've tried proof by contradiction, but all of that seems to rely on me being able to ...
0
votes
2answers
45 views

Are there multiple contrapositives?

Are there "multiple contrapositives"? Normally a contrapositive from P implies Q changes to not Q implies not P. Secondly, can a contrapositive be in the from of P in the antecedent and Q be the ...
0
votes
4answers
42 views

Proof by contradiction involving set theory

Using a contradiction, prove the following: If $S\cap T = \emptyset$ and $S\cup T = T$, then $S = \emptyset$. So far, I've written the definitions of the intersection and union, and I've ...
4
votes
2answers
957 views

“A Proof by Contradiction”

Prove that for all $x,y \in \mathbb{Z}$, $x^2 - 4y \ne 2$. Using a contradictory method would be appropriate. So, for this question, I assume, for the sake of a contradiction, that There exists ...
1
vote
2answers
43 views

Do we simplify the Proof by Contradiction?

Prove the following by contradiction: Suppose $a,b\in\mathbb{Z}$. If $4|\left(a^2+b^2\right)$, then $a$ and $b$ are not both odd (in other words, $a$ and $b$ are even) So, I did this: Assume $a$ ...
0
votes
0answers
54 views

Proving that there always exists two opposite points on a circle where the temperature difference is less than 1

You are given $n$ ($n$ is even) integers $a_0,a_1,\ldots,a_{n-1}$ representing temperature measurements, equally spaced around a circle. Since the points are "close", the temperature difference ...
0
votes
4answers
34 views

Show that if n is an integer and 3n+ 2 is even, then n is even using contradiction

Show that if $n$ is an integer and $3n+ 2$ is even, then $n$ is even, using a proof by contradiction. That's the question. So since we're using contradiction, I need to show that N is odd and prove ...
5
votes
1answer
212 views

If $x\rightarrow y$ and $y \rightarrow z$, prove, by contradiction, that $x \rightarrow z$

Say you're given $$x\Rightarrow y$$ $$y\Rightarrow z$$ Prove that $x\Rightarrow z$ by contradiction. It seems like such a simple task, because it's easy to evaluate that it must be true. But I ...
1
vote
2answers
226 views

Prove that if all edge-costs are different, then there is only one cheapest tree.

Prove that if all edge-costs are different, then there is only one cheapest tree (minimum spanning tree). (Use contradiction and make sure to keep track of the costs of the different trees involved.) ...
0
votes
1answer
61 views

is this proof by contradiction fine? sum of composite numbers

I have seen the following problem: Any number n>11 can be formed by the sum of two composite numbers and it says to prove it by contradiction. I have done the following: Assume that the sum will be ...
15
votes
10answers
2k views

Having hard time understanding proofs by contradiction.

I am reading an introductory book on mathematical proofs and I don't seem to understand the mechanics of proof by contradiction. Consider the following example. $\textbf{Theorem:}$ If $P \rightarrow ...
2
votes
2answers
53 views

Proof by Contradiction with Multiple Axioms

Looking at proofs by contradiction and it seems I've run into something that does not sit well with me. I am fine with the law of the excluded middle (thus not an intuitionist) and more fundamentally ...
4
votes
4answers
62 views

Proof by contradiction that $(n+1)^3 \not= n^3 +(n-1)^3$ for $3$ consecutive positive integers

Prove by contradiction that if n-1, n, n+1 are consecutive positive integers, then the cube of the largest cannot be equal to the sum of the cubes of the other two. Assume that: $$ (n+1)^3 = ...
1
vote
1answer
67 views

Help prove $f:X \rightarrow Y$ is an injection $\Leftrightarrow$ $f:X\rightarrow Y$ is a surjection when $|X|=|Y|$

I need to prove: Given non-empty finite sets $X$ and $Y$ with $|X| = |Y|,$ a function $X\rightarrow Y$ is an injection if and only if it is a surjection. The hint given is to use the pigeonhole ...
0
votes
3answers
167 views

Proof by contradiction using counterexample

Why can't we use one counter example as the contradiction to the contradicting statement? Example: Let a statement be A where a-->b. We can prove A is not true by finding a counter example. Now, in ...
0
votes
0answers
42 views

four point in a row

We have painted all dots of page with two colors(blue and green), proof that there are four point with green color in a line that distance of any two neighbors of this four is one unit or there are ...
0
votes
2answers
110 views

Prove: If $a\in\mathbb Z$ and $|a| > 1$, then $1/a \notin \mathbb Z$.

Prove: If $a$ is an integer and $|a| > 1$, then $1/a$ is not an integer. Hi, I need help proving this either by contradiction or contrapositive. I'm not sure where to begin
1
vote
1answer
65 views

Check workings for Strong Induction (Proof by Contradiction)

I want to prove the following: Suppose that $P(n)$ is a statement involving a general positive integer $n$. Then $P(n)$ is true for all positive integers $n$ if: i) $P(1)$ is true, and ...
0
votes
2answers
43 views

Contrapositive proof using rule of divisibility

Suppose $x,y,z$ are integers and $x \neq 0 $ if $x$ does not divide $yz$ then $x$ does not divide $y$ and $x$ does not divide $z$. So far I have: Suppose it is false that $x$ does not divide $y$ and ...
1
vote
0answers
46 views

What is the relationship between division and proving an integer is odd?

I am trying to use proof by contradiction to prove: $101$ is an odd integer. I know that the first step is to assume that $101$ is even, so: $101 = 2q, q \in \mathbb{Z}$ Then I am stuck. I don't ...
2
votes
1answer
64 views

About an impossibility

Suppose Goldbach conjecture true: $\forall{n\geq{9}}$ integer, $\exists{p_1\geq{3},p_2\geq{3}}$ primes for which $2n=p_1+p_2$. But $\forall{m>1}$ integer, $\forall{p_1\geq{3},p_2\geq{3}}$ primes, ...
0
votes
5answers
55 views

How to prove that $x^2≡2(\bmod 3)$ is not a complete square

Let $m$ be the product of first n primes (n > 1) , in the following expression : $$m=2⋅3…p_n$$ I want to prove that $(m-1)$ is not a complete square. I found two ways that might prove this . My ...
2
votes
2answers
90 views

Query about Reductio Ad Absurdum

If we use the method of contradiction(i.e.Reductio Ad Absurdum), and if one of our assumptions is wrong, does that mean that all our assumptions are wrong and is the statement or hypothesis proved?
1
vote
1answer
61 views

Mathematical Proof (Apostol)

If $x > 0$, prove that there is a positive integer $n$ such that $\frac{1}{n} < x$ byy either contradiction or contrapositives. My attempts By contrapositives: Givens by contrapositive method ...
1
vote
0answers
87 views

Can proof by contradiction and counterexample by used at the same proof?

Here is a part of a theorem: If $\alpha>1$ and $x\ge-1$ then $(1+x)^\alpha \ge 1 + \alpha x$ I was wondering if I could use proof by contradiction and counterexample at the same time. Assume ...
0
votes
1answer
19 views

Struggling with proof, by contrapositive?

I am having trouble solving this proof. I tried to do a proof by contrapositive. Q = $(u+z)/(v+w) < z/w$ P = $(u/v < x/y \land x/y < z/w)$ Assuming $\lnot Q$ got me: $u/v \ge z/w$ ...
2
votes
1answer
97 views

Counter-example to contraction principle

One of the conditions of contraction principle is $d(fx,fy)<cd(x,y)$ for all $x,y$ where $c<1$. Now I am finding an example that when the condition is replaced by $d(fx,fy)<d(x,y)$, the ...
16
votes
10answers
1k views

Challenge: Demonstrate a Contradiction in Leibniz' differential notation

I want to know if the Leibniz differential notation actually leads to contradictions - I am starting to think it does not. And just to eliminate the most commonly showcased 'difficulty': For the ...
1
vote
0answers
164 views

Proof by contradiction problem on rational numbers

Using proofs by contradiction, show that there is no smallest negative rational number and no largest positive rational number. Assume that there is a smallest negative rational number. Therefore, ...