《Mathematics for Computer》Lecture 1 Notes for Recitation

6.042/18.] Mathematics for Computer Science February 2, 2005 Srini devadas and Eric Lehman Notes for Recitation 1 logIc A proposition is a statement that is either true or false. Propositions can be joined by and","or","not"," implies", or"if and only if". For each of these connective, the defini- tion and notational shorthand are given in the table below. here a and b denote arbitrary repositions A and B A or B not A A implies B A if and only if B ABA∧BAVB-A A→B 今 T FIF TTF F F T F F FF F a predicate is a proposition whose truth depends on the value of one or more variables If P is a predicate then vx∈SP(x means that the predicate is true for every value of r in the set s. similarly x∈SP(x means that the predicate is true for at least one value of r in the set s

6.042/18.062J Mathematics for Computer Science February 2, 2005 Srini Devadas and Eric Lehman Notes for Recitation 1 1 Logic A proposition is a statement that is either true or false. Propositions can be joined by “and”, “or”, “not”, “implies”, or “if and only if”. For each of these connective, the defini￾tion and notational shorthand are given in the table below. Here A and B denote arbitrary propositions. A and B A or B not A A implies B A if and only if B A B T T A ∧ B A ∨ B ¬A A ⇒ B A ⇔ B T T F T T T F F T F F F F T F T T T F F F F F T T T A predicate is a proposition whose truth depends on the value of one or more variables. If P is a predicate, then ∀x ∈ S P(x) means that the predicate is true for every value of x in the set S. Similarly, ∃x ∈ S P(x) means that the predicate is true for at least one value of x in the set S

