For questions about contradictions, and proof by contradiction.

learn more… | top users | synonyms

2
votes
3answers
55 views

Proving that rational numbers are dense

I am trying to show that for any real number a, there exist infinitely many rational numbers m/n with $ |a - m/n| < 1 /n^{2} $. I've tried to attempt the question by assuming there are finite ...
1
vote
0answers
20 views

Twisted colouring problem

I had doubts in the following similar looking questions I came across:- $Q1.$ The Cartesian plane is coloured with 2 colours. Prove that there exists 3 points of the same colour, which are the ...
1
vote
3answers
55 views

Proof by contradiction in Discrete Mathematics

Ok, so my college book is the worst book ever and I can only survive from this site and youtube. Could someone please explain the answer below? I really do not understand the answer and to me there is ...
1
vote
0answers
51 views

Does Gödel's incompleteness theorem contradict itself?

I have problems understanding Gödel's incompleteness theorem. I presume I have a misunderstanding of some phrase or I have to look closer at the meaning of some detail. Gödel's second incompleteness ...
0
votes
1answer
36 views

Formal Method for Determining the Domain of Solutions to an Equation?

     I'm doing an algebra review packet in order to prepare to take an independent-study calculus class. About five eighths of the way through the problems posed by this ...
2
votes
1answer
39 views

Rectifying Proof

At the moment I read "How to Prove It" by Velleman. I reached & solved the same exercise as in this question: Finding flaw in proof. The exercise was formulated like this and the other asker had ...
3
votes
0answers
77 views

Is this a valid proof for $1+1=2$? [duplicate]

I am extremely new to proofs, and quite bad at them. In studying and practicing the different types of proofs, I developed this very rough proof that $1+1=2$, one of the simplest mathematical truths I ...
3
votes
2answers
149 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
59 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
74 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
27 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
28 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
637 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
44 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
44 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 ...
5
votes
3answers
130 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
36 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
20 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
74 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
141 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
88 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
19 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
71 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
78 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
176 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
119 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
43 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
132 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
46 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
962 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
44 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
56 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
43 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
213 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
242 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
72 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
55 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
66 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
68 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
191 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
112 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
68 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
45 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
48 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 ...