>proof by contradiction

like mormons ?

What's the problem with that?

>>8071276
It's poor form and 99 times out of 100, it's not really a proof by contradiction and the person should rewrite it more clearly. An obsession with proof by contradiction is the surest way to spot the kid who just passed his intro to proofs course.

> proof by contradiction
can someone give an example ?

>>8071296
I am not a math fag but I know the proof that there are an infinite number of primal numbers is an example for this.

>>8071299
It's really not.

>>8071296
A proof by contradiction would be the usual proof that the square root of 2 is irrational.

>>8071293
>It's poor form
Truth knows no poor form, pleb.

>>8071299
Well I mean the usual proof of infinitude of primes begins with "Suppose that Pn is finite list that contains all primes" ....

>>8071296
does a set of all sets contain itself?

>>8071320
Wrong. You show that given a finite list of primes, there must be some prime not included in that list, and therefore there are not finitely many primes.

>>8071251
I know your high-school pea-brain is used to only seeing proofs written out in natural language, but when you get to big boy classes on logic, a proof by contradiction/RAA is just another valid introduction rule for logical predicates.

Take a look, if you would, but try not to strain yourself
http://www.phil.cmu.edu/projects/logicandproofs/alpha/htmltest/m05_indirect_rules/translated_chapter5.html

>>8071251
Take your pedophile cartoons back to >>>/a/.

Fucking degenerate.

>>8071334
Well yeah actually your right. We just did it by contradiction in our elem. number theory course

>>8071334
You literally just outlined exactly a proof by contradiction.

Please stop being contrarian.

>>8071372
What's the contradiction? Never do I assume that there are only finitely many primes, because there's no reason for me to do so.

>>8071382
To get from your statement, 'there is no complete list of primes which is finite', to 'there are an infinite number of primes', you implicitly use a proof by contradiction.

Notice that you don't positively shown that there an infinite number, just that there can't be a finite number.

>>8071334
The list of primes can either be finite or infinite.
But we've shown that it's not finite.
So it must be ????????????

>>8071407
>>8071411
The exact statement proven is "Let L be a subset of the set P of prime numbers. If L is finite, then L is a proper subset of P." This is completely equivalent to the statement "If L=P, then L is infinite." That's called the contrapositive. Would you like me to hold your hand through writing out truth tables showing these are equivalent?

The intermediate steps in a proof by contradiction are rather useless because they do not provide new mathematical knowledge.

>>8071320
>>8071334
>>8071372
>>8071382
>>8071407
>>8071411
It's a proof by negation, not a proof by contradiction.

P is the statement "There's a finite number of primes", and we wish to prove ~P (its negation). So we assume P, and then we reach a contradiction. From that, we conclude that ~P must be true, by the proposition in predicate logic: (P→F)→~P.

Proofs by negation are completely valid in constructive logic. However, proofs by negation are not.

On the other hand, consider this: Someone proves that e^e is rational, by first assuming that it's irrational and reaching a contradiction. This method of proving relies on the proposition ~(~P)=P, or equally Pv~P, both are disallowed in constructive logic.

http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/

>>8071293
>An obsession with proof by contradiction is the surest way to spot the kid who just passed his intro to proofs course.
No, the surest way to spot the kid who just passed his intro to proofs course is autistic hairsplitting over logical minutia.

>>8071427
Sorry, I meant ~(~P)→P

>>8071427
Thanks for the clarification. I had assumed we were talking about classical logic, where they're equivalent

>>8071427
Most autistic post on /sci/ right now.

>>8071427
>It's a proof by negation, not a proof by contradiction
>So we assume P, and then we reach a contradiction. From that, we conclude that ~P must be true

>we reach a contradiction
>not a proof by contradiction

>>8071468
To be fair, there is a distinction in constructive mathematics. The guy arguing with people is still being autistic since we're working in classical logic and they're literally identical

>>8071468
It is not a proof by contradiction. You do not assume that the finite set of prime numbers is the set of all prime numbers. You take any finite set of prime numbers....

The anon saying that the proof of the infinitude of primes is not a proof by contradiction is actually right, if he's talking about the usual proof attributed to Euclid.

Euclid's original proof is constructive. I may be mistaken on this because I can't find a source right now 'cause I'm on my cellphone, but I think the misconception started when Cauchy said the proof was by contradiction or something like that. The outline of the proof is basically some thing like this: http://math.stackexchange.com/a/632129

I'll try to find the actual source when I have some time.

A good, simpls proof by contradiction is the proof that the square root of 2 is irrational.

