For questions about contradictions, and proof by contradiction.

learn more… | top users | synonyms

0
votes
1answer
29 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
55 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 ...
-2
votes
0answers
31 views

Product of irrational number by a rational number always irrational

Prove or disprove: the product of an irrational number by a rational number is always irrational. Show that $\lceil n/2 \rceil * \lfloor n/2 \rfloor = \lfloor n^2/4 \rfloor $ False. Any irrational ...
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
2answers
358 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.) ...
1
vote
0answers
37 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
36 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
50 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
64 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 ...
2
votes
2answers
47 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 ...
2
votes
2answers
89 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
2answers
43 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
43 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 ...
11
votes
6answers
517 views

How do we know that we'll never prove a contradiction in Math

I know that we can prove a contradiction in naive set theory. Let D be a set of all sets that don't contain itself. Say D does not contain D. Then D contains D. That means D contains itself. A ...
1
vote
1answer
51 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 ...
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 ...
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 ...
2
votes
3answers
70 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 ...
5
votes
3answers
144 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.
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
84 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 ...
1
vote
1answer
89 views

Proof by contradiction that if a set $A$ contains $n_0$ and contains $k+1$ whenever it contains $k$, then it contains all numbers $\ge n_0$

Prove that if a set $A$ of natural numbers contains $n_0$ and contains $k+1$ whenever it contains $k$, then $A$ contains all natural numbers $\geq n_0$. I have attempted a proof by contradiction ...
4
votes
3answers
474 views

Proof by induction or contradiction that $(4k + 3) ^2 - (4k + 3)$ is not divisible by $4$?

I have to prove that $(4k + 3) ^2 - (4k + 3)$ is not divisible by $4$. What would be the best approach for this, proof by induction or contradiction? I've tried both and haven't got very far. Any ...
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 ...
0
votes
3answers
152 views

Real analysis …show if its a rational number

Show $(3+(2\sqrt{2})^\frac{2}{3}$ is not a rational number... My result $x^3-6x^\frac{3}{2}+7=0$ $\{-1,1,-7,7\}$ will not equal to zero .. Is my polynomial acceptable? I used contradiction for ...
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
95 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
37 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
674 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 ...
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 ...
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?
-2
votes
1answer
42 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
184 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
247 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 ...