Logic, Sets, and Proofs

Logic, Sets, and Proofs 1 Logic Logical Statements. A logical statement is a mathematical statement that is either true or false. Here we denote logical statements with capital letters A, B. Logical statements be combined to form new logical statements as follows: Name Conjunction Disjunction Negation Implication Equivalence Notation A and B A or B not A ¬A A implies B if A, then B A⇒B A if and only if B A⇔B Here are some examples of conjunction, disjunction and negation: x > 1 and x < 3: This is true when x is in the open interval (1, 3). x > 1 or x < 3: This is true for all real numbers x. ¬(x > 1): This is the same as x ≤ 1. Here are two logical statements that are true: x > 4 ⇒ x > 2. x2 = 1 ⇔ (x = 1 or x = −1). Note that “x = 1 or x = −1” is usually written x = ±1. Converses, Contrapositives, and Tautologies. We begin with converses and contrapositives: • The converse of “A implies B” is “B implies A”. • The contrapositive of “A implies B” is “¬B implies ¬A” Thus the statement “x > 4 ⇒ x > 2” has: • Converse: x > 2 ⇒ x > 4. • Contrapositive: x ≤ 2 ⇒ x ≤ 4. Some logical statements are guaranteed to always be true. These are tautologies. Here are two tautologies that involve converses and contrapositives: • (A if and only if B) ⇔ ((A implies B) and (B implies A)). In other words, A and B are equivalent exactly when both A ⇒ B and its converse are true. • (A implies B) ⇔ (¬B implies ¬A). In other words, an implication is always equivalent to its contrapositive. This is important to know. There are many other tautologies. Some are pretty obvious, such as (A or B) ⇔ (B or A) (similarly for “and”), while others take a bit of thought, such as the following: Statement A or (B and C) Equivalent statement (A or B) and (A or C) Description “or” distributes over “and” A and (B or C) (A and B) or (A and C) “and” distributes over “or” ¬(A or B) ¬A and ¬B De Morgan’s law for “or” ¬(A and B) ¬A or ¬B De Morgan’s law for “and” A ⇒ (B ⇒ C) (A and B) ⇒ C conditional proof In a course that discusses mathematical logic, one uses truth tables to prove the above tautologies. 2 Sets A set is a collection of objects, which are called elements or members of the set. Two sets are equal when they have the same elements. Common Sets. Here are some important sets: • The set of all integers is Z = {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}. • The set of all real numbers is R. • The set of all complex numbers is C. • The set with no elements is ∅, the empty set. Another important set is the set of natural numbers, denoted N. In our book, N = {1, 2, 3, . . .}, However, you should be aware that in some other books, N = {0, 1, 2, 3, . . .}. Basic Definitions and Notation about Sets. • x ∈ S: x is an element or member of S. Example: 2 ∈ Z. • x∈ / S: x is not an element of S, i.e., ¬(x ∈ S). Example: 1 2 ∈ / Z. • S ⊆ T : Every element of S is also an element of T . We say that S is a subset of T and that T contains or includes S. Examples: Z ⊆ R ⊆ C and Z ⊆ Z. • S 6⊆ T : This means ¬(S ⊆ T ), i.e., some element of S is not an element of T . Example: R 6⊆ Z. • S ⊂ T : This means S ⊆ T and S 6= T . We say that S is a proper subset of T and that T properly contains or properly includes S. Example: Z ⊂ R. Note that S = T is equivalent to S ⊆ T and T ⊆ S. Describing Sets. There are two basic ways to describe a set. • Listing elements: Some sets can be described by listing their elements inside brackets { and }. Example: The set of positive squares is {1, 4, 9, 16, . . .}. When listing the elements of a set, order is unimportant, as are repetitions. Thus {1, 2, 3} = {3, 2, 1} = {1, 1, 2, 3}, since all three contain the same elements, namely 1, 2 and 3. • Set-builder notation: We can sometimes describe a set by the conditions its elements satisfy. Example: The set of positive real numbers is {x ∈ R | x > 0}. This can also be written {x | x ∈ R and x > 0}. We read “|” as “such that”. Operations on Sets. Let S and T be sets. • The union S ∪ T is the set S ∪ T = {x | x ∈ S or x ∈ T }. Thus an element lies in S ∪ T precisely when it lies in at least one of the sets. Examples: {1, 2, 3, 4} ∪ {3, 4, 5, 6} = {1, 2, 3, 4, 5, 6} {n ∈ Z | n ≥ 0} ∪ {n ∈ Z | n < 0} = Z. • The intersection S ∩ T is the set S ∩ T = {x | x ∈ S and x ∈ T }. Thus an element lies in S ∩T precisely when it lies in both of the sets. Examples: {1, 2, 3, 4} ∩ {3, 4, 5, 6} = {3, 4} {n ∈ Z | n ≥ 0} ∩ {n ∈ Z | n < 0} = ∅. • The set difference S − T is the set of elements that are in S but not in T . Example: {1, 2, 3, 4} − {3, 4, 5, 6} = {1, 2}. A common alternative notation for S − T is S \ T . 3 Variables and Quantifiers Often we are working with elements of a fixed set. In calculus, this fixed set is often the real numbers R or an interval [a, b] ⊆ R. In linear algebra, the fixed set is often Rn , Cn or an abstract vector space V (all of these terms will eventually be defined). In the discussion that follows, this fixed set will be denoted U . A variable such as x represents some unspecified element from the fixed set U . Example: If Z is the fixed set, then “x is even” is a statement that involves the variable x, and “x > y” involves x and y. When a logical statement contains one or more variables, then the truth of the statement depends on which particular members of the fixed set are plugged in for the variables. We combine quantifiers with statements involving variables to form statements about members of the fixed set U . If P (x) is a statement depending on the variable x from the fixed set U , then there are two basic types of quantifiers: • ∀x ∈ U (P (x)). This universal quantifier means that for all (or for every or for each or for any) value of x in U , P (x) is true. Example: ∀x ∈ R (2x = (x + 1) + (x − 1)). • ∃x ∈ U (P (x)). This existential quantifier means that there exists a (or there is at least one) value of x in U for which P (x) is true. Example: ∃x ∈ Z (x > 5). If the fixed set U is understood, it may be omitted from the quantifier. For example, assuming that the fixed set is Z, then the above statement can be written more simply as ∃x (x > 5). A general strategy for proving things about statements with quantifiers is to work one element at a time. Even when we are dealing with universal quantifiers and infinite fixed sets, we proceed by thinking about the properties that a particular but arbitrary element of the fixed set would have. Statements with Variables and Sets. A statement depending on a variable, such as P (x), is often used to describe a set in terms of the set-builder notation S = {x ∈ U | P (x)}. This means that the set S consists of all elements x of the fixed set for which the statement P (x) is true. Example: The definition S = {n ∈ Z | n > 5} means n ∈ S if and only if n is an integer greater than 5. If the fixed set is assumed to be Z, it can be left out of the definition, so that S = {n | n > 5}. We can recast set inclusions using quantifiers. Thus S⊆T is equivalent to is equivalent to ∀x (x ∈ S ⇒ x ∈ T ) ∀x ∈ S (x ∈ T ) As a general rule, we prove things about sets by working with the statements that define them. We will see later that the equivalences for S ⊆ T lead to a useful proof strategy. As with the case of quantifiers and statements, proving S ⊆ T means working with one element at a time. Negations of Quantifiers. It is important to understand how negation interacts with quantifiers. Here are the basic rules. • ¬∀x P (x) is equivalent to ∃x (¬P (x)). • ¬∃x P (x) is equivalent to ∀x (¬P (x)). Example: For the fixed set is R, we can understand ¬∀x (x > 0) as follows: ¬∀x (x > 0) is equivalent to is equivalent to ∃x (¬(x > 0)) ∃x (x ≤ 0). The last statement is clearly true (take x = −1, for example), hence our original statement is true. 4 Proof Strategies A proof starts with a list of hypotheses and ends with a conclusion. The proof shows the step-by-step chain of reasoning from hypotheses to conclusion. Every step needs to be justified. You can use any of the reasons below to justify a step in your proof: • A hypothesis. • A definition. • Something already proved earlier in the proof. • A result proved previously. • A consequence of earlier steps according to the rules of logic. Be sure to proceed one step at a time. Writing a good proof requires knowing definitions and previously proved results, understanding how the notation and the logic works, and having a bit of insight. It also helps to be familiar with some common strategies for different types of proofs. Direct Proof. The simplest way to prove A ⇒ B is to assume A (the “hypothesis”) and prove B (the “conclusion”). See Proof 2 in Section 5 for a direct proof of n is even ⇒ n2 is even. Proof by Contradiction. One way to prove A ⇒ B is to assume that A is true and B is false. In other words, you assume that the hypothesis is true but the conclusion is false. Then you try to derive a contradiction. See Proof 2 is Section 5 for a proof by contradiction of n2 is even ⇒ n is even. Proof by Contrapositive. A closely related strategy to prove A ⇒ B is to instead prove its contrapositive ¬B ⇒ ¬A. Hence the stategy is to assume that B is false and prove that this implies that A is also false. Proof Strategies for Quantifiers. Here is a list of strategies for proving the truth of quantified statements. • ∃x ∈ U (P (x)). Give an example value of the variable x that makes P (x) true. Example: To prove ∃x (x > 12), you can simply indicate that setting x = 14 makes x > 12 true. • ∀x ∈ U (P (x)). Assume (as a hypothesis) that x has the properties of the fixed set, but don’t assume anything more about it. Show as a conclusion that the statement must be true for that (arbitrary) value of x. • If you have a statement of the form ∀x (P (x) or Q(x)) or ∃x (P (x) or Q(x)), then you can rewrite the statement P (x) or Q(x) using any logical tautology. The same is true if “or” is replaced by “and”, “implies” or ”if and only if”. Example: By the contrapositive tautology, proving ∀x (x ≥ 1 ⇒ x2 ≥ 1) is equivalent to proving ∀x (x2 < 1 ⇒ x < 1). Proof Strategies for Sets. • (Membership) Strategy to prove x ∈ S: Show that x has the properties that define membership in S. • (Inclusion) Strategy to prove S is a subset of T , i.e., S ⊆ T : Take an arbitary element x of S. That is, x represents any specific member of S; you can assume x has the properties that define S, but you can’t assume anything more about it. Then show that x must also be an element of T using the membership strategy described above. Remember that you can assume that x satisfies the defining properties of S. • (Equality) Strategy to prove S equals T , i.e., S = T : First prove that S ⊆ T . Then prove that T ⊆ S. 5 Sample Proofs Here we give two simple proofs to illustrate various proof strategies. Proof 1. Let A, B, C be sets. Prove the distribution law for ∪ over ∩, which states A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Proof. The proof has two parts because we want to prove two sets are equal. To prove A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C), take x ∈ A ∪ (B ∩ C). Then we have a series of implications: x ∈ A ∪ (B ∩ C ) implies implies implies implies implies x ∈ A or x ∈ B ∩ C Def ∪ x ∈ A or (x ∈ B and x ∈ C ) Def ∩ (x ∈ A or x ∈ B) and (x ∈ A or x ∈ C ) Dist x ∈ A ∪ B and x ∈ A ∪ C Def ∪ x ∈ (A ∪ B) ∩ (A ∪ C ) Def ∩. This shows that A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C). For the opposite inclusion (A∪B)∩(A∪C) ⊆ A∪(B∩C), take x ∈ (A∪B)∩(A∪C). The implications in the first part of the proof are reversible, so that x ∈ A ∪ (B ∩ C). This proves (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C ), and equality follows. QED Proof 2. Prove that ∀n ∈ Z (n is even ⇔ n2 is even). Proof. Fix an arbitrary n ∈ Z. Then we need to prove that n is even ⇔ n2 is even. The proof has two parts because we want to prove an equivalence. Proof that n is even ⇒ n2 is even: Take n ∈ Z and assume n is even. By the definition of even, this means n = 2m for some m ∈ Z. Then n2 = (2m)2 = (2m)(2m) = 2(2m2 ), which shows that n2 is even. Proof that n2 is even ⇒ n is even: Now take n ∈ Z and assume n2 is even. We prove that n is even by contradiction. So assume n is not even, i.e., n is odd. This means n = 2m + 1 for some m ∈ Z. Then n2 = (2m + 1)2 = (2m + 1)(2m + 1) = 4m2 + 4m + 1 = 2(2m2 + 2m) + 1, which shows that n2 is odd. This contradicts our assumption that n2 is even, and it follows that n must be even. QED