For questions about contradictions, and proof by contradiction.

learn more… | top users | synonyms

59
votes
12answers
5k views

Conjectures that have been disproved with extremely large counterexamples?

I just came back from my Number Theory course, and during the lecture there was mention of the Collatz Conjecture. I'm sure that everyone here is familiar with it; it describes an operation on a ...
3
votes
4answers
53 views

Proof by contradiction that $(n+1)^3 \not= n^3 +(n-1)^3$ for $3$ consecutive positive integers

Prove by contradiction that if n-1, n, n+1 are consecutive positive integers, then the cube of the largest cannot be equal to the sum of the cubes of the other two. Assume that: $$ (n+1)^3 = ...
1
vote
1answer
50 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
3answers
70 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
2answers
100 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
40 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 ...
1
vote
1answer
48 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 ...
0
votes
2answers
36 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
63 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
63 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
53 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 ...
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 ...
0
votes
3answers
450 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
0answers
31 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 ...
3
votes
1answer
93 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 ...
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
52 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 ...
1
vote
1answer
53 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
68 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
98 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 ...
0
votes
1answer
107 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 ...
1
vote
8answers
109 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
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
80 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
123 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 ...
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: ...
42
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 ...
0
votes
2answers
47 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
150 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
72 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 ...
4
votes
4answers
557 views

Prove that if $(m - 1)! + 1$ is divisible by $m$, $m$ is a prime with $(m - 1)! = 1.2.3…(m - 2)(m - 1)$

$m$ is a positive integer, and $ m > 1$, Prove that if $(m - 1)! + 1$ is divisible by $m$, $m$ is a prime. Solve this by making a contradiction. My english isn't so well. Please help and thank you ...
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
148 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
127 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
106 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
105 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
61 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
59 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.
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!
3
votes
4answers
213 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 ...
0
votes
1answer
55 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
30 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?