?

Log in

No account? Create an account
any math nerds in the house? - here is where i live

> Recent Entries
> Archive
> Friends
> Profile
> <3

me!
contact info
writing/art journal
flickr
youtube
last.fm
social networking and potential boning
okcupid
myspace
facebook

July 4th, 2006


Previous Entry Share Next Entry
09:21 am - 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?
np: john brodeur - tiger pop - sucker

(10 shots upside the head | en garde!)

Comments:


[User Picture]
From:jim_smith
Date:July 4th, 2006 06:30 pm (UTC)
(Link)
why am i wrong?

Because you're asking how the law of noncontradiction--which does not allow for the existence of statements that are both true and false--applies to a statement which is both true and false. Your fallacy here is to assume that reductio ad absrudum can use the law of noncontradiction to properly evaluate statements that don't obey the law of noncontradiction to begin with. It's a bit like trying to use a screwdriver to hammer a nail.

Your question, then is: how do we logically recognize that a paradox is a paradox if we can't use the law of noncontradiction? I'm not sure (been too long since I studied logic) but my gut says "You use something else." Put the screwdriver away and get out a hammer.

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.

You can't, which is why the reductio ad absurdum has you attempt to disprove a positive (will cause contradiction) rather than prove a negative (will never cause a contradiction). This is why reductio ad absurdum can't be used to determine if, say, aliens exist--there's not enough evidence to arrive at a contradiction either way.

why did they assume "not p" is true, instead of directly assuming p is false?

We perceive that logical leap as directness because we're smart enough to intuitively understand the law of the excluded middle. For human brains it's such an incredibly obvious law that we don't even think about it as a separate step. In logic, however, every step is documented, no matter how insignificant. So when Wikipedia is explaining that, logically, "not p is true" means "p is false," it is obligated to explain exactly how it knows that.

This is a pretty important concept in computer programming, because for all their speed and logic computers are unintuitive morons, so to get them do something a human programmer has to break the process down into seemingly self-evident instructions.
[User Picture]
From:doppmonster
Date:July 4th, 2006 06:45 pm (UTC)
(Link)
I like you. Do you program? Do you need work?
[User Picture]
From:kingnixon
Date:July 4th, 2006 09:06 pm (UTC)
(Link)
haha if you start finding work in my lj, i want a cut
[User Picture]
From:kingnixon
Date:July 4th, 2006 09:56 pm (UTC)
(Link)
i wasn't assuming that (not intentionally, at least). i was wondering how you can determine whether or not the law applies to a given statement. if the law simply amounts to "no statement can be both true and false except for statements that are both true and false" then it's not much of a law. proving not p causes contradictions does not prove p won't also cause contradictions, because noncontradiction might not apply, and you can't know it applies until you have proven it succesfully one way or another. so i am not clear how reductio ad absurdum can ever be used on a statement that hasn't already been proven.
[User Picture]
From:doppmonster
Date:July 4th, 2006 07:04 pm (UTC)
(Link)
Yer Funneee.

While I think the person above me addressed it pretty well with the hammer and screwdriver concept, I'd like to point out one thing:

The logic nerds that are in the house are not necessarily math nerds.

How about approaching this one with a less blatantly absurd sentence? Say, "The Christian God exists."

Let's try to prove P is false. The Christian God does not exist.

1) The Christian God exists.

2) If the Christian God exists, then the contents of the Christian Bible are literal and true.

3) The Christian Bible tells us that women are inferior to men.

4) Women are not inferior to men.

Therefore, the Christian God does not exist.

--

Okay, so let's prove P now by proving that "It is not true that the Christian God exists" leads to a logical contradiction.

1) It is not true that the Christian God exists.

2) If the Christian God does not exist...

Shit. Is there a Christian in the house that can finish this one?
[User Picture]
From:jim_smith
Date:July 4th, 2006 07:46 pm (UTC)
(Link)
Let's try to prove P is false. The Christian God does not exist.

1) The Christian God exists.

2) If the Christian God exists, then the contents of the Christian Bible are literal and true.


This is where your argument falls apart--although some flavors of Christianity maintain the Bible is literally true, not all of them do.

Okay, so let's prove P now by proving that "It is not true that the Christian God exists" leads to a logical contradiction.

1) It is not true that the Christian God exists.

2) If the Christian God does not exist...


You can't finish this one for the same reason proving aliens do or don't exist won't work--not enough logical evidence. That means there's no logical reason God must exist, but it certainly doesn't mean God can't exist. The whole thing boils down to faith, which is outside the realm of logic anyway.
[User Picture]
From:kingnixon
Date:July 4th, 2006 09:03 pm (UTC)
(Link)
formal logic IS math, i do believe.

to address your argument-- as pointed out, the christian god's existing doesn't require the bible to be literal and true. only some flavors of christianity assert that, and their god is not required to agree with his followers. further, even if the bible IS true, the next question is which one? there are stacks of different translations.
aaaaaand the bible(s) tells us all sorts of things, many of which contradict. it only "tells us that women are inferior to men" if you emphasise some parts over other parts. not to mention, inferiority can't be proven or disproven. it's a pretty fuzzy idea to begin with.
From:sedinitia
Date:July 5th, 2006 09:49 am (UTC)
(Link)
Tisk tisk tisk... you've broken the golden rule of formal logic (and mathematics)... it cannot exist within a real world context. ;) Throw in the supernatural and sheer craziness follows:

P1. God is omnipotent
C1. God can choose to exist
C2. God can choose to not exist
P2. Humans have free will
C3. Humans may agree or disagree with P1

D'oh!

Such arguments are easier on the brain and the soul when made with "immovable forces" colliding with "immovable objects". ;)

Back to the original post... I work in the field of information security so such non-contradiction points are far simpler than in the real world, since _ideally_ the system can be broken down into finite components with unambiguous laws (policy).

The same logic applies... proving a statement is false is different than proving it isn't true, especially within finite, formal statements. A practical example of non-contradiction using "not p" to prove truth in such statements is in a web form where you are asked to fill in your email (or some such required data):

"If email is null" is false, then email is true.

PS. Just randomly found this journal though friend’s friends page and the entry looked interesting.
[User Picture]
From:kingnixon
Date:July 19th, 2006 08:37 am (UTC)
(Link)
which friend's friend is this? i don't recognize any of the names on your friendlist
From:sedinitia
Date:July 19th, 2006 08:47 am (UTC)
(Link)
Yeah, sorry... I think I was having a big bought of insomnia and i made a number of dumb, random posts that night.

I found you through eamajyn.

> Go to Top
LiveJournal.com