For questions about contradictions, and proof by contradiction.

learn more… | top users | synonyms

0
votes
1answer
30 views

Prove the following using the Real Theorem [closed]

I came across this question in a book and had difficulties in solving it: Let x,y belong to R and a>0 then show that ...
1
vote
4answers
57 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
47 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$
2
votes
2answers
32 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 ...
1
vote
0answers
59 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
95 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
74 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
33 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
69 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
40 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
144 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
67 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
120 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
72 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
106 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
78 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 ...
2
votes
2answers
71 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
56 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
64 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
70 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
62 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
51 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
53 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
66 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
51 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 ...
0
votes
1answer
22 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
289 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
315 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
68 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
146 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
248 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
106 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
510 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 ...
0
votes
3answers
323 views

The contradiction method used to prove that the square root of a prime is irrational

The contradiction method given in certain books to prove that sqare root of a prime is irrational also shows that sqare root of $4$ is irrational, so how is it acceptable? e.g. Suppose $\sqrt{4}$ is ...
1
vote
2answers
109 views

Proof by contradiction with two assumptions

I'm curious whether the following technique has ever been used in a proof of something. Assume two propositions $A$ and $B$, then derive a contradiction. Thus you know that either $\lnot A$ or $\lnot ...
5
votes
2answers
173 views

A proof by contradiction

The symmetric difference of two sets $A$ and $B$ is the set $A \vartriangle B = (A \setminus B) \cup (B\setminus A) = (A \cup B) \setminus (A \cap B)$. Prove that if $A \vartriangle B \subseteq A$ ...
3
votes
4answers
206 views

What's $P$ and what's $Q$ in this classic proof of the irrationality of $\sqrt 2$?

In this proof extracted from the Wikipedia A classic proof by contradiction from mathematics is the proof that the square root of 2 is irrational. If it were rational, it could be expressed as ...
7
votes
2answers
2k views

What's the difference between Complex infinity and undefined?

Can somebody please expand upon the specific meaning of these two similar mathematical ideas and provide usage examples of each one? Thank you!
1
vote
3answers
80 views

Is there a contradiction in this definite integral computation? [closed]

EDIT: This question is wrong. You don't need to waste your time trying to answer it. :D I need help showing that: $$ \int_a^b x f(x) dx = \frac {a+b} 2\int_a^bf(x)dx$$ My attempt. $$ I = ...
2
votes
1answer
53 views

Löb's theorem and working with connectives of two levels

I try to decipher Löb's theorem by getting rid of some of the material implications for something more intuitive and in using classical substitutions for connectives on both levels. I came up with the ...
3
votes
6answers
394 views

Proof By Contradiction, Rational Roots

This was an exam question that I got totally wrong and am a bit question. Prove $x^3 + x + 1 = 0$ has no solutions. Prove by contradiction. Assume: $x^3 +x +1 =0$ has at least one rational root. ...
5
votes
4answers
193 views

Proving $\binom{2n}{n}\le 4^n$ for all $n$ by smallest counterexample

Prove $$\binom{2n}{n}\le 4^n$$ for all natural numbers $n$ by smallest (minimal) counterexample. My attempt: First, $$\binom{2n}n = \frac{(2n)!}{(n!)^2} \le 4^n\;.$$ We know that $x\ne 0$ because ...
2
votes
1answer
99 views

3D Geometry Proof by Contradiction /Contrapositive (high school)

Could someone evaluate my work? A plane perpendicular to one of 2 parallel lines is perpendicular to the other line also. My two column proof so far: Let AB || CD and AB be perpendicular to plane ...
3
votes
1answer
295 views

Proving a function is big O

How would I go about proving a function is big O? Do I use the regular proofs (direct, contrapositive, contradiction)? Example: Prove that $x^n$ is $O(n!)$ for every real number $x$. My proof by ...
40
votes
7answers
2k views

Could I be using proof by contradiction too much?

Lately, I've developed a habit of proving almost everything by contradiction. Even for theorems for which direct proofs are the clear choice, I'd just start by writing "Assume not" then prove it ...
-1
votes
3answers
210 views

Two easy proofs by contradiction

Check the validity of the statements below using contradiction method (i) p: The sum of an irrational number and a rational number is irrational (ii) q: If $n$ is a real number with $n ...
5
votes
2answers
105 views

$\lim_{x\rightarrow\infty}\frac{f(x)}{e^x}$ for analytic functions

For some analytic function $f(x)=\lim_{n\rightarrow\infty}\sum^n_{r=0}c_rx^r$, ...
1
vote
4answers
421 views

i need your help to answer my proof by contradiction

Pythagoras stated that there exist positive natural numbers, $a$, $b$ and $c$ such that $a^2+b^2=c^2$. These three numbers, $a$, $b$ and $c$ are collectively known as a Pythagorean triple. For ...