Recitation 1 Team Problem: A Mystery A certain cabal within the 6.042 course staff is plotting to make the final exam ridiculous hard.("Problem 1. Derive all of known mathematics from first principles. Express your answer in Mayan hieroglypics The only way to stop their evil plan is to determine exactly who is in the cabal. The course staff consists of seven people Eric, Srini, Christos, Grant, Ishan, Sally, Theory Pig 1 (Sallyis the course secretary and Theory Pig is our mascot. )The cabal is a subset of these seven. A membership roster has been found and appears below, but it is deviously en crypted in logic notation. The predicate C indicates who is in the cabal; that is, C(a true if and only if a is a member. Translate each statement below into English and deduce who is in the cabal (1)x3y3(x≠y∧x≠zy≠z∧C(x)AC(y)AC(2) Solution. a direct English paraphrase would be"There exist people we'll call a, y, and z, who are all different, such that y and z are each in the cabal. " a better version would use the fact that there's no need in this case to give names to the people. Namely, a better paraphrase is"There are 3 different people in the cabal. Perhaps a simpler way to say this is: The cabal is of size at least 3 (ii)-(C(Theory Pig )AC(Grant ) Solution. Theory Pig and Grant are not both in the cabal. Equivalently: at least one of Theory Pig and grant is not in the cabal Solution. If Sallyis in the cabal, then everyone is (iv)C(Grant)-C(Theory Pig Solution. If grant is in the cabal, then Theory pig is also (v)(C(Ishan )V C(Christos ))-+-C(Srini Solution. If either of Ishan or Christos is in the cabal, then Srini is not. Equivalently, if Srini is in the cabal, the neither Christos nor Ishan is (vi)(C(Ishan )V C(Theory Pig ))--C (Eric Solution. If either of Ishan or Theory Pig is in the cabal, then Eric is not. Equiva lently, if Eric is in the cabal, the neither Ishan nor Theory Pig is sitions above is one whose members are exactly Theory Pig, Ishan, and Christl. propo- o much for the translations. We now argue that the only cabal satisfying all six

� � � Recitation 1 2 Team Problem: A Mystery A certain cabal within the 6.042 course staff is plotting to make the final exam ridiculously hard. (“Problem 1. Derive all of known mathematics from first principles. Express your answer in Mayan hieroglypics.”) The only way to stop their evil plan is to determine exactly who is in the cabal. The course staff consists of seven people: {Eric , Srini , Christos , Grant ,Ishan , Sally, Theory Pig } (Sallyis the course secretary and Theory Pig is our mascot.) The cabal is a subset of these seven. A membership roster has been found and appears below, but it is deviously en￾crypted in logic notation. The predicate C indicates who is in the cabal; that is, C(x) is true if and only if x is a member. Translate each statement below into English and deduce who is in the cabal. (i) ∃x ∃y ∃z (x = y ∧ x = z ∧ y = z ∧ C(x) ∧ C(y) ∧ C(z)) Solution. A direct English paraphrase would be “There exist people we’ll call x, y, and z, who are all different, such that x, y and z are each in the cabal.” A better version would use the fact that there’s no need in this case to give names to the people. Namely, a better paraphrase is “There are 3 different people in the cabal.” Perhaps a simpler way to say this is: “The cabal is of size at least 3.” (ii) ¬(C(Theory Pig ) ∧ C(Grant )) Solution. Theory Pig and Grant are not both in the cabal. Equivalently: at least one of Theory Pig and Grant is not in the cabal. (iii) C(Sally) → ∀x C(x) Solution. If Sallyis in the cabal, then everyone is. (iv) C(Grant ) → C(Theory Pig ) Solution. If Grant is in the cabal, then Theory Pig is also. (v) (C(Ishan ) ∨ C(Christos )) → ¬C(Srini ) Solution. If either of Ishan or Christos is in the cabal, then Srini is not. Equivalently, if Srini is in the cabal, the neither Christos nor Ishan is. (vi) (C(Ishan ) ∨ C(Theory Pig )) → ¬C(Eric ) Solution. If either of Ishan or Theory Pig is in the cabal, then Eric is not. Equiva￾lently, if Eric is in the cabal, the neither Ishan nor Theory Pig is. So much for the translations. We now argue that the only cabal satisfying all six propo￾sitions above is one whose members are exactly Theory Pig , Ishan , and Christos

Recitation 1 We first observe that by (i), there must be someone -either Theory Pig or Grant-who is not in the cabal. But if Flo were in the cabal, then by(iii), everyone would be. So we conclude by contradiction that: Sallyis not in the cabal contradicting(ii). So by again contradiction, we conclude v), Theory Pig would be too, Next observe that if grant was in the cabal, then by (iv Grant is not in the cabal Now suppose Srini is in the cabal. Then by (v), Ishan and Christos are not, and w already know Sallyand Grant are not, so only three remain who could be in the cabal namely, Srini, Theory Pig, and Eric. But by (i)the cabal must have at least three mem- bers, so it follows that the cabal must consist of exactly these three. This proves Lemma 1. If Srini is in the cabal, then Theory Pig and Eric are in the cabal But by (vi), if Theory Pig is the cabal, then Eric is not. That is, Lemma 2. Theory Pig and eric cannot both be in the cabal Now from Lemma 2 we conclude that the conclusion of Lemma l is false. So by con- trapositive, the hypothesis of Lemma 1 must also be false, namely, Srini is not in the cabal Finally, suppose Eric is in the cabal. Then by(vi), Ishan and Theory Pig are not, and we already know Sally, Grant and Srini are not. So the cabel must consist of at most two people( Christos and Eric ) This contradicts (i), and we conclude by contradiction that Eric is not in the cabal o the only remaining people who could be in the cabal are Christos, Ishan, and Theory Pig ince the cabal must have at least three members we conclude that Lemma 3. The only possible cabal consists of Christos, Ishan, and Theory Pig But were not done yet: we havent shown that a cabal consisting of Christos, Ishan ind Theory Pig actually does satisfy all six conditions. So let A= Christos, Ishan, Theory Pig and let's quickly check that A satisfies (i)-(vi) .A=3, so A satisfies(i) grant is not in A, so A satisfies(ii)and (iv)

Recitation 1 3 We first observe that by (ii), there must be someone – either Theory Pig or Grant – who is not in the cabal. But if Flo were in the cabal, then by (iii), everyone would be. So we conclude by contradiction that: Sallyis not in the cabal. (1) Next observe that if Grant was in the cabal, then by (iv), Theory Pig would be too, contradicting (ii). So by again contradiction, we conclude: Grant is not in the cabal. (2) Now suppose Srini is in the cabal. Then by (v), Ishan and Christos are not, and we already know Sallyand Grant are not, so only three remain who could be in the cabal, namely, Srini , Theory Pig , and Eric . But by (i) the cabal must have at least three mem￾bers, so it follows that the cabal must consist of exactly these three. This proves: Lemma 1. If Srini is in the cabal, then Theory Pig and Eric are in the cabal. But by (vi), if Theory Pig is the cabal, then Eric is not. That is, Lemma 2. Theory Pig and Eric cannot both be in the cabal. Now from Lemma 2 we conclude that the conclusion of Lemma 1 is false. So by con￾trapositive, the hypothesis of Lemma 1 must also be false, namely, Srini is not in the cabal. (3) Finally, suppose Eric is in the cabal. Then by (vi), Ishan and Theory Pig are not, and we already know Sally, Grant and Srini are not. So the cabel must consist of at most two people (Christos and Eric ). This contradicts (i), and we conclude by contradiction that Eric is not in the cabal. (4) So the only remaining people who could be in the cabal are Christos , Ishan , and Theory Pig . Since the cabal must have at least three members, we conclude that Lemma 3. The only possible cabal consists of Christos , Ishan , and Theory Pig . But we’re not done yet: we haven’t shown that a cabal consisting of Christos , Ishan , and Theory Pig actually does satisfy all six conditions. So let A = {Christos , Ishan , Theory Pig }, and let’s quickly check that A satisfies (i)–(vi): • |A| = 3, so A satisfies (i). • Grant is not in A, so A satisfies (ii) and (iv)

Recitation 1 Sallyis not in A, so the hypothesis of (iii)is false, which means that A satisfies(iii) Finally, Srini and Eric are not in A, so the conclusions of both(v) and (vi) are true and so A satisfies(v) and(vi) o now we have pro Proposition. Christos, Ishan, Theory Pig) is the unique cabal satisfying conditions(i)-(vi)

