For questions about contradictions, and proof by contradiction.

learn more… | top users | synonyms

2
votes
1answer
37 views

Determine whether the given pair of statements are contrary, contradictory, or neither.

Consider the following pair of statements: All multiples of three are odd / Some multiples of three are odd. No triangle has an interior angle sum of zero degrees / Some triangle has an ...
0
votes
1answer
44 views

Contradiction proofs

I'm a first year Physics student and I have some trouble approaching Proofs by Contradiction in some of my Math classes. Once I get the first 2 or 3 statements I can finish the proof but a lot of the ...
1
vote
1answer
34 views

Cases of $A^2 = -I$. Why is there a contradiction when reusing this proof?

I had to prove that $\nexists ~A \in M_{3,3}(\mathbb R) : A^2 = - \mathbb I.$ I argued $$\iff A=-A^{-1}$$ $$\iff \det( A)=\det(-A^{-1})$$ $$\iff \det( A)=(-1)^n\det A^{-1}$$ $$\iff \det (A) + \det ...
2
votes
3answers
40 views

how to prove by contradiction that any distance between a curve $x^4 - x^2 + y^4 - y^2 = 0$ and the origin is less than or equal to $\sqrt{2}$

Given a closed trajectory $x^4 - x^2 + y^4 - y^2= 0$ Prove that any distance between any point on the curve and the origin does not exceed $\sqrt2$ (ie, maximum distance from the origin to the curve ...
5
votes
1answer
66 views

Theoretical way to prove no positive integer $n$ exists such that $n+3$ and $n^2+3n+3$ are both perfect cubes.

I have to prove that for any positive integer $n$ at least one of $n+3$ and $n^2+3n+3$ is not a perfect cube. Is there a methodical way to solve this problem? I managed to solve it by contradiction, ...
2
votes
2answers
69 views

Prove that a limit doesn't exist

In my assignment I have to prove that the following function doesn't have a limit: $$f(x)=\frac{x}{x-\lfloor{\sin x}\rfloor}$$ when $${x \to 0}$$ In other words, I have to prove that for every ...
-4
votes
2answers
33 views

Can we prove $\sqrt6$ is irrational by the method of contradiction? [closed]

Can we prove that $\sqrt 6$ is irrational number using the meathod of contradiction?
5
votes
0answers
61 views

Prove that the square root of any irrational number is irrational.

The problem I'm having with this proof is that I'm not sure if my proof actually proves the theorem correct or if I'm using circular reasoning. Theorem: Prove that the square root of any irrational ...
0
votes
1answer
26 views

Rule of inference - Biconditional proposition

I'm having trouble with one of the questions given as an assignment which is to prove: $$(p\land q)\leftrightarrow(r\land s), \neg r\land q \vdash \neg p$$ I guess I should use proof by ...
0
votes
1answer
35 views

How to go about a “not divisible by..” proof

I need to show the following proof: For any integer x, x^2 + 4 is not divisible by 3. I was trying proof by contraposition, but I do not believe that is the most efficient way to go about this. ...
2
votes
0answers
58 views

Another proof of Inverse Function theorem in $\mathbb{R}$

(Inverse Function theorem in $\mathbb{R}$) Suppose $I\subset \mathbb{R}$ is an open interval and $f:I\rightarrow\mathbb{R}$ is a differentiable function.If for all $x\in I$ is such that $f^{'}(x)\ne ...
1
vote
3answers
33 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
38 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
41 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
53 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
35 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. ...
3
votes
2answers
39 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
61 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
65 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
67 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 ...
2
votes
2answers
51 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
67 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
59 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
47 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
60 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
42 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
72 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
119 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
65 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
48 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
80 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
64 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
103 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
38 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
30 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
689 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
57 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
148 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
45 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
24 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
50 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
194 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
77 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 ...