tag:blogger.com,1999:blog-610829014030908940.post4725058290534160625..comments2014-02-15T10:10:30.292+05:30Comments on Running Upstairs: An Unsatisfactory ProofRavihttp://www.blogger.com/profile/03630087669712445498noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-610829014030908940.post-71514844740335440872008-10-04T18:48:00.000+05:302008-10-04T18:48:00.000+05:30"I thought about this some more, and the more I th..."I thought about this some more, and the more I think about it the smaller the real differences between the proofs look."<BR/><BR/><BR/>True, but your version was still useful to me because it explicitly identifies the contradiction and then (explicitly) negates the assumption. This was something I missed out on in my version, where I was over focussed on the "creation of exhaustive cases" idea.Ravihttp://www.blogger.com/profile/03630087669712445498noreply@blogger.comtag:blogger.com,1999:blog-610829014030908940.post-82444608193111211612008-10-04T10:22:00.000+05:302008-10-04T10:22:00.000+05:30Here's a proof based on Boolean algebra.We'...Here's a proof based on Boolean algebra.<BR/><BR/>We're given A xor B <= A.<BR/><BR/>Using the usual definition of <= on a Boolean algebra, (A <= B <==> A + B = B), we can write: <BR/><BR/>A xor B <= A<BR/><==> A xor B + A = A.<BR/><==> A(!B) + (!A)B + A = A<BR/><==> A(!B + 1) + (!A)B = A<BR/><==> A + (!A)B = A<BR/><==> A + B = A<BR/><==> B <= APramodhttp://www.blogger.com/profile/05944922510281115321noreply@blogger.comtag:blogger.com,1999:blog-610829014030908940.post-2954988801276238692008-10-04T09:57:00.000+05:302008-10-04T09:57:00.000+05:30I thought about this some more, and the more I thi...I thought about this some more, and the more I think about it the smaller the real differences between the proofs look. My version starts with x in B and x not in A, but that is not given. It basically assumes case 1, and a more complete and formal proof would still probably contain an (x in B) and (x in A or X not in A) clause at some point. The difference is that my version no longer needs to refer back to case 1 at the end of the proof, so it can just be left out because it is so obvious.<BR/><BR/>This is the way mathematicians like to do things, and it is nicer in a lot of ways. But the difference is really more in the style of the way the proof is written than in the elegance of the actual mathematical or logical content. To make an analogy with computing, it just shifts work from the application to the interpreter, it doesn't reduce the size or complexity of the system as a whole.timblog.arakyd.netnoreply@blogger.comtag:blogger.com,1999:blog-610829014030908940.post-13953769674266826822008-10-03T20:46:00.000+05:302008-10-03T20:46:00.000+05:301) complement -> difference.Thanks, difference ...1) complement -> difference.<BR/><BR/>Thanks, difference is correct. (I've changed the entry)<BR/><BR/><BR/>As for "I would say that this is really just a cleaned up version of your proof."<BR/><BR/>this is *exactly* what I was looking for.<BR/><BR/>Much better!<BR/><BR/>Thank You!Ravihttp://www.blogger.com/profile/03630087669712445498noreply@blogger.comtag:blogger.com,1999:blog-610829014030908940.post-70356029213719854822008-10-03T19:28:00.000+05:302008-10-03T19:28:00.000+05:30I think you mean \ is difference, not compliment.I...I think you mean \ is difference, not compliment.<BR/><BR/>In case 2, you've actually derived a contradiction. You can use that to negate the premise, and the negation of the premise is what you want to prove. You don't really need case 1. To wit:<BR/><BR/>x in B and x not in A<BR/>-> x in AUB and x not in A^B<BR/>-> x in AUB\A^B<BR/>-> x in A<BR/>-> x not in B or x in A<BR/>-> (x in B -> x in A)<BR/><BR/>I would say that this is really just a cleaned up version of your proof. The problem is so simple and the proof is so short that I don't think there's a way to come up with a really different argument that is any shorter.timblog.arakyd.netnoreply@blogger.com