perplexus.info :: Paradoxes : Provably unprovable?

Provably unprovable? (Posted on 2004-08-22)

Gödel proved that there are true sentences that cannot be proved.

Suppose I told you that the Goldbach conjecture is one of those. (The Goldbach conjecture supposes that every even integer number can be expressed as the sum of two odd primes.)

Is that logically possible? (And, no, I haven't proved it!)

Submitted by Federico Kereki

Rating: 3.4167 (12 votes)

Solution: (Hide)

It's not possible. Suppose I programmed a computer to succesively test every even number, and see if it's the sum of two primes or not, and started the program.
If the program ever stopped, that would mean it had found a counterexample, which would prove the conjecture to be false. BUT, if the conjecture was true (though unprovable) then this could never happen.
So, that means that the program will never find a counterexample... but that proves the conjecture to be true, so it wasn't unprovable after all!
The final conclusion is that the conjecture may be true or false, but we cannot prove that it cannot be proved.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
Problem Stated Wrong - GC Can't Be FALSE (has counterexample) & Unrefutable	Charlie	2012-04-26 12:10:45
re: zero and infinity	Tom	2007-04-08 02:59:58
zero and infinity	matt	2006-08-06 20:34:07
ummm	Sarah	2006-04-06 03:19:09
Note:	Chris, Phd	2005-11-27 22:38:56
Solution	sean	2005-11-08 11:26:50
Randomness of prime numbers.	Patrick Blake	2005-07-29 21:04:44
No Subject	Jeff	2005-07-24 15:23:57
re: SOLUTION!	Bryan	2005-04-14 19:40:02
ehh (shrug)	Abanan	2005-03-30 12:37:49
okay, haha, I wonder it anyone has thought of this. hehe!	Vee-Liem Veefessional	2004-12-30 06:15:24
It's the idea, not the example....	Rob	2004-11-24 00:35:27
SOLUTION!!	Felix	2004-11-12 14:41:11
Need correction to the problem	doremi	2004-10-28 00:54:03
Posted Solution is Bogus	David Shin	2004-10-15 20:26:54
re: No problem	David Shin	2004-10-15 20:17:45
No problem	Steve Herman	2004-10-14 21:44:46
I disagree with the posted solution.	Ken Haley	2004-10-03 02:46:48
re: My thought is....	Ken Haley	2004-10-03 02:34:25
re: From a pure logic standpoint...	Federico Kereki	2004-08-28 21:23:23
From a pure logic standpoint...	Susan	2004-08-28 13:14:44
re(2): No Subject	e.g.	2004-08-27 20:56:01
re: No Subject	Bruce Brantley	2004-08-27 09:46:08
No Subject	Vee-Liem Veefessional	2004-08-26 23:27:35
re(3): Waiting for Godel (Spoiler)	Bruce Brantley	2004-08-23 01:08:27
re(2): Waiting for Godel (Spoiler)	Penny	2004-08-22 23:07:58
re: Waiting for Godel (Spoiler)	Bruce Brantley	2004-08-22 22:44:59
re(2): A better....	Penny	2004-08-22 15:12:34
re: A better....	e.g.	2004-08-22 13:32:29
A better....	Penny	2004-08-22 12:35:20
My thought is....	Penny	2004-08-22 12:27:19
Just thinking	Oskar	2004-08-22 11:40:41
my 2 cents	Steven	2004-08-22 10:49:02
attempt at logic	Larry	2004-08-22 09:46:19
re: Waiting for Godel (Spoiler)	Larry	2004-08-22 09:38:25
Waiting for Godel (Spoiler)	Penny	2004-08-22 08:50:48

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (19)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info