>>8071486
And this is correct.

>>8071486
Really? I was only familiar with a proof by negation :^)

>>8071490
For that proof you have the statement A (sqrt(2) is rational) then you assume that it is not A (sqrt(2) is rational). A contradiction is then arrived at. I don't see how it is negation as negation is the other way around (not A to A).

>>8071498
Correction: meant to say statement A is sqrt(2) is irrational

They seem to be the same as long as you modify what your original statement A is

I used it to prove that limits are unique. :D

File: 1459382823419.png (165KB, 777x656px) Image search: [Google]

165KB, 777x656px

>>8071251

>>8071509
Take your pedophile cartoons back to >>>/a/.

Fucking weeaboo degenerate.

Reductio ad absurdum is the best argument destroyer in philosophy

>>8071515
>I'm gonna get mad and call him names, that'll surely make him stop

>>8071427
>Proofs by negation are completely valid in constructive logic. However, proofs by negation are not.
fucking constructivists

Think about this one proof be paradox

File: 1461807293700.jpg (106KB, 720x720px) Image search: [Google]

106KB, 720x720px

>>8071515
Here have a cartoon

>>8071296
Prove there does not exist a number X such that X+1=X

Suppose there exists a number X such that X+1=X
X+1=X *is true =>
X+1+ (-X) = X + (-X) *-X exists because additive inverse =>
X+(-X)+1 = 0 * add inverse and commutativity =>
0 + 1 = 0 * neutral additive =>
1=0 ! contradiction
therefore X+1=X is not true

>>8071543
True this.

Proof by nonesense

>>8071810
Wrong. What you're referring to is a proof by negation.

See >>8071427

>>8071837
Then pls post example of proof by contradiction.

>>8071427
>Proofs by negation are completely valid in constructive logic. However, proofs by negation are not.
wat

>>8071861
I meant proofs by contradiction for the second

It was a quick post, probably not very accurate

>>8071853
http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/

>>8071865
Looks like a good blog, thanks for the link

>>8071865
Do you know of an example where ignoring the difference between proof by contradiction and proof by negation is important?
Seems like the logic is quite similar, the names are irrelevant to me if the logic speaks for itself.

>>8071871
>>8071865
The way you know someone is full of shit is when they keep posting links to blogs and whatever instead if just giving a damn example.

>>8071886
I prefer to read the blog and find out if the blog is full of shit.
There's a very pedantic atmosphere here in /sci/, so I try to avoid being a pedant.

File: contradiction.png (47KB, 1079x312px) Image search: [Google]

47KB, 1079x312px

>>8071853
Is this one?
(sorry for the mess of algebra)

>>8071903
Pure contrapositive. Which is good, since it's cleaner and most of the time when people write proofs by contradiction this is all they've actually done.

>>8071903
I don't even know what a 'connected interval' is but if my reading is correct then.

For all a and b in I, so that a < b, there exists some c such that a<c<b.

let c=(a + b)/2

(a+b)/2 > a

Assume it is not so, (a+b)/2 <= a
a+b <= 2a
b<=a

this contradicts the hypothesis, therefore (a+b)/2 > a

and

(a+b)/2 < b

assume the contrary,

(a+b)/2 > b
a+b >2b
a>b

and this contradicts the hypothesis, therefore
(a+b)/2 > a

therefore

a< (a+b)/2 < b

therefore

a < c < b.

QED.

>>8071944
A connected interval is an interval that is not disconnected.

File: ca5fc007-4c71-4af2-addf-f1969054331d.jpg (50KB, 305x302px) Image search: [Google]

50KB, 305x302px

>constructive proofs

File: 1439514124770.gif (1MB, 500x225px) Image search: [Google]

1MB, 500x225px

>>8071251
Who here contraposition master race?

>>8071334
Man, I can't believe constructive logic is actually field people study.

(Q->P)
<=>
(-(-P->-Q))

>>8071903
>its
What kind of crap textbook is this?

>>8071559
>>8071768

see >>8071515

Knowing all possible states before they happen so as to achieve the most probable losing state, like in chess.

>Abnegate

>>8071315
This

>>8071296
Monsky's theorem

>>8072497
my personal notes, lol.
fix'd

>>8071427

but <assuming "not P"> is the same as <not assuming P>

if not, why ?

File: o-PSYCHOLOGIST-facebook.jpg (213KB, 2000x1000px) Image search: [Google]

213KB, 2000x1000px

>I think about feelings, that makes me a scientist!