Classes

[Dubslow]

Originally Posted by science_man_88

so you hate Mathematical induction I assume, also aren't phrasings like "suppose..." kinda case based if so it looks like you hate proof by contradiction

also:



quite a few types of mathematical proof you seem not to like.

Induction and contradiction do not make any assumptions that lose generality. You are right, though, that I do dislike proof by exhaustion. In particular:

In proof by exhaustion, the conclusion is established by dividing it into a finite number of cases and proving each one separately.

Then you may as well have written n separate proofs (for an n-case problem) instead of one unified chain of reasoning. (I do realize that just because I don't like it doesn't mean I won't have to use it. For instance, the four color theorem has only been proven by exhaustion (and computer).)

[science_man_88]

Originally Posted by Dubslow

Induction and contradiction do not make any assumptions that lose generality. You are right, though, that I do dislike proof by exhaustion. In particular:
Then you may as well have written n separate proofs (for an n-case problem) instead of one unified chain of reasoning. (I do realize that just because I don't like it doesn't mean I won't have to use it. For instance, the four color theorem has only been proven by exhaustion (and computer).)

I was kinda making fun of "case-based": because induction uses a base statement/case, contradiction first assumes something is the case. So they both use cases. but I get that you mean infinitely many case proofs because each one unless grouped has to be done separately.

[Dubslow]

Originally Posted by science_man_88

I was kinda making fun of "case-based": because induction uses a base statement/case, contradiction first assumes something is the case. So they both use cases.

Well okay, so I implicitly was excluding 1-case proofs from my statement. If I didn't, then I'd've effectively said "I don't like any proof".


By the way, I suppose my original proof is slightly stronger, because it proves that any integer n can be written as a prime p plus n-p, where the latter is automatically coprime to the former.

[science_man_88]

Originally Posted by Dubslow

Well okay, so I implicitly was excluding 1-case proofs from my statement. If I didn't, then I'd've effectively said "I don't like any proof".


By the way, I suppose my original proof is slightly stronger, because it proves that any integer n can be written as a prime p plus n-p, where the latter is automatically coprime to the former.

for even integer n The Beal's Conjecture assumes there's a p for which n-p is not only coprime to p but is prime, anyway I'm way off topic now.

[Dubslow]

Originally Posted by science_man_88

for even integer n The Beal's Conjecture assumes there's a p for which n-p is not only coprime to p but is prime, anyway I'm way off topic now.

Then Beal's Conjecture implies (and I think is equivalent to) the Goldbach conjecture.

Edit: Your Beal and Wikipedia's Beal don't agree.

[science_man_88]

Originally Posted by Dubslow

Then Beal's Conjecture implies (and I think is equivalent to) the Goldbach conjecture.

sorry I got confused , I have a bookmark for beal's conjecture so I must of thought of that name when typing.

[Dubslow]

Originally Posted by science_man_88

sorry I got confused , I have a bookmark for beal's conjecture so I must of thought of that name when typing.

Can we name it the Winslow conjecture then? At 3 in the morning, there was about a minute where I thought I might have proven the Goldbach conjecture (ridiculous, I know), until I remembered ("realized", in that addled state of mind) that n-p is not necessarily prime just because p is.

[ewmayer]

I think comparing e.g. 4-color to a 2 or 3-case-based proof is a tad ludicrous. There are many, many fundamental (and non-machine-aided) proofs which have a small number of cases, especially of the parity-based variety. As the wise man said, "2 is the only even prime, which makes it the oddest prime of all."

I note that even Euclid's famous infinitude-of-primes-proof is case-based - should we pooh-pooh that one, too?

My 3-case proof is of the even-odd-case variety: 2 cases from n even/odd, and the even case again splits based on n/2 even/odd. Not a very deep recursion, so quit whining. :)

[Dubslow]

Originally Posted by ewmayer

I think comparing e.g. 4-color to a 2 or 3-case-based proof is a tad ludicrous. There are many, many fundamental (and non-machine-aided) proofs which have a small number of cases, especially of the parity-based variety. As the wise man said, "2 is the only even prime, which makes it the oddest prime of all."

I note that even Euclid's famous infinitude-of-primes-proof is case-based - should we pooh-pooh that one, too?

My 3-case proof is of the even-odd-case variety: 2 cases from n even/odd, and the even case again splits based on n/2 even/odd. Not a very deep recursion, so quit whining. :)

Yeah, yeah, yeah. It's just my aesthetic taste.

http://en.wikipedia.org/wiki/Proofs_from_THE_BOOK

And I would argue that the infinitude of primes is not case based -- p#+1 has at least one prime factor (whether it's itself or not) that is not in the product of primes p#.

[R. Gerbicz]

Originally Posted by Dubslow

The (semi-constructive) proof I came up with at 3am only depended on what we've covered, except that I needed Chebyshev's theorem. (I can reproduce it if anyone desires.)

Is there a proof of the statement without relying on that theorem?

A non-constructive proof, that avoids the Chebyshev's theorem, though using a similar trick used by Erdos to prove it.

Consider the expressions n=p+(n-p), where p<=n/2 is prime, this will be wrong if and only if gcd(n-p,p)=gcd(n,p)>1 so if p|n. If all forms are wrong, then this implies that p|n for all p<=n/2, from this prod(p=2,n/2,p)<=n, but this is false for n>9.

Due to odd numbers I will prove a slightly stronger theorem:
prod(p=2,N,p)>=3*N for N>4

Easily you can get (N/2)^(N/2)<=N!, because in N!=1*2*...*N you see at least N/2 numbers which are at least N/2. By Legendre formula N!=prod(p=2,N,p^e(N,p)), where e(N,p)=sum(k=1,inf,floor(N/p^k))<=N/(p-1).
Using these bounds:

(N/2)^(N/2)<=N!<=2^N*3^(N/2)*prod(p=5,N,p^e(N,p))<=2^N*3^(N/2)*prod(p=5,N,p)^(N/4), so
(N/2)^(N/2)<=2^N*3^(N/2)*prod(p=5,N,p)^(N/4) // take the N/4-th root
(N/2)^2<=16*9*prod(p=5,N,p) from this
N^2/96<=prod(p=2,N,p)

If N>=3*96=288 then N^2/96>=3*N, this proves that
if N>=288 then prod(p=2,N,p)>=3*N. For 4<N<288 it is easy to see
that this is also true (just use the small primes 2,3,5,7,11).

ps. Note that actually we proved that prod(p=2,N,p)>=N^2/96.

[Dubslow]

Originally Posted by R. Gerbicz

A non-constructive proof, that avoids the Chebyshev's theorem, though using a similar trick used by Erdos to prove it.

Consider the expressions n=p+(n-p), where p<=n/2 is prime, this will be wrong if and only if gcd(n-p,p)=gcd(n,p)>1 so if p|n. If all forms are wrong, then this implies that p|n for all p<=n/2, from this prod(p=2,n/2,p)<=n, but this is false for n>9.

Due to odd numbers I will prove a slightly stronger theorem:
prod(p=2,N,p)>=3*N for N>4.

That's remarkably similar to my proof, though slightly more complex I think. (I wish I'd kept a copy of my own proof... a picture, perhaps )

(By semi-constructive I mean that for n>6, p -|- n is a sufficient condition so that gcd(p,n-p)=1.)