July 4th, 2006

brainy smurf

any math nerds in the house?

i have a question about proof by contradiction. as i understand it[1], this works by assuming something to be true, showing that this leads to a contradiction, and then saying viola it's clearly false! or vice versa. according to wiki:
Say we wish to disprove proposition p. The procedure is to show that assuming p leads to a logical contradiction. Thus, according to the law of non-contradiction, p must be false.

Say instead we wish to prove proposition p. We can proceed by assuming "not p" (i.e. that p is false), and show that it leads to a logical contradiction. Thus, according to the law of non-contradiction, "not p" must be false, and so, according to the law of the excluded middle, p is true.
but i can't find anything about what determines whether those laws apply[3]. if assuming something is true creates a contradiction, then fine it's not true[2], but who's to say then assuming it must be false wouldn't lead to another contradiction? and to actually determine whether or not it leads to another, you have to try proving(/assuming) it false directly, but if you were able to do that why use proof by contradiction in the first place?

obvious example: Godel's incompleteness theorem, which for simplicity i will pretend states "this statement is false". now if you assume that is true you immediately get a contradiction, so viola it must be false! it being false leads straight to the same problem, of course, but you wouldn't know that until you assumed it was false and started playing (remember we are talking about logical proof here, reason and common sense don't apply). but why would you ever do that, if it is already "proven" to be so? when does the law of the excluded middle apply? you can't just say it doesn't work for paradoxes etc, because you don't know they ARE paradoxes until you've tried both sides, which means you have to for everything, which makes it a fairly useless law.

why am i wrong?

[1] this should be tacked on to every statement in this post, actually.
[2] i'm also not clear how it could ever be determined that something *doesn't* cause a contradiction, unless you are comparing it to every single other concept in the theory. that sounds like trying to prove aliens don't exist - you would have to search out every inch of the universe to be sure.
[3] sidenote: why does proving something not true make it false, but proving something not false doesn't make it true (without that extra step)? i should read up on logic sometime. why did they assume "not p" is true, instead of directly assuming p is false? can you not have a negative assumption?
  • Current Music
    john brodeur - tiger pop - sucker