Logic Sets

Proofs Homework Set 1 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. (b) If x > 0 and x2 < 0, then x ≤ −1. (c) If x > 0, then x2 < 0 or x3 > 0. (d) If 1 = 2, then Modern Family is the best sitcom on television. (e) x > 0 if and only if 2x > 0. (f) Chickens have feathers if and only if 2 is not an integer. 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. (b) I wear glasses, or I can’t read the chalkboard. (c) I like cats and I dislike dogs. (d) If you study hard, then you will do well in this class. (e) There is a student in class who will fail. (f) For every problem there is a solution. (g) There is a real number which 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? • 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? 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. (b) If x > 0 and x2 < 0, then x ≤ −1. (c) If x > 0, then x2 < 0 or x3 > 0. (d) If 1 = 2, then Modern Family is the best sitcom on television. 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. (b) Find a common English description for the following set: {a ∈ Z | a = 2k + 1 for some k ∈ Z}. (c) Let X = {1, 2, 3, 4}. How many subsets does X have? (d) Is it true that all elements of the empty set are whistling, flying purple cows? (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 . (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. (g) Which of the following statements are true? (Justify your responses.) (i) ∅ ∈ ∅. (ii) ∅ ⊆ {∅}. (iii) ∅ ∈ {∅}. (iv) {∅} ⊆ {∅, {∅}}. 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. (b) ∀ x ∈ R, ∃ y ∈ Z such that y > x. (c) ∃ x ∈ R s.t. ∀ y ∈ Z, y > x. (d) x ∈ { ab | a, b ∈ Z} =⇒ x ∈ Q. (e) Write the following statement using symbols and quantifiers: there is a set containing all rational numbers. (f) Write the following statement using symbols and quantifiers: every real number is two times a real number. (g) Write the negation of part (b). (h) Write the negation of part (c). (i) Write the converse and contrapositive of part (d). 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).