Proofs Homework Set 1

Proofs Homework Set 1 W INTER 2011 Logical Connectives. Every mathematical statement is either true or false. Starting from given mathematical statements, we can use logical operations to form new mathematical statements which are again either true or false. Let P and Q be two statements. Here are the four basic logical constructions: • The statement “P and Q” is true if both P and Q are true statements. • The statement “P or Q” is true if at least one of P or Q is true. • The statement “if P then Q” is true if both P and Q are true, or if P is false. The shorthand notation for “if P then Q” is P =⇒ Q. • The statement “P if and only if Q” is true whenever both P =⇒ Q and Q =⇒ P are true statements. The shorthand notation for “P if and only if Q” is P ⇐⇒ Q. P ROBLEM 1.1. Decide whether the following statements are true or false. Justify your answers. (a) If 9 > 5, then pigs don’t fly. Answer. True; the statements “9 > 5” and “pigs don’t fly” are both true. (b) If x > 0 and x2 < 0, then x ≤ −1. Answer. True; the statement “x2 < 0” is false, hence so is “x > 0 and x2 < 0.” (c) If x > 0, then x2 < 0 or x3 > 0. Answer. True. Since “x2 < 0 is false, the statement “x2 < 0 or x3 > 0” is true precisely when “x > 0” is true. (d) If 1 = 2, then Modern Family is the best sitcom on television. Answer. True; the statement “1 = 2” is false. (e) x > 0 if and only if 2x > 0. Answer. True. The statements “x > 0 =⇒ 2x > 0” and “2x > 0 =⇒ x > 0” are both true. (f) Chickens have feathers if and only if 2 is not an integer. Answer. False. Since “chickens have feathers” is true and “2 is not an integer” is false, the statement “if chickens have feathers then 2 is not an integer” is false. Negation. A negation of a statement P is a statement that is true whenever P is false and false whenever P is true. The negation of P is denoted “not P .” For example, the negation of the statement “If it is raining, then it is cloudy” is the statement “It is raining, and it is not cloudy.” These statements can never be true simultaneously. P ROBLEM 1.2. Formulate the negation of each of the statements below. (a) The set S contains at least two integers. Answer. A negation is “the set S contains at most one integer.” (b) I wear glasses, or I can’t read the chalkboard. Answer. A negation is “I don’t wear glasses and I can read the chalkboard.” Consider the following table of possible combinations: wear glasses can read chalkboard don’t wear glasses can read chalkboard wear glasses can’t read chalkboard don’t wear glasses can’t read chalkboard The original statement covers the first, third and fourth lines (that is, at least one of “I wear glasses” and “I can’t read the chalkboard” is true). Therefore the negation is the second line. (c) I like cats and I dislike dogs. Answer. A negation is “I dislike cats or I like dogs.” cats like like dislike dislike dogs like dislike like dislike The original statement covers only the second option, so its negation should cover the other three options. (d) If you study hard, then you will do well in this class. Answer. A negation is “you study hard and you won’t do well in this class.” (e) There is a student in class who will fail. Answer. A negation is “every student in class will pass.” (f) For every problem there is a solution. Answer. A negation is “there is a problem with no solution.” (g) There is a real number which is larger than every rational number. Answer. A negation is “no real number is larger than every rational number.” Converse and Contrapositive. There are two additional logical statements that can be formed from a given “if-then” statement: • The converse of the statement P =⇒ Q is the statement Q =⇒ P . The converse may be true or false, independent of the truth value of the original “if-then” statement. Why? Answer. Compare the truth tables for both statements: P Q P =⇒ Q Q =⇒ P T T T T T F F T F T T F F F T T The last two columns do not coincide. • The contrapositive of the statement P =⇒ Q is the statement not Q =⇒ not P . The original “if-then” statement and its contrapositive have the same truth value. Why? Answer. Compare the truth tables for both statements: P Q P =⇒ Q not Q not P not Q =⇒ not P T T T F F T T F F T F F F T T F T T F F T T T T The columns corresponding to P =⇒ Q and not Q =⇒ not P coincide. P ROBLEM 1.3. statements. Write both the converse and the contrapositive of the following four “if-then” (a) If 9 > 5, then pigs don’t fly. Answer. Converse: If pigs don’t fly, then 9 > 5. Contrapositive: If pigs fly, then 9 ≤ 5. (b) If x > 0 and x2 < 0, then x ≤ −1. Answer. Converse: If x ≤ −1, then x > 0 or x2 < 0. Contrapositive: If x > −1, then x ≤ 0 and x2 ≥ 0. (c) If x > 0, then x2 < 0 or x3 > 0. Answer. Converse: If x2 < 0 or x3 > 0, then x > 0. Contrapositive: If x2 ≥ 0 and x3 ≤ 0, then x ≤ 0. (d) If 1 = 2, then Modern Family is the best sitcom on television. Answer. Converse: If Modern Family is the best sitcom on television, then 1 = 2. Contrapositive: If Modern Family is not the best sitcom on television., then 1 6= 2. Sets. A set is a container with no distinguishing feature other than its contents. The objects contained in a set are called the elements of the set. We write a ∈ S to signify that the object a is an element of the set S. Since a set has no distinguishing feature other than its contents, there is a unique set containing no elements which is called the empty set and is denoted ∅. Some other very common sets are the set R of all real numbers, the set Q of all rational numbers, the set Z of all integers, and the set C of all complex numbers (which we will properly define later in the course). There are two important ways to specify a set. • Enumeration. One can list the contents of the set, in which case the set is denoted by enclosing the list in curly braces. For example, Z = {. . . , −2, −1, 0, 1, 2, . . .}. • Comprehension. One can describe the contents of the set by a property of its elements. If P (a) is a property of the object a, then the set of all objects a such that P (a) is true is denoted by {a | P (a)}. For example, Q = { ab | a, b ∈ Z and b 6= 0}. Let X and S be sets. We say that S is a subset of X if a ∈ S =⇒ a ∈ X holds for all objects a. We write S ⊆ X to signify that S is a subset of X. This means that S is a set consisting of some or all of the elements in X. The subset of X consisting of all elements a of X such that property P (a) holds true is denoted {a ∈ X | P (a)}. Starting from given sets, we can use set operations to form new sets. • Given sets X and Y , the intersection of X and Y is defined as X ∩ Y = {a | a ∈ X and a ∈ Y } . • Given sets X and Y , the union of X and Y is defined as X ∪ Y = {a | a ∈ X or a ∈ Y } . P ROBLEM 1.4. (a) Use set comprehension notation to define the half-open interval [a, b) in the real numbers. Answer. {x ∈ R | a ≤ x < b}. (b) Find a common English description for the following set: {a ∈ Z | a = 2k + 1 for some k ∈ Z}. Answer. The set of odd numbers. (c) Let X = {1, 2, 3, 4}. How many subsets does X have? Answer. 16. To define a subset of X we need to specify which elements are in that subset. For each element of X there are two options: either it is in that subset or it is not. Hence we have 24 = 16 subsets. (d) Is it true that all elements of the empty set are whistling, flying purple cows? Answer. Yes! There are no elements in the empty set, hence they vacuously satisfy any property. (e) Let X = {x ∈ R | −2 < x < 4} and Y = {y ∈ R | y = 2k for some k ∈ Z}. Use set comprehension notation to describe the sets X ∩ Y and X ∪ Y . Answer. X is the interval (−2, 4); Y is the set of even numbers. X ∩ Y is the set of all even numbers in the interval (−2, 4), i.e. X ∩ Y = {0, 2}. X ∪ Y = {x ∈ R | −2 < x < 4 or x = 2k for some k ∈ Z}. (f) Let A be the xz-plane in R3 and B be the yz-plane in R3 . Use set comprehension notation to describe the sets A ∩ B and A ∪ B.          x  x Answer. A = y  ∈ R3 | y = 0 and B = y  ∈ R3 | x = 0 .     z z Hence     x  A ∩ B = y  ∈ R3 | y = 0 and x = 0 ,   z and     x  A ∪ B = y  ∈ R3 | y = 0 or x = 0 .   z (g) Which of the following statements are true? (Justify your responses.) (i) ∅ ∈ ∅. Answer. False; there are no elements in the empty set. (ii) ∅ ⊆ {∅}. Answer. True; every set has the empty set as a subset. (iii) ∅ ∈ {∅}. Answer. True; {∅} is a set with one element: the empty set. So the empty set is an element of {∅}. (iv) {∅} ⊆ {∅, {∅}}. Answer. True; {∅, {∅}} has two elements ∅ and {∅}. Its subset, containing only the first of them, is {∅}. Quantifiers. Starting from a statement which involves a variable, we can form a new statement by quantifying the given variable. • The quantifier “for all” indicates that something is true about every element in a given set and is denoted ∀. For example, the truth value of the statement x2 > 0 depends on the value of x. So the quantified statement “∀ x ∈ R, x2 > 0” is false, since it fails for x = 0. • The quantifier “there exists” indicates that something is true for at least one element in a given set and is denoted ∃. For example, the truth value of the statement x2 = 0 depends on the value of x. So the quantified statement “∃ x ∈ R s.t. x2 = 0” is true, since it holds for x = 0. P ROBLEM 1.5. necessary. For (a)–(d), decide whether the given statement is true or false. No justification (a) ∀ x ∈ R, ∀ y ∈ R, we have x2 + y 2 ≥ 2xy. Answer. True. (b) ∀ x ∈ R, ∃ y ∈ Z such that y > x. Answer. True. (c) ∃ x ∈ R s.t. ∀ y ∈ Z, y > x. Answer. False. (d) x ∈ { ab | a, b ∈ Z} =⇒ x ∈ Q. Answer. False; “fractions” of the form a 0 are not rational numbers. (e) Write the following statement using symbols and quantifiers: there is a set containing all rational numbers. Answer. ∃ a set S s.t. ∀x ∈ Q, x ∈ S. (f) Write the following statement using symbols and quantifiers: every real number is two times a real number. Answer. ∀x ∈ R, ∃y ∈ R s.t. x = 2y. (g) Write the negation of part (b). Answer. ∃x ∈ R s.t. ∀y ∈ Z, y ≤ x. (h) Write the negation of part (c). Answer. ∀x ∈ R, ∃y ∈ Z s.t. y ≤ x. (i) Write the converse and contrapositive of part (d). Answer. Converse: x 6∈ { ab | a, b 6∈ Z} =⇒ x ∈ Q. Contrapositive: x 6∈ Q =⇒ x 6∈ { ab | a, b ∈ Z}. B ONUS P ROBLEM . Let X, Y, Z be sets. Prove that (X ∩ Y ) ∪ Z = (X ∪ Z) ∩ (Y ∪ Z). Hint. You can prove that two sets A and B are equal by showing that both A ⊆ B (that is, if x ∈ A then x ∈ B) and B ⊆ A (that is, if x ∈ B then x ∈ A). Proof. Let A = (X ∩ Y ) ∪ Z and B = (X ∪ Z) ∩ (Y ∪ Z). • Let’s prove that A ⊆ B, i.e. every element of A is an element of B. If a ∈ A, then a ∈ X ∩ Y or a ∈ Z. Suppose a ∈ X ∩ Y . Then a is in both X and Y and hence in both X ∪ Z and Y ∪ Z. This means that a ∈ B. Suppose a ∈ Z. Then a is in both X ∪ Z and Y ∪ Z and hence in B. • Let’s prove that B ⊆ A, i.e. every element of B is an element of A. If b ∈ B, then b is in both X ∪ Z and Y ∪ Z. This means that either b ∈ Z, or b is in X but not Z AND in Y but not Z. Suppose b ∈ Z, then b ∈ A = (X ∩ Y ) ∪ Z. Suppose b is in X but not Z AND in Y but not Z. Then b ∈ X ∩ Y and hence in A. We have shown that A ⊆ B and B ⊆ A, hence A = B.