For questions about contradictions, and proof by contradiction.

learn more… | top users | synonyms

0
votes
3answers
58 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
36 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
96 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
0
votes
0answers
43 views

What's wrong with this computations?

It is true that $\int_{-\infty}^{+\infty}f(x)dx = 1$ where $f(x)$ is standard normal distribution density function $$\int_{-\infty}^{+\infty}-f(x)d(-x) = 1 \implies \int_{-\infty}^{+\infty}f(x)d(-x) ...
1
vote
1answer
43 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 ...
1
vote
2answers
35 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
40 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
61 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
52 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 ...
1
vote
2answers
62 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
46 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
25 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
18 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
46 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 ...
15
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
1answer
36 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, ...
1
vote
4answers
66 views

Show that if $3\mid(a^2+1)$ then $3$ does not divide $(a+1)$.

Show that if $3\mid(a^2+1)$ then $3$ does not divide $(a+1)$. using proof of contradiction can someone prove this using contradiction method please
2
votes
3answers
52 views

proof by contradiction that if a and b are positive integars and $ab >100$ then at least one of the integars a and b is greater than 10 [closed]

does anyone know how to proof by contradiction that if $a$ and $b$ are positive integars and $ab >100$ then at least one of the integars $a$ and $b$ is greater than $10$
1
vote
2answers
91 views

Suppose F and G are families of sets. Prove that F and G are disjoint iff for all A∈F and B∈G, A and B are disjoint

I am trying to work through this homework problem but I am having trouble getting past how to get started. Could help with setting up this to prove? I know I need to prove by contradiction and ...
3
votes
1answer
91 views

Theorems that we can prove only by contradiction

While most of the world is fine with proofs performed by contradicting the thesis, direct proofs are sometimes considered more elegant than indirect ones. Those who prefer intuitionism or ...
1
vote
8answers
106 views

Prove if $n^3$ is odd, then $n^2 +1$ is even

I'm studying for finals and reviewing this question on my midterm. My question is stated above and I can't quite figure out the proof. On my midterm I used proof by contraposition by stating: If $n^2 ...
0
votes
1answer
97 views

[Beginner]How to tackle mathematical proofs?

So I recently joined university for a BSc in mathematics. I have never been exposed proofs but I have knowledge of algebra, trigonometry, and some differentiation/integration. Now I'm struggling with ...
0
votes
3answers
35 views

A proof using Fermat's Little Theorem?

Let $p$ be prime and let $a\in Z$ such that p doesn't divide a (sorry I couldn't find the symbol for it in MathJaX). Prove that if $k$ is the smallest integer such that $a^k\equiv 1 \pmod p$, then ...
1
vote
4answers
79 views

logic: two simple math contradictions

1.The contradiction of the sentence: - There is a greater number than a million. can be stated as follows: - There is a number which is not greater than a million. 2.and the contradiction of the ...
1
vote
2answers
47 views

Determining if $0$ is part of this set

Let $S$ be a set of rational numbers that is closed under addition and multiplication, and having the property that for every rational number $r$ exactly one the following three statements is true: ...
0
votes
2answers
44 views

Contrapositive Proof: Specific Question! Need help!

I've been stuck on this question for a few days, please help me with this contra positive proof! Suppose that $x$ and $y$ satisfy $\frac 1 2 x + \frac 1 3 y = 1$. Prove that $x^2 + y^2 > ...
3
votes
1answer
147 views

How is this a proof of the irrationality of $\sqrt2$

Proof. Suppose for the sake of contradiction that $\sqrt2$ is rational, and choose the least integer, $q \gt 0$, such that $(\sqrt2 − 1)q$ is a non negative integer. Let $q':=(\sqrt2 − 1)q$. Clearly ...
1
vote
0answers
71 views

Prove that f is identically 0

I am trying to prove this but it seems to me something went wrong. could you help me to prove it by contradiction? Let $(x_m)$ be a real sequence. Let $f:\Bbb{R}\to\Bbb{R}$ be a function such that ...
1
vote
2answers
121 views

If $2$ divides $p^2$, how does it imply $2$ divides $p$?

I'm trying to understand a proof by contradiction. It's proving by contradiction that $\sqrt2$ isn't rational. (It's a standard proof involving $\sqrt2=\frac{p}{q}$, where $p,q$ are already ...
0
votes
1answer
134 views

continuous and bounded function without maximum or minimum

Give an example that contradicts this sentence : $f:(0,1]\to\Bbb R$ is a continuous and bounded function in $(0,1]$ then : $f$ has maximum or minimum. I have understood that $\sin(1/x)$ could be a ...
1
vote
2answers
123 views

Prove or disprove that every Boolean function can be expressed by using only the operator ↓

