From meyer@imap.theory.csail.mit.edu Tue Feb 21 15:24:47 2006 Return-Path: Received: from south-station-annex.mit.edu (SOUTH-STATION-ANNEX.MIT.EDU [18.72.1.2]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1LKOl67009885 for <6042-probs@theory.csail.mit.edu>; Tue, 21 Feb 2006 15:24:47 -0500 Received: from central-city-carrier-station.mit.edu (CENTRAL-CITY-CARRIER-STATION.MIT.EDU [18.7.7.72]) by south-station-annex.mit.edu (8.12.4/8.9.2) with ESMTP id k1LKOkkL029938 for <6042-probs@theory.csail.mit.edu>; Tue, 21 Feb 2006 15:24:46 -0500 (EST) Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by central-city-carrier-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1LKOjHS005270 for <6042-probs@theory.csail.mit.edu>; Tue, 21 Feb 2006 15:24:45 -0500 (EST) Received: from GRIMWAYS.mit.edu ([18.202.1.248]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id k1LKOg1g025249 for <6042-probs@theory.csail.mit.edu>; Tue, 21 Feb 2006 15:24:42 -0500 (EST) Message-Id: <5.2.1.1.2.20060221152126.00ba2be8@po12.mit.edu> X-Sender: dfuentes@hesiod (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.2.1 Date: Tue, 21 Feb 2006 15:22:53 -0500 To: 6042-probs@theory.csail.mit.edu From: Daniel Fuentes Subject: Week 3 Comments Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO Content-Length: 143 X-UID: 1358 X-Status: A X-IMAPbase: 1126748715 1456 NonJunk $Label4 $Label1 $Label2 $Label3 $Label5 Junk $MDNSent $Forwarded NotJunk Forwarded X-Keywords: NonJunk NotJunk On page 17 we are introduced to Strong Induction. I still don't fully understand how to invoke strong induction in a proof. -Daniel Fuentes From meyer@csail.mit.edu Tue Feb 21 22:01:05 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1M31567020889; Tue, 21 Feb 2006 22:01:05 -0500 Message-ID: <43FBD3FF.2040600@csail.mit.edu> Date: Tue, 21 Feb 2006 22:01:19 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Daniel Fuentes CC: 6042-probs@theory.csail.mit.edu Subject: Re: Week 3 Comments References: <5.2.1.1.2.20060221152126.00ba2be8@po12.mit.edu> In-Reply-To: <5.2.1.1.2.20060221152126.00ba2be8@po12.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1359 Content-Length: 666 X-Keywords: Were you able to follow the two examples in the Notes (prime product and postage)? You'll see more examples Friday and several in Pset2. If you're still having trouble after Friday class, go to office hours with your TA -- or me, if you prefer. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Daniel Fuentes wrote: > On page 17 we are introduced to Strong Induction. I still don't fully > understand how to invoke strong induction in a proof. > > -Daniel Fuentes From edelmann@MIT.EDU Wed Feb 22 03:55:54 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1M8ts67006906 for <6042-probs@theory.csail.MIT.EDU>; Wed, 22 Feb 2006 03:55:54 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1M8tqI0009927 for <6042-probs@theory.csail.MIT.EDU>; Wed, 22 Feb 2006 03:55:53 -0500 (EST) Received: from w92-130-webmail-3.mit.edu (W92-130-WEBMAIL-3.MIT.EDU [18.7.22.133]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1M8tpUm028489 for <6042-probs@theory.csail.MIT.EDU>; Wed, 22 Feb 2006 03:55:51 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-3.mit.edu (8.12.4) id k1M8tp1m015036; Wed, 22 Feb 2006 03:55:51 -0500 Received: from EASTCAMPUS-ONE-O-THREE-HUNDRED-FORTY-ONE.MIT.EDU (EASTCAMPUS-ONE-O-THREE-HUNDRED-FORTY-ONE.MIT.EDU [18.238.7.74]) (User authenticated as edelmann@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Wed, 22 Feb 2006 03:55:51 -0500 Message-ID: <20060222035551.031uylre930gscc4@webmail.mit.edu> Date: Wed, 22 Feb 2006 03:55:51 -0500 From: edelmann@MIT.EDU To: 6042-probs@theory.csail.MIT.EDU Subject: Nicholas Edelman: February 24 Email Comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -1.638 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1360 Content-Length: 777 X-Status: A X-Keywords: NonJunk NotJunk Passage: The last paragraph of page 18 of the reading. The passage describes very generally how to formulate a proof using the well-ordering principle, but I do not believe that even after reading this passage that I would be able to formulate a proof using this principle. I would like this topic covered in lecture and supplemented by examples to reinforce my understanding of the principle. In addition, by lumping the entire procedure into a single paragraph, the reading became rather confusing, and I would have preferred that it was presented in a step by step format. _____________________ Nicholas A. Edelman Electrical Engineering and Computer Science | 2008 Massachusetts Institute of Technology 3 Ames Street, Box 265 Cambridge, MA 02142 Phone: 617 225 6356 From mdburro@MIT.EDU Wed Feb 22 16:14:46 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1MLEk67001567 for <6042-probs@theory.csail.MIT.EDU>; Wed, 22 Feb 2006 16:14:46 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1MLEiZd003731 for <6042-probs@theory.csail.MIT.EDU>; Wed, 22 Feb 2006 16:14:45 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1MLEcVN000227 for <6042-probs@theory.csail.MIT.EDU>; Wed, 22 Feb 2006 16:14:38 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id k1MLEc4P000390; Wed, 22 Feb 2006 16:14:38 -0500 Received: from MACGREGOR-THREE-THIRTY.MIT.EDU (MACGREGOR-THREE-THIRTY.MIT.EDU [18.239.6.75]) (User authenticated as mdburro@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Wed, 22 Feb 2006 16:14:38 -0500 Message-ID: <20060222161438.zv33htvl1i0c48og@webmail.mit.edu> Date: Wed, 22 Feb 2006 16:14:38 -0500 From: Mark D Burroughs To: 6042-probs@theory.csail.MIT.EDU Subject: reading #2 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1361 Content-Length: 953 X-Status: A X-Keywords: NonJunk If I am to understand this correctly, the minimum is the smallest of the minimal values and the maximum is the largest of the maximal values? The idea of minimal and maximal make sense in the clothes analogy and the course management problem since the minimals don't have prerequisites. But this idea becomes very confusing in problems like the in-class one on tuesday where 1 is the minimal and 0 is the maximal for the binary relation "divides". here, there are no prerequisites or chains, just bizarre cases where 0/a=0 and a/1=a. This does not follow the same concept as the parallel processing examples. Can you clarify this to make a reasonable definition for minimal/maximal outside of prerequiste problems? there is a mistake in 4.3 where it says: "(2k+1)(2k'+1)=2(kk'+k+k') + 1" this should read: "(2k+1)(2k'+1)=2(2kk'+k+k') + 1" since 2k*2k' is 4kk' not 2kk' it is irrevalant to the proof but is nonetheless inconsistent Mark Burroughs From robfalco@MIT.EDU Wed Feb 22 21:57:56 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1N2vu67024318 for <6042-probs@theory.csail.MIT.EDU>; Wed, 22 Feb 2006 21:57:56 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1N2vsm5025698 for <6042-probs@theory.csail.MIT.EDU>; Wed, 22 Feb 2006 21:57:54 -0500 (EST) Received: from w92-130-webmail-5.mit.edu (W92-130-WEBMAIL-5.MIT.EDU [18.7.22.136]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1N2vrvx029466 for <6042-probs@theory.csail.MIT.EDU>; Wed, 22 Feb 2006 21:57:53 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-5.mit.edu (8.12.4) id k1N2vqlE019689; Wed, 22 Feb 2006 21:57:52 -0500 Received: from ROBFALCONI.MIT.EDU (ROBFALCONI.MIT.EDU [18.228.0.48]) (User authenticated as robfalco@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Wed, 22 Feb 2006 21:57:52 -0500 Message-ID: <20060222215752.3kfayo8ha4zookw4@webmail.mit.edu> Date: Wed, 22 Feb 2006 21:57:52 -0500 From: Robert F Falconi To: 6042-probs@theory.csail.MIT.EDU Subject: Reading Assignment Comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1362 Content-Length: 430 X-Status: A X-Keywords: NonJunk NotJunk I like that the method of proof by induction is so simple to use, but I'm not so sure that I fully understand proof by strong induction. It seems to me like it is a proof by induction but with several bases cases. Is that right? Does that really make some proofs easier to do, as the reading implys? And how is it that the well ordering priciple is actually connected to proof by induction? Could we go over that? -Robert Falconi From wysun07@gmail.com Wed Feb 22 23:00:43 2006 Return-Path: Received: from wproxy.gmail.com (wproxy.gmail.com [64.233.184.202]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1N40a67021629 for <6042-probs@theory.csail.mit.edu>; Wed, 22 Feb 2006 23:00:42 -0500 Received: by wproxy.gmail.com with SMTP id 69so288288wri for <6042-probs@theory.csail.mit.edu>; Wed, 22 Feb 2006 20:00:28 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:to:subject:mime-version:content-type; b=JRU04kvTw3Waq/l6QemvUN08VSP/FMW3ezZ8q91vMmozG8+5h/eW1ToonlQKm5hKWVPskb8gQGDNze/8ZtpcIfhzO6puYnRLx2C35h2KuHtW4J0HNn2LlpqaQi8WgxTpMfHfS117+xOudLv6DIQ2PvU58lZ4nYJvZoRh3mMgGy4= Received: by 10.65.249.7 with SMTP id b7mr2702388qbs; Wed, 22 Feb 2006 20:00:27 -0800 (PST) Received: by 10.65.83.2 with HTTP; Wed, 22 Feb 2006 20:00:27 -0800 (PST) Message-ID: <58cad4620602222000k36d22beerb28a5da48293debe@mail.gmail.com> Date: Wed, 22 Feb 2006 23:00:27 -0500 From: "Weiyang Sun" Reply-To: wysun@mit.edu To: 6042-probs@theory.csail.mit.edu Subject: 6.042 : Comments on Week 3 Reading MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_5139_1330644.1140667227875" Status: RO X-UID: 1363 Content-Length: 1667 X-Status: A X-Keywords: NonJunk NotJunk ------=_Part_5139_1330644.1140667227875 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline 1. in section 2.1, the explanations of transitive, asymmetric, etc. would probably be easier to understand if there were more sample sets that had captions showing why the sets were transitive, asymmetric, etc. or not. 2. The explanation of minimal and maximal vs minimum and maximum were also quite confusing. especially on the in class problem appendix sheet. in general, i just wish there were more examples of things that are defined. (such as the transitive, asymmetric definitions) -- "The winner ain't the one with the fastest car, son. It's just the one who refuses to lose." --ralph earnhardt ------=_Part_5139_1330644.1140667227875 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline 1.  in section 2.1, the explanations of transitive, asymmetric, etc. would probably be easier to understand if there were more sample sets that had captions showing why the sets were transitive, asymmetric, etc. or not. 

2.  The explanation of minimal and maximal vs minimum and maximum were also quite confusing. especially on the in class problem appendix sheet.

in general, i just wish there were more examples of things that are defined.  (such as the transitive, asymmetric definitions)

--
"The winner ain't the one with the fastest car, so= n. It's just the one who refuses to lose."  --ralph earnhard= t ------=_Part_5139_1330644.1140667227875-- From mongoose@MIT.EDU Wed Feb 22 23:04:45 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1N44i67022079 for <6042-probs@theory.lcs.MIT.EDU>; Wed, 22 Feb 2006 23:04:45 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1N44hqY008036 for <6042-probs@theory.lcs.MIT.EDU>; Wed, 22 Feb 2006 23:04:43 -0500 (EST) Received: from w92-130-webmail-3.mit.edu (W92-130-WEBMAIL-3.MIT.EDU [18.7.22.133]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1N44fXl013111 for <6042-probs@theory.lcs.MIT.EDU>; Wed, 22 Feb 2006 23:04:41 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-3.mit.edu (8.12.4) id k1N44fVM016278; Wed, 22 Feb 2006 23:04:41 -0500 Received: from EYES.MIT.EDU (EYES.MIT.EDU [18.228.0.50]) (User authenticated as mongoose@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Wed, 22 Feb 2006 23:04:41 -0500 Message-ID: <20060222230441.da0dj256zncwoks8@webmail.mit.edu> Date: Wed, 22 Feb 2006 23:04:41 -0500 From: Jorge L De la Garza To: 6042-probs@theory.lcs.MIT.EDU Subject: Comments on notes 3 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1364 Content-Length: 374 X-Status: A X-Keywords: NonJunk -p. 2 - not quite clear on what image and inverse image are. An example would have been nice. -p. 4 - don't understand eqn (1). What does the notation R{x} mean? Again, an example would have been nice. -p. 9 - Don't understand Lemma 2.19. What is t? Don't understand example 2.21 -p. 16 - was only able to understand lemma 5.1 after rereading Thanks, Jorge From veenav@gmail.com Wed Feb 22 23:49:25 2006 Return-Path: Received: from nproxy.gmail.com (nproxy.gmail.com [64.233.182.199]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1N4nP67014655 for <6042-probs@theory.lcs.mit.edu>; Wed, 22 Feb 2006 23:49:25 -0500 Received: by nproxy.gmail.com with SMTP id x37so1146578nfc for <6042-probs@theory.lcs.mit.edu>; Wed, 22 Feb 2006 20:49:24 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=DTHg3pZEbxbD+ybV+puaKSMX2nQDskflSZoBP5akQjfgzPuOKn3SM5PyJ91oyj5yB9RYyulLZA/a78FFhWAsB7aikrttKUK9jjYmB7Ss6dg0Cnrs1mGOrQXqGnFDP3USPutMD6nv7l2HEaXuJszaHF8rs9W7GX+7+xP0/4s7ayc= Received: by 10.48.202.15 with SMTP id z15mr2214199nff; Wed, 22 Feb 2006 20:49:24 -0800 (PST) Received: by 10.49.28.13 with HTTP; Wed, 22 Feb 2006 20:49:24 -0800 (PST) Message-ID: <4a8b437e0602222049r51682b75x2b4ddd7a83a4cd6a@mail.gmail.com> Date: Wed, 22 Feb 2006 23:49:24 -0500 From: Veena To: 6042-probs@theory.lcs.mit.edu Subject: reading comments week 3 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by theory.csail.mit.edu id k1N4nP67014655 Status: RO X-UID: 1365 Content-Length: 463 X-Status: A X-Keywords: NonJunk NotJunk Hi, I thought that the reading was very helpful this week, particularly the way the rules for writing a proof by induction were laid out in section 4.1 on pgs 11-12. What I didn't really understand was the Well-Ordering Principle on pgs 18-19; we haven't talked about it in class yet, and I wasn't really clear as to what it meant when I was doing the tutor problems. Hopefully this will be cleared up in class tomorrow. --Veena Venkatachalam (TA: Christos) From rfh08@MIT.EDU Thu Feb 23 01:15:30 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1N6FU67031899 for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 01:15:30 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1N6FTqY019516 for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 01:15:29 -0500 (EST) Received: from [18.239.6.229] (MACGREGOR-FOUR-EIGHTY-FOUR.MIT.EDU [18.239.6.229]) (authenticated bits=0) (User authenticated as rfh08@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1N6FMGs002985 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 01:15:23 -0500 (EST) Message-ID: <43FD52F9.3020306@mit.edu> Date: Thu, 23 Feb 2006 01:15:21 -0500 From: Richard Hermosillo User-Agent: Thunderbird 1.5 (Windows/20051201) MIME-Version: 1.0 To: 6042-probs@theory.lcs.mit.edu Subject: Reading Comment 3 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1366 Content-Length: 273 X-Status: A X-Keywords: NonJunk One thing I would like discussed more fully in lecture is deciding between simple and strong induction (p. 16). I realize we haven't finished going over induction yet but I think it would be very helpful to spend a little extra time on this topic. Richard Hermosillo From meyer@imap.theory.csail.mit.edu Thu Feb 23 11:05:36 2006 Message-ID: <43FDDD5F.3010209@csail.mit.edu> Date: Thu, 23 Feb 2006 11:05:51 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Richard Hermosillo Subject: Re: Reading Comment 3 References: <43FD52F9.3020306@mit.edu> In-Reply-To: <43FD52F9.3020306@mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 596 X-UID: 1367 X-Keywords: That's what Friday lecture is all about. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Richard Hermosillo wrote: > One thing I would like discussed more fully in lecture is deciding > between simple and strong induction (p. 16). I realize we haven't > finished going over induction yet but I think it would be very helpful > to spend a little extra time on this topic. > > Richard Hermosillo From meyer@csail.mit.edu Thu Feb 23 11:09:24 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NG9O67003147; Thu, 23 Feb 2006 11:09:24 -0500 Message-ID: <43FDDE43.4020002@csail.mit.edu> Date: Thu, 23 Feb 2006 11:09:39 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Veena CC: 6042-probs@theory.lcs.mit.edu Subject: Re: reading comments week 3 References: <4a8b437e0602222049r51682b75x2b4ddd7a83a4cd6a@mail.gmail.com> In-Reply-To: <4a8b437e0602222049r51682b75x2b4ddd7a83a4cd6a@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1368 Content-Length: 962 X-Keywords: We'll do a class problem Friday that nicely (I hope) shows how the Well-ordering Principle can be used. Meanwhile, look again at the proof of Lemma 2.11 in Notes 3 and see if you can spot the use of Well-ordering there. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Veena wrote: >Hi, > >I thought that the reading was very helpful this week, particularly >the way the rules for writing a proof by induction were laid out in >section 4.1 on pgs 11-12. What I didn't really understand was the >Well-Ordering Principle on pgs 18-19; we haven't talked about it in >class yet, and I wasn't really clear as to what it meant when I was >doing the tutor problems. Hopefully this will be cleared up in class >tomorrow. > >--Veena Venkatachalam (TA: Christos) > > > From meyer@csail.mit.edu Thu Feb 23 12:06:21 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NH6L67009146; Thu, 23 Feb 2006 12:06:21 -0500 Message-ID: <43FDEB9C.4090808@csail.mit.edu> Date: Thu, 23 Feb 2006 12:06:36 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Mark D Burroughs CC: 6042-probs@theory.csail.MIT.EDU Subject: Re: reading #2 References: <20060222161438.zv33htvl1i0c48og@webmail.mit.edu> In-Reply-To: <20060222161438.zv33htvl1i0c48og@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1369 Content-Length: 3342 X-Keywords: In general, a miniMUM val in a partial order is an element that is smaller than all other elements. 1 is miniMUM under "divides" on the nonnegative integers because it divides them all. A miniMAL value is an element that has nothing else smaller than it. An example would be the set of integers greater than 1 under "divides". Now 1 isn't there, leaving each prime with no other element in the set that is smaller than (divides) it. This makes all the primes MAL-- and there is no MUM -- for this example. In general, a miniMUM val, if there is one, will, by def, alway also be MAL. But a MUM has to be unique: nothing else can be MAL or MUM. There reason is that a MUM val is, by def, smaller than every other val. So every other val has something -- namely, the MUM val -- smaller than it, which means the other values aren't MAL (or MUM). So when there is more than one MAL val, there can't be a MUM val. In fact, for finite sets, the converse holds: if there is only one MAL val in a FINITE partially ordered set, it must be a MUM. A proof of this resembles the proof in Notes 3 that every finite partially ordered set has a MAL element. Proving this is a neat exercise that I may use on a future pset or -- with suitable hints -- as a quiz problem. This ain't true for infinite sets though: a simple of a set with a unique MAL and no MUM is the set of real numbers along with the single complex number, i. We can strictly partial order this set by the rule that any pair of reals is ordered by '<' and the number, i, is not related to anything. Now the complex number, i, is MAL (nothing is smaller -- or bigger -- than it), but it's not MUM, since it isn't smaller than any of the real numbers. And i is the only MAL, since every real has another real < than it. The treatment in the class problem was regrettably, but necessarily, brief (in the Notes too), and it does take some time to decipher such definitions. I hope this long answer hasn't made things seem more complicated than before. Feel free to ask if you have any more questions. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Mark D Burroughs wrote: >If I am to understand this correctly, the minimum is the smallest of the minimal >values and the maximum is the largest of the maximal values? > >The idea of minimal and maximal make sense in the clothes analogy and the course >management problem since the minimals don't have prerequisites. But this idea >becomes very confusing in problems like the in-class one on tuesday where 1 is >the minimal and 0 is the maximal for the binary relation "divides". here, >there are no prerequisites or chains, just bizarre cases where 0/a=0 and a/1=a. > This does not follow the same concept as the parallel processing examples. Can >you clarify this to make a reasonable definition for minimal/maximal outside of >prerequiste problems? > >there is a mistake in 4.3 where it says: >"(2k+1)(2k'+1)=2(kk'+k+k') + 1" >this should read: >"(2k+1)(2k'+1)=2(2kk'+k+k') + 1" since 2k*2k' is 4kk' not 2kk' >it is irrevalant to the proof but is nonetheless inconsistent > >Mark Burroughs > > From meyer@csail.mit.edu Thu Feb 23 12:46:03 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NHk367013357; Thu, 23 Feb 2006 12:46:03 -0500 Message-ID: <43FDF4EA.8050108@csail.mit.edu> Date: Thu, 23 Feb 2006 12:46:18 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Daniel Fuentes CC: 6042-probs@theory.csail.mit.edu Subject: Re: Week 3 Comments References: <5.2.1.1.2.20060221152126.00ba2be8@po12.mit.edu> In-Reply-To: <5.2.1.1.2.20060221152126.00ba2be8@po12.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1372 Content-Length: 458 X-Keywords: That's what Friday lecture is all about. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Daniel Fuentes wrote: > On page 17 we are introduced to Strong Induction. I still don't fully > understand how to invoke strong induction in a proof. > > -Daniel Fuentes From meyer@csail.mit.edu Thu Feb 23 12:47:53 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NHlq67017441; Thu, 23 Feb 2006 12:47:53 -0500 Message-ID: <43FDF558.5040906@csail.mit.edu> Date: Thu, 23 Feb 2006 12:48:08 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Robert F Falconi CC: 6042-probs@theory.csail.MIT.EDU Subject: Re: Reading Assignment Comments References: <20060222215752.3kfayo8ha4zookw4@webmail.mit.edu> In-Reply-To: <20060222215752.3kfayo8ha4zookw4@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1373 Content-Length: 765 X-Keywords: Strong induction is what Friday lecture is all about. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Robert F Falconi wrote: >I like that the method of proof by induction is so simple to use, but I'm not so >sure that I fully understand proof by strong induction. It seems to me like it >is a proof by induction but with several bases cases. Is that right? Does that >really make some proofs easier to do, as the reading implys? And how is it that >the well ordering priciple is actually connected to proof by induction? Could we >go over that? >-Robert Falconi > > From safiamc@MIT.EDU Thu Feb 23 12:55:19 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NHtJ67019082 for <6042-probs@theory.csail.MIT.EDU>; Thu, 23 Feb 2006 12:55:19 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1NHtIDH015204 for <6042-probs@theory.csail.MIT.EDU>; Thu, 23 Feb 2006 12:55:18 -0500 (EST) Received: from mass-toolpike.mit.edu (MASS-TOOLPIKE.MIT.EDU [18.7.16.71]) (authenticated bits=56) (User authenticated as safiamc@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1NHtChQ023472 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.MIT.EDU>; Thu, 23 Feb 2006 12:55:12 -0500 (EST) Received: (from safiamc@localhost) by mass-toolpike.mit.edu (8.12.9) id k1NHtBYE013560; Thu, 23 Feb 2006 12:55:11 -0500 (EST) Date: Thu, 23 Feb 2006 12:55:10 -0500 (EST) From: Safia M Chettih To: 6042-probs@theory.csail.MIT.EDU Subject: Friday Readings Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1374 Content-Length: 635 X-Status: A X-Keywords: NotJunk First, in section 2.1, right before definition 2.2, the notes say "Reflexive partial orders called weak." Perhaps it would be clearer to say "Reflexive partial orders _are_ called weak." In the second-to-last paragraph of the reading, I think you want a "been" in between the "we've" & "using". Also, in the second footnote, you might want to replace the first "that" with a "than". I think the footnote makes a very important distinction that was not explicitly stated in class. I was a bit confused about calling something both partial and total at the same time, so I'm glad the notes cleared that up for me. Safia Chettih From meyer@csail.mit.edu Thu Feb 23 13:12:03 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NIC367029960; Thu, 23 Feb 2006 13:12:03 -0500 Message-ID: <43FDFB02.8050802@csail.mit.edu> Date: Thu, 23 Feb 2006 13:12:18 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Jorge L De la Garza CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Comments on notes 3 References: <20060222230441.da0dj256zncwoks8@webmail.mit.edu> In-Reply-To: <20060222230441.da0dj256zncwoks8@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1375 Content-Length: 1428 X-Keywords: Jorge L De la Garza wrote: >-p. 2 - not quite clear on what image and inverse image are. An example would >have been nice. > >-p. 4 - don't understand eqn (1). What does the notation R{x} mean? Again, an >example would have been nice. > > > When R is a binary relation, you can apply it to any set C in two ways -- on the left or right-- notation being CR or RC, with the defs in section 1.2 that you were unsure about. So in particular, if R is a partial order (think of it as 'smaller') on a set A, and x is an element of A, then {x} is a set with one element, so R{x} is defined by 1.2. In fact, it is simply the set of all elements in A that are 'smaller' than x (including x since R is weak). >-p. 9 - Don't understand Lemma 2.19. What is t? > > It's the t that appears throughout the preceding section 2.6. But I think it would be better to say explicitly in Lemma 2.19 that t is a nonnegative real number (though usually an integer), and I will add this. thx for pointing this out.. > Don't understand example 2.21 > > Take another look at sect 2.6. If you still can't understand example 2.21 after that, ask for an explanation from a TA (or me) in office hours >-p. 16 - was only able to understand lemma 5.1 after rereading > > > > yeah there's a bunch of symbols k,m,n that can be distracting. I'd be pleased to have suggestions for a clearer writeup. >Thanks, >Jorge > > From meyer@csail.mit.edu Thu Feb 23 13:14:56 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NIEt67030427; Thu, 23 Feb 2006 13:14:56 -0500 Message-ID: <43FDFBAF.60503@csail.mit.edu> Date: Thu, 23 Feb 2006 13:15:11 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: edelmann@MIT.EDU CC: 6042-probs@theory.csail.MIT.EDU Subject: Re: Nicholas Edelman: February 24 Email Comments References: <20060222035551.031uylre930gscc4@webmail.mit.edu> In-Reply-To: <20060222035551.031uylre930gscc4@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1376 Content-Length: 1295 X-Keywords: We'll do a class problem Friday that nicely (I hope) shows how the Well-ordering Principle can be used. Meanwhile, look again at the proof of Lemma 2.11 in Notes 3 and see if you can spot the use of Well-ordering there. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ edelmann@MIT.EDU wrote: >Passage: The last paragraph of page 18 of the reading. > >The passage describes very generally how to formulate a proof using the >well-ordering principle, but I do not believe that even after reading this >passage that I would be able to formulate a proof using this principle. I >would like this topic covered in lecture and supplemented by examples to >reinforce my understanding of the principle. In addition, by lumping the >entire procedure into a single paragraph, the reading became rather confusing, >and I would have preferred that it was presented in a step by step format. > > > > >_____________________ >Nicholas A. Edelman >Electrical Engineering and Computer Science | 2008 >Massachusetts Institute of Technology >3 Ames Street, Box 265 >Cambridge, MA 02142 >Phone: 617 225 6356 > > From meyer@csail.mit.edu Thu Feb 23 13:16:22 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NIGL67000782; Thu, 23 Feb 2006 13:16:22 -0500 Message-ID: <43FDFC05.6050405@csail.mit.edu> Date: Thu, 23 Feb 2006 13:16:37 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Safia M Chettih CC: 6042-probs@theory.csail.MIT.EDU Subject: Re: Friday Readings References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1377 Content-Length: 963 X-Keywords: thx for corrections. I will make them. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Safia M Chettih wrote: > First, in section 2.1, right before definition 2.2, the notes say > "Reflexive partial orders called weak." Perhaps it would be clearer to > say "Reflexive partial orders _are_ called weak." In the > second-to-last paragraph of the reading, I think you want a "been" in > between the "we've" & "using". Also, in the second footnote, you might > want to replace the first "that" with a "than". I think the footnote > makes a very important distinction that was not explicitly stated in > class. I was a bit confused about calling something both partial and > total at the same time, so I'm glad the notes cleared that up for me. > > Safia Chettih From costan@MIT.EDU Thu Feb 23 13:52:38 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NIqb67007820 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 13:52:38 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1NIq4DH012232 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 13:52:04 -0500 (EST) Received: from w92-130-webmail-1.mit.edu (W92-130-WEBMAIL-1.MIT.EDU [18.7.22.131]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1NIq2Wi015764 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 13:52:03 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-1.mit.edu (8.12.4) id k1NIq2M4004267; Thu, 23 Feb 2006 13:52:02 -0500 Received: from DEW-CD-11.MIT.EDU (DEW-CD-11.MIT.EDU [18.171.0.87]) (User authenticated as costan@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Thu, 23 Feb 2006 13:52:02 -0500 Message-ID: <20060223135202.jl4f29w6rogg4c08@webmail.mit.edu> Date: Thu, 23 Feb 2006 13:52:02 -0500 From: Victor Marius Costan To: 6042-probs@theory.lcs.MIT.EDU Subject: Email reading comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1378 Content-Length: 594 X-Status: A X-Keywords: NonJunk NotJunk The proofs on the existence of a topological sorting and on the minimum length of a parallel planning are a bit unclear. I'll read the notes on that again soon. Here are some errors I found: * page 2, section 1.2, paragraph 2 -- "we could have defined the range" implies that the range of a relationship was already defined in lecture notes * page 12, last line, last sentence -- "we'll show you some tricks for finding such formulas a few weeks" is not good English IMHO (a preposition is missing) I hope this is sufficient proof that I went through the lecture notes. Victor Costan From meyer@csail.mit.edu Thu Feb 23 13:59:17 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NIxH67008422; Thu, 23 Feb 2006 13:59:17 -0500 Message-ID: <43FE0614.5020408@csail.mit.edu> Date: Thu, 23 Feb 2006 13:59:32 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Victor Marius Costan CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Email reading comments References: <20060223135202.jl4f29w6rogg4c08@webmail.mit.edu> In-Reply-To: <20060223135202.jl4f29w6rogg4c08@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1379 Content-Length: 980 X-Keywords: Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Victor Marius Costan wrote: >The proofs on the existence of a topological sorting and on the minimum length >of a parallel planning are a bit unclear. I'll read the notes on that again >soon. > >Here are some errors I found: > >* page 2, section 1.2, paragraph 2 -- "we could have defined the range" implies >that the range of a relationship was already defined in lecture notes > > > Range(f) was defined in Notes 2 as f^{hat}(domain(f)) >* page 12, last line, last sentence -- "we'll show you some tricks for finding >such formulas a few weeks" is not good English IMHO (a preposition is missing) > > > > thx for correction. >I hope this is sufficient proof that I went through the lecture notes. > > Victor Costan > > yes it is :-) From free.leekai@gmail.com Thu Feb 23 17:36:34 2006 Return-Path: Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.195]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NMaX67009863 for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 17:36:33 -0500 Received: by zproxy.gmail.com with SMTP id 12so175437nzp for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 14:36:33 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:sender:to:subject:mime-version:content-type; b=F31e2b5BlHNMSABoe6pKxUSD1I7MK5Ew/cANuBwTLRlCcITXvVmWunQ/zl+jKGgwK1STvrQ5xIbAwNFRdLDO3y2e+kkq/LTYM5V6drfULH5H9hPSITO2l91OpPYPjjkkAP2l/w++5NuLaPaP2zFG6ug/oRPsrUKG5tESZEHi2Cg= Received: by 10.65.159.15 with SMTP id l15mr1417080qbo; Thu, 23 Feb 2006 14:36:33 -0800 (PST) Received: by 10.64.27.14 with HTTP; Thu, 23 Feb 2006 14:36:33 -0800 (PST) Message-ID: <7b0264ba0602231436w13a1e9ch6ac05946898ccb3f@mail.gmail.com> Date: Thu, 23 Feb 2006 17:36:33 -0500 From: lee-kai Sender: free.leekai@gmail.com To: 6042-probs@theory.lcs.mit.edu Subject: ln3 / ln3-tue MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_2126_11875353.1140734193486" Status: RO X-UID: 1380 Content-Length: 1451 X-Status: A X-Keywords: ------=_Part_2126_11875353.1140734193486 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline The parts I liked most were Dilworth's Lemma and the Well Ordering Principle, although I thought section on the latter might have included a proof of the equivalence between it and induction. In the first paragraph of page 1 "lees" should be "less". On the top of page 15 of ln3.pdf (February 21, 2006, 1223 minutes) "Asume" should be "Assume". This is evidently an older version than ln3-tue.pdf by three minutes, and the section with the error does not appear in the latter= , but I state it nevertheless. ------=_Part_2126_11875353.1140734193486 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline The parts I liked most were Dilworth's Lemma and the Well Ordering Principle, although I thought section on the latter might have included a proof of the equivalence between it and induction.

In the first paragraph of page 1 "lees" should be "less"= ;.

On the top of page 15 of ln3.pdf (February 21, 2006, 1223 minutes) "Asume" should be "Assume".  This is evidently an = older version than ln3-tue.pdf by three minutes, and the section with the error does not appear in the latter, but I state it nevertheless.
------=_Part_2126_11875353.1140734193486-- From meyer@csail.mit.edu Thu Feb 23 17:39:29 2006 Return-Path: Received: from [192.168.1.103] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NMdT67010145; Thu, 23 Feb 2006 17:39:29 -0500 Message-ID: <43FE39AC.4060006@csail.mit.edu> Date: Thu, 23 Feb 2006 17:39:40 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: wysun@mit.edu CC: 6042-probs@theory.csail.mit.edu Subject: Re: 6.042 : Comments on Week 3 Reading References: <58cad4620602222000k36d22beerb28a5da48293debe@mail.gmail.com> In-Reply-To: <58cad4620602222000k36d22beerb28a5da48293debe@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1381 Content-Length: 2210 X-Keywords: Weiyang Sun wrote: > 1. in section 2.1, the explanations of transitive, asymmetric, etc. > would probably be easier to understand if there were more sample sets > that had captions showing why the sets were transitive, asymmetric, etc. > or not. > Prompted by your comment, I went back and counted 5 example classes of partial orders in Notes 3; actually, 7 examples if you count the particular Course 6 prerequisites and "getting dressed" instances as examples. This seems to me like enough examples of partial orders. I agree that we didn't give many examples of relations (maybe none in the notes, but there were a few in Tutor Pset 3) that did NOT have properties like transitive, asymm, etc. Classifying arbitrary relations by which of these properties they may have is not important for anything, and we're not trying to teach that. But negative examples can be helpful in understanding the definitions of the properties. Any particular properties where you think negative examples might be helpful? > 2. The explanation of minimal and maximal vs minimum and maximum were > also quite confusing. especially on the in class problem appendix sheet. I hope my email cleared things up a bit. > > in general, i just wish there were more examples of things that are > defined. (such as the transitive, asymmetric definitions) > It's always reasonable to ask for more ---or more informative ---examples, but the trade off is that the Notes get longer and take more time to read. So we try to give just enough for students to understand a topic. Of course that's hard guage precisely, and students do vary, so I'm always happy to have feedback about this. A few students who want more examples can be accommodated in office hours, and if more than a few, I'm happy to revise the Notes in response. > -- > "The winner ain't the one with the fastest car, son. It's just the one > who refuses to lose." --ralph earnhardt Regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617-253-6024 (fax: -8005) meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ From meyer@csail.mit.edu Thu Feb 23 17:43:29 2006 Return-Path: Received: from [192.168.1.103] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NMhT67018952; Thu, 23 Feb 2006 17:43:29 -0500 Message-ID: <43FE3A9D.7050804@csail.mit.edu> Date: Thu, 23 Feb 2006 17:43:41 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: lee-kai CC: 6042-probs@theory.lcs.mit.edu Subject: Re: ln3 / ln3-tue References: <7b0264ba0602231436w13a1e9ch6ac05946898ccb3f@mail.gmail.com> In-Reply-To: <7b0264ba0602231436w13a1e9ch6ac05946898ccb3f@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1383 Content-Length: 1056 X-Keywords: lee-kai wrote: > The parts I liked most were Dilworth's Lemma and the Well Ordering > Principle, although I thought section on the latter might have included > a proof of the equivalence between it and induction. We used to and discovered that more students found it confusing than helpful, so we cut it. But now you mention it, I'll consider using this as a "backup" team problem tomorrow for any teams that finish early. > > In the first paragraph of page 1 "lees" should be "less". > > On the top of page 15 of ln3.pdf (February 21, 2006, 1223 minutes) > "Asume" should be "Assume". This is evidently an older version than > ln3-tue.pdf by three minutes, and the section with the error does not > appear in the latter, but I state it nevertheless. Thx for the typos. Every one helps. Regards, A. -- Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617-253-6024 (fax: -8005) meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ From estickgold@gmail.com Thu Feb 23 17:44:44 2006 Return-Path: Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.197]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NMii67019041 for <6042-probs@theory.csail.mit.edu>; Thu, 23 Feb 2006 17:44:44 -0500 Received: by zproxy.gmail.com with SMTP id s1so197341nze for <6042-probs@theory.csail.mit.edu>; Thu, 23 Feb 2006 14:44:44 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:mime-version:content-type; b=usPPtnL15LuuU6l0F7xlioE/azsWX2oj08LKUAFfQinrnZeK6KcwpLaLB/NGrjpv2tvo2MgEeZx1QlmVXu5ZWewWo6s7KP3Bsad3OKlbI1CnUtn5ORki+jyQj7za9KYIpWb8+/Zi2MFeQpzhQPdnx2CaWvYLSru4K+4NuXyu7Pk= Received: by 10.65.230.14 with SMTP id h14mr3160192qbr; Thu, 23 Feb 2006 14:44:42 -0800 (PST) Received: by 10.64.208.5 with HTTP; Thu, 23 Feb 2006 14:44:42 -0800 (PST) Message-ID: <24d26e5c0602231444u4ab6a182y7e44b9df1071f0a5@mail.gmail.com> Date: Thu, 23 Feb 2006 17:44:42 -0500 From: "Eli Stickgold" To: 6042-probs@theory.csail.mit.edu Subject: Reading Comments MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_13085_29206561.1140734682587" Status: RO X-UID: 1384 Content-Length: 1458 X-Status: A X-Keywords: NonJunk NotJunk ------=_Part_13085_29206561.1140734682587 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline I found the last paragraph of the reading, dealing with the various upsides and downsides of proof by induction vs. proof using the Well Ordering Principle, particularly interesting, and I'd love to see it gone into in more depth in class. Particularly, the text says that often proof by the Well-Ordering Principle is quicker, but must be done via contradiction. I'= d love to see an example of this in class so as to see this in action, and maybe hear a little more about why this is the case. -Eli Stickgold ------=_Part_13085_29206561.1140734682587 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline I found the last paragraph of the reading, dealing with the various upsides and downsides of proof by induction vs. proof using the Well Ordering Principle, particularly interesting, and I'd love to see it gone into in more depth in class.  Particularly, the text says that often proof by the Well-Ordering Principle is quicker, but must be done via contradiction.  I'd love to see an example of this in class so as to see this in action, and maybe hear a little more about why this is the case.

-Eli Stickgold
------=_Part_13085_29206561.1140734682587-- From fanyang@MIT.EDU Thu Feb 23 17:51:45 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NMpj67027518 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 17:51:45 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1NMpiY6003199 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 17:51:44 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1NMpc97021673 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 17:51:38 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id k1NMpcge009164; Thu, 23 Feb 2006 17:51:38 -0500 Received: from MACLAURIN-FOUR-O-SIX.MIT.EDU (MACLAURIN-FOUR-O-SIX.MIT.EDU [18.90.6.151]) (User authenticated as fanyang@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Thu, 23 Feb 2006 17:51:38 -0500 Message-ID: <20060223175138.e0uckd0zifsw8kgs@webmail.mit.edu> Date: Thu, 23 Feb 2006 17:51:38 -0500 From: fanyang@MIT.EDU To: 6042-probs@theory.lcs.MIT.EDU Subject: Fan's Comments on reading MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -1.638 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1385 Content-Length: 518 X-Status: A X-Keywords: NonJunk NotJunk Name: Fan Yang 1. The most difficult part: I think the section 2.1 "Axioms for Partial Orders" on page 3 where they defined the terms "transitive" "asymmetric" "antisymmetric" and "reflexive" was the hardest to understand. I wasn't sure what they meant when they're applied to a set of pairs of integers. I was confused about that on the online tutor problems. Now I understand it after my TA explained it to me. I think it would be helpful to have some examples in addition to further illustrate these definitions. From meyer@csail.mit.edu Thu Feb 23 17:52:41 2006 Return-Path: Received: from [192.168.1.103] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NMqe67027529; Thu, 23 Feb 2006 17:52:41 -0500 Message-ID: <43FE3CC4.7080708@csail.mit.edu> Date: Thu, 23 Feb 2006 17:52:52 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Eli Stickgold CC: 6042-probs@theory.csail.mit.edu Subject: Re: Reading Comments References: <24d26e5c0602231444u4ab6a182y7e44b9df1071f0a5@mail.gmail.com> In-Reply-To: <24d26e5c0602231444u4ab6a182y7e44b9df1071f0a5@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1386 Content-Length: 1195 X-Keywords: Eli Stickgold wrote: > I found the last paragraph of the reading, dealing with the various > upsides and downsides of proof by induction vs. proof using the Well > Ordering Principle, particularly interesting, and I'd love to see it > gone into in more depth in class. We used to and discovered that more students found it confusing than helpful, so we cut it. But now you mention it, I'll consider using a proof of the well-ordering principle by induction and vice versa, as a "backup" team problem tomorrow for any teams that finish early. Particularly, the text says that > often proof by the Well-Ordering Principle is quicker, but must be done > via contradiction. I'd love to see an example of this in class so as to > see this in action, and maybe hear a little more about why this is the case. > We'll do a class problem Friday that nicely (I hope) shows how the Well-ordering Principle can be used. > -Eli Stickgold Regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617-253-6024 (fax: -8005) meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ From meyer@csail.mit.edu Thu Feb 23 17:54:20 2006 Return-Path: Received: from [192.168.1.103] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1NMsK67027589; Thu, 23 Feb 2006 17:54:20 -0500 Message-ID: <43FE3D28.50405@csail.mit.edu> Date: Thu, 23 Feb 2006 17:54:32 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: fanyang@MIT.EDU CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Fan's Comments on reading References: <20060223175138.e0uckd0zifsw8kgs@webmail.mit.edu> In-Reply-To: <20060223175138.e0uckd0zifsw8kgs@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1387 Content-Length: 952 X-Keywords: fanyang@MIT.EDU wrote: > Name: Fan Yang > > 1. The most difficult part: > > I think the section 2.1 "Axioms for Partial Orders" on page 3 where they defined > the terms "transitive" "asymmetric" "antisymmetric" and "reflexive" was the > hardest to understand. I wasn't sure what they meant when they're applied to a > set of pairs of integers. I was confused about that on the online tutor > problems. Now I understand it after my TA explained it to me. I think it would > be helpful to have some examples in addition to further illustrate these > definitions. There were 7 ---count 'em :-) ---examples of different partial orders in Notes 3. What additional examples were you looking for? Regards, A. -- Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617-253-6024 (fax: -8005) meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ From sbhat@MIT.EDU Thu Feb 23 19:23:49 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O0Nn67007745 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 19:23:49 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O0NmY6002745 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 19:23:48 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1O0Nl8n011044 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 19:23:47 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id k1O0NlLm018805; Thu, 23 Feb 2006 19:23:47 -0500 Received: from NEXT-SIX-EIGHTY-SIX.MIT.EDU (NEXT-SIX-EIGHTY-SIX.MIT.EDU [18.242.7.175]) (User authenticated as sbhat@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Thu, 23 Feb 2006 19:23:47 -0500 Message-ID: <20060223192347.jviizwwmctc0cwk8@webmail.mit.edu> Date: Thu, 23 Feb 2006 19:23:47 -0500 From: Sharat Bhat To: 6042-probs@theory.lcs.MIT.EDU Subject: Reading comments Week #2 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1388 Content-Length: 369 X-Status: A X-Keywords: NonJunk NotJunk Hi, On the last page(#19) you wrote "We?ve using the Well-ordering Principle on the sly from early on!" but I think you meant "We?ve BEEN using the Well-ordering Principle on the sly from early on!" or something similar to that. The Well-Ordering principle on page 18 was new to me. I understand it now, but you may want to cover it more than you did. -Sharat Bhat From jwan@MIT.EDU Thu Feb 23 20:22:44 2006 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O1Mi67030616 for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 20:22:44 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O1Mi24027284 for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 20:22:44 -0500 (EST) Received: from STANLEY.mit.edu (JWAN2.MIT.EDU [18.223.0.121]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id k1O1Mb1g014880 for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 20:22:37 -0500 (EST) Message-Id: <5.1.0.14.2.20060223193705.01c59880@hesiod> X-Sender: jwan@hesiod (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 23 Feb 2006 20:22:35 -0500 To: 6042-probs@theory.lcs.mit.edu From: Jordan Wan Subject: Notes 3 Reading Assignment Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1389 Content-Length: 1105 X-Keywords: NonJunk NotJunk Induction is a pretty powerful concept. I read over the rules of induction and exactly why it is able to generalize statements. I guess the problem was while I understand each individual step in induction, I don't understand why it is proves a statement in the general case. It seemed like such basic principles couldn't have so much power, but in truth Induction is actually just a simple idea that has powerful and could involve complex applications. I looked up on-line a little further for an analogy of why Induction works. I came across a robot analogy where, the statement you are trying to prove is really analogous to an action you would like your robot to perform. The ladder analogy that was used is that the base case is like getting the robot onto the ladder. The induction step is then the programming of the robot to know how to move from rung a on a ladder to rung a + 1, in this way, if you can code the robot to get onto the ladder (base case) and show that it can move from any one of the ladder to the next step, then the robot can move down the ladder indefinitely. From kelleyk@MIT.EDU Thu Feb 23 21:04:57 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O24v67021054 for <6042-probs@theory.csail.mit.edu>; Thu, 23 Feb 2006 21:04:57 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O24uvV029340 for <6042-probs@theory.csail.mit.edu>; Thu, 23 Feb 2006 21:04:56 -0500 (EST) Received: from [18.245.6.249] (BAKER-FIVE-O-FOUR.MIT.EDU [18.245.6.249]) (authenticated bits=0) (User authenticated as kelleyk@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1O24rwQ027356 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Thu, 23 Feb 2006 21:04:54 -0500 (EST) Message-ID: <43FE69BF.2010609@mit.edu> Date: Thu, 23 Feb 2006 21:04:47 -0500 From: Kevin Kelley User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.csail.mit.edu Subject: Reading comments for 24 Feb Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1390 Content-Length: 644 X-Keywords: NotJunk I thought that this week's reading was a lot more accessible than last week's; by the time I finished the reading and the tutor problemset, I felt like I had a decent handle on the material and on the new vocabulary dealing with relations and orders. It would be nice, though, if images and inverse images (mentioned on pg. 2) got a few more minutes of attention. I understand and can write out the set-notation definition of CR and RC, but I still do not have an intuitive sense of how the image or inverse image follows from either set or the relation. -- Kevin M. Kelley Massachusetts Institute of Technology From meyer@csail.mit.edu Thu Feb 23 21:09:35 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O29Z67022784; Thu, 23 Feb 2006 21:09:35 -0500 Message-ID: <43FE6AEE.8060104@csail.mit.edu> Date: Thu, 23 Feb 2006 21:09:50 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Sharat Bhat CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Reading comments Week #2 References: <20060223192347.jviizwwmctc0cwk8@webmail.mit.edu> In-Reply-To: <20060223192347.jviizwwmctc0cwk8@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1391 Content-Length: 754 X-Keywords: We'll do a class problem Friday that nicely (I hope) shows how the Well-ordering Principle can be used. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Sharat Bhat wrote: >Hi, > >On the last page(#19) you wrote "We?ve using the Well-ordering Principle on >the sly from early on!" but I think you meant "We?ve BEEN using the >Well-ordering Principle on the sly from early on!" or something similar to >that. > >The Well-Ordering principle on page 18 was new to me. I understand it now, but >you may want to cover it more than you did. > >-Sharat Bhat > > From pawand@MIT.EDU Thu Feb 23 23:12:53 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O4Cr67029945 for <6042-probs@theory.csail.mit.edu>; Thu, 23 Feb 2006 23:12:53 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O4CqJl012836 for <6042-probs@theory.csail.mit.edu>; Thu, 23 Feb 2006 23:12:52 -0500 (EST) Received: from Pawan ([18.235.1.201]) (authenticated bits=0) (User authenticated as pawand@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1O4CoPN018198 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Thu, 23 Feb 2006 23:12:50 -0500 (EST) Message-Id: <200602240412.k1O4CoPN018198@outgoing.mit.edu> From: "Pawan Deedwaniya" To: <6042-probs@theory.csail.mit.edu> Subject: Week 3 Comments Date: Thu, 23 Feb 2006 23:12:49 -0500 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0132_01C638CE.AA949340" X-Mailer: Microsoft Office Outlook, Build 11.0.5510 Thread-Index: AcY4+JJ3SmGMloBNQDi/I36YIFL6lQ== X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 X-Spam-Score: 2.779 X-Spam-Level: ** (2.779) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1392 Content-Length: 3736 X-Status: A X-Keywords: NonJunk NotJunk This is a multi-part message in MIME format. ------=_NextPart_000_0132_01C638CE.AA949340 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Hi, comment for Week 3: In example 2.21 it says "Has no chain of size 5, but has an antichain of size 4 greater than or equal to 10/4. I don't know if I am mistaken but would it be an antichain of size 3 greater than or equal to 10/4 Because you can have chains of size 4, 3, 3, this would produce the largest antichain to be 3. The well ordering principle seems interesting. I would like to see more examples of it in lecture. Also would like to see some examples of Products of Relations if possible. Pawan Deedwaniya ------=_NextPart_000_0132_01C638CE.AA949340 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable

Hi, comment for Week 3:

 

In example 2.21 it says “Has no chain of size = 5, but has an antichain of size 4 greater than or equal to = 10/4.

I don’t know if I am mistaken but would it be = an antichain of size 3 greater than or equal to = 10/4

Because you can have chains of size 4, 3, 3, this = would produce the largest antichain to be 3.

 

The well ordering principle seems interesting. I = would like to see more examples of it in lecture.

Also would like to see some examples of Products of Relations if possible.

 

Pawan Deedwaniya

------=_NextPart_000_0132_01C638CE.AA949340-- From colinc@MIT.EDU Thu Feb 23 23:13:30 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O4DU67029997 for <6042-probs@theory.lcs.MIT.EDU>; Thu, 23 Feb 2006 23:13:30 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O4DQJl013196; Thu, 23 Feb 2006 23:13:27 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1O4DPsZ018294; Thu, 23 Feb 2006 23:13:25 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id k1O4DPag008668; Thu, 23 Feb 2006 23:13:25 -0500 Received: from ATO-SIXTY-FOUR.MIT.EDU (ATO-SIXTY-FOUR.MIT.EDU [18.232.1.64]) (User authenticated as colinc@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Thu, 23 Feb 2006 23:13:25 -0500 Message-ID: <20060223231325.m99xsmeax4iog0s8@webmail.mit.edu> Date: Thu, 23 Feb 2006 23:13:25 -0500 From: Colin M Clarke To: 6042-probs@theory.lcs.MIT.EDU Subject: 2/24 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1393 Content-Length: 92 X-Keywords: NonJunk NotJunk I'm confused with all the definitions of operators. Does a a total operator imply partial? From varenc@MIT.EDU Thu Feb 23 23:17:34 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O4HY67030328 for <6042-probs@theory.csail.mit.edu>; Thu, 23 Feb 2006 23:17:34 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O4HWJl015464; Thu, 23 Feb 2006 23:17:33 -0500 (EST) Received: from [18.54.6.37] (NONE-TWO-NINETY-TWO.MIT.EDU [18.54.6.37]) (authenticated bits=0) (User authenticated as varenc@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1O4HQKP018856 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Thu, 23 Feb 2006 23:17:26 -0500 (EST) Message-ID: <43FE88DA.30405@mit.edu> Date: Thu, 23 Feb 2006 23:17:30 -0500 From: Chris V User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.csail.mit.edu Subject: Reading Comment Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1394 Content-Length: 366 X-Keywords: NonJunk NotJunk Hello! Right before 2.13 there's a small typo "A set of asks that must...." should probably be "A set of *t*asks that must" (this of course did not detract from understanding) one point of frustration was not having the different set relations in a singular place. A nice table would make them easier to find! Other than that, all is well. -Chris Varenhorst From fagin@MIT.EDU Thu Feb 23 23:47:13 2006 Return-Path: Received: from grand-central-station.mit.edu (GRAND-CENTRAL-STATION.MIT.EDU [18.7.21.82]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O4lD67008930 for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 23:47:13 -0500 Received: from outgoing-legacy.mit.edu (OUTGOING-LEGACY.MIT.EDU [18.7.22.104]) by grand-central-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O4lCo1005149 for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 23:47:12 -0500 (EST) Received: from Eddie-Latitude.mit.edu ([18.228.0.126]) ) by outgoing-legacy.mit.edu (8.12.4/8.12.4) with ESMTP id k1O4lB1g028379 for <6042-probs@theory.lcs.mit.edu>; Thu, 23 Feb 2006 23:47:11 -0500 (EST) Message-Id: <6.2.3.4.2.20060223233437.01cfcdf8@hesiod> X-Mailer: QUALCOMM Windows Eudora Version 6.2.3.4 Date: Thu, 23 Feb 2006 23:47:09 -0500 To: 6042-probs@theory.lcs.mit.edu From: Eddie Fagin Subject: Notes #3 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1395 Content-Length: 1417 X-Status: A X-Keywords: I guess I had the biggest issue with the Well-Ordering Principle. I'm sure it's sound, and I'm sure it's useful, but I'd definitely bomb a test question on Well-Ordering. The tutor problem had us put it into symbols, and I honestly had to guess between Well-Ordering and "none of the above" for that question. The notes explain the idea, but there's no formulation in the notes. If it's there and I'm just missing something, I apologize. Whatever the case, I'd like to request we go over the whole thing in more detail in class Friday, unless it's not in the scope of this course. And now, typos. I printed this on Wednesday, so I apologize if these are out of date. 1. P1 first pgh - "is the first lees than" --> "less" 2. P3 Sec. 2.1 - "Reflexive partial orders called weak:" ---> I don't know how you want this worded, but it seems incomplete. 3. P4 before Sec 2.2 - "...on the nonegative integers" --> "nonnegative" 4. P4 footnote - "... that being a partial order that is a total relation." ---> first that should be than, I think. 5. P9 Sec 3 - "to understand" -----> capitalize "to" 6. P12 bottom - a) "discovering the first place" ---> insert "in" before "the" b) "such formulas a few weeks" ----> insert "in" before "a" That's all I found. I was focusing more on content so I probably missed a few things. (6.004 test in the morning. I'm a little distracted.) Nothing major, though. -e From ruthdhan@MIT.EDU Thu Feb 23 23:55:44 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O4th67009616 for <6042-probs@theory.csail.MIT.EDU>; Thu, 23 Feb 2006 23:55:43 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O4tgJl006888 for <6042-probs@theory.csail.MIT.EDU>; Thu, 23 Feb 2006 23:55:42 -0500 (EST) Received: from no-knife.mit.edu (NO-KNIFE.MIT.EDU [18.7.16.64]) (authenticated bits=56) (User authenticated as ruthdhan@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1O4te6A024844 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.MIT.EDU>; Thu, 23 Feb 2006 23:55:41 -0500 (EST) Received: (from ruthdhan@localhost) by no-knife.mit.edu (8.12.9) id k1O4teFW010736; Thu, 23 Feb 2006 23:55:40 -0500 (EST) Date: Thu, 23 Feb 2006 23:55:40 -0500 (EST) From: Ruth Dhanaraj To: 6042-probs@theory.csail.MIT.EDU Subject: feb 24 reading assignment Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1396 Content-Length: 607 X-Keywords: NonJunk NotJunk Comments: typo in third line: 'lees' instead of 'less' So in lecture, we did a faulty induction proof where the problem was that using ellipses made the base case confusing. (It started 2 + 3 + ... + n, and then they used a base case of n=0). I wasn't exactly sure where and why the induction failed. It was obvious that it DID -- the case n=1 didn't work, period, but we weren't considering that. With the horses reasoning in the notes, it was easy to see why you couldn't move from n=1 to n=2, but with algebra it's harder to see. It'd be nice if you added an explanation of that. Ruth Dhanaraj From cak@mit.edu Fri Feb 24 00:27:30 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O5RU67019028; Fri, 24 Feb 2006 00:27:30 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1O5RUOO013972; Fri, 24 Feb 2006 00:27:30 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1O5RUo3013968; Fri, 24 Feb 2006 00:27:30 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 00:27:30 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Robert F Falconi cc: 6042-probs@theory.csail.MIT.EDU Subject: Re: Reading Assignment Comments In-Reply-To: <20060222215752.3kfayo8ha4zookw4@webmail.mit.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1397 Content-Length: 908 X-Keywords: Hi Robert, > I like that the method of proof by induction is so simple to use, but I'm not so > sure that I fully understand proof by strong induction. It seems to me like it > is a proof by induction but with several bases cases. Is that right? Yeap, that's right. > Does that really make some proofs easier to do, as the reading implys? Absolutely! We'll see examples of this. > And how is it that the well ordering priciple is actually connected to > proof by induction? Could we go over that? The connection is that whatever can be proved by induction can be proved by the well ordering principle, too; and vice-versa. The best way to understand the connection is to actually take a proof by induction and convert it into a proof by the well-ordering principle. If we don't see an example of this in lecture, we can discuss it in person after lecture ---or in office hours. Christos. From pengk@MIT.EDU Fri Feb 24 00:46:40 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O5ke67024494 for <6042-probs@theory.lcs.mit.edu>; Fri, 24 Feb 2006 00:46:40 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O5kdJl005626 for <6042-probs@theory.lcs.mit.edu>; Fri, 24 Feb 2006 00:46:39 -0500 (EST) Received: from [18.242.5.106] (NEXT-ONE-O-SIX.MIT.EDU [18.242.5.106]) (authenticated bits=0) (User authenticated as pengk@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1O5kbTg002337 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Fri, 24 Feb 2006 00:46:38 -0500 (EST) Message-ID: <43FE9DB9.1060100@mit.edu> Date: Fri, 24 Feb 2006 00:46:33 -0500 From: Kenny Peng User-Agent: Thunderbird 1.5 (Windows/20051201) MIME-Version: 1.0 To: 6042-probs@theory.lcs.mit.edu Subject: Comments for Readings for Week 3 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Spam-Score: 3.631 X-Spam-Level: *** (3.631) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1398 Content-Length: 567 X-Keywords: NonJunk NotJunk Page 20: The fact that we used the Well-Ordering Principle many times without really knowing that we were in fact using it was extremely surprising. But the way it is stated, it would lead me to think that it could be expanded such that if we map a subset of the integers onto a number line such that the subset has a lower bound, then those subsets also have a smallest element. The natural numbers fall into this, being that the lower bound is 0. I don't know if I have stated this correctly, but I wonder if there exists anything similar to this. - Kenny From cak@mit.edu Fri Feb 24 00:50:57 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O5ov67024854; Fri, 24 Feb 2006 00:50:57 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1O5ovOO014012; Fri, 24 Feb 2006 00:50:57 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1O5ou54014008; Fri, 24 Feb 2006 00:50:56 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 00:50:56 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Jorge L De la Garza cc: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Comments on notes 3 In-Reply-To: <20060222230441.da0dj256zncwoks8@webmail.mit.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1399 Content-Length: 1585 X-Keywords: Hi Jorge, > What does the notation R{x} mean? I feel the notation from Section 1.2 is not clear. Let me at least explain this. Think of two holes around the symbol for relation R, like this: __ R __ If you fill these holes with two elements a and b you get a R b and this simply means that "a relates to b". If you fill only the first hole, you get a R __ which means "the set of all b that you could put in the other hole to make aRb true". So, the notation aR means the set of all elements that a relates to: aR = { b | aRb } If you fill only the second hole, you get __ R b which means "the set of all a that you could put in the first hole to make aRb true". So, the notation Rb means the set of all elements that relate to b: Rb = { a | aRb } Now, if you fill the first hole with a _set_ C of elements (as opposed to just one element a), like C R __ the meaning is "the set of all b that you could put in the second whole to make aRb true for _some_ a in C". So, the notation CR means the set of all elements that the elements of C relate to: CR = { b | for some a in C: aRb } Similarly, if you fill the second hole with a set C, you get __ R C which means "the set of all a that you could put in the first hole to make aRb true for _some_ b in C": RC = { a | aRb for some b in C } So, the notation R{x} (or Rx, according to what I say above) is of the form __ R {x} and therefore means the set of all elements that relate to x. Long explanation, but I hope it is helpful. Let's talk about this in lecture, too. Christos. From cak@mit.edu Fri Feb 24 01:17:57 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O6Hv67028235; Fri, 24 Feb 2006 01:17:57 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1O6HvOO014116; Fri, 24 Feb 2006 01:17:57 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1O6HvOr014112; Fri, 24 Feb 2006 01:17:57 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 01:17:57 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Safia M Chettih cc: 6042-probs@theory.csail.MIT.EDU Subject: Re: Friday Readings In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1400 Content-Length: 929 X-Keywords: Hi Safia, > I think the footnote makes a very important distinction that was not > explicitly stated in class. I was a bit confused about calling something > both partial and total at the same time, so I'm glad the notes cleared > that up for me. Let me make sure we understand correctly what that footnote clarified. Yes, a partial order R on a set S can at the same time be called "total", in two senses: 1. as a relation: in the sense that every a relates to some b (for all a in S)(there exists b in S)( aRb ) 2. as a partial order: in the sense that every two elements are related in at least one of the two possible directions: (for all a in S)(for all b in S)(aRb or bRa) The footnote just separates these two meanings. Still, when someone says "this partial order is total" they definitely mean (2). If they want to imply (1), they will explicitely say "this partial order is a total relation". Christos. From cak@mit.edu Fri Feb 24 01:47:30 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O6lU67003140; Fri, 24 Feb 2006 01:47:30 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1O6lTOO014250; Fri, 24 Feb 2006 01:47:29 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1O6lTas014246; Fri, 24 Feb 2006 01:47:29 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 01:47:29 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Ruth Dhanaraj cc: 6042-probs@theory.csail.MIT.EDU Subject: Re: feb 24 reading assignment In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1401 Content-Length: 1026 X-Keywords: Hi Ruth, > typo in third line: 'lees' instead of 'less' Thanks, I'll fix it. > So in lecture, we did a faulty induction proof where the problem was > that using ellipses made the base case confusing. (It started 2 + 3 + > ... + n, and then they used a base case of n=0). I wasn't exactly sure > where and why the induction failed. It was obvious that it DID -- the > case n=1 didn't work, period, but we weren't considering that. With the > horses reasoning in the notes, it was easy to see why you couldn't move > from n=1 to n=2, but with algebra it's harder to see. It'd be nice if > you added an explanation of that. Have you checked the solution to the class problem? Here is the link to all solutions http://theory.csail.mit.edu/classes/6.042/spring06/solutions/cp3wsol.pdf (you can get them from the course calendar, the link inside the Feb 22 box) If you have already checked the solution, or you still have questions after reading it, let me know and we can discuss it after lecture tomorrow. Christos. From xiaotao88@yahoo.com Fri Feb 24 02:05:34 2006 Return-Path: Received: from web52315.mail.yahoo.com (web52315.mail.yahoo.com [206.190.48.158]) by theory.csail.mit.edu (8.12.10/8.12.1) with SMTP id k1O75Y67017285 for <6042-probs@theory.lcs.mit.edu>; Fri, 24 Feb 2006 02:05:34 -0500 Received: (qmail 54106 invoked by uid 60001); 24 Feb 2006 07:05:29 -0000 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=Message-ID:Received:Date:From:Subject:To:MIME-Version:Content-Type:Content-Transfer-Encoding; b=Ito6yeVx6+KLltgtUbKGdAQaJiyQSq7R3ngTAYkkWV/VhpNCjVwn85XVUrD0QIAtq7Y34hQKiDK6t8TRLAIr+v6lOuCEmAoApsstzvBytnuouZdo4jq9i/vXmL7HdrPkvoYTGxLIuxoNmsIfVKp5AdJVFmYZz0ec/nQEhimR+JM= ; Message-ID: <20060224070529.54104.qmail@web52315.mail.yahoo.com> Received: from [18.241.6.98] by web52315.mail.yahoo.com via HTTP; Thu, 23 Feb 2006 23:05:29 PST Date: Thu, 23 Feb 2006 23:05:29 -0800 (PST) From: Zuoyu Tao Subject: comments on reading To: 6042-probs@theory.lcs.mit.edu MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Status: RO X-UID: 1403 Content-Length: 534 X-Keywords: NotJunk The passage I found most interesting was the about the well-ordering principle and how it is essential equivalent to induction. Though the text mentioned how we can change any inductive proof to a proof using the well-ordering principle, the text did not explicitly give a way to do so. It would be good if the lecture talked more about how this is done. Zuoyu Tao TA: Christos __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com From olgaw@MIT.EDU Fri Feb 24 03:38:26 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O8cQ67017430 for <6042-probs@theory.csail.mit.edu>; Fri, 24 Feb 2006 03:38:26 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O8cPZu022885 for <6042-probs@theory.csail.mit.edu>; Fri, 24 Feb 2006 03:38:25 -0500 (EST) Received: from OLGA2 (EASTCAMPUS-SEVEN-TWENTY-THREE.MIT.EDU [18.238.5.212]) (authenticated bits=0) (User authenticated as olgaw@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1O8cLcZ014933 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Fri, 24 Feb 2006 03:38:22 -0500 (EST) Message-Id: <200602240838.k1O8cLcZ014933@outgoing.mit.edu> Reply-To: From: "Olga Wichrowska" To: <6042-probs@theory.csail.mit.edu> Subject: Email Comments: TP3 Reading Date: Fri, 24 Feb 2006 03:38:20 -0500 Organization: Massachusetts Institute of Technology MIME-Version: 1.0 Content-Type: text/plain; charset="windows-1250" Content-Transfer-Encoding: 7bit X-Mailer: Microsoft Office Outlook, Build 11.0.6353 Thread-Index: AcY5HaSBRvQ5cFFMT8iOofRuh4DabA== X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 X-Spam-Score: 0.178 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1404 Content-Length: 959 X-Keywords: NotJunk Oh, gross. I don't know if it's the sleep deprivation, but I am having a lot of trouble making sense of this reading, especially induction. Let me rephrase: I am having trouble seeing *where* exactly proofs go wrong, and why. Intuitively, I definitely grasp the concept and even the little steps. I get lost when new terminology is introduced and we are presented with theory that I don't see an immediate use for and that I cannot seem to apply to any real problems. As a result, TP3 was pretty much impossible: I couldn't make sense of the formulas at all. TP5 was worse. I'm actually still working on it, trying to figure out why I am allowed to anything but the obvious. I might need a little more practice, but getting this whole topic (the nuances of induction) clarified would be very helpful. ~Olga -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.375 / Virus Database: 268.0.0/267 - Release Date: 2/22/2006 From irenefan@gmail.com Fri Feb 24 05:33:23 2006 Return-Path: Received: from zproxy.gmail.com (zproxy.gmail.com [64.233.162.205]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OAXM67026751 for <6042-probs@theory.lcs.mit.edu>; Fri, 24 Feb 2006 05:33:23 -0500 Received: by zproxy.gmail.com with SMTP id z3so282695nzf for <6042-probs@theory.lcs.mit.edu>; Fri, 24 Feb 2006 02:33:22 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:sender:to:subject:mime-version:content-type; b=jbHTydplif3W6lrjsmrz0xXEDe0+vQMxfXjzKD/hHOhy0/3wEV9b5Bw7u8gic3bYxmKvLif8qNetfNahPdnJq09SV7jndEKM4xU6GiHsl3DSf9nn+y5N+UzYQsr3B+7fzWyvN3f1QQxnEaPrVjjHGVweoF/luwfuAJfwao6Xn8o= Received: by 10.64.10.11 with SMTP id 11mr2955596qbj; Fri, 24 Feb 2006 02:33:22 -0800 (PST) Received: by 10.65.22.20 with HTTP; Fri, 24 Feb 2006 02:33:22 -0800 (PST) Message-ID: Date: Fri, 24 Feb 2006 05:33:22 -0500 From: "Irene Fan" Sender: irenefan@gmail.com To: 6042-probs@theory.lcs.mit.edu Subject: comments for reading 3 MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_15169_16180547.1140777202098" Status: RO X-UID: 1405 Content-Length: 1347 X-Keywords: NonJunk NotJunk ------=_Part_15169_16180547.1140777202098 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline I found the definitions given for weak and strong partial orders (p.3) most difficult to understand; I felt like if there were a few more concrete examples for asymmetric vs. antisymmetric as well as the reflexive property= , it would have made me a little less confused. The examples for weak and strong partial orders were good, but trying to figure out the properties that defined them was tough. Irene Fan --------------------------------- irenefan@mit.edu ------=_Part_15169_16180547.1140777202098 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline I found the definitions given for weak and strong partial orders (p.3) most difficult to understand; I felt like if there were a few more concrete examples for asymmetric vs. antisymmetric as well as the reflexive property, it would have made me a little less confused. The examples for weak and strong partial orders were good, but trying to figure out the properties that defined them was tough.

Irene Fan
---------------------------------
irenefan@mit.edu
------=_Part_15169_16180547.1140777202098-- From soroush@MIT.EDU Fri Feb 24 06:19:10 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OBJA67022606 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 24 Feb 2006 06:19:10 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1OBJ9pE027363 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 24 Feb 2006 06:19:09 -0500 (EST) Received: from w92-130-webmail-1.mit.edu (W92-130-WEBMAIL-1.MIT.EDU [18.7.22.131]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1OBJ89X020977 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 24 Feb 2006 06:19:08 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-1.mit.edu (8.12.4) id k1OBJ81f023196; Fri, 24 Feb 2006 06:19:08 -0500 Received: from M56-129-12.MIT.EDU (M56-129-12.MIT.EDU [18.56.0.41]) (User authenticated as soroush@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 24 Feb 2006 06:19:08 -0500 Message-ID: <20060224061908.fdqsk9u9vflwosc8@webmail.mit.edu> Date: Fri, 24 Feb 2006 06:19:08 -0500 From: Soroush Vosoughi To: 6042-probs@theory.lcs.MIT.EDU Subject: Comments on Notes3 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1406 Content-Length: 422 X-Status: A X-Keywords: NonJunk NotJunk Hello, On page 2, section 1.2 in week3 course notes, it is stated that RC ::= {a E A | aRc for some c E C} and this is said to be the inverse image of C under R. At first I thought I understood the defination but then in the online pset, there was a question with the answer being that, a relation R from a set A to a set B is total iff RB=A. I don't see this. Could you please explain this a bit more? -Soroush Vosoughi From rudd@MIT.EDU Fri Feb 24 06:31:23 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OBVN67027814 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 24 Feb 2006 06:31:23 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1OBVMpE002516 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 24 Feb 2006 06:31:22 -0500 (EST) Received: from w92-130-webmail-1.mit.edu (W92-130-WEBMAIL-1.MIT.EDU [18.7.22.131]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1OBVLwP021665 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 24 Feb 2006 06:31:21 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-1.mit.edu (8.12.4) id k1OBVLZk023850; Fri, 24 Feb 2006 06:31:21 -0500 Received: from NEW-SEVEN.MIT.EDU (NEW-SEVEN.MIT.EDU [18.241.5.7]) (User authenticated as rudd@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 24 Feb 2006 06:31:21 -0500 Message-ID: <20060224063121.z4c6gh9nr5wkcogc@webmail.mit.edu> Date: Fri, 24 Feb 2006 06:31:21 -0500 From: Robert A Rudd To: 6042-probs@theory.lcs.MIT.EDU Subject: Lecture note comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1407 Content-Length: 306 X-Keywords: NotJunk The part I found most difficult was the one on images and inverse images. For the most part binary relations was pretty easy to understand, however i'm not sure what exactly is meant by the 'image' or 'inverse image' of a set. An example would've probably helped to illucidate the situation. Robert Rudd From garym@MIT.EDU Fri Feb 24 08:51:21 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1ODpL67010851 for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 08:51:21 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1ODpKW4016652 for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 08:51:20 -0500 (EST) Received: from w20-575-9.mit.edu (W20-575-9.MIT.EDU [18.187.0.28]) (authenticated bits=56) (User authenticated as garym@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1ODpHCN009510 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 08:51:17 -0500 (EST) Received: (from garym@localhost) by w20-575-9.mit.edu (8.12.9) id k1ODpG28032322; Fri, 24 Feb 2006 08:51:16 -0500 Subject: Reading Comments... From: "Gary M. Matthias" To: 6042-probs@theory.csail.MIT.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit Date: Fri, 24 Feb 2006 08:51:16 -0500 Message-Id: <1140789076.32124.3.camel@w20-575-9.mit.edu> Mime-Version: 1.0 X-Mailer: Evolution 2.0.4 X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1408 Content-Length: 261 X-Keywords: NotJunk I found the reading to be pretty difficult to understand. Had I not gone to lecture, I may have been completely lost. I would have liked to have seen some images (like the ones on the slides) for me to get a more intuitive grasp of the material. Gary Matthias From meyer@imap.theory.csail.mit.edu Fri Feb 24 01:47:05 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1O6l567002620 for <6.042-online-tutor@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 01:47:05 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1O6l4Jl005149 for <6.042-online-tutor@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 01:47:04 -0500 (EST) Received: from w92-130-webmail-3.mit.edu (W92-130-WEBMAIL-3.MIT.EDU [18.7.22.133]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1O6kvUs008401 for <6.042-online-tutor@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 01:46:57 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-3.mit.edu (8.12.4) id k1O6kvmg025063; Fri, 24 Feb 2006 01:46:57 -0500 Received: from ASHDOWN-TWO-NINETY-FIVE.MIT.EDU (ASHDOWN-TWO-NINETY-FIVE.MIT.EDU [18.250.6.40]) (User authenticated as lisa_hsu@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 24 Feb 2006 01:46:57 -0500 Message-ID: <20060224014657.rneib1tvq3ccwosg@webmail.mit.edu> Date: Fri, 24 Feb 2006 01:46:57 -0500 From: Lisa Hsu To: 6.042-online-tutor@theory.csail.MIT.EDU Subject: Week 2 Email comments MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO Content-Length: 467 X-UID: 1410 X-Keywords: NonJunk NotJunk I don't understand what the symbols that look like bent <= and bent >= signs and the sideways C. The "ordering style symbols" discussed on page 4. Also on page 6, the definition 2.9 "A topological sort of a partial order, on a set, A, is a total ordering, on A such that..." I have no idea what this means. Maybe I'm just sleepy. Finally, there is a small typo on the last page. It says "We've using the well-ordering" and I think you're missing a been. -Lisa From meyer@imap.theory.csail.mit.edu Fri Feb 24 09:58:42 2006 Message-ID: <43FF1F32.6060108@csail.mit.edu> Date: Fri, 24 Feb 2006 09:58:58 -0500 From: "Prof. Albert R. Meyer" Reply-To: 6042-meyer@theory.csail.mit.edu Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Soroush Vosoughi Subject: Re: Comments on Notes3 References: <20060224061908.fdqsk9u9vflwosc8@webmail.mit.edu> In-Reply-To: <20060224061908.fdqsk9u9vflwosc8@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 952 Status: RO X-UID: 1411 X-Keywords: In words, RB is the set of things in A that are related (have an arrow) to something in B. R being total means that everything in A is related (has an arrow) to something in B. So RB must equal A in order for R to be total. Does that help? regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Soroush Vosoughi wrote: >Hello, >On page 2, section 1.2 in week3 course notes, it is stated that >RC ::= {a E A | aRc for some c E C} and this is said to be the inverse image of >C under R. At first I thought I understood the defination but then in the online >pset, there was a question with the answer being that, a relation R from a set A >to a set B is total iff RB=A. I don't see this. Could you please explain this a >bit more? >-Soroush Vosoughi > > From dbw@MIT.EDU Fri Feb 24 10:32:40 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OFWe67022575 for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 10:32:40 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1OFWcW4024979 for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 10:32:38 -0500 (EST) Received: from w92-130-webmail-2.mit.edu (W92-130-WEBMAIL-2.MIT.EDU [18.7.22.132]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1OFWa7W016304 for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 10:32:36 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-2.mit.edu (8.12.4) id k1OFWabS020673; Fri, 24 Feb 2006 10:32:36 -0500 Received: from beac531-0b01-dhcp186.bu.edu (beac531-0b01-dhcp186.bu.edu [168.122.164.186]) (User authenticated as dbw@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 24 Feb 2006 10:32:36 -0500 Message-ID: <20060224103236.tsl3rhsz3s2okoos@webmail.mit.edu> Date: Fri, 24 Feb 2006 10:32:36 -0500 From: Daniel B Wilson To: 6042-probs@theory.csail.MIT.EDU MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -0.783 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1412 Content-Length: 506 X-Keywords: NonJunk I am still somewhat cofused about the difference between simple induction and strong induction. It seems that strong induction just means that more is implied. Or rather that strong induction just skips a big step of simple induction. Is the difference more of just a situational usage allowing for different assumptions to be made? I also noticed one small correction was needed at the end with the sentence: "We?ve using the Well-ordering Principle on the sly from early on!" Thanks, -Daniel Wilson From jessicao@MIT.EDU Fri Feb 24 10:35:57 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OFZv67027885 for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 10:35:57 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1OFZuW4028084 for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 10:35:56 -0500 (EST) Received: from w20-575-11.mit.edu (W20-575-11.MIT.EDU [18.187.0.30]) (authenticated bits=56) (User authenticated as jessicao@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1OFZqKx017585 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 10:35:53 -0500 (EST) Received: (from jessicao@localhost) by w20-575-11.mit.edu (8.12.9) id k1OFZqjI019610; Fri, 24 Feb 2006 10:35:52 -0500 Subject: Week 3 Comments From: Jessica A Owens To: 6042-probs@theory.csail.MIT.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit Date: Fri, 24 Feb 2006 10:35:51 -0500 Message-Id: <1140795351.19349.15.camel@w20-575-11.mit.edu> Mime-Version: 1.0 X-Mailer: Evolution 2.0.4 X-Spam-Score: 1.217 X-Spam-Level: * (1.217) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1413 Content-Length: 409 X-Keywords: NonJunk NotJunk I don't fully understand the difference between a relation on a set being asymmetric versus antisymmetric. In the axioms for partial orders section [2.1 on page 3], it seems that asymmetry and antisymmetry have essentially the same definition other than that under antisymmetry, it is explicitly states that a and b cannot be equal. Does this mean that under asymmetry a and b may be equal? -- Jessica Owens From scmcduff@MIT.EDU Fri Feb 24 10:43:59 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OFhx67014150 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 24 Feb 2006 10:43:59 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1OFhwW4005993 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 24 Feb 2006 10:43:58 -0500 (EST) Received: from w92-130-webmail-6.mit.edu (W92-130-WEBMAIL-6.MIT.EDU [18.7.22.137]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1OFhun6020951 for <6042-probs@theory.lcs.MIT.EDU>; Fri, 24 Feb 2006 10:43:56 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-6.mit.edu (8.12.4) id k1OFhuIE002711; Fri, 24 Feb 2006 10:43:56 -0500 Received: from cadet.psfc.mit.edu (cadet.psfc.mit.edu [198.125.177.225]) (User authenticated as scmcduff@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Fri, 24 Feb 2006 10:43:56 -0500 Message-ID: <20060224104356.yzifhdwq7wogo44c@webmail.mit.edu> Date: Fri, 24 Feb 2006 10:43:56 -0500 From: Sean C McDuffee To: 6042-probs@theory.lcs.MIT.EDU Subject: LN 3 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1414 Content-Length: 502 X-Keywords: NonJunk NotJunk I understand the induction material pretty well I believe, but the partial order stuff is giving me trouble. I think I just need some examples explained to me a bit more. When I was doing the online problem set, I had a hard time telling if a relation was reflexive or antisymetric and whatnot. I think I'll come to one of the TA's office hours. Sean -- Sean McDuffee Research Specialist MIT-NW17 175 Albany St. Cambridge, MA 02139 USA Tel. 617-253-0599 Fax. 617-258-7929 Email: scmcduff@mit.edu From ubong@MIT.EDU Fri Feb 24 10:51:09 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OFp967018705 for <6042-probs@theory.csail.mit.edu>; Fri, 24 Feb 2006 10:51:09 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1OFp7W4013293 for <6042-probs@theory.csail.mit.edu>; Fri, 24 Feb 2006 10:51:07 -0500 (EST) Received: from UB (NEW-ONE-FIFTY-THREE.MIT.EDU [18.241.5.153]) (authenticated bits=0) (User authenticated as ubong@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1OFoxGF023963 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Fri, 24 Feb 2006 10:51:00 -0500 (EST) From: "U.b." To: <6042-probs@theory.csail.mit.edu> Subject: Week 3 Comments Date: Fri, 24 Feb 2006 10:52:59 -0500 Message-ID: <003101c6395a$63a95740$9905f112@UB> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0032_01C63930.7AD4D5E0" X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2616 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 Importance: Normal X-Spam-Score: 0.388 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1415 Content-Length: 4166 X-Keywords: NonJunk NotJunk This is a multi-part message in MIME format. ------=_NextPart_000_0032_01C63930.7AD4D5E0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit On the Soundness of Strong Induction: It's not so obvious why one can assume the strong induction antecedent that p(n) is true for all between the base case and some n. It just seems as if it might lead to a lot of incorrect proofs. U.b. ------=_NextPart_000_0032_01C63930.7AD4D5E0 Content-Type: text/html; charset="us-ascii" Content-Transfer-Encoding: quoted-printable

On the Soundness of Strong = Induction:

It’s not so obvious why one can assume the = strong induction antecedent that p(n) is true for = all between the base case and some n. It just seems as if it might lead to a lot of incorrect proofs.

 

U.b.

 

------=_NextPart_000_0032_01C63930.7AD4D5E0-- From sjcates@theory.csail.mit.edu Fri Feb 24 12:23:21 2006 Return-Path: Received: from [127.0.0.1] (30-7-33.wireless.csail.mit.edu [128.30.7.33]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OHMO69016864; Fri, 24 Feb 2006 12:23:21 -0500 Message-ID: <43FF40CB.9040109@theory.csail.mit.edu> Date: Fri, 24 Feb 2006 12:22:19 -0500 From: Sonya Cates Reply-To: 6042-probs@theory.csail.mit.edu User-Agent: Thunderbird 1.5 (Windows/20051201) MIME-Version: 1.0 To: Kevin Kelley CC: 6042-probs@theory.csail.mit.edu Subject: Re: Reading comments for 24 Feb References: <43FE69BF.2010609@mit.edu> In-Reply-To: <43FE69BF.2010609@mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1416 Content-Length: 730 X-Keywords: NonJunk NotJunk I'll try to explain this with a picture during class. I don't think I can do much better with words over email. Sonya Kevin Kelley wrote: > I thought that this week's reading was a lot more accessible than last > week's; by the time I finished the reading and the tutor problemset, I > felt like I had a decent handle on the material and on the new > vocabulary dealing with relations and orders. It would be nice, > though, if images and inverse images (mentioned on pg. 2) got a few > more minutes of attention. I understand and can write out the > set-notation definition of CR and RC, but I still do not have an > intuitive sense of how the image or inverse image follows from either > set or the relation. > From sjcates@theory.csail.mit.edu Fri Feb 24 12:29:15 2006 Return-Path: Received: from [127.0.0.1] (30-7-33.wireless.csail.mit.edu [128.30.7.33]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OHT769021284; Fri, 24 Feb 2006 12:29:15 -0500 Message-ID: <43FF425E.90808@theory.csail.mit.edu> Date: Fri, 24 Feb 2006 12:29:02 -0500 From: Sonya Cates Reply-To: 6042-probs@theory.csail.mit.edu User-Agent: Thunderbird 1.5 (Windows/20051201) MIME-Version: 1.0 To: Robert A Rudd CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Lecture note comments References: <20060224063121.z4c6gh9nr5wkcogc@webmail.mit.edu> In-Reply-To: <20060224063121.z4c6gh9nr5wkcogc@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1417 Content-Length: 446 X-Keywords: NonJunk NotJunk I'll try to give you an example with a picture during class. Others had the same question. Sonya Robert A Rudd wrote: > The part I found most difficult was the one on images and inverse images. For > the most part binary relations was pretty easy to understand, however i'm not > sure what exactly is meant by the 'image' or 'inverse image' of a set. An > example would've probably helped to illucidate the situation. > > Robert Rudd > From presbrey@MIT.EDU Fri Feb 24 12:36:43 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OHah67022451 for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 12:36:43 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1OHagmK000762 for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 12:36:42 -0500 (EST) Received: from contents-vnder-pressvre.mit.edu (CONTENTS-VNDER-PRESSVRE.MIT.EDU [18.7.16.67]) (authenticated bits=56) (User authenticated as presbrey@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1OHaYkE007817 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.MIT.EDU>; Fri, 24 Feb 2006 12:36:35 -0500 (EST) Received: (from presbrey@localhost) by contents-vnder-pressvre.mit.edu (8.12.9) id k1OHaYOE025308; Fri, 24 Feb 2006 12:36:34 -0500 (EST) Date: Fri, 24 Feb 2006 12:36:34 -0500 (EST) From: presbrey To: 6042-probs@theory.csail.MIT.EDU Subject: notes 3 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1418 Content-Length: 330 X-Keywords: NotJunk Partial ordering was not very well explained to me. The notion of maximum vs. maximal, etc. and what it means for something to be "larger" than something else really messed me up on TP.3.4. Even though I finally got the right answers for that question, it was really hard trying to figure out what the question was asking. From sjcates@theory.csail.mit.edu Fri Feb 24 12:53:02 2006 Return-Path: Received: from [127.0.0.1] (30-7-33.wireless.csail.mit.edu [128.30.7.33]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OHqg69029651; Fri, 24 Feb 2006 12:53:02 -0500 Message-ID: <43FF47E5.80603@theory.csail.mit.edu> Date: Fri, 24 Feb 2006 12:52:37 -0500 From: Sonya Cates Reply-To: 6042-probs@theory.csail.mit.edu User-Agent: Thunderbird 1.5 (Windows/20051201) MIME-Version: 1.0 To: olgaw@MIT.EDU CC: 6042-probs@theory.csail.mit.edu Subject: Re: Email Comments: TP3 Reading References: <200602240838.k1O8cLcZ014933@outgoing.mit.edu> In-Reply-To: <200602240838.k1O8cLcZ014933@outgoing.mit.edu> Content-Type: text/plain; charset=windows-1250; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1419 Content-Length: 1469 X-Keywords: NonJunk NotJunk Finding mistakes in proofs takes a lot of practice (that's why you're shown so many wrong ones during class). For problem 3, I would recommend making up some small example sets and applying the relations, just to make things more concrete. Of course you can't prove anything by making up a set and showing something works on it, but it can often clarify the problem. For problem 5, try rereading sections 5.1 and 6 in the notes. You'll find that the three techniques can be used for the same thing.(you might have to read carefully) Now why would one way be easier? (It's in there) Sonya Olga Wichrowska wrote: > Oh, gross. > I don't know if it's the sleep deprivation, but I am having a lot of trouble > making sense of this reading, especially induction. > Let me rephrase: I am having trouble seeing *where* exactly proofs go wrong, > and why. Intuitively, I definitely grasp the concept and even the little > steps. I get lost when new terminology is introduced and we are presented > with theory that I don't see an immediate use for and that I cannot seem to > apply to any real problems. As a result, TP3 was pretty much impossible: I > couldn't make sense of the formulas at all. TP5 was worse. I'm actually > still working on it, trying to figure out why I am allowed to anything but > the obvious. I might need a little more practice, but getting this whole > topic (the nuances of induction) clarified would be very helpful. > > ~Olga > > From cak@mit.edu Fri Feb 24 15:10:19 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKAJ67019114; Fri, 24 Feb 2006 15:10:19 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKAJOO017799; Fri, 24 Feb 2006 15:10:19 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKAJrl017795; Fri, 24 Feb 2006 15:10:19 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:10:19 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Zuoyu Tao cc: 6042-probs@theory.lcs.mit.edu Subject: Re: comments on reading In-Reply-To: <20060224070529.54104.qmail@web52315.mail.yahoo.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1420 Content-Length: 478 X-Keywords: Hi Zuoyu, > The passage I found most interesting was the about the > well-ordering principle and how it is essential > equivalent to induction. Though the text mentioned how > we can change any inductive proof to a proof using the > well-ordering principle, the text did not explicitly > give a way to do so. It would be good if the lecture > talked more about how this is done. There is also going to be a small revision to the notes including this, by tonight. Christos. From cak@mit.edu Fri Feb 24 15:16:20 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKGK67020408; Fri, 24 Feb 2006 15:16:20 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKGKOO017818; Fri, 24 Feb 2006 15:16:20 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKGKuA017814; Fri, 24 Feb 2006 15:16:20 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:16:20 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Mark D Burroughs cc: 6042-probs@theory.csail.MIT.EDU Subject: Re: reading #2 In-Reply-To: <20060222161438.zv33htvl1i0c48og@webmail.mit.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1421 Content-Length: 254 X-Keywords: > there is a mistake in 4.3 where it says: > "(2k+1)(2k'+1)=2(kk'+k+k') + 1" > this should read: > "(2k+1)(2k'+1)=2(2kk'+k+k') + 1" since 2k*2k' is 4kk' not 2kk' > it is irrevalant to the proof but is nonetheless inconsistent Fixed. Thanks! Christos. From cak@mit.edu Fri Feb 24 15:20:34 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKKY67020765; Fri, 24 Feb 2006 15:20:34 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKKYOO017831; Fri, 24 Feb 2006 15:20:34 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKKX5r017827; Fri, 24 Feb 2006 15:20:33 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:20:33 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Safia M Chettih cc: 6042-probs@theory.csail.MIT.EDU Subject: Re: Friday Readings In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1422 Content-Length: 456 X-Keywords: > First, in section 2.1, right before definition 2.2, the notes say > "Reflexive partial orders called weak." Perhaps it would be clearer to say > "Reflexive partial orders _are_ called weak." Fixed. > In the second-to-last > paragraph of the reading, I think you want a "been" in between the "we've" > & "using". Fixed. > Also, in the second footnote, you might want to replace the > first "that" with a "than". Fixed. Thanks! Christos. From cak@mit.edu Fri Feb 24 15:23:14 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKNE67020952; Fri, 24 Feb 2006 15:23:14 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKNEOO017838; Fri, 24 Feb 2006 15:23:14 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKNEXY017834; Fri, 24 Feb 2006 15:23:14 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:23:14 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: lee-kai cc: 6042-probs@theory.lcs.mit.edu Subject: Re: ln3 / ln3-tue In-Reply-To: <7b0264ba0602231436w13a1e9ch6ac05946898ccb3f@mail.gmail.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1423 Content-Length: 192 X-Keywords: > In the first paragraph of page 1 "lees" should be "less". > On the top of page 15 of ln3.pdf (February 21, 2006, 1223 minutes) > "Asume" should be "Assume". Fixed. Thanks! Christos. From cak@mit.edu Fri Feb 24 15:24:10 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKOA67021035; Fri, 24 Feb 2006 15:24:10 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKO9OO017845; Fri, 24 Feb 2006 15:24:09 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKO9mE017841; Fri, 24 Feb 2006 15:24:09 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:24:09 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Sharat Bhat cc: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Reading comments Week #2 In-Reply-To: <20060223192347.jviizwwmctc0cwk8@webmail.mit.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1424 Content-Length: 261 X-Keywords: > On the last page(#19) you wrote "We?ve using the Well-ordering Principle on > the sly from early on!" but I think you meant "We?ve BEEN using the > Well-ordering Principle on the sly from early on!" or something similar to > that. Fixed. Thanks! Christos. From cak@mit.edu Fri Feb 24 15:26:11 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKQB67021436; Fri, 24 Feb 2006 15:26:11 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKQBOO017855; Fri, 24 Feb 2006 15:26:11 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKQAsA017851; Fri, 24 Feb 2006 15:26:10 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:26:10 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Chris V cc: 6042-probs@theory.csail.mit.edu Subject: Re: Reading Comment In-Reply-To: <43FE88DA.30405@mit.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1425 Content-Length: 165 X-Keywords: > "A set of asks that must...." > should probably be "A set of *t*asks that must" > (this of course did not detract from understanding) Fixed. Thanks! Christos. From cak@mit.edu Fri Feb 24 15:28:22 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKSM67022126; Fri, 24 Feb 2006 15:28:22 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKSLOO017862; Fri, 24 Feb 2006 15:28:21 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKSLEJ017858; Fri, 24 Feb 2006 15:28:21 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:28:21 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Eddie Fagin cc: 6042-probs@theory.lcs.mit.edu Subject: Re: Notes #3 In-Reply-To: <6.2.3.4.2.20060223233437.01cfcdf8@hesiod> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1426 Content-Length: 625 X-Keywords: > 1. P1 first pgh - "is the first lees than" --> "less" > 2. P3 Sec. 2.1 - "Reflexive partial orders called weak:" ---> I don't > know how you want this worded, but it seems incomplete. > 3. P4 before Sec 2.2 - "...on the nonegative integers" --> "nonnegative" > 4. P4 footnote - "... that being a partial order that is a total > relation." ---> first that should be than, I think. > 5. P9 Sec 3 - "to understand" -----> capitalize "to" > 6. P12 bottom - > a) "discovering the first place" ---> insert "in" before "the" > b) "such formulas a few weeks" ----> insert "in" before "a" All fixed. Thanks! Christos. From cak@mit.edu Fri Feb 24 15:28:48 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKSm67022437; Fri, 24 Feb 2006 15:28:48 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKSmOO017869; Fri, 24 Feb 2006 15:28:48 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKSlv4017865; Fri, 24 Feb 2006 15:28:47 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:28:47 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Ruth Dhanaraj cc: 6042-probs@theory.csail.MIT.EDU Subject: Re: feb 24 reading assignment In-Reply-To: Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1427 Content-Length: 75 X-Keywords: > typo in third line: 'lees' instead of 'less' Fixed. Thanks! Christos. From cak@mit.edu Fri Feb 24 15:30:35 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKUZ67024850; Fri, 24 Feb 2006 15:30:35 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKUZOO017889; Fri, 24 Feb 2006 15:30:35 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKUZFu017885; Fri, 24 Feb 2006 15:30:35 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:30:35 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Daniel B Wilson cc: 6042-probs@theory.csail.MIT.EDU Subject: Re: your mail In-Reply-To: <20060224103236.tsl3rhsz3s2okoos@webmail.mit.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1428 Content-Length: 100 X-Keywords: > > "We?ve using the Well-ordering Principle on the sly from early on!" Fixed. Thanks! Christos. From gjw@theory.csail.mit.edu Fri Feb 24 16:11:03 2006 Return-Path: Received: from falcon.csail.mit.edu (falcon.csail.mit.edu [128.30.51.39]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLB367002665; Fri, 24 Feb 2006 16:11:03 -0500 Received: from falcon.csail.mit.edu (localhost.localdomain [127.0.0.1]) by falcon.csail.mit.edu (8.13.1/8.13.1) with ESMTP id k1OLB3KX032079; Fri, 24 Feb 2006 16:11:03 -0500 Received: from localhost (gjw@localhost) by falcon.csail.mit.edu (8.13.1/8.13.1/Submit) with ESMTP id k1OLB3fC032076; Fri, 24 Feb 2006 16:11:03 -0500 X-Authentication-Warning: falcon.csail.mit.edu: gjw owned process doing -bs Date: Fri, 24 Feb 2006 16:11:03 -0500 (EST) From: Grant Wang X-X-Sender: gjw@falcon.csail.mit.edu To: Richard Hermosillo cc: 6042-probs@theory.lcs.mit.edu Subject: Re: Reading Comment 3 In-Reply-To: <43FD52F9.3020306@mit.edu> Message-ID: References: <43FD52F9.3020306@mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1429 Content-Length: 514 X-Keywords: NotJunk Hi, We talked about this today in class -- did it help to see the examples with stamps and see why we needed strong induction (and not just regular induction) in this case? -Grant On Thu, 23 Feb 2006, Richard Hermosillo wrote: > One thing I would like discussed more fully in lecture is deciding > between simple and strong induction (p. 16). I realize we haven't > finished going over induction yet but I think it would be very helpful > to spend a little extra time on this topic. > > Richard Hermosillo > From gjw@theory.csail.mit.edu Fri Feb 24 16:14:03 2006 Return-Path: Received: from falcon.csail.mit.edu (falcon.csail.mit.edu [128.30.51.39]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLE367003305; Fri, 24 Feb 2006 16:14:03 -0500 Received: from falcon.csail.mit.edu (localhost.localdomain [127.0.0.1]) by falcon.csail.mit.edu (8.13.1/8.13.1) with ESMTP id k1OLE3qV032097; Fri, 24 Feb 2006 16:14:03 -0500 Received: from localhost (gjw@localhost) by falcon.csail.mit.edu (8.13.1/8.13.1/Submit) with ESMTP id k1OLE3GE032094; Fri, 24 Feb 2006 16:14:03 -0500 X-Authentication-Warning: falcon.csail.mit.edu: gjw owned process doing -bs Date: Fri, 24 Feb 2006 16:14:03 -0500 (EST) From: Grant Wang X-X-Sender: gjw@falcon.csail.mit.edu To: Jordan Wan cc: 6042-probs@theory.lcs.mit.edu Subject: Re: Notes 3 Reading Assignment In-Reply-To: <5.1.0.14.2.20060223193705.01c59880@hesiod> Message-ID: References: <5.1.0.14.2.20060223193705.01c59880@hesiod> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1430 Content-Length: 1618 X-Keywords: NotJunk Hi, On Thu, 23 Feb 2006, Jordan Wan wrote: > Induction is a pretty powerful concept. I read over the rules of > induction and exactly why it is able to generalize statements. I guess > the problem was while I understand each individual step in induction, I > don't understand why it is proves a statement in the general case. It > seemed like such basic principles couldn't have so much power, but in > truth Induction is actually just a simple idea that has powerful and > could involve complex applications. Yup, that's exactly what it is. It's a simple idea (as in the dominos example), but can be used to prove very complex things. > I looked up on-line a little further for an analogy of why Induction > works. I came across a robot analogy where, the statement you are > trying to prove is really analogous to an action you would like your > robot to perform. The ladder analogy that was used is that the base > case is like getting the robot onto the ladder. The induction step is > then the programming of the robot to know how to move from rung a on a > ladder to rung a + 1, in this way, if you can code the robot to get onto > the ladder (base case) and show that it can move from any one of the > ladder to the next step, then the robot can move down the ladder > indefinitely. Yup, this is another good analogy. I like to put myself in the shoes of someone who is told two facts: 1. that the first domino has been pushed over, and 2. If any domino falls, the one next to it falls. I think it's prettyy easy to conclude that all the dominos fall, and that's exactly what induction is. -Grant From gjw@theory.csail.mit.edu Fri Feb 24 16:20:32 2006 Return-Path: Received: from falcon.csail.mit.edu (falcon.csail.mit.edu [128.30.51.39]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLKW67007696; Fri, 24 Feb 2006 16:20:32 -0500 Received: from falcon.csail.mit.edu (localhost.localdomain [127.0.0.1]) by falcon.csail.mit.edu (8.13.1/8.13.1) with ESMTP id k1OLKWKk032168; Fri, 24 Feb 2006 16:20:32 -0500 Received: from localhost (gjw@localhost) by falcon.csail.mit.edu (8.13.1/8.13.1/Submit) with ESMTP id k1OLKWxD032165; Fri, 24 Feb 2006 16:20:32 -0500 X-Authentication-Warning: falcon.csail.mit.edu: gjw owned process doing -bs Date: Fri, 24 Feb 2006 16:20:32 -0500 (EST) From: Grant Wang X-X-Sender: gjw@falcon.csail.mit.edu To: Colin M Clarke cc: 6042-probs@theory.lcs.MIT.EDU Subject: Re: 2/24 In-Reply-To: <20060223231325.m99xsmeax4iog0s8@webmail.mit.edu> Message-ID: References: <20060223231325.m99xsmeax4iog0s8@webmail.mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1431 Content-Length: 302 X-Keywords: NotJunk Hi, By "operator", do you mean order? And yes, a total order does imply that it's partial. Indeed, total orders are a refinement of partial orders. -Grant On Thu, 23 Feb 2006, Colin M Clarke wrote: > I'm confused with all the definitions of operators. Does a a total operator > imply partial? > From gjw@theory.csail.mit.edu Fri Feb 24 16:27:21 2006 Return-Path: Received: from falcon.csail.mit.edu (falcon.csail.mit.edu [128.30.51.39]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLRK67008415; Fri, 24 Feb 2006 16:27:20 -0500 Received: from falcon.csail.mit.edu (localhost.localdomain [127.0.0.1]) by falcon.csail.mit.edu (8.13.1/8.13.1) with ESMTP id k1OLRKeb032207; Fri, 24 Feb 2006 16:27:20 -0500 Received: from localhost (gjw@localhost) by falcon.csail.mit.edu (8.13.1/8.13.1/Submit) with ESMTP id k1OLRKaQ032204; Fri, 24 Feb 2006 16:27:20 -0500 X-Authentication-Warning: falcon.csail.mit.edu: gjw owned process doing -bs Date: Fri, 24 Feb 2006 16:27:20 -0500 (EST) From: Grant Wang X-X-Sender: gjw@falcon.csail.mit.edu To: Chris V cc: 6042-probs@theory.csail.mit.edu Subject: Re: Reading Comment In-Reply-To: <43FE88DA.30405@mit.edu> Message-ID: References: <43FE88DA.30405@mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1432 Content-Length: 361 X-Keywords: NotJunk Hi, On Thu, 23 Feb 2006, Chris V wrote: > one point of frustration was not having the different set relations in a > singular place. A nice table would make them easier to find! Other > than that, all is well. Yes, that is a good idea -- maybe putting in a reference table after a discussion would be helpful for people trying to do a problem set. -Grant From gjw@theory.csail.mit.edu Fri Feb 24 16:30:10 2006 Return-Path: Received: from falcon.csail.mit.edu (falcon.csail.mit.edu [128.30.51.39]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLUA67008728; Fri, 24 Feb 2006 16:30:10 -0500 Received: from falcon.csail.mit.edu (localhost.localdomain [127.0.0.1]) by falcon.csail.mit.edu (8.13.1/8.13.1) with ESMTP id k1OLUA48032229; Fri, 24 Feb 2006 16:30:10 -0500 Received: from localhost (gjw@localhost) by falcon.csail.mit.edu (8.13.1/8.13.1/Submit) with ESMTP id k1OLUAwD032226; Fri, 24 Feb 2006 16:30:10 -0500 X-Authentication-Warning: falcon.csail.mit.edu: gjw owned process doing -bs Date: Fri, 24 Feb 2006 16:30:10 -0500 (EST) From: Grant Wang X-X-Sender: gjw@falcon.csail.mit.edu To: Kenny Peng cc: 6042-probs@theory.lcs.mit.edu Subject: Re: Comments for Readings for Week 3 In-Reply-To: <43FE9DB9.1060100@mit.edu> Message-ID: References: <43FE9DB9.1060100@mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1433 Content-Length: 1055 X-Keywords: NotJunk Hi, On Fri, 24 Feb 2006, Kenny Peng wrote: > The fact that we used the Well-Ordering Principle many times without > really knowing that we were in fact using it was extremely surprising. > But the way it is stated, it would lead me to think that it could be > expanded such that if we map a subset of the integers onto a number line > such that the subset has a lower bound, then those subsets also have a > smallest element. The natural numbers fall into this, being that the > lower bound is 0. I don't know if I have stated this correctly, but I > wonder if there exists anything similar to this. The well-ordering principle does indeed hold for any non-emtpy *subset* of the natural numbers, as I believe you're suggesting. It is neat concept, and just another example of the many things you take for granted (as in the proof that sqrt(2) is irrational). Indeed, the fact that we take it for granted is an example of why writing correct proofs is so important -- it's easy to take several things for granted that aren't necessarily true. -Grant From gjw@theory.csail.mit.edu Fri Feb 24 16:36:52 2006 Return-Path: Received: from falcon.csail.mit.edu (falcon.csail.mit.edu [128.30.51.39]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLaq67013989; Fri, 24 Feb 2006 16:36:52 -0500 Received: from falcon.csail.mit.edu (localhost.localdomain [127.0.0.1]) by falcon.csail.mit.edu (8.13.1/8.13.1) with ESMTP id k1OLaqCk032271; Fri, 24 Feb 2006 16:36:52 -0500 Received: from localhost (gjw@localhost) by falcon.csail.mit.edu (8.13.1/8.13.1/Submit) with ESMTP id k1OLaqNK032268; Fri, 24 Feb 2006 16:36:52 -0500 X-Authentication-Warning: falcon.csail.mit.edu: gjw owned process doing -bs Date: Fri, 24 Feb 2006 16:36:52 -0500 (EST) From: Grant Wang X-X-Sender: gjw@falcon.csail.mit.edu To: Jessica A Owens cc: 6042-probs@theory.csail.mit.edu Subject: Re: Week 3 Comments In-Reply-To: <1140795351.19349.15.camel@w20-575-11.mit.edu> Message-ID: References: <1140795351.19349.15.camel@w20-575-11.mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1434 Content-Length: 691 X-Keywords: NotJunk Yes, that's exactly the distinction: under asymmetry, we have a R b => not(b R a) for every a, b. But in antisymmetry, we only need this to hold for pairs where a is not equal to b! Does this clear things up? -Grant On Fri, 24 Feb 2006, Jessica A Owens wrote: > I don't fully understand the difference between a relation on a set > being asymmetric versus antisymmetric. In the axioms for partial orders > section [2.1 on page 3], it seems that asymmetry and antisymmetry have > essentially the same definition other than that under antisymmetry, it > is explicitly states that a and b cannot be equal. Does this mean that > under asymmetry a and b may be equal? > > -- Jessica Owens > From gjw@theory.csail.mit.edu Fri Feb 24 16:38:19 2006 Return-Path: Received: from falcon.csail.mit.edu (falcon.csail.mit.edu [128.30.51.39]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLcJ67018294; Fri, 24 Feb 2006 16:38:19 -0500 Received: from falcon.csail.mit.edu (localhost.localdomain [127.0.0.1]) by falcon.csail.mit.edu (8.13.1/8.13.1) with ESMTP id k1OLcJbj032282; Fri, 24 Feb 2006 16:38:19 -0500 Received: from localhost (gjw@localhost) by falcon.csail.mit.edu (8.13.1/8.13.1/Submit) with ESMTP id k1OLcJrm032279; Fri, 24 Feb 2006 16:38:19 -0500 X-Authentication-Warning: falcon.csail.mit.edu: gjw owned process doing -bs Date: Fri, 24 Feb 2006 16:38:19 -0500 (EST) From: Grant Wang X-X-Sender: gjw@falcon.csail.mit.edu To: Sean C McDuffee cc: 6042-probs@theory.lcs.MIT.EDU Subject: Re: LN 3 In-Reply-To: <20060224104356.yzifhdwq7wogo44c@webmail.mit.edu> Message-ID: References: <20060224104356.yzifhdwq7wogo44c@webmail.mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1435 Content-Length: 664 X-Keywords: NotJunk On Fri, 24 Feb 2006, Sean C McDuffee wrote: > I understand the induction material pretty well I believe, but the > partial order stuff is giving me trouble. I think I just need some > examples explained to me a bit more. Yes, the partial order stuff is very abstract -- learning from examples does help, and then understanding them from a general perspective to see what the definitions mean might clear things up. > When I was doing the online problem set, I had a hard time telling if a > relation was reflexive or antisymetric and whatnot. I think I'll come > to one of the TA's office hours. Sure thing -- we'd be glad to help explain something. -Grant From helentchou@gmail.com Fri Feb 24 16:38:45 2006 Return-Path: Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.196]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLcj67018507 for <6042-probs@theory.csail.mit.edu>; Fri, 24 Feb 2006 16:38:45 -0500 Received: by xproxy.gmail.com with SMTP id s19so294878wxc for <6042-probs@theory.csail.mit.edu>; Fri, 24 Feb 2006 13:38:44 -0800 (PST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:sender:to:subject:mime-version:content-type; b=q8Yb7TU33GrPGR2Z/KdzyO+nNRx0fqqL24K10Aof4FCQIzbhM/k5C6L24f1bK7HlbIwvpMilByhNvUED0saYCs730PcWyarUSQO4wz/5N2xIMeMNnQ7XKeGI3F8MEV/vnd7mlfQlxcmmjP7rBvmYAK/r8p7XMSt+8tQazCZdF3w= Received: by 10.70.59.2 with SMTP id h2mr2821527wxa; Fri, 24 Feb 2006 13:38:44 -0800 (PST) Received: by 10.70.89.9 with HTTP; Fri, 24 Feb 2006 13:38:44 -0800 (PST) Message-ID: Date: Fri, 24 Feb 2006 16:38:44 -0500 From: "Helen T Chou" Sender: helentchou@gmail.com To: 6042-probs@theory.csail.mit.edu Subject: 6.042! Fwd: Delivery Status Notification (Failure) MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_10488_20150114.1140817124592" Status: RO X-UID: 1436 Content-Length: 4422 X-Keywords: NotJunk ------=_Part_10488_20150114.1140817124592 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Hi, Sorry, I sent this to the wrong email! But I did send in comments on time...here are the forwarded messages! -Helen ---------- Forwarded message ---------- From: Mail Delivery Subsystem Date: Feb 24, 2006 9:05 AM Subject: Delivery Status Notification (Failure) To: helentchou@gmail.com This is an automatically generated Delivery Status Notification Delivery to the following recipient failed permanently: 6042-probs@mit.edu Technical details of permanent failure: PERM_FAILURE: SMTP Error (state 9): 550 5.1.1 <6042-probs@mit.edu>... User unknown ----- Original message ----- Received: by 10.70.126.12 with SMTP id y12mr3042440wxc; Fri, 24 Feb 2006 06:05:24 -0800 (PST) Received: by 10.70.89.9 with HTTP; Fri, 24 Feb 2006 06:05:23 -0800 (PST) Message-ID: Date: Fri, 24 Feb 2006 09:05:23 -0500 From: "Helen T Chou" Sender: helentchou@gmail.com To: 6042-probs@mit.edu Subject: 6.042 mailing MIME-Version: 1.0 Content-Type: multipart/alternative; boundary=3D"----=3D_Part_4478_7479655.1140789923262" ------=3D_Part_4478_7479655.1140789923262 Content-Type: text/plain; charset=3DISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Professor Meyer sent the following: "A miniMAL value is an element that has nothing else smaller than it. An illustrative example would be the set of integers GREATER THAN 1 under "divides". Now 1 isn't there, ----- Message truncated ----- ------=_Part_10488_20150114.1140817124592 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Hi,

Sorry, I sent this to the wrong email! But I did send in comments on time..= .here are the forwarded messages!

-Helen




---------- Forwarded message ----------
From: Mail Delivery Subsystem <mailer-daemon@gmail.com>
= Date: Feb 24, 2006 9:05 AM
Subject: Delivery Status Notification (Failure)
To: helentchou@gmail.com

This is an a= utomatically generated Delivery Status Notification

Delivery to the = following recipient failed permanently:

     6042= -probs@mit.edu

Technical details of permanent failure:
PERM_F= AILURE: SMTP Error (state 9): 550 5.1.1 <6042-probs@mit.edu >... User unknown

   ----- Original message -----
Received: by 10.70.126.12 with SM= TP id y12mr3042440wxc;
        F= ri, 24 Feb 2006 06:05:24 -0800 (PST)
Received: by=20 10.70.89.9 with HTTP; Fri, 24 Feb 2006 06= :05:23 -0800 (PST)
Message-ID: <fc63cfb80602240605v2c22bda7s96807= 36a827327c2@mail.gmail.com >
Date: Fri, 24 Feb 2006 09:05:23 -0500
From: "Helen T Ch= ou" <htchou@mit.edu>
Se= nder: helentchou@gmail.com
T= o:=20 6042-probs@mit.edu
Subject: 6.= 042 mailing
MIME-Version: 1.0
Content-Type: multipart/alternative;        boundary=3D"----=3D_P= art_4478_7479655.1140789923262"

------=3D_Part_4478_7479655.1140789923262
Content-Type: text/plain; char= set=3DISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-= Disposition: inline

Professor Meyer sent the following:

"= ;A miniMAL value is an element that has nothing else smaller
than it.  An illustrative example would be the set of
inte= gers GREATER THAN 1 under "divides".  Now 1 isn't there= ,

   ----- Message truncated -----

------=_Part_10488_20150114.1140817124592-- From gjw@theory.csail.mit.edu Fri Feb 24 16:41:16 2006 Return-Path: Received: from falcon.csail.mit.edu (falcon.csail.mit.edu [128.30.51.39]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLfG67018896; Fri, 24 Feb 2006 16:41:16 -0500 Received: from falcon.csail.mit.edu (localhost.localdomain [127.0.0.1]) by falcon.csail.mit.edu (8.13.1/8.13.1) with ESMTP id k1OLfGDT032305; Fri, 24 Feb 2006 16:41:16 -0500 Received: from localhost (gjw@localhost) by falcon.csail.mit.edu (8.13.1/8.13.1/Submit) with ESMTP id k1OLfGbD032302; Fri, 24 Feb 2006 16:41:16 -0500 X-Authentication-Warning: falcon.csail.mit.edu: gjw owned process doing -bs Date: Fri, 24 Feb 2006 16:41:16 -0500 (EST) From: Grant Wang X-X-Sender: gjw@falcon.csail.mit.edu To: presbrey cc: 6042-probs@theory.csail.mit.edu Subject: Re: notes 3 In-Reply-To: Message-ID: References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO X-UID: 1437 Content-Length: 711 X-Keywords: NotJunk Hi, On Fri, 24 Feb 2006, presbrey wrote: > Partial ordering was not very well explained to me. The notion of > maximum vs. maximal, etc. and what it means for something to be "larger" > than something else really messed me up on TP.3.4. Even though I > finally got the right answers for that question, it was really hard > trying to figure out what the question was asking. Yes, the main problem is that minimum vs. minimal is something that you might have some intuition about beforehand. Unfortunately, that intuition doesn't necessarily apply in this case because minimum and minimal have meanings that are not really linked to what our intuition is. Did Albert's email clear things up a bit? -Grant From meyer@imap.theory.csail.mit.edu Fri Feb 24 15:29:20 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OKTK67022462; Fri, 24 Feb 2006 15:29:20 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k1OKTKOO017876; Fri, 24 Feb 2006 15:29:20 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k1OKTKj9017872; Fri, 24 Feb 2006 15:29:20 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Fri, 24 Feb 2006 15:29:20 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Lisa Hsu cc: 6.042-online-tutor@theory.csail.MIT.EDU Subject: Re: Week 2 Email comments In-Reply-To: <20060224014657.rneib1tvq3ccwosg@webmail.mit.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on theory.csail.mit.edu X-Spam-Level: X-Spam-Status: No, hits=-4.8 required=3.7 tests=AWL,BAYES_00 autolearn=ham version=2.63 Status: RO Content-Length: 157 X-UID: 1438 X-Keywords: > Finally, there is a small typo on the last page. It says "We've using the > well-ordering" and I think you're missing a been. Fixed. Thanks! Christos. From meyer@imap.theory.csail.mit.edu Fri Feb 24 16:34:47 2006 Return-Path: Received: from falcon.csail.mit.edu (falcon.csail.mit.edu [128.30.51.39]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1OLYk67013738; Fri, 24 Feb 2006 16:34:46 -0500 Received: from falcon.csail.mit.edu (localhost.localdomain [127.0.0.1]) by falcon.csail.mit.edu (8.13.1/8.13.1) with ESMTP id k1OLYk27032254; Fri, 24 Feb 2006 16:34:46 -0500 Received: from localhost (gjw@localhost) by falcon.csail.mit.edu (8.13.1/8.13.1/Submit) with ESMTP id k1OLYk3P032251; Fri, 24 Feb 2006 16:34:46 -0500 X-Authentication-Warning: falcon.csail.mit.edu: gjw owned process doing -bs Date: Fri, 24 Feb 2006 16:34:46 -0500 (EST) From: Grant Wang X-X-Sender: gjw@falcon.csail.mit.edu To: Lisa Hsu cc: 6.042-online-tutor@theory.csail.mit.edu Subject: Re: Week 2 Email comments In-Reply-To: <20060224014657.rneib1tvq3ccwosg@webmail.mit.edu> Message-ID: References: <20060224014657.rneib1tvq3ccwosg@webmail.mit.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on theory.csail.mit.edu X-Spam-Level: X-Spam-Status: No, hits=-4.6 required=3.7 tests=AWL,BAYES_00 autolearn=ham version=2.63 Status: RO Content-Length: 1119 X-UID: 1439 X-Keywords: NotJunk Hi, On Fri, 24 Feb 2006, Lisa Hsu wrote: > I don't understand what the symbols that look like bent <= and bent >= > signs and the sideways C. The "ordering style symbols" discussed on > page 4. Also on page 6, the definition 2.9 "A topological sort of a > partial order, on a set, A, is a total ordering, on A such that..." I > have no idea what this means. Maybe I'm just sleepy. Let me know if you have more questions. The bent <= and >= are just symbols we use in partial orders. There's no *specific* meaning to them, but they mean different things in different circumstances. With regards to the sentence, "A topological sort of a partial order, on a set A, is a total ordering on A such that..." just means that a topological sort puts the elements of the partial order in a sequence a b c d e such that (a (bent <=) b (bent <=) c ...). Does the specific example with clothes make things clearer? If not, do let me know. > Finally, there is a small typo on the last page. It says "We've using the > well-ordering" and I think you're missing a been. Yup, you're right about this. Thanks! -Grant From meyer@imap.theory.csail.mit.edu Fri Feb 24 20:35:02 2006 Message-ID: <43FFB44A.7070001@csail.mit.edu> Date: Fri, 24 Feb 2006 20:35:06 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Eddie Fagin Subject: Re: Notes #3 References: <6.2.3.4.2.20060223233437.01cfcdf8@hesiod> In-Reply-To: <6.2.3.4.2.20060223233437.01cfcdf8@hesiod> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 1635 Status: RO X-UID: 1440 X-Keywords: Eddie Fagin wrote: > I guess I had the biggest issue with the Well-Ordering Principle. I'm > sure it's sound, and I'm sure it's useful, but I'd definitely bomb a > test question on Well-Ordering. The tutor problem had us put it into > symbols, and I honestly had to guess between Well-Ordering and "none > of the above" for that question. The notes explain the idea, but > there's no formulation in the notes. If it's there and I'm just > missing something, I apologize. Whatever the case, I'd like to request > we go over the whole thing in more detail in class Friday, unless it's > not in the scope of this course. > > And now, typos. I printed this on Wednesday, so I apologize if these > are out of date. > > 1. P1 first pgh - "is the first lees than" --> "less" > 2. P3 Sec. 2.1 - "Reflexive partial orders called weak:" ---> I don't > know how you want this worded, but it seems incomplete. > 3. P4 before Sec 2.2 - "...on the nonegative integers" --> "nonnegative" > 4. P4 footnote - "... that being a partial order that is a total > relation." ---> first that should be than, I think. > 5. P9 Sec 3 - "to understand" -----> capitalize "to" > 6. P12 bottom - > a) "discovering the first place" ---> insert "in" before "the" > b) "such formulas a few weeks" ----> insert "in" before "a" > > That's all I found. I was focusing more on content which is what you should be -- good for you. but I do appreciate your telling us about typos you spot; these are all fixed now. thanks, A. > so I probably missed a few things. (6.004 test in the morning. I'm a > little distracted.) Nothing major, though. > > -e > From meyer@csail.mit.edu Fri Feb 24 20:54:27 2006 Return-Path: Received: from [68.244.165.158] (000-042-562.area3.spcsdns.net [68.244.165.158]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1P1sK67021126; Fri, 24 Feb 2006 20:54:25 -0500 Message-ID: <43FFB8D3.7020202@csail.mit.edu> Date: Fri, 24 Feb 2006 20:54:27 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Pawan Deedwaniya CC: 6042-probs@theory.csail.mit.edu Subject: Re: Week 3 Comments References: <200602240412.k1O4CoPN018198@outgoing.mit.edu> In-Reply-To: <200602240412.k1O4CoPN018198@outgoing.mit.edu> Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Status: RO X-UID: 1441 Content-Length: 3741 X-Keywords: Pawan Deedwaniya wrote:

Hi, comment for Week 3:

 

In example 2.21 it says “Has no chain of size 5, but has an antichain of size 4 greater than or equal to 10/4.

I don’t know if I am mistaken but would it be an antichain of size 3 greater than or equal to 10/4

Because you can have chains of size 4, 3, 3, this would produce the largest antichain to be 3.

No, what you say is a little mixed up.  Dilworth's Lemma tells you that there will be a chain or an antichain of AT LEAST certain sizes, but they may be bigger -- as indeed they are in this example: for t=4, there is no chain of size >t, so there must be an antichain of size >= 10/4 = 2.2, which means there must be an antichain of size 3 OR MORE.  In this example, there are several such antichains, including one of size 4.

Hope that helps explain things, but if not, go to a TA (or my) offices to talk it over.

regards, A.

 

The well ordering principle seems interesting. I would like to see more examples of it in lecture.

Also would like to see some examples of Products of Relations if possible.

 

Pawan Deedwaniya

From ruthdhan@MIT.EDU Sat Feb 25 19:25:41 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1Q0Pf67010014 for <6042-probs@theory.csail.MIT.EDU>; Sat, 25 Feb 2006 19:25:41 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k1Q0PdSs022608; Sat, 25 Feb 2006 19:25:40 -0500 (EST) Received: from mass-toolpike.mit.edu (MASS-TOOLPIKE.MIT.EDU [18.7.16.71]) (authenticated bits=56) (User authenticated as ruthdhan@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k1Q0Pb8o022968 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Sat, 25 Feb 2006 19:25:37 -0500 (EST) Received: (from ruthdhan@localhost) by mass-toolpike.mit.edu (8.12.9) id k1Q0Pb3C005364; Sat, 25 Feb 2006 19:25:37 -0500 (EST) Date: Sat, 25 Feb 2006 19:25:37 -0500 (EST) From: Ruth Dhanaraj To: "Christos A. Kapoutsis" cc: 6042-probs@theory.csail.MIT.EDU Subject: Re: feb 24 reading assignment In-Reply-To: Message-ID: References: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-UID: 1443 Content-Length: 306 X-Status: A X-Keywords: NonJunk NotJunk Someone may have pointed this out already, but there's another typo in section 2.6 just before Definition 2.13. "set of asks" where it should be "set of tasks". Ruth On Fri, 24 Feb 2006, Christos A. Kapoutsis wrote: > >> typo in third line: 'lees' instead of 'less' > > Fixed. Thanks! > Christos. > > From meyer@csail.mit.edu Sat Feb 25 23:38:55 2006 Return-Path: Received: from [192.168.1.100] (pool-70-20-30-132.bstnma.fios.verizon.net [70.20.30.132]) (authenticated bits=0) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k1Q4ct67026203; Sat, 25 Feb 2006 23:38:55 -0500 Message-ID: <440130F1.6090400@csail.mit.edu> Date: Sat, 25 Feb 2006 23:39:13 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Ruth Dhanaraj CC: "Christos A. Kapoutsis" , 6042-probs@theory.csail.MIT.EDU Subject: Re: feb 24 reading assignment References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO X-UID: 1444 Content-Length: 732 X-Keywords: yes, this was fixed already. but we appreciate being notified of typos and concerns with the Notes, so thx for watching out for these. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Ruth Dhanaraj wrote: > Someone may have pointed this out already, but there's another typo in > section 2.6 just before Definition 2.13. "set of asks" where it should > be "set of tasks". > > Ruth > > On Fri, 24 Feb 2006, Christos A. Kapoutsis wrote: > >> >>> typo in third line: 'lees' instead of 'less' >> >> >> Fixed. Thanks! >> Christos. >> >> From meyer@imap.theory.csail.mit.edu Thu Feb 23 12:46:04 2006 Message-ID: <43FDF4EA.8050108@csail.mit.edu> Date: Thu, 23 Feb 2006 12:46:18 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Daniel Fuentes CC: 6042-probs@theory.csail.mit.edu Subject: Re: Week 3 Comments References: <5.2.1.1.2.20060221152126.00ba2be8@po12.mit.edu> In-Reply-To: <5.2.1.1.2.20060221152126.00ba2be8@po12.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 459 X-UID: 1445 X-Keywords: That's what Friday lecture is all about. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Daniel Fuentes wrote: > On page 17 we are introduced to Strong Induction. I still don't fully > understand how to invoke strong induction in a proof. > > -Daniel Fuentes From meyer@imap.theory.csail.mit.edu Thu Feb 23 12:47:53 2006 Message-ID: <43FDF558.5040906@csail.mit.edu> Date: Thu, 23 Feb 2006 12:48:08 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Robert F Falconi CC: 6042-probs@theory.csail.MIT.EDU Subject: Re: Reading Assignment Comments References: <20060222215752.3kfayo8ha4zookw4@webmail.mit.edu> In-Reply-To: <20060222215752.3kfayo8ha4zookw4@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 766 X-UID: 1446 X-Keywords: Strong induction is what Friday lecture is all about. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Robert F Falconi wrote: >I like that the method of proof by induction is so simple to use, but I'm not so >sure that I fully understand proof by strong induction. It seems to me like it >is a proof by induction but with several bases cases. Is that right? Does that >really make some proofs easier to do, as the reading implys? And how is it that >the well ordering priciple is actually connected to proof by induction? Could we >go over that? >-Robert Falconi > > From meyer@imap.theory.csail.mit.edu Thu Feb 23 13:12:03 2006 Message-ID: <43FDFB02.8050802@csail.mit.edu> Date: Thu, 23 Feb 2006 13:12:18 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Jorge L De la Garza CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Comments on notes 3 References: <20060222230441.da0dj256zncwoks8@webmail.mit.edu> In-Reply-To: <20060222230441.da0dj256zncwoks8@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 1429 X-UID: 1447 X-Keywords: Jorge L De la Garza wrote: >-p. 2 - not quite clear on what image and inverse image are. An example would >have been nice. > >-p. 4 - don't understand eqn (1). What does the notation R{x} mean? Again, an >example would have been nice. > > > When R is a binary relation, you can apply it to any set C in two ways -- on the left or right-- notation being CR or RC, with the defs in section 1.2 that you were unsure about. So in particular, if R is a partial order (think of it as 'smaller') on a set A, and x is an element of A, then {x} is a set with one element, so R{x} is defined by 1.2. In fact, it is simply the set of all elements in A that are 'smaller' than x (including x since R is weak). >-p. 9 - Don't understand Lemma 2.19. What is t? > > It's the t that appears throughout the preceding section 2.6. But I think it would be better to say explicitly in Lemma 2.19 that t is a nonnegative real number (though usually an integer), and I will add this. thx for pointing this out.. > Don't understand example 2.21 > > Take another look at sect 2.6. If you still can't understand example 2.21 after that, ask for an explanation from a TA (or me) in office hours >-p. 16 - was only able to understand lemma 5.1 after rereading > > > > yeah there's a bunch of symbols k,m,n that can be distracting. I'd be pleased to have suggestions for a clearer writeup. >Thanks, >Jorge > > From meyer@imap.theory.csail.mit.edu Thu Feb 23 13:14:56 2006 Message-ID: <43FDFBAF.60503@csail.mit.edu> Date: Thu, 23 Feb 2006 13:15:11 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: edelmann@MIT.EDU CC: 6042-probs@theory.csail.MIT.EDU Subject: Re: Nicholas Edelman: February 24 Email Comments References: <20060222035551.031uylre930gscc4@webmail.mit.edu> In-Reply-To: <20060222035551.031uylre930gscc4@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 1296 X-UID: 1448 X-Keywords: We'll do a class problem Friday that nicely (I hope) shows how the Well-ordering Principle can be used. Meanwhile, look again at the proof of Lemma 2.11 in Notes 3 and see if you can spot the use of Well-ordering there. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ edelmann@MIT.EDU wrote: >Passage: The last paragraph of page 18 of the reading. > >The passage describes very generally how to formulate a proof using the >well-ordering principle, but I do not believe that even after reading this >passage that I would be able to formulate a proof using this principle. I >would like this topic covered in lecture and supplemented by examples to >reinforce my understanding of the principle. In addition, by lumping the >entire procedure into a single paragraph, the reading became rather confusing, >and I would have preferred that it was presented in a step by step format. > > > > >_____________________ >Nicholas A. Edelman >Electrical Engineering and Computer Science | 2008 >Massachusetts Institute of Technology >3 Ames Street, Box 265 >Cambridge, MA 02142 >Phone: 617 225 6356 > > From meyer@imap.theory.csail.mit.edu Thu Feb 23 13:16:22 2006 Message-ID: <43FDFC05.6050405@csail.mit.edu> Date: Thu, 23 Feb 2006 13:16:37 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Safia M Chettih CC: 6042-probs@theory.csail.MIT.EDU Subject: Re: Friday Readings References: In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 964 X-UID: 1449 X-Keywords: thx for corrections. I will make them. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Safia M Chettih wrote: > First, in section 2.1, right before definition 2.2, the notes say > "Reflexive partial orders called weak." Perhaps it would be clearer to > say "Reflexive partial orders _are_ called weak." In the > second-to-last paragraph of the reading, I think you want a "been" in > between the "we've" & "using". Also, in the second footnote, you might > want to replace the first "that" with a "than". I think the footnote > makes a very important distinction that was not explicitly stated in > class. I was a bit confused about calling something both partial and > total at the same time, so I'm glad the notes cleared that up for me. > > Safia Chettih From meyer@imap.theory.csail.mit.edu Thu Feb 23 13:59:18 2006 Message-ID: <43FE0614.5020408@csail.mit.edu> Date: Thu, 23 Feb 2006 13:59:32 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Victor Marius Costan CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Email reading comments References: <20060223135202.jl4f29w6rogg4c08@webmail.mit.edu> In-Reply-To: <20060223135202.jl4f29w6rogg4c08@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 981 X-UID: 1450 X-Keywords: Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Victor Marius Costan wrote: >The proofs on the existence of a topological sorting and on the minimum length >of a parallel planning are a bit unclear. I'll read the notes on that again >soon. > >Here are some errors I found: > >* page 2, section 1.2, paragraph 2 -- "we could have defined the range" implies >that the range of a relationship was already defined in lecture notes > > > Range(f) was defined in Notes 2 as f^{hat}(domain(f)) >* page 12, last line, last sentence -- "we'll show you some tricks for finding >such formulas a few weeks" is not good English IMHO (a preposition is missing) > > > > thx for correction. >I hope this is sufficient proof that I went through the lecture notes. > > Victor Costan > > yes it is :-) From meyer@imap.theory.csail.mit.edu Thu Feb 23 17:43:29 2006 Message-ID: <43FE3A9D.7050804@csail.mit.edu> Date: Thu, 23 Feb 2006 17:43:41 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: lee-kai CC: 6042-probs@theory.lcs.mit.edu Subject: Re: ln3 / ln3-tue References: <7b0264ba0602231436w13a1e9ch6ac05946898ccb3f@mail.gmail.com> In-Reply-To: <7b0264ba0602231436w13a1e9ch6ac05946898ccb3f@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 1057 X-UID: 1451 X-Keywords: lee-kai wrote: > The parts I liked most were Dilworth's Lemma and the Well Ordering > Principle, although I thought section on the latter might have included > a proof of the equivalence between it and induction. We used to and discovered that more students found it confusing than helpful, so we cut it. But now you mention it, I'll consider using this as a "backup" team problem tomorrow for any teams that finish early. > > In the first paragraph of page 1 "lees" should be "less". > > On the top of page 15 of ln3.pdf (February 21, 2006, 1223 minutes) > "Asume" should be "Assume". This is evidently an older version than > ln3-tue.pdf by three minutes, and the section with the error does not > appear in the latter, but I state it nevertheless. Thx for the typos. Every one helps. Regards, A. -- Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617-253-6024 (fax: -8005) meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ From meyer@imap.theory.csail.mit.edu Thu Feb 23 17:52:41 2006 Message-ID: <43FE3CC4.7080708@csail.mit.edu> Date: Thu, 23 Feb 2006 17:52:52 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Eli Stickgold CC: 6042-probs@theory.csail.mit.edu Subject: Re: Reading Comments References: <24d26e5c0602231444u4ab6a182y7e44b9df1071f0a5@mail.gmail.com> In-Reply-To: <24d26e5c0602231444u4ab6a182y7e44b9df1071f0a5@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 1196 X-UID: 1452 X-Keywords: Eli Stickgold wrote: > I found the last paragraph of the reading, dealing with the various > upsides and downsides of proof by induction vs. proof using the Well > Ordering Principle, particularly interesting, and I'd love to see it > gone into in more depth in class. We used to and discovered that more students found it confusing than helpful, so we cut it. But now you mention it, I'll consider using a proof of the well-ordering principle by induction and vice versa, as a "backup" team problem tomorrow for any teams that finish early. Particularly, the text says that > often proof by the Well-Ordering Principle is quicker, but must be done > via contradiction. I'd love to see an example of this in class so as to > see this in action, and maybe hear a little more about why this is the case. > We'll do a class problem Friday that nicely (I hope) shows how the Well-ordering Principle can be used. > -Eli Stickgold Regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617-253-6024 (fax: -8005) meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ From meyer@imap.theory.csail.mit.edu Thu Feb 23 17:54:20 2006 Message-ID: <43FE3D28.50405@csail.mit.edu> Date: Thu, 23 Feb 2006 17:54:32 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: fanyang@MIT.EDU CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Fan's Comments on reading References: <20060223175138.e0uckd0zifsw8kgs@webmail.mit.edu> In-Reply-To: <20060223175138.e0uckd0zifsw8kgs@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 953 X-UID: 1453 X-Keywords: fanyang@MIT.EDU wrote: > Name: Fan Yang > > 1. The most difficult part: > > I think the section 2.1 "Axioms for Partial Orders" on page 3 where they defined > the terms "transitive" "asymmetric" "antisymmetric" and "reflexive" was the > hardest to understand. I wasn't sure what they meant when they're applied to a > set of pairs of integers. I was confused about that on the online tutor > problems. Now I understand it after my TA explained it to me. I think it would > be helpful to have some examples in addition to further illustrate these > definitions. There were 7 ---count 'em :-) ---examples of different partial orders in Notes 3. What additional examples were you looking for? Regards, A. -- Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617-253-6024 (fax: -8005) meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ From meyer@imap.theory.csail.mit.edu Thu Feb 23 21:09:35 2006 Message-ID: <43FE6AEE.8060104@csail.mit.edu> Date: Thu, 23 Feb 2006 21:09:50 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Sharat Bhat CC: 6042-probs@theory.lcs.MIT.EDU Subject: Re: Reading comments Week #2 References: <20060223192347.jviizwwmctc0cwk8@webmail.mit.edu> In-Reply-To: <20060223192347.jviizwwmctc0cwk8@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 755 X-UID: 1454 X-Keywords: We'll do a class problem Friday that nicely (I hope) shows how the Well-ordering Principle can be used. regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ Sharat Bhat wrote: >Hi, > >On the last page(#19) you wrote "We?ve using the Well-ordering Principle on >the sly from early on!" but I think you meant "We?ve BEEN using the >Well-ordering Principle on the sly from early on!" or something similar to >that. > >The Well-Ordering principle on page 18 was new to me. I understand it now, but >you may want to cover it more than you did. > >-Sharat Bhat > > From meyer@imap.theory.csail.mit.edu Fri Feb 24 20:54:29 2006 Message-ID: <43FFB8D3.7020202@csail.mit.edu> Date: Fri, 24 Feb 2006 20:54:27 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Pawan Deedwaniya CC: 6042-probs@theory.csail.mit.edu Subject: Re: Week 3 Comments References: <200602240412.k1O4CoPN018198@outgoing.mit.edu> In-Reply-To: <200602240412.k1O4CoPN018198@outgoing.mit.edu> Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Status: RO Content-Length: 3742 X-UID: 1455 X-Keywords: Pawan Deedwaniya wrote:

Hi, comment for Week 3:

 

In example 2.21 it says “Has no chain of size 5, but has an antichain of size 4 greater than or equal to 10/4.

I don’t know if I am mistaken but would it be an antichain of size 3 greater than or equal to 10/4

Because you can have chains of size 4, 3, 3, this would produce the largest antichain to be 3.

No, what you say is a little mixed up.  Dilworth's Lemma tells you that there will be a chain or an antichain of AT LEAST certain sizes, but they may be bigger -- as indeed they are in this example: for t=4, there is no chain of size >t, so there must be an antichain of size >= 10/4 = 2.2, which means there must be an antichain of size 3 OR MORE.  In this example, there are several such antichains, including one of size 4.

Hope that helps explain things, but if not, go to a TA (or my) offices to talk it over.

regards, A.

 

The well ordering principle seems interesting. I would like to see more examples of it in lecture.

Also would like to see some examples of Products of Relations if possible.

 

Pawan Deedwaniya

From meyer@imap.theory.csail.mit.edu Sat Feb 25 15:27:34 2006 Message-ID: <4400BDBD.9060005@csail.mit.edu> Date: Sat, 25 Feb 2006 15:27:41 -0500 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.7 (Windows/20050923) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Veena CC: 6042-staff@theory.csail.mit.edu Subject: Re: 6.042 pset question References: <4a8b437e0602251136m13eb3f26t97ec3fc1d294d59d@mail.gmail.com> In-Reply-To: <4a8b437e0602251136m13eb3f26t97ec3fc1d294d59d@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 740 X-UID: 1456 X-Keywords: Veena wrote: >Hi! > >I was confused about problem #2 on pset 2; for part (a), it asks us to >prove that a binary relation, R, on a set, A, is a strict partial >order iff it is transitive and irreflexive...but that is how we >defined a strict partial order!! > No, it's not: check def 2.1 in Notes 3 again for the def of strict. Regards, A. Albert R. Meyer Hitachi America Professor of Engineering MIT Computer Science & AI Laboratory The Stata Center, 32-G624 32 Vassar Street Cambridge, MA 02139 617.253.6024 meyer@csail.mit.edu http://theory.csail.mit.edu/~meyer/ > By telling us that it was transitive >and irreflexive, didn't the problem prove that R was a strict partial >order already? > >THanks, > >--Veena Venkatachalam > > From colinc@MIT.EDU Tue Feb 28 19:09:18 2006 Return-Path: Received: from biscayne-one-station.mit.edu (BISCAYNE-ONE-STATION.MIT.EDU [18.7.7.80]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k2109I67003637 for <6042-probs@theory.lcs.MIT.EDU>; Tue, 28 Feb 2006 19:09:18 -0500 Received: from outgoing.mit.edu (OUTGOING-AUTH.MIT.EDU [18.7.22.103]) by biscayne-one-station.mit.edu (8.12.4/8.9.2) with ESMTP id k2109GEe012182 for <6042-probs@theory.lcs.MIT.EDU>; Tue, 28 Feb 2006 19:09:16 -0500 (EST) Received: from w92-130-webmail-1.mit.edu (W92-130-WEBMAIL-1.MIT.EDU [18.7.22.131]) ) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id k21099va010453 for <6042-probs@theory.lcs.MIT.EDU>; Tue, 28 Feb 2006 19:09:10 -0500 (EST) Received: (from nobody@localhost) by w92-130-webmail-1.mit.edu (8.12.4) id k21099IM022194; Tue, 28 Feb 2006 19:09:09 -0500 Received: from ATO-SIXTY-FOUR.MIT.EDU (ATO-SIXTY-FOUR.MIT.EDU [18.232.1.64]) (User authenticated as colinc@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Tue, 28 Feb 2006 19:09:09 -0500 Message-ID: <20060228190909.a4inhepkyjkk0csc@webmail.mit.edu> Date: Tue, 28 Feb 2006 19:09:09 -0500 From: Colin M Clarke To: 6042-probs@theory.lcs.MIT.EDU Subject: 3/3 question MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 7bit User-Agent: Internet Messaging Program (IMP) H3 (4.0.3) X-Spam-Score: -2.599 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 So, again I'm a little confused with minimal vs maximal. If we have < on natural numbers, 0 is minimal. If we have > on the natural numbers, would 0 be maximal? Hopefully you can respond before the test tomorrow. Colin From cak@mit.edu Tue Feb 28 21:37:24 2006 Return-Path: Received: from parrot.csail.mit.edu (parrot.csail.mit.edu [128.30.51.165]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id k212bO67007458; Tue, 28 Feb 2006 21:37:24 -0500 Received: from parrot.csail.mit.edu (localhost.localdomain [127.0.0.1]) by parrot.csail.mit.edu (8.12.8/8.12.8) with ESMTP id k212bOOO021755; Tue, 28 Feb 2006 21:37:24 -0500 Received: from localhost (cak@localhost) by parrot.csail.mit.edu (8.12.8/8.12.8/Submit) with ESMTP id k212bNRV021751; Tue, 28 Feb 2006 21:37:23 -0500 X-Authentication-Warning: parrot.csail.mit.edu: cak owned process doing -bs Date: Tue, 28 Feb 2006 21:37:23 -0500 (EST) From: "Christos A. Kapoutsis" X-X-Sender: cak@parrot.csail.mit.edu To: Colin M Clarke cc: 6042-probs@theory.lcs.MIT.EDU Subject: Re: 3/3 question In-Reply-To: <20060228190909.a4inhepkyjkk0csc@webmail.mit.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Hi Collin, > So, again I'm a little confused with minimal vs maximal. If we have < > on natural numbers, 0 is minimal. Yeap, 0 is minimal (there is no x with x<0). In addition, it is minimum (since for all x, we have 0<=x). > If we have > on the natural numbers, would 0 be maximal? Hopefully you > can respond before the test tomorrow. Right. It is maximal (since there is no x such that 0>x). And it is also maximum (because for every x we have x>=0). Christos.