X-Gmail-Received: 4f9137ba2b528ad8158b2bd0308727d64ab03014 Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 07:45:18 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 10:45:18 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: nancyk@mit.edu Subject: Re: Reading assignment -- Weeks 1 & 2 Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_44593_9862883.1127227518585" Delivered-To: minilek@gmail.com ------=_Part_44593_9862883.1127227518585 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Nancy, Regarding why false implies everything. A-->B in English basically means=20 "whenever A is true, B is true". But if A is actually the literal "False",= =20 then A is never true. So the statement that "whenever A is true, B is true"= =20 is what we call *vacuously true*. In other words, it is true that whenever = A=20 is true B is true, because A is never true. Let me know if this cleared=20 things up. -Jelani ------------------------------------------------------------------------ Hi, here are my Week 2 and Week 1 comments: Week 2 Reading -- "Predicates and Sets": Passage 3.5 "Functions -- Lemma (Mapping Rule)," pg 12: At first I struggled with the implication in the first bullet ( If f : A ->= =20 B is surjective, then |A| >=3D |B|. ). I thought the proposition needed to=20 mention surjective *and* total. Only after doing the online tutor problems did I realize that the implication is valid because a function can only have one y-value for each x-value (or only one resulting value for each argument to= =20 the function). --------------------------------------------------------------------------- Week 1 Reading -- "Proofs": Passage 7.1.2 "Implies," pg. 12: Even after careful reading, for some reason I still don't understand the=20 truth table results of "P implies Q" or "if P then Q." The summary statement at= =20 the end of 7.1.2 ("An implication is true when the if-part is false or the then-part is true") is a very helpful rule, but I found the basic logic of= =20 the table difficult. Why does false imply true and false imply false? -- Nancy Keuss ------=_Part_44593_9862883.1127227518585 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Nancy,

Regarding why false implies everything.  A-->B in English basically means "whenever A is true, B is true".  But if A i= s actually the literal "False", then A is never true.  So the statement that "whenever A is true, B is true" is what we call *vacuously true*.  In other words, it is true that whenever A is true B is true, because A is never true.  Let me know if this cleared things up.

-Jelani
------------------------------------------------------------------------ Hi, here are my Week 2 and Week 1 comments:


Week 2 Reading -- "Predicates and Sets":

Passage 3.5 "Functions -- Lemma (Mapping Rule)," pg 12:

At first I struggled with the implication in the first bullet ( If  f = : A -> B
is surjective, then |A| >=3D |B|. ). I thought the proposition needed to= mention
surjective *and* total. Only after doing the online tutor problems did I realize that the implication is valid because a function can only have one<= br> y-value for each x-value (or only one resulting value for each argument to = the
function).

---------------------------------------------------------------------------=


Week 1 Reading -- "Proofs":

Passage 7.1.2 "Implies," pg. 12:

