For questions about contradictions, and proof by contradiction.

learn more… | top users | synonyms

1
vote
3answers
32 views

Disproving a inequality implication by contradiction.

Let $x,y \in R$. If $0 \leq y < x$ for all $x > 0$, then $y=0$. Proof by contradiction: Assume the opposite that is; "If $0 \leq y < x$ for all $x > 0$, then $y\neq0$". ...
1
vote
0answers
36 views

Proof by contradiction to prove an inequality does not hold

I am trying to prove that there is no positive integer x such that $2x < x^2 < 3x$. I started by assuming that this statement is true. I then subtracted 3x from each part of the inequality to ...
2
votes
2answers
39 views

Proving injectivity by contradiction

Define the function $g:\mathbb N \rightarrow \mathbb N$ with $g(d)= d^2 + d + 1$ I started out by assuming that if two arbitrary elements of $\mathbb N$, $x$ and $y$,where $x>y$ without loss of ...
2
votes
1answer
50 views

Implementing the $\Rightarrow \Leftarrow$ contradiction symbol?

How is the $\Rightarrow \Leftarrow$ symbol actually used in practice? I think my issue here is that I don't know what the symbol is meant to mean. For example, I know that $\implies$ means "which ...
1
vote
1answer
33 views

Proof by contradiction

I want to prove that, for all algebraic $n\neq0\text{ or }1$, $\ln n$ is transcendental. Here's how I tried to do it: $n$ is an algebraic number, $n\neq0\text{ or }1$. Assume $x$ is algebraic. ...
2
votes
2answers
35 views

Have troubles with contradiction of a statement

"Suppose that there are 13 people in a room. Prove: "At least two of these people were born in the same month". Use the indirect method." The question I have is: Which of the following (if any) are ...
0
votes
1answer
49 views

How to prove a tautology using proof by contradiction?

I am trying to learn proof by contradiction. How would i go about proving that ((A => B) and (C => D)) => ((A => D) or (C => B)) is a tautology, ...
2
votes
1answer
45 views

Contradicting theorems

Let $a,x,y\in\mathbb{Z}$ and $m\in\mathbb{N}$ Theorem 1: If $x\equiv y\pmod{m}$ and $a>0$ then $ax\equiv ay\pmod{am}$ Theorem 2: $ax\equiv ay\pmod{m}\Leftrightarrow x\equiv ...
0
votes
4answers
63 views

Proof by contradiction that $B \cap C$ is an empty set

Let $B$ and $C$ be sets such that $$B = \{b \in\mathbb{Z} \mid b = 8n+2 \text{ for some } n\in\mathbb{Z}\}$$ $$C = \{c \in\mathbb{Z} \mid c = 4m \text{ for some } m\in\mathbb{Z}\}$$ Prove by ...
2
votes
1answer
63 views

How do I use proof by contradiction to prove that for all prime numbers $x$, $y$, and $z$, $x^2 + y^2 \neq z^2$?

Original implication: For all prime numbers $x$, $y$, and $z$, $x^2 + y^2 \neq z^2$. I'm not certain if I'm understanding the process of proof by contradiction correctly. What I am understanding so ...
1
vote
2answers
41 views

How to define new constants in Tableaux Method of predicate logic

As you all know, in predicate logic when using Tableaux Method the quantifiers must be removed and their variables must be replaced with constants inside the relations and functions. The problem is I ...
0
votes
2answers
66 views

Statement of “proof by contradiction”

Wikipedia states: In mathematical logic, the proof by contradiction is represented as "if $S \cup \{ P \} \vdash \mathbb{F}$ then $S \vdash \neg P$" or "if $S \cup \{ \neg P \} \vdash ...
0
votes
2answers
38 views

Discrtete math proof by contradiction problem

I have the following problem that I must prove by CONTRADICTION: "Show that if you pick three socks from a drawer containing just blue socks and black socks, you must get either a pair of blue socks ...
0
votes
2answers
41 views

Proof : Do 4 days fall on the same day?

I was working my way through some discrete math proof examples from Discrete Math by Rosen and being a newbie am stuck on this problem : Show that at least four of any 22 days must fall on the ...
1
vote
1answer
46 views

Puzzle : Truant List of Statements

I was working my way through some puzzles in Discrete Maths by Rosen, when I came across the following question: The $n^{th}$ statement in a list of 100 statements is : "Exactly $n$ of the ...
3
votes
1answer
18 views

Find X so that $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is contradiction

I have to find X so that this $(p \Longleftrightarrow ¬q) ∧ (r ⇒ X) ∧ (¬r ⇒ ¬X)$ is a contradiction. Then I also have to find out whether or not I can find an X is a tautology. What's the most ...
0
votes
0answers
37 views

Contrapositive/contradiction of statement with quantifiers

In general how does one formulate a proof by controposition or contradiction for the following general form: $\forall x\exists ! y (P(x)\wedge Q(y) \rightarrow R(x,y))$ Or more specifically: $\forall ...
2
votes
3answers
68 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
21 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
79 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
62 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 ...
2
votes
1answer
43 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
79 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
162 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
63 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
94 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
36 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
29 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
672 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
45 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
51 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
143 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
39 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
23 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
49 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 ...
6
votes
1answer
179 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
94 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
75 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
83 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
243 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
159 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
73 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
257 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 ...
1
vote
2answers
55 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
48 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
994 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
46 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
68 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
187 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 ...