Recitation 1 4 • Sallyis not in A, so the hypothesis of (iii) is false, which means that A satisfies (iii). • Finally, Srini and Eric are not in A, so the conclusions of both (v) and (vi) are true, and so A satisfies (v) and (vi). So now we have proved Proposition. {Christos , Ishan , Theory Pig } is the unique cabal satisfying conditions (i)–(vi)

Recitation 1 Team Problem: Swapping Quantifiers Suppose P is predicate that depends on two variables that take on values in the set s Here are two propositions wx∈Sy∈SP(x,y)→(y∈Svr∈sP(x,y) (y∈svr∈SP(x,y)→(w∈S∈SP(x,y) (a) give an example of a predicate P and set S that makes one of these propositions false. The set S can be anything you choose: colors, animals, food, people, etc. Solution. Let S be the set of all people who have ever lived, and let P(r, y) be the proposition that" the mother of person z is person y Then the left side of the first proposition is true; every person has a mother. How- ever, the right side is not true; there is not a single person who is everyones mother Thus, the first proposition as a whole is false (b) Explain why the other proposition is always true Solution. The left side of the second proposition asserts that there exists a y- call it yo-such that P(a, y) is true regardless of the value of z. This implies that the right side of the proposition is also true; for every a there exists a y(namely, yo)such that P(, y) is true

Recitation 1 5 Team Problem: Swapping Quantifiers Suppose P is predicate that depends on two variables that take on values in the set S. Here are two propositions: (∀x ∈ S ∃y ∈ S P(x, y)) ⇒ (∃y ∈ S ∀x ∈ S P(x, y)) (1) (∃y ∈ S ∀x ∈ S P(x, y)) ⇒ (∀x ∈ S ∃y ∈ S P(x, y)) (2) (a) Give an example of a predicate P and set S that makes one of these propositions false. (The set S can be anything you choose: colors, animals, food, people, etc.). Solution. Let S be the set of all people who have ever lived, and let P(x, y) be the proposition that “the mother of person x is person y”. Then the left side of the first proposition is true; every person has a mother. How￾ever, the right side is not true; there is not a single person who is everyone’s mother. Thus, the first proposition as a whole is false. (b) Explain why the other proposition is always true. Solution. The left side of the second proposition asserts that there exists a y— call it y0— such that P(x, y) is true regardless of the value of x. This implies that the right side of the proposition is also true; for every x there exists a y (namely, y0) such that P(x, y) is true