Even after careful reading, for some reason I still don't understand the tr= uth
table results of "P implies Q" or "if P then Q." The su= mmary statement at the
end of 7.1.2 ("An implication is true when the if-part is false or the=
then-part is true") is a very helpful rule, but I found the basic logi= c of the
table difficult. Why does false imply true and false imply false?




-- Nancy Keuss X-Gmail-Received: 6801f1c6374cd99a2cb4f126dfc2ca53ec2247bc Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 07:37:02 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 10:37:02 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: benlu@mit.edu Subject: Re: [6.042] comment on reading 2 Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_44512_31489427.1127227022695" Delivered-To: minilek@gmail.com ------=_Part_44512_31489427.1127227022695 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Ben, S =3D {x | P(x) } is the set of all elements x such that P(x) is true. If= =20 you've used Scheme before, you can think of it as "filter" in Scheme. So what the statement was saying was, a function is defined by its domain= =20 (where it maps from), codomain (where it maps to), and the set of pairs=20 (a,b) such that f(a) =3D b (how it maps the elements). -Jelani ---------------------------------------------------------------------------= ------------- "Everything about a function is captured by three sets: its domain, its=20 codomain, and the set {(a,b)|f(a)=3Db} which is called the graph of f." This was the most confusing thing in the reading for me because I have=20 never seen a formal definition of functions before and I am somewhat=20 unfamiliar with a lot of the notation. Specifically, what does the bar=20 between the sequence and the statement mean? How would that set be read=20 aloud? Cheers, ~Ben ------=_Part_44512_31489427.1127227022695 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Ben,

S =3D {x | P(x) } is the set of all elements x such that P(x) is true.  If you've used Scheme before, you can think of it as "filter" in Scheme.
So what the statement was saying was, a function is defined by its domain (where it maps from), codomain (where it maps to), and the set of pairs (a,b) such that f(a) =3D b (how it maps the elements).

-Jelani
---------------------------------------------------------------------------= -------------
"Everything about a function is captured by three sets: its domain, it= s
codomain, and the set {(a,b)|f(a)=3Db} which is called the graph of f."= ;

This was the most confusing thing in the reading for me because I have
never seen a formal definition of functions before and I am somewhat
unfamiliar with a lot of the notation. Specifically, what does the bar
between the sequence and the statement mean? How would that set be read aloud?

Cheers,
~Ben
X-Gmail-Received: 10f976bc5127ca2f355fd6774a0af853c6eb1314 Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 07:30:49 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 10:30:49 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: clintonb@mit.edu Subject: Re: Reading comments Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_44435_2315022.1127226649707" Delivered-To: minilek@gmail.com ------=_Part_44435_2315022.1127226649707 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Clinton, If A is equal to B, then A is a subset of B. A "proper subset" though is a= =20 subset that is not equal to the set itself, so A would not be a proper=20 subset of B. Let me know if there were any other confusing terms or=20 notation. -Jelani ---------------------------------------------------------------------------= ------------- Section 3.2, page 9. The subset notations are confusing. What exactly is the difference between = . Are there better examples? Never mind. I see now that the difference occurs in conditional statements. Although, if A is equal to B, does A not qualify as a subset of B?=20 Either way, I found this difficult as it took me a few read-throughs and this email to understand. ---- Clinton C. Blackburn MIT Class of 2008 X-Gmail-Received: 8e7b6752df12006814f31d1e89b0f3c2a5627d17 Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 07:26:54 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 10:26:54 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: arup@mit.edu Subject: Re: Week 2 Comments Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_44375_14408544.1127226414758" Delivered-To: minilek@gmail.com ------=_Part_44375_14408544.1127226414758 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Arup, In general, it suffices to prove something false by just giving a=20 counter-example. What did you have in mind when you said a more general way= ?=20 For example, even though it is not a validity it can still be true for some= =20 predicates P. Consider the predicate P(x,y) =3D True. -Jelani ---------------------------------------------------------------------------= -------- Section 2.6, page 8: I would like to have the last (false) assertion explained more=20 fully. While I understand the proof for why it would not be true, I=20 want to know if there is any more general way of understanding it=20 besides the example given, since at first glance it does not appear=20 to be incorrect. |Arup| ------=_Part_44375_14408544.1127226414758 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Arup,

In general, it suffices to prove something false by just giving a counter-example.  What did you have in mind when you said a more general way?  For example, even though it is not a validity it can still be true for some predicates P.  Consider the predicate P(x,y) =3D True.

-Jelani
---------------------------------------------------------------------------= --------
Section 2.6, page 8:

I would like to have the last (false) assertion explained more
fully.  While I understand the proof for why it would not be true, I <= br> want to know if there is any more general way of understanding it
besides the example given, since at first glance it does not appear
to be incorrect.

|Arup| X-Gmail-Received: 4e601b3a0fe19f7b8677f1feb577b592fd83af3e Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 07:21:59 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 10:21:59 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: sriaz@mit.edu Subject: Re: 6.042 Reading Comments Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_44315_26985981.1127226119384" Delivered-To: minilek@gmail.com ------=_Part_44315_26985981.1127226119384 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Sameer, Are you still confused by the definitions of surjective, injective, and=20 bijective? If so, let me know tomorrow in class and I'll try to better explain them. -Jelani ---------------------------------------------------------------------------= -------------- One aspect I would like to have explained in class further is (3.5=20 Functions, page 11) where surjectives, injectives, and bijectives are=20 explained. The terminology here is confusing, and it would be useful to=20 go over the Lemma and definitions once more. ------=_Part_44315_26985981.1127226119384 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Sameer,

Are you still confused by the definitions of surjective, injective, and bij= ective?  If so, let me know tomorrow
in class and I'll try to better explain them.

-Jelani
---------------------------------------------------------------------------= --------------
One aspect I would like to have explained in class further is (3.5
Functions, page 11) where surjectives, injectives, and bijectives are
explained.  The terminology here is confusing, and it would be useful = to
go over the Lemma and definitions once more.
X-Gmail-Received: 7d3b52505cb1e28200f5b701439b3d04e7ca8049 Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 07:19:02 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 10:19:02 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: scot@mit.edu Subject: Re: weekly problem comments Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_44283_33339107.1127225942076" Delivered-To: minilek@gmail.com ------=_Part_44283_33339107.1127225942076 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Scot, The truth table for implies is basically saying True implies only True, and= =20 False implies anything. The contrapositive says if A implies B, then not B= =20 implies not A. Before looking at the truth tables, you can try to reason=20 about it. If A implies B, that means whenever A is true then B must be true= .=20 So if B isn't true, then A couldn't be true either (because if it were, it= =20 would imply B were true, which we said it isn't). Think about it for a=20 little, and let me know if you still have questions. -Jelani ---------------------------------------------------------------------------= ----- Hello, In Week 1 readings, on page 15, I found it more difficult to understand=20 the contrapositive. In lecture I thought it made sense, but even some=20 aspects of the 'implies' truth table also seem confusing. Scot Frank ------=_Part_44283_33339107.1127225942076 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Scot,

The truth table for implies is basically saying True implies only True, and False implies anything.  The contrapositive says if A implies B, then not B implies not A.  Before looking at the truth tables, you can try to reason about it.  If A implies B, that means whenever A is true then B must be true.  So if B isn't true, then A couldn't be true either (because if it were, it would imply B were true, which we said it isn't).  Think about it for a little, and let me know if you still have questions.

-Jelani
---------------------------------------------------------------------------= -----
Hello,

In Week 1 readings, on page 15, I found it more difficult to understand the contrapositive. In lecture I thought it made sense, but even some
aspects of the 'implies' truth table also seem confusing.

Scot Frank X-Gmail-Received: 6d7a8711d8a9fb9a496f04807a5d275c70884d27 Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 07:11:39 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 10:11:39 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: natalia3@mit.edu Subject: Re: Required Reading Comments 1 Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_44238_1308454.1127225499871" Delivered-To: minilek@gmail.com ------=_Part_44238_1308454.1127225499871 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Natalia, With long lists of statements, order matters and you should begin reading= =20 from the left That is to say: there exists a, there exists b, there exists c, for all d P(a,b,c,d) is the same as there exists a (there exists b (there exists c (for all d P(a,b,c,d)))) In this case parentheses didn't matter. But, parentheses in predicates=20 matter for cases such as the following: (P ^ (Q v R)) v S vs. P ^ (Q v R v S) The first says that either S is true, or P is true and one of Q and R is=20 true. The second says that P is true and one of Q,R,S is true. In particular, S=3DTrue, P=3DQ=3DR=3DFalse makes the first one evaluate to = true but=20 the second one evaluate to false. For 2.4.1 in the reading, the parentheses= =20 weren't incorrect, but they didn't add any extra information. Please let me know if you still have questions. -Jelani ---------------------------------------------------------------------------= ------------- The part I had the most trouble with was the notation. It became especially difficult in parts 2.2 through 2.4 (pp. 6-7). I am not sure how to interpret long lists of statements, such as in 2.4, and also how to read the meaning of parentheses when predicates are enclosed within them (2.4.1).=20 Natalia Chernenko ------=_Part_44238_1308454.1127225499871 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Natalia,

With long lists of statements, order matters and you should begin reading f= rom the left

That is to say:

there exists a, there exists b, there exists c, for all d P(a,b,c,d)

is the same as

there exists a (there exists b (there exists c (for all d P(a,b,c,d))))

In this case parentheses didn't matter.  But, parentheses in predicate= s matter for cases such as the following:

(P ^ (Q v R)) v S

vs.

P ^ (Q v R v S)

The first says that either S is true, or P is true and one of Q and R is tr= ue.
The second says that P is true and one of Q,R,S is true.

In particular, S=3DTrue, P=3DQ=3DR=3DFalse makes the first one evaluate to = true but the second one evaluate to false.  For 2.4.1 in the reading, the parentheses weren't incorrect, but they didn't add any extra information.

Please let me know if you still have questions.

-Jelani
---------------------------------------------------------------------------= -------------
The part I had the most trouble with was the notation. It became
especially difficult in parts 2.2 through 2.4 (pp. 6-7). I am not sure
how to interpret long lists of statements, such as in 2.4, and also how
to read the meaning of parentheses when predicates are enclosed within
them (2.4.1).

Natalia Chernenko 
X-Gmail-Received: 5283e43b5ac09356c15648a5775b77684063c451 Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 06:53:52 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 09:53:52 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: fluff@mit.edu Subject: Re: week 2 reading Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_44114_29818067.1127224432098" Delivered-To: minilek@gmail.com ------=_Part_44114_29818067.1127224432098 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Crystal, The case with 4 strangers and a pair who knows each other is actually=20 covered by our cases. We picked an x, and Case 2 says that at least 3 people have not met x. If= =20 there are 4 strangers and a pair who know each other, we will be in Case 2.= =20 The, we will get into Case 2.2 which says that at least one pair of people= =20 haven't met each other, and we will conclude that there is a group of at=20 least 3 strangers (which is true, since there are 4). Please let me know if this made things clearer. If you still have questions= ,=20 feel free to email me or ask me in class or office hours. -Jelani ---------------------------------------------------------------------------= - I was confused by the strangers/clubs proof by case analysis (p.=20 3-4), especially cases 1.2 and 2.2. How does one know there isn't a=20 set of, say, four strangers, and then a pair who knows each other? I=20 mean, I trust that it works, but I got lost in all the wording. I=20 think a visual depiction of the problem would have been effective.=20 (Also, just so you know, there is a small typo on p. 3; it says,=20 "Among... at least 3 have did not met x.") ~Crystal ------=_Part_44114_29818067.1127224432098 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Crystal,

The case with 4 strangers and a pair who knows each other is actually cover= ed by our cases.

We picked an x, and Case 2 says that at least 3 people have not met x.  If there are 4 strangers and a pair who know each other, we will be in Case 2.  The, we will get into Case 2.2 which says that at least one pair of people haven't met each other, and we will conclude that there is a group of at least 3 strangers (which is true, since there are 4).

Please let me know if this made things clearer.  If you still have questions, feel free to email me or ask me in class or office hours.

-Jelani
---------------------------------------------------------------------------= -
I was confused by the strangers/clubs proof by case analysis (p.  
3-4), especially cases 1.2 and 2.2. How does one know there isn't a  <= br> set of, say, four strangers, and then a pair who knows each other? I  =
mean, I trust that it works, but I got lost in all the wording. I   think a visual depiction of the problem would have been effective.   (Also, just so you know, there is a small typo on p. 3; it says,  
"Among... at least 3 have did not met x.")

~Crystal X-Gmail-Received: b1a97598e0cc28777be1763354a6e6c985299167 Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 06:46:18 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 09:46:18 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: vixen@mit.edu Subject: Re: Cc: 6042-staff@theory.csail.mit.edu Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_44062_6233465.1127223978732" Delivered-To: minilek@gmail.com ------=_Part_44062_6233465.1127223978732 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline With set builder notation, we say things like S =3D {a in A | P (a)}. You c= an=20 read the | as a "such that", so what this is saying is that S consists of= =20 all elements a in A such that P(a) is true. Please let me know if you are still confused about the definitions of total= ,=20 surjective, injective, and bijective. If so, I'd be happy to go over them= =20 with you with examples. -Jelani ------------------------------------------------------------------------ I found set builder notation (pg 10) and functions (pg 11) most=20 confusing. I would not be able to describe a set using the words=20 total, surjective, injective, or bijective. ------=_Part_44062_6233465.1127223978732 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline With set builder notation, we say things like S =3D {a in A | P (a)}.  You can read the | as a "such that", so what this is = saying is that S consists of all elements a in A such that P(a) is true.

Please let me know if you are still confused about the definitions of total, surjective, injective, and bijective.  If so, I'd be happy to go over them with you with examples.

-Jelani

------------------------------------------------------------------------ I found set builder notation (pg 10) and functions (pg 11) most
confusing.  I would not be able to describe a set using the words
total, surjective, injective, or bijective. X-Gmail-Received: 333e6ea08698d973e0b8071ffc6963ae892c0158 Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 06:35:33 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 09:35:33 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: a_lopez@mit.edu Subject: Re: week 1 and week 2 readings Cc: 6042-staff@theory.csail.mit.edu Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_43962_1209255.1127223333682" Delivered-To: minilek@gmail.com ------=_Part_43962_1209255.1127223333682 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Adriana, >> I was wondering, is there a way to say "P(n) is true for exactly one n" = ? Yes. You could say that there exists an n such that P(n), and for all m P(m= )=20 implies m =3D n. >> for exactly m n's where m is an integer greater than 1? This can be done also, and I'll let you think about it as practice. As a=20 hint, consider trying to modify the solution for "P(n) is true for exactly= =20 one n". -Jelani ---------------------------------------------------------------------- In the readings for week 2, on page 5: "Sometimes True: There exists an n such that P(n) is true. P(n) is true for some n. P(n) is true for at least one n." I was wondering, is there a way to say "P(n) is true for exactly one n" ?= =20 for at most one n? for exactly m n's where m is an integer greater than 1? I would like this to be discussed more fully in class. Adriana Lopez ------=_Part_43962_1209255.1127223333682 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Adriana,

>> I was wondering, is there a way to say "P(n) is true for exac= tly one n" ?
Yes.  You could say that there exists an n such that P(n), and for all= m P(m) implies m =3D n.

>> for exactly m n's where m is an integer greater than 1?
This can be done also, and I'll let you think about it as practice.  As a hint, consider trying to modify the solution for "P(n) is true for exactly one n".

-Jelani

----------------------------------------------------------------------
In the readings for week 2, on page 5:

"Sometimes True:
There exists an n such that P(n) is true.
P(n) is true for some n.
P(n) is true for at least one n."

I was wondering, is there a way to say "P(n) is true for exactly one n= " ? for at
most one n?  for exactly m n's where m is an integer greater than 1?
I would like this to be discussed more fully in class.

Adriana Lopez X-Gmail-Received: 470e0df7236341a7bff356b3bd22b43c65a00040 Received: by 10.70.52.3 with HTTP; Tue, 20 Sep 2005 06:26:14 -0700 (PDT) Message-ID: Date: Tue, 20 Sep 2005 09:26:14 -0400 From: Jelani Nelson Reply-To: Jelani Nelson Sender: minilek@gmail.com To: bens@mit.edu Subject: Re: 3 sentences max Cc: 6042-staff@theory.csail.mit.edu Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_43914_15116132.1127222774227" Delivered-To: minilek@gmail.com ------=_Part_43914_15116132.1127222774227 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Notationally speaking, computability people have already come up with their= =20 own style for dealing with exactly this. They say a "language" is just a se= t=20 of strings over some alphabet. They then say an algorithm A "decides" a=20 language L if A always halts when given an input, and it returns true=20 ("accepts" the input) if the input was in L and it rejects otherwise. So=20 using this framework you could ask things like, "does there exist an=20 algorithm that decides the language consisting of all predicates?". If you're interested in this, you should read "Introduction to the Theory o= f=20 Computation" by Michael Sipser, or take 6.840, which he teaches. -Jelani ** ---------------------------------------------------------------------------= ------------ I think Predicate notation (pg. 4) is very cool, because it allows us to=20 write functions f: -> {T,F}. In particular, it would be cool=20 to think about predicates whose arguments are logical statements. That=20 might provide a good notation for reasoning about theorem-provers and=20 computability. -Ben ------=_Part_43914_15116132.1127222774227 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Notationally speaking, computability people have already come up with their own style for dealing with exactly this.  They say a "language" is just a set of strings over some alphabet.  The= y then say an algorithm A "decides" a language L if A always halts when = given an input, and it returns true ("accepts" the input) if the input = was in L and it rejects otherwise.  So using this framework you could ask things like, "does there exist an algorithm that decides the language consisting of all predicates?".

If you're interested in this, you should read "Intro= duction to the Theory of Computation" by Michael Sipser, or tak= e 6.840, which he teaches.

-Jelani

-------------------------------------------= --------------------------------------------
I think Predicate notation (pg. 4) is very cool, because it allows us to write functions f:<anything> -> {T,F}.  In particular, it wou= ld be cool
to think about predicates whose arguments are logical statements.  Tha= t
might provide a good notation for reasoning about theorem-provers and
computability.

-Ben From meyer@imap.theory.csail.mit.edu Thu Sep 15 15:13:56 2005 X-Account-Key: account2 X-UIDL: c6b8c09a35bd2a8ceb4a74d487ed2065 X-Apparently-To: armeyer10@yahoo.com via 66.218.78.124; Thu, 15 Sep 2005 12:07:49 -0700 X-Originating-IP: [128.30.51.92] Return-Path: Authentication-Results: mta336.mail.scd.yahoo.com from=MIT.EDU; domainkeys=neutral (no sig) Received: from 128.30.51.92 (EHLO theory.csail.mit.edu) (128.30.51.92) by mta336.mail.scd.yahoo.com with SMTP; Thu, 15 Sep 2005 12:07:49 -0700 Received: from harrier.csail.mit.edu (harrier.csail.mit.edu [128.30.51.159]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id j8FJ7maJ024425 for ; Thu, 15 Sep 2005 15:07:48 -0400 Received: from harrier.csail.mit.edu (localhost.localdomain [127.0.0.1]) by harrier.csail.mit.edu (8.13.1/8.13.1) with ESMTP id j8FJ7m6j011431 for ; Thu, 15 Sep 2005 15:07:48 -0400 Received: (from meyer@localhost) by harrier.csail.mit.edu (8.13.1/8.13.1/Submit) id j8FJ7mBH011428; Thu, 15 Sep 2005 15:07:48 -0400 Resent-Message-Id: <200509151907.j8FJ7mBH011428@harrier.csail.mit.edu> Message-Id: <200509151907.j8FJ7mBH011428@harrier.csail.mit.edu> Resent-From: meyer@csail.mit.edu Resent-Date: 15 Sep 2005 15:07:48 -0400 Resent-To: armeyer10@yahoo.com Date: Thu, 15 Sep 2005 14:52:44 -0400 (EDT) From: Yuhsin Chen To: 6042-probs@theory.lcs.MIT.EDU Subject: mistake MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Status: RO X-Status: A Content-Length: 826 X-IMAPbase: 1126811609 14 NonJunk $Forwarded NotJunk Junk X-UID: 1 X-Keywords: NotJunk I just realized that I didn't turn in my reading comment or the online tutor problem. I'm very sorry, I was mixed up on the dates. Now that I'm off on a bad start, would you suggest that I drop the class and take it again at some later date, or should I keep trying? Yuhsin (Joyce) Chen The comment I found most interesting in the reading over Sets and Functions was in section 2.4, page 6, regarding Order of Quantifiers. Had I submitted it in on time, I would've liked to have a chance to go over how order influences the logical flow in lecture. (not directly related to the reading, I also found prefixing "not" in front of a proposition surprising--"not all P are true" is equivalent to "there exists P that is false". Perhaps I am just very interested in how many ways a proposition can be transformed). From meyer@imap.theory.csail.mit.edu Thu Sep 15 15:24:31 2005 BCC: 6042-staff@theory.csail.mit.edu Message-ID: <4329CA79.3070405@csail.mit.edu> Date: Thu, 15 Sep 2005 15:24:41 -0400 From: "Prof. Albert R. Meyer" Reply-To: 6042-meyer <6042-meyer@theory.csail.mit.edu> Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Yuhsin Chen Subject: Re: mistake References: <200509151907.j8FJ7mBH011428@harrier.csail.mit.edu> In-Reply-To: <200509151907.j8FJ7mBH011428@harrier.csail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Status: RO Content-Length: 1463 X-UID: 2 X-Keywords: I won't penalize you for your late email comments. It's good that you asked. And for goodness sake, I hope you won't consider dropping again in the event of another such minor problem! (Do the Math: online tutor + email totals 5% of the final grade, of which the email is about half. There are about a dozen required emails, and being a day late would get you part credit anyway. So even if I did penalize you, it would be for an imperceptible 0.1% of your grade.) Anyway, it will be a pleasure to have you continue in the course. I hope you enjoy it. Regards, A. Yuhsin Chen wrote: > I just realized that I didn't turn in my reading comment or the online > tutor problem. I'm very sorry, I was mixed up on the dates. Now that I'm > off on a bad start, would you suggest that I drop the class and take it > again at some later date, or should I keep trying? > > Yuhsin (Joyce) Chen > > The comment I found most interesting in the reading over Sets and > Functions was in section 2.4, page 6, regarding Order of Quantifiers. > Had I submitted it in on time, I would've liked to have a chance to go > over how order influences the logical flow in lecture. (not directly > related to the reading, I also found prefixing "not" in front of a > proposition surprising--"not all P are true" is equivalent to "there > exists P that is false". Perhaps I am just very interested in how many > ways a proposition can be transformed). > > > > From meyer@imap.theory.csail.mit.edu Fri Sep 16 00:16:19 2005 BCC: 6042-staff@theory.csail.mit.edu Message-ID: <432A471D.1070107@csail.mit.edu> Date: Fri, 16 Sep 2005 00:16:29 -0400 From: "Prof. Albert R. Meyer" Reply-To: 6042-meyer <6042-meyer@theory.csail.mit.edu> Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Zev Benjamin Subject: Re: Week 2 Comments References: <4327D7E0.3050401@mit.edu> In-Reply-To: <4327D7E0.3050401@mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 822 Status: RO X-UID: 3 X-Keywords: ZFC was introduced in Week 1 Notes, pp.4--5. Did you read them? Regards, A. Zev Benjamin wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > The most difficult section I found in the reading was 3.5 Functions > (page 11). The various terms and their definitions are rather > confusing. Section four mentions ZFC axioms without explaining what the > acronym expands to and without much pretext. It's odd that it jumps > into talking about proving mathematics without explaining what it is > talking about. > > > Zev > -----BEGIN PGP SIGNATURE----- > Version: GnuPG v1.4.1 (GNU/Linux) > Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org > > iD8DBQFDJ9fglO3j8HLL0+4RAoiOAJ4xjTtvYLzW/F0y1C4uv1Xc8D6M8QCg91tt > 9iEB7LH7N65459bGCwf1ms8= > =0/lc > -----END PGP SIGNATURE----- From meyer@imap.theory.csail.mit.edu Wed Sep 14 21:47:32 2005 X-Coding-System: iso-8859-1-unix Mail-from: From zev@MIT.EDU Wed Sep 14 03:57:29 2005 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 j8E7vTaJ028229 for <6042-probs@theory.csail.mit.edu>; Wed, 14 Sep 2005 03:57:29 -0400 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 j8E7vS95016530 for <6042-probs@theory.csail.mit.edu>; Wed, 14 Sep 2005 03:57:28 -0400 (EDT) Received: from [18.243.2.35] (GALVATRON.MIT.EDU [18.243.2.35]) (authenticated bits=0) (User authenticated as zev@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id j8E7vKpI028640 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-probs@theory.csail.mit.edu>; Wed, 14 Sep 2005 03:57:25 -0400 (EDT) Message-ID: <4327D7E0.3050401@mit.edu> Date: Wed, 14 Sep 2005 03:57:20 -0400 From: Zev Benjamin User-Agent: Debian Thunderbird 1.0.2 (X11/20050602) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-probs@theory.csail.mit.edu Subject: Week 2 Comments X-Enigmail-Version: 0.91.0.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: -2.099 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-Status: A Content-Length: 666 X-UID: 4 X-Keywords: NonJunk NotJunk -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 The most difficult section I found in the reading was 3.5 Functions (page 11). The various terms and their definitions are rather confusing. Section four mentions ZFC axioms without explaining what the acronym expands to and without much pretext. It's odd that it jumps into talking about proving mathematics without explaining what it is talking about. Zev -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org iD8DBQFDJ9fglO3j8HLL0+4RAoiOAJ4xjTtvYLzW/F0y1C4uv1Xc8D6M8QCg91tt 9iEB7LH7N65459bGCwf1ms8= =0/lc -----END PGP SIGNATURE----- From meyer@imap.theory.csail.mit.edu Fri Sep 16 00:20:43 2005 BCC: 6042-staff@theory.csail.mit.edu Message-ID: <432A4824.40600@csail.mit.edu> Date: Fri, 16 Sep 2005 00:20:52 -0400 From: "Prof. Albert R. Meyer" Reply-To: 6042-meyer <6042-meyer@theory.csail.mit.edu> Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Anton Katz Subject: Re: would like to have discussed more fully it in the next lecture References: <200509141302.j8ED2CMA029410@outgoing.mit.edu> In-Reply-To: <200509141302.j8ED2CMA029410@outgoing.mit.edu> Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit Content-Length: 522 Status: RO X-UID: 5 X-Keywords: did wed lecture and problems help you sort this out? If not, go to TA's office hours and ask for more explanation. regards, A. Anton Katz wrote: > Page 6, > > 2.4 = order of Quantifiers. > > > > Seems pretty clear but had trouble with the last question in the tutor. > > > > When you write: > > ’¢Ï//x//’¢Ð//y// //Q//(//x//, //y//) ’¢ª ’¢Ð//y//’¢Ï//x// //Q//(//x//, //y//) > > > > How are the different components connected amongst each other? (and, or’¡Ä) > > > > > From meyer@imap.theory.csail.mit.edu Wed Sep 14 21:47:33 2005 X-Coding-System: iso-2022-jp-unix Mail-from: From antonk@MIT.EDU Wed Sep 14 09:02:20 2005 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 j8ED2KaJ009057 for <6042-probs@theory.lcs.mit.edu>; Wed, 14 Sep 2005 09:02:20 -0400 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 j8ED2Iko010544 for <6042-probs@theory.lcs.mit.edu>; Wed, 14 Sep 2005 09:02:19 -0400 (EDT) Received: from silencer (SILUET.MIT.EDU [18.234.0.112]) (authenticated bits=0) (User authenticated as antonk@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id j8ED2CMA029410 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT) for <6042-probs@theory.lcs.mit.edu>; Wed, 14 Sep 2005 09:02:12 -0400 (EDT) Message-Id: <200509141302.j8ED2CMA029410@outgoing.mit.edu> From: "Anton Katz" To: <6042-probs@theory.lcs.mit.edu> Subject: would like to have discussed more fully it in the next lecture Date: Wed, 14 Sep 2005 09:02:04 -0400 Organization: Massachusetts Institute of Technology MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0090_01C5B90A.FA2AD610" X-Mailer: Microsoft Office Outlook, Build 11.0.5510 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 Thread-Index: AcW5LIC6RAFOaPOOSYe/jJpvzqE/tg== X-Spam-Score: 1.293 X-Spam-Level: * (1.293) X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-Status: A Content-Length: 5382 X-UID: 6 X-Keywords: NonJunk NotJunk Page 6, 2.4 = order of Quantifiers. Seems pretty clear but had trouble with the last question in the tutor. When you write: ¢Ïx¢Ðy Q(x, y) ¢ª ¢Ðy¢Ïx Q(x, y) How are the different components connected amongst each other? (and, or¡Ä)  -=- MIME -=-  This is a multi-part message in MIME format. ------=_NextPart_000_0090_01C5B90A.FA2AD610 Content-Type: text/plain; charset="iso-2022-jp" Content-Transfer-Encoding: 7bit Page 6, 2.4 = order of Quantifiers. Seems pretty clear but had trouble with the last question in the tutor. When you write: ¢Ïx¢Ðy Q(x, y) ¢ª ¢Ðy¢Ïx Q(x, y) How are the different components connected amongst each other? (and, or¡Ä) ------=_NextPart_000_0090_01C5B90A.FA2AD610 Content-Type: text/html; charset="iso-2022-jp" Content-Transfer-Encoding: quoted-printable

Page 6,

2.4 =3D order of = Quantifiers.

 

Seems pretty clear but had trouble with the last = question in the tutor.

 

When you write:

=1B$B"O=1B(Jx=1B$B"P=1B(Jy Q(x, = y) = =1B$B"*=1B(J =1B$B"P=1B(Jy=1B$B"O=1B(Jx Q(x, = y)

 

=

How are the different components connected amongst each other? (and, = or=1B$B!D=1B(J)

 

=

 

------=_NextPart_000_0090_01C5B90A.FA2AD610-- From meyer@imap.theory.csail.mit.edu Fri Sep 16 00:22:23 2005 BCC: 6042-staff@theory.csail.mit.edu Message-ID: <432A4888.3090706@csail.mit.edu> Date: Fri, 16 Sep 2005 00:22:32 -0400 From: "Prof. Albert R. Meyer" Reply-To: 6042-meyer <6042-meyer@theory.csail.mit.edu> Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Zachary Adam Ozer Subject: Re: Email comment References: <4f2613e505091405417acd5051@mail.gmail.com> In-Reply-To: <4f2613e505091405417acd5051@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 657 Status: RO X-UID: 7 X-Keywords: did wed lecture and problems help you sort this out? If not, go to TA's office hours and ask for more explanation. regards, A. Zachary Adam Ozer wrote: > My confusion arises from the order of quantifiers section (2.4) of > week 2 course notes. On page 6, the statement "Swapping quantifiers in > Goldbach's Conjecture creates a patently false statement." I suppose > that I don't understand why the statement which follows is indeed > patently false. Indeed, in English one could say either "I will stand > up every time I hear the bell" or "Every time I hear a bell I will > stand up." The statements are equivalent, why not so in math? > > -zozer > From meyer@imap.theory.csail.mit.edu Wed Sep 14 21:47:33 2005 X-Coding-System: iso-8859-1-unix Mail-from: From zacharyozer@gmail.com Wed Sep 14 08:41:21 2005 Return-Path: Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.200]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id j8ECfLaJ005412 for <6042-probs@theory.lcs.mit.edu>; Wed, 14 Sep 2005 08:41:21 -0400 Received: by xproxy.gmail.com with SMTP id h28so205050wxd for <6042-probs@theory.lcs.mit.edu>; Wed, 14 Sep 2005 05:41:15 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:sender:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=ZC06ZTDPwXsiXFAHxXHfLZC24r7fj5p2TpGY4hL0pSV5QqRI3GJn4Ss3PSotvjbE/hgJuyyFkUEyoQXAL1rzF9cKx4Qy6a/CLCxmzQ0yUeSMSu1ompCx05GXxEnElmjolB+n/QCZR/SYLGV3dlyOB3jsYQS1m/4vOa6uBUgJDA0= Received: by 10.70.43.12 with SMTP id q12mr188761wxq; Wed, 14 Sep 2005 05:41:15 -0700 (PDT) Received: by 10.70.9.14 with HTTP; Wed, 14 Sep 2005 05:41:15 -0700 (PDT) Message-ID: <4f2613e505091405417acd5051@mail.gmail.com> Date: Wed, 14 Sep 2005 08:41:15 -0400 From: Zachary Adam Ozer Reply-To: Zachary Adam Ozer Sender: zacharyozer@gmail.com To: 6042-probs@theory.lcs.mit.edu Subject: Email comment 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 j8ECfLaJ005412 Status: RO X-Status: A Content-Length: 481 X-UID: 8 X-Keywords: NonJunk NotJunk My confusion arises from the order of quantifiers section (2.4) of week 2 course notes. On page 6, the statement "Swapping quantifiers in Goldbach's Conjecture creates a patently false statement." I suppose that I don't understand why the statement which follows is indeed patently false. Indeed, in English one could say either "I will stand up every time I hear the bell" or "Every time I hear a bell I will stand up." The statements are equivalent, why not so in math? -zozer From meyer@imap.theory.csail.mit.edu Fri Sep 16 00:26:31 2005 BCC: 6042-staff@theory.csail.mit.edu Message-ID: <432A4981.40208@csail.mit.edu> Date: Fri, 16 Sep 2005 00:26:41 -0400 From: "Prof. Albert R. Meyer" Reply-To: 6042-meyer <6042-meyer@theory.csail.mit.edu> Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Knight W Fu Subject: Re: Required Reading Comment References: <20050914045543.6yddpubg7w0soo40@webmail.mit.edu> In-Reply-To: <20050914045543.6yddpubg7w0soo40@webmail.mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 2170 Status: RO X-UID: 9 X-Keywords: the "C" in ZFC stands for Zermelo-Frankel with "C"hoice. It's not really controversial -- virtually all mathematicians accept it an axiom; what was a surprise is that Choice does not follow from ZF; it really has to be added as an extra axiom. Regards, A. Knight W Fu wrote: > The ZFC Axioms > For the record, we list the axioms of Zermelo-Frankel Set Theory. > Essentially all of mathematics can be derived from these axioms together > with a few logical deduction rules. > Extensionality. Two sets are equal if they have the same members. In > formal logical notation, this would be stated as: > (8z. (z 2 x ! z 2 y)) ?! x = y. > Pairing. For any two sets x and y, there is a set, {x, y}, with x and y as > its only elements. > Union. The union of a collection, z, of sets is also a set. > 9u8x. (9y. x 2 y ^ y 2 z) ! x 2 u. > Infinity. There is an infinite set; specifically, a nonempty set, x, such > that for any set y 2 x, the set {y} is also a member of x > Subset. Given any set, x, and any proposition P(y), there is a set containing > precisely those elements y 2 x for which P(y) holds. > Power Set. All the subsets of a set form another set. > Replacement. The image of a set under a function is a set. > Foundation. For every non-empty set, x, there is a set y 2 x such that > x and y are disjoint. (In particular, this axiom prevents a set from > being a member of itself.) > Choice. We can choose one element from each set in a collection of > nonempty sets. More precisely, if f is a function on a set, and > the result of applying f to any element in the set is always > a nonempty set, then there is a ?choice? function g such that > g(y) 2 y for every y in the set. > We?re not going to be working with the ZFC axioms in this course. We > just thought you might like to see them. > > - The above passage was quoted from page 5 > > I had read a few books that mention the axioms of set theory, and I have > actually not seen the ZFC Axioms so completely listed. I have studied the > axioms of choice in a topology class, and I was told that it was very > controversial in the math world. I never thought that it was one of the ZFC > axioms. From meyer@imap.theory.csail.mit.edu Wed Sep 14 21:47:32 2005 X-Coding-System: iso-8859-1-unix Mail-from: From knightfu@MIT.EDU Wed Sep 14 04:59:48 2005 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 j8E8xmaJ006073 for <6042-probs@theory.lcs.MIT.EDU>; Wed, 14 Sep 2005 04:59:48 -0400 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 j8E8xjDr015094 for <6042-probs@theory.lcs.MIT.EDU>; Wed, 14 Sep 2005 04:59:46 -0400 (EDT) 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 j8E8thku000659 for <6042-probs@theory.lcs.MIT.EDU>; Wed, 14 Sep 2005 04:55:44 -0400 (EDT) Received: (from nobody@localhost) by w92-130-webmail-5.mit.edu (8.12.4) id j8E8thcg030090; Wed, 14 Sep 2005 04:55:43 -0400 Received: from EASTCAMPUS-THREE-EIGHTY-FOUR.MIT.EDU (EASTCAMPUS-THREE-EIGHTY-FOUR.MIT.EDU [18.248.6.129]) (User authenticated as knightfu@ATHENA.MIT.EDU) by webmail.mit.edu (Horde MIME library) with HTTP for ; Wed, 14 Sep 2005 04:55:43 -0400 Message-ID: <20050914045543.6yddpubg7w0soo40@webmail.mit.edu> Date: Wed, 14 Sep 2005 04:55:43 -0400 From: Knight W Fu To: 6042-probs@theory.lcs.MIT.EDU Subject: Required Reading Comment 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.541 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO X-Status: A Content-Length: 1819 X-UID: 10 X-Keywords: NonJunk NotJunk The ZFC Axioms For the record, we list the axioms of Zermelo-Frankel Set Theory. Essentially all of mathematics can be derived from these axioms together with a few logical deduction rules. Extensionality. Two sets are equal if they have the same members. In formal logical notation, this would be stated as: (8z. (z 2 x ! z 2 y)) ?! x = y. Pairing. For any two sets x and y, there is a set, {x, y}, with x and y as its only elements. Union. The union of a collection, z, of sets is also a set. 9u8x. (9y. x 2 y ^ y 2 z) ! x 2 u. Infinity. There is an infinite set; specifically, a nonempty set, x, such that for any set y 2 x, the set {y} is also a member of x Subset. Given any set, x, and any proposition P(y), there is a set containing precisely those elements y 2 x for which P(y) holds. Power Set. All the subsets of a set form another set. Replacement. The image of a set under a function is a set. Foundation. For every non-empty set, x, there is a set y 2 x such that x and y are disjoint. (In particular, this axiom prevents a set from being a member of itself.) Choice. We can choose one element from each set in a collection of nonempty sets. More precisely, if f is a function on a set, and the result of applying f to any element in the set is always a nonempty set, then there is a ?choice? function g such that g(y) 2 y for every y in the set. We?re not going to be working with the ZFC axioms in this course. We just thought you might like to see them. - The above passage was quoted from page 5 I had read a few books that mention the axioms of set theory, and I have actually not seen the ZFC Axioms so completely listed. I have studied the axioms of choice in a topology class, and I was told that it was very controversial in the math world. I never thought that it was one of the ZFC axioms. From meyer@imap.theory.csail.mit.edu Fri Sep 16 00:38:35 2005 BCC: 6042-staff@theory.csail.mit.edu Message-ID: <432A4C53.7060001@csail.mit.edu> Date: Fri, 16 Sep 2005 00:38:43 -0400 From: "Prof. Albert R. Meyer" Reply-To: 6042-meyer <6042-meyer@theory.csail.mit.edu> Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Irene Zhang Subject: Re: question about pset References: <432A47E1.5050909@mit.edu> In-Reply-To: <432A47E1.5050909@mit.edu> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Content-Length: 515 Status: RO X-UID: 11 X-Keywords: the domain of f is A, and the codomain of f is the powerset of A. So what we know is that for each x in A, the value f(x) is a subset of A. (Technically, f(x) also might be undefined for certain x, since it's possible that f is not total. But it's ok to assume that f is total in this problem if that makes things clearer.) regards, A. Irene Zhang wrote: > In problem 4, could you explain the {x \in A | x \notin f(x)}? Would the > f(x) be the range of the function? or the codomain? > > Thanks, > Irene From meyer@imap.theory.csail.mit.edu Fri Sep 16 02:42:02 2005 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 j8G6g2aJ012224 for <6042-meyer@theory.csail.mit.edu>; Fri, 16 Sep 2005 02:42:02 -0400 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 j8G6g1e5002020 for <6042-meyer@theory.csail.mit.edu>; Fri, 16 Sep 2005 02:42:01 -0400 (EDT) Received: from [18.243.2.35] (GALVATRON.MIT.EDU [18.243.2.35]) (authenticated bits=0) (User authenticated as zev@ATHENA.MIT.EDU) by outgoing.mit.edu (8.13.1/8.12.4) with ESMTP id j8G6fr3s023796 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT) for <6042-meyer@theory.csail.mit.edu>; Fri, 16 Sep 2005 02:41:58 -0400 (EDT) Message-ID: <432A6931.6060902@mit.edu> Date: Fri, 16 Sep 2005 02:41:53 -0400 From: Zev Benjamin User-Agent: Debian Thunderbird 1.0.2 (X11/20050602) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-meyer <6042-meyer@theory.csail.mit.edu> Subject: Re: Week 2 Comments References: <4327D7E0.3050401@mit.edu> <432A471D.1070107@csail.mit.edu> In-Reply-To: <432A471D.1070107@csail.mit.edu> X-Enigmail-Version: 0.91.0.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam-Score: -2.099 X-Spam-Flag: NO X-Scanned-By: MIMEDefang 2.42 Status: RO Content-Length: 1086 X-UID: 12 X-Keywords: NotJunk -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Ah. I didn't see the lecture notes links on the calendar because I followed the week two lecture notes from the tutor and was confused when the week 1 tutor problem set linked to the week 2 lecture notes. Now that I found them, I'll review them. Thanks! Zev Prof. Albert R. Meyer wrote: > ZFC was introduced in Week 1 Notes, pp.4--5. Did you read them? > > Regards, A. > > Zev Benjamin wrote: > The most difficult section I found in the reading was 3.5 Functions > (page 11). The various terms and their definitions are rather > confusing. Section four mentions ZFC axioms without explaining what the > acronym expands to and without much pretext. It's odd that it jumps > into talking about proving mathematics without explaining what it is > talking about. > > > Zev -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) Comment: Using GnuPG with Thunderbird - http://enigmail.mozdev.org iD8DBQFDKmkwlO3j8HLL0+4RAo63AKDJtKGT4SLpmhwUu1ah3BzmH/K4fwCgmjVh o24n6i/JN4G73khrrdavuZU= =r4VZ -----END PGP SIGNATURE----- From meyer@imap.theory.csail.mit.edu Fri Sep 16 01:30:48 2005 Return-Path: Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.202]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id j8G5UlaJ031715 for <6042-meyer@theory.csail.mit.edu>; Fri, 16 Sep 2005 01:30:47 -0400 Received: by xproxy.gmail.com with SMTP id i28so139155wxd for <6042-meyer@theory.csail.mit.edu>; Thu, 15 Sep 2005 22:30:42 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=ErcU0bar4YzPbNVZRSZD1Uyd5T81WGmuaMPKLJm/K1htimHg71FWzehlg7KQzWr2zif3rzpmqsxwttYYxx/GNc32h3W3sOWI2BjQ/dJ4FOZaf/ixMEkowp2p7px6LYuk/GhgkSEW1didtIEhjzYYuh5j+Y9BpeD7S0uIK/1jFtw= Received: by 10.70.26.3 with SMTP id 3mr753wxz; Thu, 15 Sep 2005 22:30:42 -0700 (PDT) Received: by 10.70.9.14 with HTTP; Thu, 15 Sep 2005 22:30:42 -0700 (PDT) Message-ID: <4f2613e505091522304b587338@mail.gmail.com> Date: Fri, 16 Sep 2005 01:30:42 -0400 From: Zachary Adam Ozer Reply-To: Zachary Adam Ozer Sender: zacharyozer@gmail.com To: 6042-meyer <6042-meyer@theory.csail.mit.edu> Subject: Re: Email comment In-Reply-To: <432A4888.3090706@csail.mit.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline References: <4f2613e505091405417acd5051@mail.gmail.com> <432A4888.3090706@csail.mit.edu> Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by theory.csail.mit.edu id j8G5UlaJ031715 X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on theory.csail.mit.edu X-Spam-Level: X-Spam-Status: No, hits=-4.9 required=3.7 tests=BAYES_00 autolearn=ham version=2.63 Status: RO Content-Length: 856 X-UID: 13 X-Keywords: $Forwarded NotJunk Absolutely. I now understand why the statements are not equivalent. Thanks again for your help. -zozer On 9/16/05, Prof. Albert R. Meyer wrote: > did wed lecture and problems help you sort this out? If not, go to > TA's office hours and ask for more explanation. > > regards, A. > > Zachary Adam Ozer wrote: > > My confusion arises from the order of quantifiers section (2.4) of > > week 2 course notes. On page 6, the statement "Swapping quantifiers in > > Goldbach's Conjecture creates a patently false statement." I suppose > > that I don't understand why the statement which follows is indeed > > patently false. Indeed, in English one could say either "I will stand > > up every time I hear the bell" or "Every time I hear a bell I will > > stand up." The statements are equivalent, why not so in math? > > > > -zozer > > > From meyer@imap.theory.csail.mit.edu Fri Sep 16 12:04:51 2005 Message-ID: <432AED22.7070201@csail.mit.edu> Date: Fri, 16 Sep 2005 12:04:50 -0400 From: "Prof. Albert R. Meyer" Organization: MIT CSAIL User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: 6042-tas@theory.csail.mit.edu, Ronitt Rubinfeld Subject: [Fwd: Re: Email comment] Content-Type: multipart/mixed; boundary="------------040301010107080900080704" Status: RO Content-Length: 3235 X-UID: 14 X-Keywords: This is a multi-part message in MIME format. --------------040301010107080900080704 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit The kind of email reply I hope for. regards, A. --------------040301010107080900080704 Content-Type: message/rfc822; name="Re: Email comment" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="Re: Email comment" Return-Path: Received: from xproxy.gmail.com (xproxy.gmail.com [66.249.82.202]) by theory.csail.mit.edu (8.12.10/8.12.1) with ESMTP id j8G5UlaJ031715 for <6042-meyer@theory.csail.mit.edu>; Fri, 16 Sep 2005 01:30:47 -0400 Received: by xproxy.gmail.com with SMTP id i28so139155wxd for <6042-meyer@theory.csail.mit.edu>; Thu, 15 Sep 2005 22:30:42 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:reply-to:sender:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references; b=ErcU0bar4YzPbNVZRSZD1Uyd5T81WGmuaMPKLJm/K1htimHg71FWzehlg7KQzWr2zif3rzpmqsxwttYYxx/GNc32h3W3sOWI2BjQ/dJ4FOZaf/ixMEkowp2p7px6LYuk/GhgkSEW1didtIEhjzYYuh5j+Y9BpeD7S0uIK/1jFtw= Received: by 10.70.26.3 with SMTP id 3mr753wxz; Thu, 15 Sep 2005 22:30:42 -0700 (PDT) Received: by 10.70.9.14 with HTTP; Thu, 15 Sep 2005 22:30:42 -0700 (PDT) Message-ID: <4f2613e505091522304b587338@mail.gmail.com> Date: Fri, 16 Sep 2005 01:30:42 -0400 From: Zachary Adam Ozer Reply-To: Zachary Adam Ozer Sender: zacharyozer@gmail.com To: 6042-meyer <6042-meyer@theory.csail.mit.edu> Subject: Re: Email comment In-Reply-To: <432A4888.3090706@csail.mit.edu> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Disposition: inline References: <4f2613e505091405417acd5051@mail.gmail.com> <432A4888.3090706@csail.mit.edu> Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by theory.csail.mit.edu id j8G5UlaJ031715 X-Spam-Checker-Version: SpamAssassin 2.63 (2004-01-11) on theory.csail.mit.edu X-Spam-Level: X-Spam-Status: No, hits=-4.9 required=3.7 tests=BAYES_00 autolearn=ham version=2.63 X-UID: 816 X-Keywords: Absolutely. I now understand why the statements are not equivalent. Thanks again for your help. -zozer On 9/16/05, Prof. Albert R. Meyer wrote: > did wed lecture and problems help you sort this out? If not, go to > TA's office hours and ask for more explanation. > > regards, A. > > Zachary Adam Ozer wrote: > > My confusion arises from the order of quantifiers section (2.4) of > > week 2 course notes. On page 6, the statement "Swapping quantifiers in > > Goldbach's Conjecture creates a patently false statement." I suppose > > that I don't understand why the statement which follows is indeed > > patently false. Indeed, in English one could say either "I will stand > > up every time I hear the bell" or "Every time I hear a bell I will > > stand up." The statements are equivalent, why not so in math? > > > > -zozer > > > --------------040301010107080900080704--