I know that the ↓ operator means "nor" but how do I prove/disprove that every Boolean function can be expressed using only this operator ? Induction ? Contradiction ? I have to idea where to begin. ...
1
vote
1answer
80 views

Is this a correct proof by contradiction?

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 as ...
3
votes
2answers
96 views

prove that one of the digits 1,2…9 occurs infinitely often in the decimal expansion of pi

prove that one of the digits 1,2...9 occurs infinitely often in the decimal expansion of pi. you may use without proof the fact that pi is irrational. It is recommended using proof by contradiction. ...
1
vote
3answers
58 views

Prove by contradiction: $(a + b + 1) ^ {\frac {1} {a + b}} $ is irrational

Suppose if it is rational: $9 ^ {\frac {1} {8}} = {\frac {m} {n}}$ I know what to do with relative primes. M and N are the relative primes. $(n \times 9 ^ {\frac {1} {8}}) = m $ $(n \times 9 ^ ...
2
votes
3answers
66 views

Prove that if $n^{2} - \left(n - 2\right)^{2}$ is not divisible by $8$ then $n$ is even

Let n be an integer. Prove that if $n^{2} -\left(n - 2\right)^{2}$ is not divisible by $8$ then $n$ is even. Can anyone help me step by step to understand this.
0
votes
1answer
92 views

Proofs by contradiction and set theory

I'm having trouble understanding proofs by contradiction. I'm running things by memory and not by understanding what a contradiction is. I'd like to know what we're assuming and how to start. My ...
0
votes
3answers
63 views

Is it right to say that: if $2a+1=2b$ we have a contradiction?

I am trying to prove by contradiction and I have reached the conclusion that $2a+1=2b$. Now I am tempted to say it's a contradiction and call it a night. Is it a contradiction? because one is even and ...
0
votes
2answers
60 views

Using induction to prove $a_n >2^n$

For the sequence $a_n=2a_{n-1}+1$ where $a_0=1$ Show that $a_n>2^n$ using induction. Use proof by contradiction (minimum counterexample). Attempt: 1. I assume, that ...
0
votes
2answers
57 views

Question Regarding Logical Contradiction

Let's say I attempted to solve a logical statement in the form using contradiction: $\forall x \in \Bbb R, (P \implies Q)$ Negated: $\exists x \in \Bbb R, (P \land \lnot$ Q). Initially I did not ...
1
vote
4answers
67 views

Prove that if $3|(a^2+b^2)$, then $3|a$ and $3|b$, where $a, b$ are integers [duplicate]

I would like to know how to prove the above statement by contradition. Somebody said that one should prove it by this method but I have no idea what it is.
0
votes
1answer
54 views

Is this proof correct? (GCD)

If this proof is incorrect can someone tell me what is wrong with it, and which step is incorrect. Let a, b ∈ℤ If gcd(a, b) = 35, then 25 ∤ a or 25 ∤ b. Proof Consider the contrapositive: if 25|a ...
-1
votes
1answer
29 views

proofs involving power sets and universal quantifiers

Im having trouble solving with a proof problem "A is not equal to the Null class then the intersection of class A is a set" and help on proofing this?
6
votes
3answers
298 views

Does a proof by contradiction always exist?

Good day, Usually, proofs by contradictions are the easier, and sometimes, even the only ones available. However, there are cases where the easiest proof is not the proof by contradiction. For ...
4
votes
3answers
338 views

Proof by induction or contradiction?

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 ...
1
vote
1answer
71 views

Prove the limit..

$\varinjlim \sqrt{n^2+1}-n=0$. I need to prove that this converges to 0. Usung the definition of a sequence helps for the normal problems but for this I believe the triangle inequality is used at ...
2
votes
3answers
177 views

How to solve a statement with contradiction evidence?

I'm trying to solve the statement below with contradiction evidence. If $(P \rightarrow Q)$ and $(Q \rightarrow R)$ is true, then $(P \rightarrow R)$ is true. This is what i've done so far: ...
13
votes
2answers
296 views

What practical proofs work in intuitionistic but not minimal logic?

Intuitionistic logic contains the rule $\bot \rightarrow \phi$ for every $\phi$. In the formulations I have seen this is a separate axiom, and the logic without this axiom(?) is termed "minimal ...
2
votes
1answer
120 views

Is proof by contradiction always a sufficient proof technique?

Is proof by contradiction always a sufficient proof technique ? A proof by contradiction has the form: Let $P$ and $Q$ be statements. If $ P \rightarrow Q \land \lnot Q $ then you can conclude ...
0
votes
3answers
123 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 this ...
2
votes
2answers
652 views

Contradict the Contraction Mapping Theorem

I am trying to show that the function $f(x) = 2\pi+x-\tan^{-1}x$ is contractive but has no fixed points. Finally I wish to conclude that it does not contradict the contraction mapping theorem. $f$ is ...