Mathematics for Natural Sciences PDF

MINISTRY OF SCIENCE AND HIGHER EDUCATION ashkas Mathematics for Natural Sciences Prepared by: 1. Ato Arbsie Yasin 2. Dr. Berhanu Bekele 3. Dr. Berhanu Guta 4. Ato Wondwosen Zemene MOSHE SEPTEMBER, 2019 ...

MINISTRY OF SCIENCE AND HIGHER EDUCATION ashkas Mathematics for Natural Sciences Prepared by: 1. Ato Arbsie Yasin 2. Dr. Berhanu Bekele 3. Dr. Berhanu Guta 4. Ato Wondwosen Zemene MOSHE SEPTEMBER, 2019  Chapter One Propositional Logic and Set Theory In this chapter, we study the basic concepts of propositional logic and some part of set theory. In the first part, we deal about propositional logic, logical connectives, quantifiers and arguments. In the second part, we turn our attention to set theory and discus about description of sets and operations of sets. Main Objectives of this Chapter At the end of this chapter, students will be able to:-  Know the basic concepts of mathematical logic.  Know methods and procedures in combining the validity of statements.  Understand the concept of quantifiers.  Know basic facts about argument and validity.  Understand the concept of set.  Apply rules of operations on sets to find the result.  Show set operations using Venn diagrams. 1.1. Propositional Logic Mathematical or symbolic logic is an analytical theory of the art of reasoning whose goal is to systematize and codify principles of valid reasoning. It has emerged from a study of the use of language in argument and persuasion and is based on the identification and examination of those parts of language which are essential for these purposes. It is formal in the sense that it lacks reference to meaning. Thereby it achieves versatility: it may be used to judge the correctness of a chain of reasoning (in particular, a "mathematical proof") solely on the basis of the form (and not the content) of the sequence of statements which make up the chain. There is a variety of symbolic logics. We shall be concerned only with that one which encompasses most of the deductions of the sort encountered in mathematics. Within the context of logic itself, this is "classical" symbolic logic. Section objectives: After completing this section, students will be able to:-  Identify the difference between proposition and sentence.  Describe the five logical connectives.  Determine the truth values of propositions using the rules of logical connectives. 1   Construct compound propositions using the five logical connectives.  Determine the truth values of compound propositions.  Distinguish a given compound proposition is whether tautology or contradiction. 1.1.1. Definition and examples of propositions Consider the following sentences. a. 2 is an even number. b. A triangle has four sides. c. Emperor Menelik ate chicken soup the night after the battle of Adwa. d. May God bless you! e. Give me that book. f. What is your name? The first three sentences are declarative sentences. The first one is true and the second one is false. The truth value of the third sentence cannot be ascertained because of lack of historical records but it is, by its very form, either true or false but not both. On the other hand, the last three sentences have not truth value. So they are not declaratives. Now we begin by examining proposition, the building blocks of every argument. A proposition is a sentence that may be asserted or denied. Proposition in this way are different from questions, commands, and exclamations. Neither questions, which can be asked, nor exclamations, which can be uttered, can possibly be asserted or denied. Only propositions assert that something is (or is not) the case, and therefore only they can be true or false. Definition 1.1: A proposition (or statement) is a sentence which has a truth value (either True or False but not both). The above definition does not mean that we must always know what the truth value is. For example, the sentence “The 1000th digit in the decimal expansion of 𝜋 is 7” is a proposition, but it may be necessary to find this information in a Web site on the Internet to determine whether this statement is true. Indeed, for a sentence to be a proposition (or a statement), it is not a requirement that we be able to determine its truth value. Remark: Every proposition has a truth value, namely true (denoted by 𝑻) or false (denoted by 𝑭). 1.1.2. Logical connectives In mathematical discourse and elsewhere one constantly encounters declarative sentences which have been formed by modifying a sentence with the word “not” or by connecting sentences with the words “and”, “or”, “if... then (or implies)”, and “if and only if”. These five words or combinations of words are called propositional connectives. Note: Letters such as 𝑝, 𝑞, 𝑟, 𝑠 etc. are usually used to denote actual propositions. 2 Conjunction When two propositions are joined with the connective “and,” the proposition formed is a logical conjunction. “and” is denoted by “ ”. So, the logical conjunction of two propositions, 𝑝 and 𝑞, is written: 𝑝 ∧ 𝑞, read as “𝑝 and 𝑞,” or “𝑝 conjunction 𝑞”. p and q are called the components of the conjunction. 𝑝 ∧ 𝑞 is true if and only if 𝑝 is true and 𝑞 is true. The truth table for conjunction is given as follows: 𝒑 𝒒 𝒑∧𝑞 𝑻 𝑻 𝑻 𝑻 𝑭 𝑭 𝑭 𝑻 𝑭 𝑭 𝑭 𝑭 Example 1.1: Consider the following propositions: 𝑝: 3 is an odd number. (True) 𝑞: 27 is a prime number. (False) 𝑟: Addis Ababa is the capital city of Ethiopia. (True) a. 𝑝 ∧ 𝑞: 3 is an odd number and 27 is a prime number. (False) b. 𝑝 ∧ 𝑟: 3 is an odd number and Addis Ababa is the capital city of Ethiopia. (True) Disjunction When two propositions are joined with the connective “or,” the proposition formed is called a logical disjunction. “or” is denoted by “ ”. So, the logical disjunction of two propositions, 𝑝 and 𝑞, is written: 𝑝 ∨ 𝑞 read as “𝑝 or 𝑞” or “𝑝 disjunction 𝑞.” 𝑝 ∨ 𝑞 is false if and only if both 𝑝 and 𝑞 are false. The truth table for disjunction is given as follows: 𝒑 𝒒 𝒑∨𝑞 𝑻 𝑻 𝑻 𝑻 𝑭 𝑻 𝑭 𝑻 𝑻 𝑭 𝑭 𝑭 3 Example 1.2: Consider the following propositions: 𝑝: 3 is an odd number. (True) 𝑞: 27 is a prime number. (False) 𝑠: Nairobi is the capital city of Ethiopia. (False) a. 𝑝 ∨ 𝑞: 3 is an odd number or 27 is a prime number. (True) b. p ∨ s : 27 is a prime number or Nairobi is the capital city of Ethiopia. (False) Note: The use of “or” in propositional logic is rather different from its normal use in the English language. For example, if Solomon says, “I will go to the football match in the afternoon or I will go to the cinema in the afternoon,” he means he will do one thing or the other, but not both. Here “or” is used in the exclusive sense. But in propositional logic, “or” is used in the inclusive sense; that is, we allow Solomon the possibility of doing both things without him being inconsistent. Implication When two propositions are joined with the connective “implies,” the proposition formed is called a logical implication. “implies” is denoted by “.” So, the logical implication of two propositions, 𝑝 and 𝑞, is written: 𝑝 ⟹ 𝑞 read as “𝑝 implies 𝑞.” The function of the connective “implies” between two propositions is the same as the use of “If … then …” Thus 𝑝 ⟹ 𝑞 can be read as “if 𝑝, then 𝑞.” 𝑝 ⟹ 𝑞 is false if and only if 𝑝 is true and 𝑞 is false. This form of a proposition is common in mathematics. The proposition 𝑝 is called the hypothesis or the antecedent of the conditional proposition 𝑝 ⟹ 𝑞 while 𝑞 is called its conclusion or the consequent. The following is the truth table for implication. 𝑝 𝒒 𝒑⟹𝑞 𝑻 𝑻 𝑻 𝑻 𝑭 𝑭 𝑭 𝑻 𝑻 𝑭 𝑭 𝑻 Examples 1.3: Consider the following propositions: 𝑝: 3 is an odd number. (True) 𝑞: 27 is a prime number. (False) 𝑟: Addis Ababa is the capital city of Ethiopia. (True) 𝑝 ⟹ 𝑞: If 3 is an odd number, then 27 is prime. (False) 𝑝 ⟹ 𝑟: If 3 is an odd number, then Addis Ababa is the capital city of Ethiopia. (True) 4 We have already mentioned that the implication 𝑝 ⟹ 𝑞 can be expressed as both “If 𝑝, then 𝑞” and “𝑝 implies 𝑞.” There are various ways of expressing the proposition 𝑝 ⟹ 𝑞, namely: If 𝑝, then 𝑞. 𝑞 if 𝑝. 𝑝 implies 𝑞. 𝑝 only if 𝑞. 𝑝 is sufficient for 𝑞. 𝑞 is necessary for 𝑝 Bi-implication When two propositions are joined with the connective “bi-implication,” the proposition formed is called a logical bi-implication or a logical equivalence. A bi-implication is denoted by “ ”. So the logical bi- implication of two propositions, 𝑝 and 𝑞, is written: 𝑝 ⟺ 𝑞. 𝑝 ⟺ 𝑞 is false if and only if 𝑝 and 𝑞 have different truth values. The truth table for bi-implication is given by: 𝒑 𝒒 𝒑⟺𝑞 𝑻 𝑻 𝑻 𝑻 𝑭 𝑭 𝑭 𝑻 𝑭 𝑭 𝑭 𝑻 Examples 1.4: a. Let 𝑝: 2 is greater than 3. (False) 𝑞: 5 is greater than 4. (True) Then 𝑝 ⟺ 𝑞: 2 is greater than 3 if and only if 5 is greater than 4. (False) b. Consider the following propositions: 𝑝: 3 is an odd number. (True) 𝑞: 2 is a prime number. (True) 𝑝 ⟺ 𝑞: 3 is an odd number if and only if 2 is a prime number. (True) There are various ways of stating the proposition 𝑝 ⟺ 𝑞. 𝑝 if and only if 𝑞 (also written as 𝑝 iff 𝑞), 𝑝 implies 𝑞 and 𝑞 implies 𝑝, 𝑝 is necessary and sufficient for 𝑞 𝑞 is necessary and sufficient for 𝑝 𝑝 is equivalent to 𝑞 5 Negation Given any proposition 𝑝, we can form the proposition 𝑝 called the negation of 𝑝. The truth value of 𝑝 is 𝐹 if 𝑝 is 𝑇 and 𝑇 if 𝑝 is 𝐹. We can describe the relation between 𝑝 and 𝑝 as follows. 𝒑 𝑝 𝐓 𝐅 𝐅 𝐓 Example 1.5: Let 𝑝: Addis Ababa is the capital city of Ethiopia. (True) 𝑝: Addis Ababa is not the capital city of Ethiopia. (False) Exercises 1. Which of the following sentences are propositions? For those that are, indicate the truth value. a. 123 is a prime number. b. 0 is an even number. c. 𝑥 2 − 4 = 0. d. Multiply 5𝑥 + 2 by 3. e. What an impossible question! 2. State the negation of each of the following statements. a. √2 is a rational number. b. 0 is not a negative integer. c. 111 is a prime number. 3. Let 𝑝: 15 is an odd number. 𝑞: 21 is a prime number. State each of the following in words, and determine the truth value of each. a. 𝑝 ∨ 𝑞. e. 𝑝 ⟹ 𝑞. b. 𝑝 ∧ 𝑞. f. 𝑞 ⟹ 𝑝. c. 𝑝 ∨ 𝑞. a. 𝑝 ⟹ 𝑞. d. 𝑝 ∧ 𝑞. g. 𝑞 ⟹ 𝑝. 6  4. Complete the following truth table. 𝒑 𝒒 𝒒 𝒑 ∧ 𝒒 𝑻 𝑻 𝑻 𝑭 𝑭 𝑻 𝑭 𝑭 1.1.3. Compound (or complex) propositions So far, what we have done is simply to define the logical connectives, and express them through algebraic symbols. Now we shall learn how to form propositions involving more than one connective, and how to determine the truth values of such propositions. Definition 1.2: The proposition formed by joining two or more proposition by connective(s) is called a compound statement. Note: We must be careful to insert the brackets in proper places, just as we do in arithmetic. For example, the expression 𝑝 ⟹ 𝑞 ∧ 𝑟 will be meaningless unless we know which connective should apply first. It could mean (𝑝 ⟹ 𝑞) ∧ 𝑟 or 𝑝 ⟹ (𝑞 ∧ 𝑟), which are very different propositions. The truth value of such complicated propositions is determined by systematic applications of the rules for the connectives. The possible truth values of a proposition are often listed in a table, called a truth table. If 𝑝 and 𝑞 are propositions, then there are four possible combinations of truth values for 𝑝 and 𝑞. That is, 𝑇𝑇, 𝑇𝐹, 𝐹𝑇 and 𝐹𝐹. If a third proposition 𝑟 is involved, then there are eight possible combinations of truth values for 𝑛 𝑝,𝑞 and 𝑟. In general, a truth table involving “𝑛” propositions 𝑝1 , 𝑝2 ,…, 𝑝𝑛 contains 2 possible combinations of truth values for these propositions and a truth table showing these combinations would 𝑛 have 𝑛 columns and 2 rows. So, we use truth tables to determine the truth value of a compound proposition based on the truth value of its constituent component propositions. Examples 1.6: a. Suppose 𝑝 and 𝑟 are true and 𝑞 and 𝑠 are false. What is the truth value of (𝑝 ∧ 𝑞) ⟹ (𝑟 ∨ 𝑠)? i. Since 𝑝 is true and 𝑞 is false, 𝑝 ∧ 𝑞 is false. ii. Since 𝑟 is true and 𝑠 is false, 𝑟 ∨ 𝑠 is true. iii. Thus by applying the rule of implication, we get that (𝑝 ∧ 𝑞) ⟹ (𝑟 ∨ 𝑠) is true. b. Suppose that a compound proposition is symbolized by (𝑝 ∨ 𝑞) ⟹ (𝑟 ⟺ s) 7 and that the truth values of 𝑝, 𝑞, 𝑟, and 𝑠 are 𝑇, 𝐹, 𝐹, and 𝑇, respectively. Then the truth value of 𝑝 ∨ 𝑞 is 𝑇, that of s is , that of 𝑟 ⟺ s is 𝑇. So the truth value of (𝑝 ∨ 𝑞) ⟹ (𝑟 ⟺ s) is 𝑇. Remark: When dealing with compound propositions, we shall adopt the following convention on the use of parenthesis. Whenever “ ” or “ ” occur with “ ” or “ ”, we shall assume that “ ” or “ ” is applied first, and then “ ” or “ ” is then applied. For example, 𝑝 ∧ 𝑞 ⟹ 𝑟 means (𝑝 ∧ 𝑞) ⟹ 𝑟 𝑝 ∨ 𝑞 ⟺ 𝑟 means (𝑝 ∨ 𝑞) ⟺ 𝑟 𝑞 ⟹ 𝑝 means (𝑞) ⟹ (𝑝) 𝑞 ⟹ 𝑝 ⟺ 𝑟 means ((𝑞) ⟹ 𝑝) ⟺ 𝑟 However, it is always advisable to use brackets to indicate the order of the desired operations.. Definition 1.3: Two compound propositions 𝑃 and 𝑄 are said to be equivalent if they have the same truth value for all possible combinations of truth values for the component propositions occurring in both 𝑃 and 𝑄. In this case we write 𝑃 ≡ 𝑄. Example 1.7: Let 𝑃: 𝑝 ⟹ 𝑞. Q: q ⟹ p. 𝒑 𝒒 𝑝 𝑞 𝒑⟹𝑞 𝑞 ⟹ p 𝑻 𝑻 𝑭 𝑭 𝑻 𝑻 𝑻 𝑭 𝑭 𝑻 𝑭 𝑭 𝑭 𝑻 𝑻 𝑭 𝑻 𝑻 𝑭 𝑭 𝑻 𝑻 𝑻 𝑻 Then, 𝑃 is equivalent to 𝑄, since columns 5 and 6 of the above table are identical. Example 1.8: Let 𝑃: 𝑝 ⟹ 𝑞. 𝑄: 𝑝 ⟹ 𝑞. Then 𝒑 𝒒 𝑝 𝑞 𝒑⟹𝑞 𝒑 ⟹ 𝒒 𝑻 𝑻 𝑭 𝑭 𝑻 𝑻 𝑻 𝑭 𝑭 𝑻 𝑭 𝑻 𝑭 𝑻 𝑻 𝑭 𝑻 𝑭 𝑭 𝑭 𝑻 𝑻 𝑻 𝑻 Looking at columns 5 and 6 of the table we see that they are not identical. Thus 𝑃 ≢ 𝑄. It is useful at this point to mention the non-equivalence of certain conditional propositions. Given the conditional 𝑝 ⟹ 𝑞, we give the related conditional propositions:- 𝑞 ⟹ 𝑝: Converse of 𝑝 ⟹ 𝑞 8  𝑝 ⟹ 𝑞: Inverse of 𝑝 ⟹ 𝑞 𝑞 ⟹ 𝑝: Contrapositive of 𝑝 ⟹ 𝑞 As we observed from example 1.7, the conditional 𝑝 ⟹ 𝑞 and its contrapositve 𝑞 ⟹ 𝑝 are equivalent. On the other hand, 𝑝 ⟹ 𝑞 ≢ 𝑞 ⟹ 𝑝 and p ⟹ q ≢ p ⟹ q. Do not confuse the contrapositive and the converse of the conditional proposition. Here is the difference: Converse: The hypothesis of a converse statement is the conclusion of the conditional statement and the conclusion of the converse statement is the hypothesis of the conditional statement. Contrapositive: The hypothesis of a contrapositive statement is the negation of conclusion of the conditional statement and the conclusion of the contrapositive statement is the negation of hypothesis of the conditional statement. Example 1.9: a. If Kidist lives in Addis Ababa, then she lives in Ethiopia. Converse: If Kidist lives in Ethiopia, then she lives in Addis Ababa. Contrapositive: If Kidist does not live in Ethiopia, then she does not live in Addis Ababa. Inverse: If Kidist does not live in Addis Ababa, then she does not live in Ethiopia. b. If it is morning, then the sun is in the east. Converse: If the sun is in the east, then it is morning. Contrapositive: If the sun is not in the east, then it is not morning. Inverse: If it is not morning, then the sun is not the east. Propositions, under the relation of logical equivalence, satisfy various laws or identities, which are listed below. 1. Idempotent Laws a. 𝑝 ≡ 𝑝 ∨ 𝑝. b. 𝑝 ≡ 𝑝 ∧ 𝑝. 2. Commutative Laws a. p ∧ q ≡ q ∧ p. b. p ∨ q ≡ q ∨ p. 3. Associative Laws a. 𝑝 ∧ (𝑞 ∧ 𝑟) ≡ (𝑝 ∧ 𝑞) ∧ 𝑟. b. 𝑝 ∨ (𝑞 ∨ 𝑟) ≡ (𝑝 ∨ 𝑞) ∨ 𝑟. 4. Distributive Laws a. 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟). b. 𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟). 5. De Morgan’s Laws a. (𝑝 ∧ 𝑞) ≡ 𝑝 ∨ 𝑞. 9  b. (𝑝 ∨ 𝑞) ≡ 𝑝 ∧ 𝑞 6. Law of Contrapositive 𝑝 ⟹ 𝑞 ≡ 𝑞 ⟹ 𝑝 7. Complement Law (𝑝) ≡ 𝑝. 1.1.4. Tautology and contradiction Definition: A compound proposition is a tautology if it is always true regardless of the truth values of its component propositions. If, on the other hand, a compound proposition is always false regardless of its component propositions, we say that such a proposition is a contradiction. Examples 1.10: a. Suppose 𝑝 is any proposition. Consider the compound propositions 𝑝 ∨ 𝑝 and 𝑝 ∧ 𝑝. 𝒑 𝑝 𝒑 ∨ 𝑝 𝒑 ∧ 𝑝 𝐓 𝐅 𝑻 𝑭 𝐅 𝐓 𝑻 𝑭 Observe that 𝑝 ∨ 𝑝 is a tautology while 𝑝 ∧ 𝑝 is a contradiction. b. For any propositions 𝑝 and 𝑞. Consider the compound proposition 𝑝 ⟹ (𝑞 ⟹ 𝑝). Let us make a truth table and study the situation. 𝒑 𝒒 𝒒⟹𝑝 𝒑 ⟹ (𝑞 ⟹ 𝑝) 𝑻 𝑻 𝑻 T 𝑻 𝑭 𝑻 T 𝑭 𝑻 𝑭 T 𝑭 𝑭 𝑻 T We have exhibited all the possibilities and we see that for all truth values of the constituent propositions, the proposition 𝑝 ⟹ (𝑞 ⟹ 𝑝) is always true. Thus, 𝑝 ⟹ (𝑞 ⟹ 𝑝) is a tautology. c. The truth table for the compound proposition (𝑝 ⟹ 𝑞) ⟺ (𝑝 ∧ 𝑞). 𝒑 𝒒 𝑞 𝒑 ∧ 𝑞 𝒑⟹𝑞 (𝑝 ⟹ 𝑞) ⟺ (𝑝 ∧ 𝑞) 𝑻 𝑻 𝑭 𝑭 𝑻 𝑭 𝑻 𝑭 𝑻 𝑻 𝑭 𝑭 𝑭 𝑻 𝑭 𝑭 𝑻 𝑭 𝑭 𝑭 𝑻 𝑭 𝑻 𝑭 10 In example 1.10(c), the given compound proposition has a truth value 𝐹 for every possible combination of assignments of truth values for the component propositions 𝑝 and 𝑞. Thus (𝑝 ⟹ 𝑞) ⟺ (𝑝 ∧ 𝑞) is a contradiction. Remark: 1. In a truth table, if a proposition is a tautology, then every line in its column has 𝑇 as its entry; if a proposition is a contradiction, every line in its column has 𝐹 as its entry. 2. Two compound propositions 𝑃 and 𝑄 are equivalent if and only if “𝑃 ⟺ 𝑄” is a tautology. Exercises 1. For statements 𝑝, 𝑞 and 𝑟, use a truth table to show that each of the following pairs of statements is logically equivalent. a. (𝑝 ∧ 𝑞) ⟺ 𝑝 and 𝑝 ⟹ 𝑞. b. 𝑝 ⟹ (𝑞 ∨ 𝑟) and 𝑞 ⟹ (𝑝 ∨ 𝑟). c. (𝑝 ∨ 𝑞) ⟹ 𝑟 and (𝑝 ⟹ 𝑞) ∧ (𝑞 ⟹ 𝑟). d. 𝑝 ⟹ (𝑞 ∨ 𝑟) and (𝑟) ⟹ (𝑝 ⟹ 𝑞). e. 𝑝 ⟹ (𝑞 ∨ 𝑟) and ((𝑟) ∧ 𝑝) ⟹ 𝑞. 2. For statements 𝑝, 𝑞, and 𝑟, show that the following compound statements are tautology. a. 𝑝 ⟹ (𝑝 ∨ 𝑞). b. (𝑝 ∧ (𝑝 ⟹ 𝑞)) ⟹ 𝑞. c. ((𝑝 ⟹ 𝑞) ∧ (𝑞 ⟹ 𝑟)) ⟹ (𝑝 ⟹ 𝑟). 3. For statements 𝑝 and 𝑞, show that (𝑝 ∧ 𝑞) ∧ (𝑝 ∧ 𝑞) is a contradiction. 4. Write the contrapositive and the converse of the following conditional statements. a. If it is cold, then the lake is frozen. b. If Solomon is healthy, then he is happy. c. If it rains, Tigist does not take a walk. 5. Let 𝑝 and 𝑞 be statements. Which of the following implies that 𝑝 ∨ 𝑞 is false? a. 𝑝 ∨ 𝑞 is false. d. 𝑝 ⟹ 𝑞 is true. b. 𝑝 ∨ 𝑞 is true. e. 𝑝 ∧ 𝑞 is false. c. 𝑝 ∧ 𝑞 is true. 6. Suppose that the statements 𝑝, 𝑞, 𝑟, and 𝑠 are assigned the truth values 𝑇, 𝐹, 𝐹, and 𝑇, respectively. Find the truth value of each of the following statements. a. (𝑝 ∨ 𝑞) ∨ 𝑟. f. (𝑝 ∨ 𝑟) ⟺ (𝑟 ∧ 𝑠). b. 𝑝 ∨ (𝑞 ∨ 𝑟). g. (𝑠 ⟺ 𝑝) ⟹ (𝑝 ∨ 𝑠). c. 𝑟 ⟹ (𝑠 ∧ 𝑝). h. (𝑞 ∧ 𝑠) ⟹ (𝑝 ⟺ 𝑠). d. 𝑝 ⟹ (𝑟 ⟹ 𝑠). i. (𝑟 ∧ 𝑠) ⟹ (𝑝 ⟹ (𝑞 ∨ 𝑠)). e. 𝑝 ⟹ (𝑟 ∨ 𝑠). j. (𝑝 ∨ 𝑞) ∨ 𝑟 ⟹ (𝑠 ∧ 𝑠). 7. Suppose the value of 𝑝 ⟹ 𝑞 is 𝑇; what can be said about the value of 𝑝 ∧ 𝑞 ⟺ 𝑝 ∨ 𝑞? 11  8. a. Suppose the value of 𝑝 ⟺ 𝑞 is 𝑇; what can be said about the values of 𝑝 ⟺ 𝑞 and 𝑝 ⟺ 𝑞? b. Suppose the value of 𝑝 ⟺ 𝑞 is 𝐹; what can be said about the values of 𝑝 ⟺ 𝑞 and 𝑝 ⟺ 𝑞? 9. Construct the truth table for each of the following statements. a. 𝑝 ⟹ (𝑝 ⟹ 𝑞). d. (𝑝 ⟹ 𝑞) ⟺ (𝑝 ∨ 𝑞). b. (𝑝 ∨ 𝑞) ⟺ (𝑞 ∨ 𝑝). e. (p ⟹ (q ∧ r)) ∨ (p ∧ q). c. 𝑝 ⟹ (𝑞 ∧ 𝑟). f. (𝑝 ∧ 𝑞) ⟹ ((𝑞 ∧ 𝑞) ⟹ (𝑟 ∧ 𝑞)). 10. For each of the following determine whether the information given is sufficient to decide the truth value of the statement. If the information is enough, state the truth value. If it is insufficient, show that both truth values are possible. a. (𝑝 ⟹ 𝑞) ⟹ 𝑟, where 𝑟 = 𝑇. b. 𝑝 ∧ (𝑞 ⟹ 𝑟), where 𝑞 ⟹ 𝑟 = 𝑇. c. 𝑝 ∨ (𝑞 ⟹ 𝑟), where 𝑞 ⟹ 𝑟 = 𝑇. d. (𝑝 ∨ 𝑞) ⟺ (𝑝 ∧ 𝑞), where 𝑝 ∨ 𝑞 = 𝑇. e. (𝑝 ⟹ 𝑞) ⟹ (𝑞 ⟹ 𝑝), where 𝑞 = 𝑇. f. (𝑝 ∧ 𝑞) ⟹ (𝑝 ∨ 𝑠), where 𝑝 = 𝑇 and 𝑠 = 𝐹. 1.2. Open propositions and quantifiers In mathematics, one frequently comes across sentences that involve a variable. For example, 𝑥 2 + 2𝑥 − 3 = 0 is one such. The truth value of this statement depends on the value we assign for the variable 𝑥. For example, if 𝑥 = 1, then this sentence is true, whereas if 𝑥 = −1, then the sentence is false. Section objectives: After completing this section, students will be able to:-  Define open proposition.  Analyze the difference between proposition and open proposition.  Differentiate the two types of quantifiers.  Convert open propositions into propositions using quantifiers.  Determine the truth value of a quantified proposition.  Convert a quantified proposition into words and vise versa.  Explain the relationship between existential and universal quantifiers.  Analyze quantifiers occurring in combinations. 12 Definition 1.4: An open statement (also called a predicate) is a sentence that contains one or more variables and whose truth value depends on the values assigned for the variables. We represent an open statement by a capital letter followed by the variable(s) in parenthesis, e.g., 𝑃(𝑥), 𝑄(𝑥) etc. Example 1.11: Here are some open propositions: a. 𝑥 is the day before Sunday. b. 𝑦 is a city in Africa. c. 𝑥 is greater than 𝑦. d. 𝑥 + 4 = −9. It is clear that each one of these examples involves variables, but is not a proposition as we cannot assign a truth value to it. However, if individuals are substituted for the variables, then each one of them is a proposition or statement. For example, we may have the following. a. Monday is the day before Sunday. b. London is a city in Africa. c. 5 is greater than 9. d. –13 + 4= –9 Remark The collection of all allowable values for the variable in an open sentence is called the universal set (the universe of discourse) and denoted by 𝑼. Definition 1.5: Two open proposition 𝑃(𝑥) and 𝑄 (𝑥) are said to be equivalent if and only if 𝑃(𝑎) = 𝑄(𝑎) for all individual 𝑎. Note that if the universe 𝑈 is specified, then 𝑃(𝑥) and 𝑄 (𝑥) are equivalent if and only if 𝑃(𝑎) = 𝑄(𝑎) for all 𝑎 ∈ 𝑈. Example 1.12: Let 𝑃(𝑥): 𝑥 2 − 1 = 0. 𝑄(𝑥): |𝑥| ≥ 1. 1 Let 𝑈 = {−1, − 2 , 0,1}. Then for all 𝑎 ∈ 𝑈; 𝑃(𝑎) and 𝑄(𝑎) have the same truth value. 𝑃(−1): (−1)2 − 1 = 0 (𝑇) 𝑄(−1): |−1| ≥ 1 (𝑇) 1 1 1 1 𝑃 (− 2) : (− 2)2 − 1 = 0 (𝐹) 𝑄 (− 2) : |− 2| ≥ 1 (𝐹) 𝑃(0): 0 − 1 = 0 (𝐹) 𝑄(0): |0| ≥ 1 (𝐹) 𝑃(1): 1 − 1 = 0 (𝑇) 𝑄(1): |1| ≥ 1 (𝑇) Therefore 𝑃(𝑎) = 𝑄(𝑎) for all 𝑎 ∈ 𝑈. Definition 1.6: Let 𝑈 be the universal set. An open proposition 𝑃(𝑥) is a tautology if and only if 𝑃(𝑎) is always true for all values of 𝑎 ∈ 𝑈. 13 Example 1.13: The open proposition 𝑃(𝑥): 𝑥 2 ≥ 0 is a tautology. As we have observed in example 1.11, an open proposition can be converted into a proposition by substituting the individuals for the variables. However, there are other ways that an open proposition can be converted into a proposition, namely by a method called quantification. Let 𝑃(𝑥) be an open proposition over the domain 𝑆. Adding the phrase “For every 𝑥 ∈ 𝑆” to 𝑃(𝑥) or “For some 𝑥 ∈ 𝑆” to 𝑃(𝑥) produces a statement called a quantified statement. Consider the following open propositions with universe. a. 𝑅(𝑥): 𝑥 2 ≥ 0. b. 𝑃(𝑥): (𝑥 + 2)(𝑥 − 3) = 0. c. 𝑄(𝑥): 𝑥 2 < 0. Then 𝑅(𝑥) is always true for each 𝑥 ∈ ℝ, 𝑃(𝑥) is true only for 𝑥 = −2 and 𝑥 = 3, 𝑄(𝑥) is always false for all values of 𝑥 ∈ ℝ. Hence, given an open proposition 𝑃(𝑥), with universe 𝑈, we observe that there are three possibilities. a. 𝑃(𝑥) is true for all 𝑥 ∈ 𝑈. b. 𝑃(𝑥) is true for some 𝑥 ∈ 𝑈. c. 𝑃(𝑥) is false for all 𝑥 ∈ 𝑈. Now we proceed to study open propositions which are satisfied by “all” and “some” members of the given universe. a. The phrase "for every 𝑥 " is called a universal quantifier. We regard "for every 𝑥," "for all 𝑥," and "for each 𝑥 " as having the same meaning and symbolize each by “(∀𝑥).” Think of the symbol as an inverted 𝐴(representing all). If 𝑃(𝑥) is an open proposition with universe 𝑈, then (∀𝑥)𝑃(𝑥) is a quantified proposition and is read as “every 𝑥 ∈ 𝑈 has the property 𝑃.” b. The phrase "there exists an 𝑥 " is called an existential quantifier. We regard "there exists an 𝑥," "for some 𝑥," and "for at least one 𝑥 " as having the same meaning, and symbolize each by “(∃𝑥).” Think of the symbol as the backwards capital 𝐸(representing exists). If 𝑃(𝑥) is an open proposition with universe 𝑈, then (∃𝑥)𝑃(𝑥) is a quantified proposition and is read as “there exists 𝑥 ∈ 𝑈 with the property 𝑃.” Remarks: i. To show that (∀𝑥)𝑃(𝑥) is 𝐹, it is sufficient to find at least one 𝑎 ∈ 𝑈 such that 𝑃(𝑎) is 𝐹. Such an element 𝑎 ∈ 𝑈 is called a counter example. ii. (∃𝑥)𝑃(𝑥) is 𝐹 if we cannot find any 𝑎 ∈ 𝑈 having the property 𝑃. Example 1.14: a. Write the following statements using quantifiers. i. For each real number 𝑥 > 0, 𝑥 2 + 𝑥 − 6 = 0. 14  Solution: (∀𝑥 > 0)(𝑥 2 + 𝑥 − 6 = 0). ii. There is a real number 𝑥 > 0 such that 𝑥 2 + 𝑥 − 6 = 0. Solution: (∃𝑥 > 0)(𝑥 2 + 𝑥 − 6 = 0). iii. The square of any real number is nonnegative. Solution: (∀𝑥 ∈ ℝ)(𝑥 2 ≥ 0). b. i. Let 𝑃(𝑥): 𝑥 2 + 1 ≥ 0. The truth value for (∀𝑥)𝑃(𝑥) [i.e (∀𝑥)(𝑥 2 + 1 ≥ 0)] is 𝑇. 1 ii. Let 𝑃(𝑥): 𝑥 < 𝑥 2. The truth value for (∀𝑥)(𝑥 < 𝑥 2 ) is 𝐹. 𝑥 = 2 is a 1 1 1 counterexample since 2 ∈ ℝ but < 4. On the other hand, (∃𝑥)𝑃(𝑥) is true, since 2 −1 ∈ ℝ such that −1 < 1. iii. Let 𝑃(𝑥): |𝑥| = −1. The truth value for (∃𝑥)𝑃(𝑥) is 𝐹 since there is no real number whose absolute value is −1. Relationship between the existential and universal quantifiers If 𝑃(𝑥) is a formula in 𝑥, consider the following four statements. a. (∀𝑥)𝑃(𝑥). b. (∃𝑥)𝑃(𝑥). c. (∀x)P(x). d. (∃x)P(x). We might translate these into words as follows. a. Everything has property 𝑃. b. Something has property 𝑃. c. Nothing has property 𝑃. d. Something does not have property 𝑃. Now (d) is the denial of (a), and (c) is the denial of (b), on the basis of everyday meaning. Thus, for example, the existential quantifier may be defined in terms of the universal quantifier. Now we proceed to discuss the negation of quantifiers. Let 𝑃(𝑥) be an open proposition. Then (∀𝑥)𝑃(𝑥) is false only if we can find an individual “𝑎” in the universe such that 𝑃(𝑎) is false. If we succeed in getting such an individual, then (∃𝑥)𝑃(𝑥) is true. Hence (∀𝑥)𝑃(𝑥) will be false if (∃𝑥)𝑃(𝑥) is true. Therefore the negation of (∀𝑥)𝑃(𝑥) is (∃𝑥)𝑃(𝑥). Hence we conclude that (∀𝑥)𝑃(𝑥) ≡ (∃𝑥)𝑃(𝑥). Similarly, we can easily verified that (∃𝑥)𝑃(𝑥) ≡ (∀𝑥)𝑃(𝑥). Remark: To negate a statement that involves the quantifiers and , change each to , change each to , and negate the open statement. 15 Example 1.15: Let 𝑈 = ℝ. a. (∃𝑥)(𝑥 < 𝑥 2 ) ≡ (∀𝑥)(𝑥 < 𝑥 2 ) ≡ (∀𝑥)(𝑥 ≥ 𝑥 2 ). b. (∀𝑥)(4𝑥 + 1 = 0) ≡ (∃𝑥)(4𝑥 + 1 = 0) ≡ (∃𝑥)(4𝑥 + 1 ≠ 0). Given propositions containing quantifiers we can form a compound proposition by joining them with connectives in the same way we form a compound proposition without quantifiers. For example, if we have (∀𝑥)𝑃(𝑥) and (∃𝑥)𝑄(𝑥) we can form (∀𝑥)𝑃(𝑥) ⟺ (∃𝑥)𝑄(𝑥). Consider the following statements involving quantifiers. Illustrations of these along with translations appear below. a. All rationals are reals. (∀𝑥)(ℚ(𝑥) ⟹ ℝ(𝑥)). b. No rationals are reals. (∀𝑥)(ℚ(𝑥) ⟹ ℝ(𝑥)). c. Some rationals are reals. (∃𝑥)(ℚ(𝑥) ∧ ℝ(𝑥)). d. Some rationals are not reals. (∃𝑥)(ℚ(𝑥) ∧ ℝ(𝑥)). Example 1.16: Let 𝑈 = The set of integers. Let 𝑃(𝑥): 𝑥 is a prime number. 𝑄(𝑥): 𝑥 is an even number. 𝑅(𝑥): 𝑥 is an odd number. Then a. (∃𝑥)[𝑃(𝑥) ⟹ 𝑄(𝑥)] is 𝑇; since there is an 𝑥, say 2, such that 𝑃(2) ⟹ 𝑄(2) is 𝑇. b. (∀𝑥)[𝑃(𝑥) ⟹ 𝑄(𝑥)] is 𝐹. As a counterexample take 7. Then 𝑃(7) is 𝑇 and 𝑄(7) is 𝐹. Hence 𝑃(7) ⟹ 𝑄(7). c. (∀𝑥)[𝑅(𝑥) ∧ 𝑃(𝑥)] is 𝐹. d. (∀𝑥)[(𝑅(𝑥) ∧ 𝑃(𝑥)) ⟹ 𝑄(𝑥)] is 𝐹. Quantifiers Occurring in Combinations So far, we have only considered cases in which universal and existential quantifiers appear simply. However, if we consider cases in which universal and existential quantifiers occur in combination, we are lead to essentially new logical structures. The following are the simplest forms of combinations: 1. (∀𝑥)(∀𝑦)𝑃(𝑥, 𝑦) “for all 𝑥 and for all 𝑦 the relation 𝑃(𝑥, 𝑦) holds”; 2. (∃𝑥)(∃𝑦)𝑃(𝑥, 𝑦) “there is an 𝑥 and there is a 𝑦 for which 𝑃(𝑥, 𝑦) holds”; 3. (∀𝑥)(∃𝑦)𝑃(𝑥, 𝑦) “for every 𝑥 there is a 𝑦 such that 𝑃(𝑥, 𝑦) holds”; 16  4. (∃𝑥)(∀𝑦)𝑃(𝑥, 𝑦) “there is an 𝑥 which stands to every 𝑦 in the relation 𝑃(𝑥, 𝑦).” Example 1.17: Let 𝑈 = The set of integers. Let 𝑃(𝑥, 𝑦): 𝑥 + 𝑦 = 5. a. (∃𝑥) (∃𝑦) 𝑃(𝑥, 𝑦) means that there is an integer 𝑥 and there is an integer 𝑦 such that 𝑥 + 𝑦 = 5. This statement is true when 𝑥 = 4 and 𝑦 = 1, since 4 + 1 = 5. Therefore, the statement (∃𝑥) (∃𝑦) 𝑃(𝑥, 𝑦) is always true for this universe. There are other choices of 𝑥 and 𝑦 for which it would be true, but the symbolic statement merely says that there is at least one choice for 𝑥 and 𝑦 which will make the statement true, and we have demonstrated one such choice. b. (∃𝑥) (∀𝑦) 𝑃(𝑥, 𝑦) means that there is an integer 𝑥0 such that for every 𝑦, 𝑥0 + 𝑦 = 5. This is false since no fixed value of 𝑥0 will make this true for all 𝑦 in the universe; e.g. if 𝑥0 = 1, then 1 + 𝑦 = 5 is false for some 𝑦. c. (∀𝑥) (∃𝑦) 𝑃(𝑥, 𝑦) means that for every integer 𝑥, there is an integer 𝑦 such that 𝑥 + 𝑦 = 5. Let 𝑥 = 𝑎, then 𝑦 = 5 − 𝑎 will always be an integer, so this is a true statement. d. (∀𝑥) (∀𝑦) 𝑃(𝑥, 𝑦) means that for every integer 𝑥 and for every integer 𝑦, 𝑥 + 𝑦 = 5. This is false, for if 𝑥 = 2 and 𝑦 = 7, we get 2 + 7 = 9 ≠ 5. Example 1.18: a. Consider the statement For every two real numbers 𝑥 and 𝑦,𝑥 2 + 𝑦 2 ≥ 0. If we let 𝑃(𝑥, 𝑦): 𝑥 2 + 𝑦 2 ≥ 0 where the domain of both 𝑥 and 𝑦 is , the statement can be expressed as (∀𝑥 ∈ ℝ)(∀𝑦 ∈ ℝ)𝑃(𝑥, 𝑦) or as (∀𝑥 ∈ ℝ)(∀𝑦 ∈ ℝ)(𝑥 2 + 𝑦 2 ≥ 0). Since 𝑥 2 ≥ 0 and 𝑦 2 ≥ 0 for all real numbers 𝑥 and 𝑦, it follows that 𝑥 2 + 𝑦 2 ≥ 0 and so 𝑃(𝑥, 𝑦) is true for all real numbers 𝑥 and 𝑦. Thus the quantified statement is true. b. Consider the open statement 𝑃(𝑥, 𝑦): |𝑥 − 1| + |𝑦 − 2| ≤ 2 where the domain of the variable 𝑥 is the set 𝐸 of even integers and the domain of the variable 𝑦 is the set 𝑂 of odd integers. Then the quantified statement (∃𝑥 ∈ 𝐸)(∃𝑦 ∈ 𝑂)𝑃(𝑥, 𝑦) 17 can be expressed in words as There exist an even integer 𝑥 and an odd integer 𝑦 such that |𝑥 − 1| + |𝑦 − 2| ≤ 2. Since 𝑃(2,3): 1 + 1 ≤ 2 is true, the quantified statement is true. c. Consider the open statement 𝑃(𝑥, 𝑦): 𝑥𝑦 = 1 where the domain of both 𝑥 and 𝑦 is the set ℚ+ of positive rational numbers. Then the quantified statement (∀𝑥 ∈ ℚ+ )(∃𝑦 ∈ ℚ+ )𝑃(𝑥, 𝑦) can be expressed in words as For every positive rational number 𝑥, there exists a positive rational number 𝑦 such that 𝑥𝑦 = 1. It turns out that the quantified statement is true. If we replace ℚ+ by , then we have (∀𝑥 ∈ ℝ)(∃𝑦 ∈ ℝ)𝑃(𝑥, 𝑦). Since 𝑥 = 0 and for every real number 𝑦, 𝑥𝑦 = 0 ≠ 1, (∀𝑥 ∈ ℝ)(∃𝑦 ∈ ℝ)𝑃(𝑥, 𝑦) is false. d. Consider the open statement 𝑃(𝑥, 𝑦): 𝑥𝑦 is odd where the domain of both 𝑥 and 𝑦 is the set of natural numbers. Then the quantified statement (∃𝑥 ∈ ℕ)(∀𝑦 ∈ ℕ)𝑃(𝑥, 𝑦), expressed in words, is There exists a natural number 𝑥 such that for every natural numbers 𝑦, 𝑥𝑦 is odd. The statement is false. In general, from the meaning of the universal quantifier it follows that in an expression (∀𝑥)(∀𝑦)𝑃(𝑥, 𝑦) the two universal quantifiers may be interchanged without altering the sense of the sentence. This also holds for the existential quantifies in an expression such as (∃𝑥)(∃𝑦)𝑃(𝑥, 𝑦). In the statement (∀𝑥)(∃𝑦)𝑃(𝑥, 𝑦) , the choice of 𝑦 is allowed to depend on 𝑥 - the 𝑦 that works for one 𝑥 need not work for another 𝑥. On the other hand, in the statement (∃𝑦)(∀𝑥)𝑃(𝑥, 𝑦), the 𝑦 must work for all 𝑥, i.e., 𝑦 is independent of 𝑥. For example, the expression (∀𝑥)(∃𝑦)(𝑥 < 𝑦), where 𝑥 and 𝑦 are variables referring to the domain of real numbers, constitutes a true proposition, namely, “For every number 𝑥, there is a number 𝑦, such that 𝑥 is less that 𝑦,” i.e., “given any number, there is a greater number.” However, if the order of the symbol (∀𝑥) and (∃𝑦) is changed, in this case, we obtain: (∃𝑦)(∀𝑥)(𝑥 < 𝑦), which is a false proposition, namely, “There is a number which is greater than every number.” By transposing (∀𝑥) and (∃𝑦), therefore, we get a different statement. The logical situation here is: (∃𝑦)(∀𝑥)𝑃(𝑥, 𝑦) ⟹ (∀𝑥)(∃𝑦)𝑃(𝑥, 𝑦). Finally, we conclude this section with the remark that there are no mechanical rules for translating sentences from English into the logical notation which has been introduced. In every 18 case one must first decide on the meaning of the English sentence and then attempt to convey that same meaning in terms of predicates, quantifiers, and, possibly, individual constants. Exercises 1. In each of the following, two open statements 𝑃(𝑥, 𝑦) and 𝑄(𝑥, 𝑦) are given, where the domain of both 𝑥 and 𝑦 is. Determine the truth value of 𝑃(𝑥, 𝑦) ⟹ 𝑄(𝑥, 𝑦) for the given values of 𝑥 and 𝑦. a. 𝑃(𝑥, 𝑦): 𝑥 2 − 𝑦 2 = 0. and 𝑄(𝑥, 𝑦): 𝑥 = 𝑦. (𝑥, 𝑦) ∈ {(1, −1), (3,4), (5,5)}. b. 𝑃(𝑥, 𝑦): |𝑥| = |𝑦|. and 𝑄(𝑥, 𝑦): 𝑥 = 𝑦. (𝑥, 𝑦) ∈ {(1,2), (2, −2), (6,6)}. c. 𝑃(𝑥, 𝑦): 𝑥 2 + 𝑦 2 = 1. and 𝑄(𝑥, 𝑦): 𝑥 + 𝑦 = 1. (𝑥, 𝑦) ∈ {(1, −1), (−3,4), (0, −1), (1,0)}. 2. Let 𝑂 denote the set of odd integers and let 𝑃(𝑥): 𝑥 2 + 1 is even, and 𝑄(𝑥): 𝑥 2 is even. be open statements over the domain 𝑂. State (∀𝑥 ∈ 𝑂)𝑃(𝑥) and (∃𝑦 ∈ 𝑂)𝑄(𝑥) in words. 3. State the negation of the following quantified statements. 1 a. For every rational number 𝑟, the number 𝑟 is rational. b. There exists a rational number 𝑟 such that 𝑟 2 = 2. 5𝑛−6 4. Let 𝑃(𝑛): is an integer. be an open sentence over the domain. Determine, with 3 explanations, whether the following statements are true or false: a. (∀𝑛 ∈ ℤ)𝑃(𝑛). b. (∃𝑛 ∈ ℤ)𝑃(𝑛). 5. Determine the truth value of the following statements. a. (∃𝑥 ∈ ℝ)(𝑥 2 − 𝑥 = 0). b. (∀𝑥 ∈ ℕ)(𝑥 + 1 ≥ 2). c. (∀𝑥 ∈ ℝ)(√𝑥 2 = 𝑥). d. (∃𝑥 ∈ ℚ)(3𝑥 2 − 27 = 0). e. (∃𝑥 ∈ ℝ)(∃𝑦 ∈ ℝ)(𝑥 + 𝑦 + 3 = 8). f. (∃𝑥 ∈ ℝ)(∃𝑦 ∈ ℝ)(𝑥 2 + 𝑦 2 = 9). g. (∀𝑥 ∈ ℝ)(∃𝑦 ∈ ℝ)(𝑥 + 𝑦 = 5). h. (∃𝑥 ∈ ℝ)(∀𝑦 ∈ ℝ)(𝑥 + 𝑦 = 5) 6. Consider the quantified statement For every 𝑥 ∈ 𝐴 and 𝑦 ∈ 𝐴, 𝑥𝑦 − 2 is prime. where the domain of the variables 𝑥 and 𝑦 is 𝐴 = {3,5,11}. a. Express this quantified statement in symbols. b. Is the quantified statement in (a) true or false? Explain. c. Express the negation of the quantified statement in (a) in symbols. d. Is the negation of the quantified in (a) true or false? Explain. 𝑥 7. Consider the open statement 𝑃(𝑥, 𝑦): 𝑦 < 1. where the domain of 𝑥 is 𝐴 = {2,3,5} and the 19  domain of 𝑦 is 𝐵 = {2,4,6}. a. State the quantified statement (∀𝑥 ∈ 𝐴)(∃𝑦 ∈ 𝐵)𝑃(𝑥, 𝑦) in words. b. Show quantified statement in (a) is true. 8. Consider the open statement 𝑃(𝑥, 𝑦): 𝑥 − 𝑦 < 0. where the domain of 𝑥 is 𝐴 = {3,5,8} and the domain of 𝑦 is 𝐵 = {3,6,10}. a. State the quantified statement (∃𝑦 ∈ 𝐵)(∀𝑥 ∈ 𝐴)𝑃(𝑥, 𝑦) in words. b. Show quantified statement in (a) is true. 1. 3. Argument and Validity Section objectives: After completing this section, students will be able to:-  Define argument (or logical deduction).  Identify hypothesis and conclusion of a given argument.  Determine the validity of an argument using a truth table.  Determine the validity of an argument using rules of inferences. Definition 1.7: An argument (logical deduction) is an assertion that a given set of statements 𝑝1 , 𝑝2 , 𝑝3 , … , 𝑝𝑛 , called hypotheses or premises, yield another statement 𝑄, called the conclusion. Such a logical deduction is denoted by: 𝑝1 , 𝑝2 , 𝑝3 , … , 𝑝𝑛 ├ 𝑄 or 𝑝1 𝑝2  𝑝𝑛 𝑄 Example 1.19: Consider the following argument: If you study hard, then you will pass the exam. You did not pass the exam. Therefore, you did not study hard. Let 𝑝: You study hard. 𝑞: You will pass the exam. The argument form can be written as: 20  pq q p When is an argument form accepted to be correct? In normal usage, we use an argument in order to demonstrate that a certain conclusion follows from known premises. Therefore, we shall require that under any assignment of truth values to the statements appearing, if the premises became all true, then the conclusion must also become true. Hence, we state the following definition. Definition 1.8: An argument form 𝑝1 , 𝑝2 , 𝑝3 , … , 𝑝𝑛 ├ 𝑄 is said to be valid if 𝑄 is true whenever all the premises 𝑝1 , 𝑝2 , 𝑝3 , … , 𝑝𝑛 are true; otherwise it is invalid. Example 1.20: Investigate the validity of the following argument: a. p  q,  q   p b. p  q,  q  r  p c. If it rains, crops will be good. It did not rain. Therefore, crops were not good. Solution: First we construct a truth table for the statements appearing in the argument forms. a. 𝒑 𝒒 𝑝 𝑞 𝒑⟹𝑞 𝑻 𝑻 𝑭 𝑭 𝑻 𝑻 𝑭 𝑭 𝑻 𝑭 𝑭 𝑻 𝑻 𝑭 𝑻 𝑭 𝑭 𝑻 𝑻 𝑻 The premises 𝑝 ⟹ 𝑞 and 𝑞 are true simultaneously in row 4 only. Since in this case 𝑝 is also true, the argument is valid. b. 𝒑 𝒒 𝒓 𝑞 𝒑 ⟹ 𝑞 𝑞 ⟹ 𝑟 𝑻 𝑻 𝑻 𝑭 𝑻 𝑻 𝑻 𝑻 𝑭 𝑭 𝑻 𝑻 𝑻 𝑭 𝑻 𝑻 𝑭 𝑻 𝑻 𝑭 𝑭 𝑻 𝑭 𝑭 𝑭 𝑻 𝑻 𝑭 𝑻 𝑻 𝑭 𝑻 𝑭 𝑭 𝑻 𝑻 𝑭 𝑭 𝑻 𝑻 𝑻 𝑻 𝑭 𝑭 𝑭 𝑻 𝑻 𝑭 21 The 1st, 2nd, 5th, 6th and 7th rows are those in which all the premises take value 𝑇. In the 5th, 6th and 7th rows however the conclusion takes value 𝐹. Hence, the argument form is invalid. c. Let 𝑝: It rains. 𝑞: Crops are good. 𝑝: It did not rain. 𝑞: Crops were not good. The argument form is 𝑝 ⟹ 𝑞, 𝑝├𝑞 Now we can use truth table to test validity as follows: 𝒑 𝒒 𝑝 𝑞 𝒑⟹𝑞 𝑻 𝑻 𝑭 𝑭 𝑻 𝑻 𝑭 𝑭 𝑻 𝑭 𝑭 𝑻 𝑻 𝑭 𝑻 𝑭 𝑭 𝑻 𝑻 𝑻 The premises 𝑝 ⟹ 𝑞 and 𝑝 are true simultaneously in row 4 only. Since in this case 𝑞 is also true, the argument is valid. Remark: 1. What is important in validity is the form of the argument rather than the meaning or content of the statements involved. 2. The argument form 𝑝1 , 𝑝2 , 𝑝3 , … , 𝑝𝑛 ├ 𝑄 is valid iff the statement (𝑝1 ∧ 𝑝2 ∧ 𝑝3 ∧ … ∧ 𝑝𝑛 ) ⟹ 𝑄 is a tautology. Rules of inferences Below we list certain valid deductions called rules of inferences. 1. Modes Ponens 𝑝 𝑝⟹𝑞 𝑞 2. Modes Tollens 𝑞 𝑝⟹𝑞 𝑝 3. Principle of Syllogism 𝑝⟹𝑞 𝑞⟹𝑟 𝑝⟹𝑟 22  4. Principle of Adjunction a. 𝑝 𝑞 𝑝∧𝑞 b. 𝑞 𝑝∨𝑞 5. Principle of Detachment 𝑝∧𝑞 𝑝, 𝑞 6. Modes Tollendo Ponens 𝑝 𝑝∨𝑞 𝑞 7. Modes Ponendo Tollens (𝑝 ∧ 𝑞) 𝑝 𝑞 8. Constructive Dilemma (𝑝 ⟹ 𝑞) ∧ (𝑟 ⟹ 𝑠) 𝑝∨𝑟 𝑞∨𝑠 9. Principle of Equivalence 𝑝⟺𝑞 𝑝 𝑞 10. Principle of Conditionalization 𝑝 𝑞⟹𝑝 Formal proof of validity of an argument Definition 1.9: A formal proof of a conclusion 𝑄 given hypotheses 𝑝1 , 𝑝2 , 𝑝3 , … , 𝑝𝑛 is a sequence of stapes, each of which applies some inference rule to hypotheses or previously proven statements (antecedent) to yield a new true statement (the consequent). A formal proof of validity is given by writing on the premises and the statements which follows from them in a single column, and setting off in another column, to the right of each statement, its justification. It is convenient to list all the premises first. 23 Example 1.21: Show that 𝑝 ⟹ 𝑞, 𝑞├𝑝 is valid. Solution: 1. 𝑞 is true premise 2. 𝑝 ⟹ 𝑞 premise 3. 𝑞 ⟹ 𝑝 contrapositive of (2) 4. p Modes Ponens using (1) and (3) Example 1.22: Show that the hypotheses It is not sunny this afternoon and it is colder than yesterday. If we go swimming, then it is sunny. If we do not go swimming, then we will take a canoe trip. If we take a canoe trip, then we will be home by sunset. Lead to the conclusion: We will be home by sunset. Let 𝑝: It is sunny this afternoon. 𝑞: It is colder than yesterday. 𝑟: We go swimming. 𝑠: We take a canoe trip. 𝑡: We will be home by sunset. Then 1. 𝑝 ∧ 𝑞 hypothesis 2. 𝑝 simplification using (1) 3. 𝑟 ⟹ 𝑝 hypothesis 4. 𝑟 Modus Tollens using (2) and (3) 5. 𝑟 ⟹ 𝑠 hypothesis 6. 𝑠 Modus Ponens using (4) and (5) 7. 𝑠 ⟹ 𝑡 hypothesis 8. 𝑡 Modus Ponens using (6) and (7) Exercises 1. Use the truth table method to show that the following argument forms are valid. i. 𝑝 ⟹ 𝑞, 𝑞 ├ 𝑝. ii. 𝑝 ⟹ 𝑝, 𝑝, 𝑟 ⟹ 𝑞 ├ 𝑟. iii. 𝑝 ⟹ 𝑞, 𝑟 ⟹ 𝑞 ├𝑟 ⟹ 𝑝. iv. 𝑟 ∨ 𝑠, (𝑠 ⟹ 𝑝) ⟹ 𝑟 ├ 𝑝. v. 𝑝 ⟹ 𝑞, 𝑝 ⟹ 𝑟, 𝑟 ⟹ 𝑠├ 𝑞 ⟹ 𝑠. 2. For the following argument given a, b and c below: i. Identify the premises. ii. Write argument forms. 24  iii. Check the validity. a. If he studies medicine, he will get a good job. If he gets a good job, he will get a good wage. He did not get a good wage. Therefore, he did not study medicine. b. If the team is late, then it cannot play the game. If the referee is here, then the team is can play the game. The team is late. Therefore, the referee is not here. c. If the professor offers chocolate for an answer, you answer the professor’s question. The professor offers chocolate for an answer. Therefore, you answer the professor’s question 3. Give formal proof to show that the following argument forms are valid. a. 𝑝 ⟹ 𝑞, 𝑞 ├ 𝑝. b. 𝑝 ⟹ 𝑞, 𝑝, 𝑟 ⟹ 𝑞 ├ 𝑟. c. 𝑝 ⟹ 𝑞, 𝑟 ⟹ 𝑞 ├ 𝑟 ⟹ 𝑝. d. 𝑟 ∧ 𝑠, (𝑠 ⟹ 𝑝) ⟹ 𝑟 ├ 𝑝. e. 𝑝 ⟹, 𝑝 ⟹ 𝑟, 𝑟 ⟹ 𝑠 ├ 𝑞 ⟹ 𝑠. f. 𝑝 ∨ 𝑞, 𝑟 ⟹ 𝑝, 𝑟 ├ 𝑞. g. 𝑝 ∧ 𝑞, (𝑞 ∨ 𝑟) ⟹ 𝑝 ├ 𝑟. h. 𝑝 ⟹ (𝑞 ∨ 𝑟), 𝑟, 𝑝 ├ 𝑞. i. 𝑞 ⟹ 𝑝, 𝑟 ⟹ 𝑝, 𝑞 ├ 𝑟. 4. Prove the following are valid arguments by giving formal proof. a. If the rain does not come, the crops are ruined and the people will starve. The crops are not ruined or the people will not starve. Therefore, the rain comes. b. If the team is late, then it cannot play the game. If the referee is here then the team can play the game. The team is late. Therefore, the referee is not here. 1.4. Set theory In this section, we study some part of set theory especially description of sets, Venn diagrams and operations of sets. Section objectives: After completing this section, students will be able to:-  Explain the concept of set.  Describe sets in different ways.  Identify operations of sets.  Illustrate sets using Venn diagrams. 25  1.4.1. The concept of a set The term set is an undefined term, just as a point and a line are undefined terms in geometry. However, the concept of a set permeates every aspect of mathematics. Set theory underlies the language and concepts of modern mathematics. The term set refers to a well-defined collection of objects that share a certain property or certain properties. The term “well-defined” here means that the set is described in such a way that one can decide whether or not a given object belongs in the set. If 𝐴 is a set, then the objects of the collection 𝐴 are called the elements or members of the set 𝐴. If 𝑥 is an element of the set 𝐴, we write 𝑥 ∈ 𝐴. If 𝑥 is not an element of the set 𝐴, we write 𝑥 ∉ 𝐴. As a convention, we use capital letters to denote the names of sets and lowercase letters for elements of a set. Note that for each objects 𝑥 and each set 𝐴, exactly one of 𝑥 𝐴 or 𝑥 𝐴 but not both must be true. 1.4.2. Description of sets Sets are described or characterized by one of the following four different ways. 1. Verbal Method In this method, an ordinary English statement with minimum mathematical symbolization of the property of the elements is used to describe a set. Actually, the statement could be in any language. Example 1.23: a. The set of counting numbers less than ten. b. The set of letters in the word “Addis Ababa.” c. The set of all countries in Africa. 2. Roster/Complete Listing Method If the elements of a set can all be listed, we list them all between a pair of braces without repetition separating by commas, and without concern about the order of their appearance. Such a method of describing a set is called the roster/complete listing method. Examples 1.24: a. The set of vowels in English alphabet may also be described as {𝑎, 𝑒, 𝑖, 𝑜, 𝑢}. b. The set of positive factors of 24 is also described as {1, 2, 3, 4, 6, 8, 12, 24}. Remark: i. We agree on the convention that the order of writing the elements in the list is immaterial. As a result the sets {𝑎, 𝑏, 𝑐}, {𝑏, 𝑐, 𝑎} and {𝑐, 𝑎, 𝑏} contain the same elements, namely 𝑎, 𝑏 and 𝑐. ii. The set {𝑎, 𝑎, 𝑏, 𝑏, 𝑏} contains just two distinct elements; namely 𝑎 and 𝑏, hence it is the same set as {𝑎, 𝑏}. We list distinct elements without repetition. 26 Example 1.25: a. Let 𝐴 = {𝑎, 𝑏, {𝑐}}. Elements of 𝐴 are 𝑎, 𝑏 and {𝑐}. Notice that 𝑐 and {𝑐} are different objects. Here {𝑐} ∈ 𝐴 but 𝑐 ∉ 𝐴. b. Let 𝐵 = {{𝑎}}. The only element of 𝐵 is {𝑎}. But 𝑎 ∉ 𝐵. c. Let 𝐶 = {𝑎, 𝑏, {𝑎, 𝑏}, {𝑎, {𝑎}}}. Then C has four elements. The readers are invited to write down all the elements of C. 3. Partial Listing Method In many occasions, the number of elements of a set may be too large to list them all; and in other occasions there may not be an end to the list. In such cases we look for a common property of the elements and describe the set by partially listing the elements. More precisely, if the common property is simple that it can easily be identified from a list of the first few elements, then with in a pair of braces, we list these few elements followed (or preceded) by exactly three dotes and possibly by one last element. The following are such instances of describing sets by partial listing method. Example 1.26: a. The set of all counting numbers is ℕ = {1, 2, 3, 4, … }. b. The set of non-positive integers is {… , −4, −3, −2, −1, 0}. c. The set of multiples of 5 is {… , −15, −10, −5, 0 5, 10, 15, … }. d. The set of odd integers less than 100 is {… , −3, −1, 1, 3, 5, … 99}. 4. Set-builder Method When all the elements satisfy a common property 𝑃, we express the situation as an open proposition 𝑃(𝑥) and describe the set using a method called the Set-builder Method as follows: 𝐴 = {𝑥 | 𝑃(𝑥)} 𝑜𝑟 𝐴 = {𝑥: 𝑃(𝑥)} We read it as “𝐴 is equal to the set of all 𝑥’s such that 𝑃(𝑥) is true.” Here the bar “| ‟ and the colon “ ” mean “such that.” Notice that the letter 𝑥 is only a place holder and can be replaced throughout by other letters. So, for a property 𝑃, the set {𝑥 | 𝑃(𝑥)}, {𝑡 | 𝑃(𝑡)} and {𝑦 |𝑃(𝑦)} are all the same set. Example 1.27: The following sets are described using the set-builder method. a. 𝐴 = {𝑥 | 𝑥 is a vowel in the English alphabet}. b. 𝐵 = {𝑡 | 𝑡 is an even integer}. c. 𝐶 = {𝑛 | 𝑛 is a natural number and 2𝑛 – 15 is negative}. d. 𝐷 = {𝑦| 𝑦 2 – 𝑦 – 6 = 0}. e. 𝐸 = {𝑥 | 𝑥 is an integer and 𝑥 – 1 < 0 ⟹ 𝑥 2 – 4 > 0}. Exercise: Express each of the above by using either the complete or the partial listing method. Definition 1.10: The set which has no element is called the empty (or null) set and is denoted by 𝜙 or {}. 27 Example 1.28: The set of 𝑥 ∈ ℝ such that 𝑥 2 + 1 = 0 is an empty set. Relationships between two sets Definition 1.11: Set 𝐵 is said to be a subset of set 𝐴 (or is contained in 𝐴), denoted by 𝐵 ⊆ 𝐴, if every element of 𝐵 is an element of 𝐴, i.e., (∀𝑥)(𝑥 ∈ 𝐵 ⟹ 𝑥 ∈ 𝐴). It follows from the definition that set 𝐵 is not a subset of set 𝐴 if at least one element of 𝐵 is not an element of 𝐴. i.e., 𝐵 ⊈ 𝐴 ⟺ (∃𝑥)(𝑥 ∈ 𝐵 ⟹ 𝑥 ∉ 𝐴). In such cases we write 𝐵 ⊈ 𝐴 or 𝐴 ⊉ 𝐵. Remarks: For any set 𝐴, 𝜙 ⊆ 𝐴 and 𝐴 ⊆ 𝐴. Example 1.29: a. If 𝐴 = {𝑎, 𝑏}, 𝐵 = {𝑎, 𝑏, 𝑐} and 𝐶 = {𝑎, 𝑏, 𝑑}, then 𝐴 ⊆ 𝐵 and 𝐴 ⊆ 𝐶. On the other hand, it is clear that: 𝐵 ⊈ 𝐴, 𝐵 ⊈ 𝐶 and 𝐶 ⊈ 𝐵. b. If 𝑆 = {𝑥 | 𝑥 is a multiple of 6} and 𝑇 = {𝑥 | 𝑥 is even integer}, then 𝑆 ⊆ 𝑇 since every multiple of 6 is even. However, 2 ∈ 𝑇 while 2 ∉ 𝑆. Thus 𝑇 ⊈ 𝑆. c. If 𝐴 = {𝑎, {𝑏}}, then {𝑎} ⊆ 𝐴and {{𝑏}} ⊆ 𝐴. On the other hand, since 𝑏 ∉ 𝐴, {𝑏} ⊈ 𝐴, and {a, 𝑏} ⊈ 𝐴. Definition 1.12: Sets 𝐴 and 𝐵 are said to be equal if they contain exactly the same elements. In this case, we write 𝐴 = 𝐵. That is, (∀𝑥)(𝑥 ∈ 𝐵 ⟺ 𝑥 ∈ 𝐴). Example 1.30: a. The sets {1, 2, 3}, {2, 1, 3}, {1, 3, 2} are all equal. b. {x | x is a counting number} = {x | x is a positive integer} Definition 1.13: Set 𝐴 is said to be a proper subset of set 𝐵 if every element of 𝐴 is also an element of 𝐵, but 𝐵 has at least one element that is not in 𝐴. In this case, we write 𝐴 ⊂ 𝐵. We also say 𝐵 is a proper super set of A, and write 𝐵 ⊃ 𝐴. It is clear that 𝐴 ⊂ 𝐵 ⟺ [(∀𝑥)(𝑥 ∈ 𝐴 ⟹ 𝑥 ∈ 𝐵) ∧ (𝐴 ≠ 𝐵)]. Remark: Some authors do not use the symbol. Instead they use the symbol for both subset and proper subset. In this material, we prefer to use the notations commonly used in high school mathematics, and we continue using and differently, namely for subset and proper subset, respectively. Definition 1.14: Let 𝐴 be a set. The power set of 𝐴, dented by 𝑃(𝐴), is the set whose elements are all subsets of 𝐴. That is, 𝑃(𝐴) = {𝐵: 𝐵 ⊆ 𝐴}. 28 Example 1.31: Let 𝐴 = {𝑥, 𝑦, 𝑧}. As noted before, 𝜙 and 𝐴 are subset of 𝐴. Moreover, {𝑥}, {𝑦}, {𝑧}, {𝑥, 𝑦}, {𝑥, 𝑧} and {𝑦, 𝑧} are also subsets of 𝐴. Therefore, 𝑃(𝐴) = {𝜙, {𝑥}, {𝑦}, {𝑧}, {𝑥, 𝑦}, {𝑥, 𝑧}, {𝑦, 𝑧}, 𝐴}. Frequently it is necessary to limit the topic of discussion to elements of a certain fixed set and regard all sets under consideration as a subset of this fixed set. We call this set the universal set or the universe and denoted by 𝑼. Exercises 1. Which of the following are sets? a. 1,2,3 b. {1,2},3 c. {{1},2},3 d. {1,{2},3} e. {1,2,a,b}. 2. Which of the following sets can be described in complete listing, partial listing and/or set-builder methods? Describe each set by at least one of the three methods. a. The set of the first 10 letters in the English alphabet. b. The set of all countries in the world. c. The set of students of Addis Ababa University in the 2018/2019 academic year. d. The set of positive multiples of 5. e. The set of all horses with six legs. 3. Write each of the following sets by listing its elements within braces. a. 𝐴 = {𝑥 ∈ ℤ: −4 < 𝑥 ≤ 4} b. 𝐵 = {𝑥 ∈ ℤ: 𝑥 2 < 5} c. 𝐶 = {𝑥 ∈ ℕ: 𝑥 3 < 5} d. 𝐷 = {𝑥 ∈ ℝ: 𝑥 2 − 𝑥 = 0} e. 𝐸 = {𝑥 ∈ ℝ: 𝑥 2 + 1 = 0}. 4. Let 𝐴 be the set of positive even integers less than 15. Find the truth value of each of the following. a. 15 ∈ 𝐴 b. −16 ∈ 𝐴 c. 𝜙 ∈ 𝐴 d. 12 ⊂ 𝐴 e. {2, 8,14}𝐴 f. {2,3,4} ⊆ 𝐴 g. {2,4} ∈ 𝐴 h. 𝜙 ⊂ 𝐴 29  i. {246} ⊆ 𝐴 5. Find the truth value of each of the following and justify your conclusion. a. 𝜙 ⊆ 𝜙 b. {1,2} ⊆ {1,2} c. 𝜙 ∈ 𝐴 for any set A d. {𝜙} ⊆ 𝐴, for any set A e. 5, 7 ⊆ {5, 6, 7, 8} f. 𝜙 ∈ {{𝜙}} g. For any set 𝐴, 𝐴 ⊂ 𝐴 h. {𝜙} = 𝜙 6. For each of the following set, find its power set. a. {𝑎𝑏} b. {1, 1.5} c. {𝑎, 𝑏} d. {𝑎, 0.5, 𝑥} 7. How many subsets and proper subsets do the sets that contain exactly 1, 2, 3, 4, 8, 10 and 20 elements have? 8. If 𝑛 is a whole number, use your observation in Problems 6and 7 to discover a formula for the number of subsets of a set with 𝑛 elements. How many of these are proper subsets of the set? 9. Is there a set A with exactly the following indicated property? a. Only one subset b. Only one proper subset c. Exactly 3 proper subsets d. Exactly 4 subsets e. Exactly 6 proper subsets f. Exactly 30 subsets g. Exactly 14 proper subsets h. Exactly 15 proper subsets 10. How many elements does A contain if it has: a. 64 subsets? b. 31 proper subsets? c. No proper subset? d. 255 proper subsets? 11. Find the truth value of each of the following. a. 𝜙 ∈ 𝑃(𝜙) b. 𝐹𝑜𝑟 𝑎𝑛𝑦 𝑠𝑒𝑡 𝐴, 𝜙 ⊆ 𝑃(𝐴) 30  c. 𝐹𝑜𝑟 𝑎𝑛𝑦 𝑠𝑒𝑡 𝐴, 𝐴 ∈ 𝑃(𝐴) d. 𝐹𝑜𝑟 𝑎𝑛𝑦 𝑠𝑒𝑡 𝐴, 𝐴 ⊂ 𝑃(𝐴). 12. For any three sets 𝐴, 𝐵 and 𝐶, prove that: a. If 𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐶, then 𝐴 ⊆ 𝐶. b. If 𝐴 ⊂ 𝐵 and 𝐵 ⊂ 𝐶, then 𝐴 ⊂ 𝐶. 1.4.3. Set Operations and Venn diagrams Given two subsets 𝐴 and 𝐵 of a universal set 𝑈, new sets can be formed using 𝐴 and 𝐵 in many ways, such as taking common elements or non-common elements, and putting everything together. Such processes of forming new sets are called set operations. In this section, three most important operations, namely union, intersection and complement are discussed. Definition 1.15: The union of two sets 𝐴 and 𝐵, denoted by 𝐴 ∪ 𝐵, is the set of all elements that are either in 𝐴 or in 𝐵 (or in both sets). That is, 𝐴 ∪ 𝐵 = {𝑥: (𝑥 ∈ 𝐴) ∨ (𝑥 ∈ 𝐵)}. As easily seen the union operator “ ” in the theory of set is the counterpart of the logical operator “ ”. Definition 1.16: The intersection of two sets 𝐴 and 𝐵, denoted by 𝐴 ∩ 𝐵, is the set of all elements that are in 𝐴 and 𝐵. That is, 𝐴 ∩ 𝐵 = {𝑥: (𝑥 ∈ 𝐴) ∧ (𝑥 ∈ 𝐵)}. As suggested by definition 1.15, the intersection operator “ ” in the theory of sets is the counterpart of the logical operator “ ”. Note: - Two sets 𝐴 and 𝐵 are said to be disjoint sets if 𝐴 ∩ 𝐵 = 𝜙. Example 1.32: a. Let 𝐴 = {0, 1, 3, 5, 6} and 𝐵 = {1, 2, 3, 4, 6, 7}. Then, 𝐴 ∪ 𝐵 = {0, 1, 2, 3, 4, 5, 6, 7} and 𝐴 ∩ 𝐵 = {1, 3, 6}. b. Let 𝐴 = The set of positive even integers, and 𝐵 = The set of positive multiples of 3. Then, 𝐴 ∪ 𝐵 = {𝑥: 𝑥 is a positive intger that is either even or a multiple of 3} = {2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, … } 𝐴 ∩ 𝐵 = {𝑥 | 𝑥 is a positive integer that is both even and multiple of 3} = {6, 12, 18, 24, … } = {𝑥 | 𝑥 is a positive multiple of 6. } 31 Definition 1.17: The difference between two sets 𝐴 and 𝐵, denoted by 𝐴 − 𝐵, is the of all elements in 𝐴 and not in 𝐵; this set is also called the relative complement of 𝐵 with respect to 𝐴. Symbolically, 𝐴 − 𝐵 = {𝑥: 𝑥 ∈ 𝐴 ∧ 𝑥 ∉ 𝐵}. Example 1.33: If = {1,3,5}, 𝐵 = {1,2}, then 𝐴 − 𝐵 = {3,5} and 𝐵 − 𝐴 = {2}. Note: The above example shows that, in general, 𝐴 − 𝐵 are 𝐵 − 𝐴 disjoint. Definition 1.18: Let 𝐴 be a subset of a universal set 𝑈. The absolute complement (or simply 𝑐 ̅ ), is defined to be the set of all elements of 𝑈 that are not in complement) of 𝐴, denoted by 𝐴′ (or 𝐴 or 𝐴 𝐴. That is, 𝐴′ = {𝑥: 𝑥 ∈ 𝑈 ∧ 𝑥 ∉ 𝐴} or 𝑥 ∈ 𝐴′ ⟺ 𝑥 ∉ 𝐴 ⟺ (𝑥 ∈ 𝐴). Notice that taking the absolute complement of 𝐴 is the same as finding the relative complement of 𝐴 with respect to the universal set 𝑈. That is, 𝐴′ = 𝑈 − 𝐴. Example 1.34: a. If 𝑈 = {0,1,2,3,4}, and if 𝐴 = {3,4}, then 𝐴′ = {3,4}. b. Let 𝑈 = {1, 2, 3, … , 12} 𝐴 = {𝑥 | 𝑥 𝑖𝑠 𝑎 𝑝𝑜𝑠𝑖𝑡𝑖𝑣𝑒 𝑓𝑎𝑐𝑡𝑜𝑟 𝑜𝑓 12} and 𝐵 = {𝑥 | 𝑥 𝑖𝑠 𝑎𝑛 𝑜𝑑𝑑 𝑖𝑛𝑡𝑒𝑔𝑒𝑟 𝑖𝑛 𝑈}. Then, 𝐴 = {5, 7, 8, 9, 10, 11}, 𝐵 = {2, 4, 6, 8, 10, 12}, (𝐴 ∪ 𝐵) = (8, 10}, 𝐴 ∪ 𝐵 = {2, 4, 5, 6, … , 12}, 𝐴 ∩ 𝐵 = {8, 10}, and (𝐴\𝐵) = {1, 3, 5, 7, 8, 9, 10, 11}. c. Let 𝑈 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ}, 𝐴 = {𝑎, 𝑒, 𝑔, ℎ} and 𝐵 = {𝑏, 𝑐, 𝑒, 𝑓, ℎ}. Then 𝐴 = {𝑏, 𝑐, 𝑑, 𝑓}, 𝐵 = {𝑎, 𝑑, 𝑔}, 𝐵 – 𝐴 = {𝑏, 𝑐, 𝑓}, 𝐴 – 𝐵 = {𝑎, 𝑔}, and (𝐴 ∪ 𝐵)′ = {𝑑}. Find (𝐴 ∩ 𝐵)′, 𝐴 ∩ 𝐵′, 𝐴 ∪ 𝐵′. Which of these are equal? Theorem 1.1: For any two sets 𝐴 and 𝐵, each of the following holds. 1. (𝐴) = 𝐴. 2. 𝐴 = 𝑈 – 𝐴. 3. 𝐴 – 𝐵 = 𝐴  𝐵′. 4. (𝐴 𝐵) = 𝐴𝐵′. 5. (𝐴 𝐵) = 𝐴𝐵′. 6. 𝐴 ⊆ 𝐵 ⟺ 𝐵′ ⊆ 𝐴′. 32 Now we define the symmetric difference of two sets. Definition 1.17: The symmetric difference of two sets 𝐴 and 𝐵, denoted by 𝐴Δ𝐵, is the set 𝐴Δ𝐵 = (𝐴 − 𝐵) ∪ (𝐵 − 𝐴). Example 1.35: Let 𝑈 = {1,2,3, … ,10} be the universal set, 𝐴 = {2,4,6,8,9,10} and 𝐵 = {3,5,7,9}. Then 𝐵 − 𝐴 = {3,5,7} and 𝐴 − 𝐵 = {2,4,6,8,10}. Thus 𝐴ΔB = {2,3,4,5,6,7,8,10}. Theorem 1.2: For any three sets 𝐴, 𝐵 and 𝐶, each of the following holds. a. 𝐴 ∪ 𝐵 = 𝐵 ∪ 𝐴. ( is commutative) b. 𝐴 ∩ 𝐵 = 𝐵 ∩ 𝐴. ( is commutative) c. (𝐴 ∪ 𝐵) ∪ 𝐶 = 𝐴 ∪ (𝐵 ∪ 𝐶). ( is associative) d. (𝐴 ∩ 𝐵) ∩ 𝐶 = 𝐴 ∩ (𝐵 ∩ 𝐶). ( is associative) e. 𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶). ( is distributive over ) f. 𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶). ( is distributive over ) Let us prove property “e” formally. 𝑥 ∈ 𝐴 ∪ (𝐵 ∩ 𝐶) ⟺ (𝑥 ∈ 𝐴) ∨ (𝑥 ∈ 𝐵 ∩ 𝐶) (definition of ) ⟺ 𝑥 ∈ 𝐴 ∨ (𝑥 ∈ 𝐵 ∧ 𝑥 ∈ 𝐶) (definition of ) ⟺ (𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵) ∧ (𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐶) ( is distributive over ) ⟺ (𝑥 ∈ 𝐴 ∪ 𝐵) ∧ (𝑥 ∈ 𝐴 ∪ 𝐶) (definition of ) ⟺ 𝑥 ∈ (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶)(definition of ) Therefore, we have 𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶). The readers are invited to prove the rest part of theorem (1.2). Venn diagrams While working with sets, it is helpful to use diagrams, called Venn diagrams, to illustrate the relationships involved. A Venn diagram is a schematic or pictorial representative of the sets involved in the discussion. Usually sets are represented as interlocking circles, each of which is enclosed in a rectangle, which represents the universal set 𝑈. In some 33 occasions, we list the elements of set 𝐴 inside the closed curve representing 𝐴. Example 1.36: a. If 𝑈 = {1, 2, 3, 4, 5, 6, 7} and 𝐴 = {2, 4, 6}, then a Venn diagram representation of these two sets looks like the following. b. Let 𝑈 = {𝑥 | 𝑥 is a positive integer less than 13} 𝐴 = {𝑥 | 𝑥 ∈ 𝑈 and 𝑥 is even} 𝐵 = {𝑥 | 𝑥 ∈ 𝑈 and 𝑥 is a multiple of 3}. A Venn diagram representation of these sets is given below. Example 1.37: Let U = The set of one digits numbers A = The set of one digits even numbers B = The set of positive prime numbers less than 10 We illustrate the sets using a Venn diagram as follows. A B U 0 4 3 1 2 6 5 9 8 7 34 a. Illustrate 𝐴 ∩ 𝐵 by a Venn diagram A B U A B : The shaded portion b. Illustrate A’ by a Venn diagram U A A’ : The shaded portion c. Illustrate A\B by using a Venn diagram A B U A \ B: The shaded portion 35 Now we illustrate intersections and unions of sets by Venn diagram. Cases Shaded is 𝐴 ∪ 𝐵 Shaded 𝐴 ∩ 𝐵 Only some A B A B common elements B B 𝐴⊆𝐵 A A A B A B No common element A  B = Exercises 1. If 𝐵 ⊆ 𝐴, 𝐴 ∩ 𝐵 ′ = {1,4,5} and 𝐴 ∪ 𝐵 = {1,2,3,4,5,6}, find 𝐵. 2. Let 𝐴 = {2,4,6,7,8,9}, 𝐵 = {1,3,5,6,10} and 𝐶 ={ 𝑥: 3𝑥 + 6 = 0 or 2𝑥 + 6 = 0}. Find a. 𝐴 ∪ 𝐵. b. Is (𝐴 ∪ 𝐵) ∪ 𝐶 = 𝐴 ∪ (𝐵 ∪ 𝐶)? 3. Suppose 𝑈 = The set of one digit numbers and 𝐴 ={𝑥: 𝑥 is an even natural number less than or equal to 9} Describe each of the sets by complete listing method: a. 𝐴′. b. 𝐴 ∩ 𝐴′. c. 𝐴 ∪ 𝐴′. d. (𝐴′)′ e. 𝜙 − 𝑈. f. 𝜙′ g. 𝑈′ 36  4. Suppose 𝑈 = The set of one digit numbers and 𝐴 ={𝑥: 𝑥 is an even natural number less than or equal to 9} Describe each of the sets by complete listing method: h. 𝐴′. i. 𝐴 ∩ 𝐴′. j. 𝐴 ∪ 𝐴′. k. (𝐴′)′ l. 𝜙 − 𝑈. m. 𝜙′ n. 𝑈′ 5. Use Venn diagram to illustrate the following statements: a. (𝐴 ∪ 𝐵)′ = 𝐴′ ∩ 𝐵′. b.(𝐴 ∩ 𝐵)′ = 𝐴′ ∪ 𝐵′. c. If 𝐴 ⊈ 𝐵, then 𝐴\𝐵 ≠ 𝜙. d.𝐴 ∪ 𝐴′ = 𝑈. 6. Let 𝐴 = {5,7,8,9} and 𝐶 = {6,7,8}. Then show that (𝐴\𝐵)\𝑐 = 𝐴(𝐵\𝐶). 7. Perform each of the following operations. a. 𝜙 ∩ {𝜙} b. {𝜙, {𝜙}} – {{𝜙}} c. {𝜙, {𝜙}} – {𝜙} d. {{{𝜙}}} – 𝜙 8. Let 𝑈 = {2, 3, 6, 8, 9, 11, 13, 15}, 𝐴 = {𝑥|𝑥 is a positive prime factor of 66} 𝐵 ={ 𝑥 ∈ 𝑈| 𝑥 is composite number } and 𝐶 = {𝑥 ∈ 𝑈| 𝑥 – 5 ∈ 𝑈}. Then find each of the following. 𝐴 ∩ 𝐵, (𝐴 ∪ 𝐵) ∩ 𝐶, (𝐴 – 𝐵) ∪ 𝐶, (𝐴 – 𝐵) – 𝐶, 𝐴 – (𝐵 – 𝐶), (𝐴 – 𝐶) – (𝐵 – 𝐴), 𝐴 ∩ 𝐵 ∩ 𝐶 9. Let 𝐴 ∪ 𝐵 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑥, 𝑦, 𝑧} and 𝐴 ∩ 𝐵 = {𝑏, 𝑒, 𝑦}. a. 𝐼𝑓 𝐵 – 𝐴 = {𝑥, 𝑧}, then 𝐴 = ________________________ b. 𝐼𝑓 𝐴 – 𝐵 = 𝜙, then 𝐵 = _________________________ c. 𝐼𝑓 𝐵 = {𝑏, 𝑒, 𝑦, 𝑧}, then 𝐴 – 𝐵 = ____________________ 10. Let 𝑈 = {1, 2, … , 10}, 𝐴 = {3, 5, 6, 8, 10}, 𝐵 = {1, 2, 4, 5, 8, 9}, 𝐶 = {1, 2, 3, 4, 5, 6, 8} and 𝐷 = {2, 3, 5, 7, 8, 9}. Verify each of the following. a. (𝐴 ∪ 𝐵) ∪ 𝐶 = 𝐴 ∪ (𝐵 ∪ 𝐶). b. 𝐴 ∩ (𝐵 ∪ 𝐶 ∪ 𝐷) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶) ∪ (𝐴 ∩ 𝐷). c. (𝐴 ∩ 𝐵 ∩ 𝐶 ∩ 𝐷) = 𝐴 ∪ 𝐵 ∪ 𝐶 ∪ 𝐷. d. 𝐶 – 𝐷 = 𝐶 ∩ 𝐷. e. 𝐴 ∩ (𝐵 ∩ 𝐶) = (𝐴 – 𝐵) ∪ (𝐴 – 𝐶). 37 11. Depending on question No. 10 find. a. 𝐴 ∆ 𝐵. b. 𝐶 ∆ 𝐷. c. (𝐴 ∆ 𝐶)∆ 𝐷. d. (𝐴 ∪ 𝐵)\ (𝐴 ∆ 𝐵). 12. For any two subsets 𝐴 and 𝐵 of a universal set 𝑈, prove that: a. 𝐴 ∆ 𝐵 = 𝐵 ∆ 𝐴. b. 𝐴 ∆ 𝐵 = (𝐴 ∪ 𝐵) – (𝐴 ∩ 𝐵). c. 𝐴 ∆ 𝜙 = 𝐴. d. 𝐴 ∆ 𝐴 = 𝜙. 13. Draw an appropriate Venn diagram to depict each of the following sets. a. U = The set of high school students in Addis Ababa. A = The set of female high school students in Addis Ababa. B = The set of high school anti-AIDS club member students in Addis Ababa. C = The set of high school Nature Club member students in Addis Ababa. b. U = The set of integers. A = The set of even integers. B = The set of odd integers. C = The set of multiples of 3. D = The set of prime numbers. 38  Chapter 2 The Real and the Complex Number System In everyday life, knowingly or unknowingly, we are doing with numbers. Therefore, it will be nice if we get familiarized with numbers. Whatever course (which needs the concept of mathematics) we take, we face with the concept of numbers directly or indirectly. For this purpose, numbers and their basic properties will be introduced under this chapter. Objective of the Chapter At the end of this chapter, students will be able to: - identify the notions of the common sets of numbers - check the closure property of a given set of numbers on some operations - determine the GCF and LCM of natural numbers - apply the principle of mathematical induction to prove different mathematical formulae - determine whether a given real number is rational number or not - to plot complex numbers on the complex plane - to convert a complex number from rectangular form to polar form and vice-versa - to extract roots of complex numbers 2.1 The real number System 2.1.1 The set of natural numbers The history of numbers indicated that the first set of numbers used by the ancient human beings for counting purpose was the set of natural (counting) numbers. Definition 2.1.1 The set of natural numbers is denoted by N and is described as N =  1, 2, 3, 2.1.1.1 Operations on the set of natural numbers i) Addition (+) If two natural numbers a & b are added using the operation “+”, then the sum a+b is also a natural number. If the sum of the two natural numbers a & b is denoted by c, then we can write the operation as: c = a+b, where c is called the sum and a & b are called terms. Example: 3+8 = 11, here 11 is the sum whereas 3 & 8 are terms. ii) Multiplication (  ) If two natural numbers a & b are multiplied using the operation “  ”, then the product a  b is also a natural number. If the product of the two natural numbers a & b is denoted by c, then we can write the operation as: c = a  b, where c is called the product and a & b are called factors. Example 2.1.3: 3  4 = 12, here 12 is the product whereas 3 & 4 are factors. 39 Properties of addition and multiplication on the set of natural numbers i. For any two natural numbers a & b, the sum a+b is also a natural number. For instance in the above example, 3 and 8 are natural numbers, their sum 11 is also a natural number. In general, we say that the set of natural numbers is closed under addition. ii. For any two natural numbers a & b, a + b = b + a. Example 2.1.1: 3+8 = 8+3 = 11. In general, we say that addition is commutative on the set of natural numbers. iii. For any three natural numbers a, b & c, (a+b)+c = a +(b+c). Example 2.1.2: (3+8)+6 = 3+(8+6) = 17. In general, we say that addition is associative on the set of natural numbers. iv. For any two natural numbers a & b, the product a  b is also a natural number. For instance in the above example, 3 and 4 are natural numbers, their product 12 is also a natural number. In general, we say that the set of natural numbers is closed under multiplication. v. For any two natural numbers a & b, a  b = b  a. Example 2.1.4: 3  4 = 4  3 = 12. In general, we say that multiplication is commutative on the set of natural numbers. vi. For any three natural numbers a, b & c, (a  b)  c = a  (b  c). Example 2.1.5: (2  4)  5 = 2  (4  5) = 40. In general, we say that multiplication is associative on the set of natural numbers. vi. For any natural number a, it holds that a  1 = 1  a = a. Example 2.1.6: 6  1 = 1  6 = 6. In general, we say that multiplication has an identity element on the set of natural numbers and 1 is the identity element. vii. For any three natural numbers a, b & c, a  (b+c) = (a  b)+(a  c). Example 2.1.7: 3  (5+7) = (3  5)+ (3  7) = 36. In general, we say that multiplication is distributive over addition on the set of natural numbers. Note: Consider two numbers a and b, we say a is greater than b denoted by a  b if a – b is positive. 2.1.1.2 Order Relation in N i) Transitive property: For any three natural numbers a, b & c, a  b & b  c  a  c ii) Addition property: For any three natural numbers a, b & c, a  b  a  c  b  c iii) Multiplication property: For any three natural numbers a, b and c, a  b  ac  bc iv) Law of trichotomy For any two natural numbers a & b we have a  b or a  b or a  b. 40 2.1.1.3 Factors of a number Definition 2.2 If a, b, c  N such that ab  c , then a & b are factors (divisors) of c and c is called product (multiple) of a & b. Example 2.8: Find the factors of 15. Solution: Factors of 15 are 1, 3, 5, 15. Or we can write it as : F15   1, 3, 5, 15  Definition 2.3 A number a  N is said to be i. Even if it is divisible by 2. ii. Odd if it is not divisible by 2. iii. Prime if it has only two factors (1 and itself). iv. Composite: if it has three or more factors. Example 2.9: 2, 4, 6,... are even numbers Example 2.10: 1, 3, 5,... are odd numbers Example 2.11: 2, 3, 5,... are prime numbers Example 2.12: 4, 6, 8, 9,... are composite numbers Remark: 1 is neither prime nor composite. 2.1.1.5 Prime Factorization Definition 2.4 Prime factorization of a composite number is the product of all its prime factors. Example 2.9: a) 6  2  3 b) 30  2  3  5 c) 12  2  2  3  2 2  3 d ) 8  2  2  2  2 3 e) 180  2 2  32  5 Fundamental Theorem of Arithmetic: Every composite number can be expressed as a product of its prime factors. This factorization is unique except the order of the factors. 41 2.1.1.6 Greatest Common Factor (GCF) Definition 2.5 The greatest common factor (GCF) of two numbers a & b is denoted by GCF (a, b) and is the greatest number which is a factor of each of the given number. Note: If the GCF of two numbers is 1, then the numbers are called relatively prime. Example 2.10: Consider the two numbers 24 and 60. Now F24   1, 2, 3, 4, 6, 8, 12, 24  and F60   1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60  Next F24  F60   1, 2, 3, 4, 6, 12  from which 12 is the greatest. Therefore, GCF(24, 60) = 12. This method of finding the GCF of two or more numbers is usually lengthy and time consuming. Hence an alternative method (Prime factorization method) is provided as below: Step 1: Find the prime factorization of each of the natural numbers Step 2: Form the GCF of the given numbers as the product of every factor that appears in each of the prime factorization but take the least number of times it appears. Example 2.11: Consider the two numbers 24 and 60. Step1 : 24  2 3  3 60  2 2  3  5 Step 2: The factors that appear in both cases are 2 and 3, but take the numbers with the least number of times.  GCF (24, 60 )  2 2  3  12 Example 2.12: Consider the three numbers 20, 80 and 450. Step1 : 20  2 2  5 80  2 4  5 450  2  3 2  5 2 Step 2: The factors that appear in all cases are 2 and 5, but take the numbers with the least number of times.  GCF (20, 80, 450 )  2  5  10 2.1.1.7 Least Common Multiple (LCM) Definition 2.6 The least common multiple (LCM) of two numbers a & b is denoted by LCM (a, b) and is the least number which is a multiple of each of the given number. Example 2.13: Consider the two numbers 18 and 24. 42 Now M 18   18, 36, 54, 72, 90, 108 , 126 , 144 ,   and M 24   24, 48, 72, 96,120 , 144 ,   Next M 18  M 24   72, 144 ,   from which 72 is the least. Therefore, LCM (18, 24) = 72. This method of finding the LCM of two or more numbers is usually lengthy and time consuming. Hence an alternative method (Prime factorization method) is provided as below: Step 1: Find the prime factorization of each of the natural numbers Step 2: Form the LCM of the given numbers as the product of every factor that appears in any of the prime factorization but take the highest number of times it appears. Example 2.14: Consider the two numbers 18 and 24. Step1 : 18  2 2  3 2 24  2 3  3 Step 2: The factors that appear in any case are 2 and 3, but take the numbers with the highest number of times.  LCM (18, 24 )  2 3  3 2  72 Example 2.15: Consider the three numbers 20, 80 and 450. Step1 : 20  2 2  5 80  2 4  5 450  2  3 2  5 2 Step 2: The factors that appear in any cases are 2 , 3 and 5, but take the numbers with the highest number of times.  LCM (20, 80, 450 )  2 4  3 2  5 2  3600 2.1.1.8 Well ordering Principle in the set of natural numbers Definition 2.7 Every non-empty subset of the set of natural numbers has smallest (least) element. Example 2.16 A   2 , 3, 4,    N. smallest element of A  2. Note: The set of counting numbers including zero is called the set of whole numbers and is denoted by W. i.e W = 0, 1, 2, 3, 43 2.1.1.9 Principle of Mathematical Induction Mathematical induction is one of the most important techniques used to prove in mathematics. It is used to check conjectures about the outcome of processes that occur repeatedly according to definite patterns. We will introduce the technique with examples. For a given assertion involving a natural number n, if i. the assertion is true for n = 1 (usually). ii. it is true for n = k+1, whenever it is true for n = k (k  1), then the assertion is true for every natural number n. The method is used to prove different propositions involving positive integers using three steps: Step1: Prove that Tk (usually T1 ) holds true. Step 2: Assume that Tk for k = n is true. Step 3: Show that Tk is true for k = n+1. Example 2.17 Show that 1  3  5    (2n  1)  n 2. Proof: Step1. For n  1, 1  12 which is true. Step2. Assume that it is true for n  k i.e. 1  3  5    (2k  1)  k 2. Step3. We should show that it is true for n  k  1. Claim :1  3  5    (2k  1)  (2k  1)  (k  1) 2 Now 1  3  5    (2k  1)  (2k  1)  k 2  (2k  1)  k 2  2k  1  (k  1) 2 which is the required result.  It is true for any natural number n. n (n  1) Example 2.18 Show that 1  2  3    (n) . 2 Proof: 1(1  1) Step1. For n  1, 1  which is true. 2 Step2. Assume that it is true for n  k k ( k  1) i.e. 1  2  3    ( k ) . 2 Step3. We should show that it is true for n  k  1 44  ( k  1) ( k  2) Claim :1  2  3    ( k )  (k  1) . 2 k ( k  1) Now 1  2  3    ( k )  ( k  1)   ( k  1) 2 k ( k  1)  2 ( k  1)  2 ( k  1)( k  2)  which is the required result. 2  It is true for any natural number n. Example 2.19 Show that 5 n  6 n  9 n for n  2. Proof: Step1. For n  2, 61  81 which is true Step2. Assume that it is true for n  k. i.e. 5 k  6 k  9 k. Step3. We should show that it is true for n  k  1 Claim : 5 k 1  6 k 1  9 k 1. Now 5 k 1  6 k 1  5.5 k  6. 6 k  6.5 k  6. 6 k  6(5 k  6 k )  9 (5 k  6 k )  9(9 k )  9 k 1  5 k 1  6 k 1  9 k 1 which is the required format.  It is true for any natural number n  2. 2.1.2 The set of Integers As the knowledge and interest of human beings increased, it was important and obligatory to extend the natural number system. For instance to solve the equation x+1= 0, the set of natural numbers was not sufficient. Hence the set of integers was developed to satisfy such extended demands. Definition 2.8 The set of integers is dented by Z and described as Z = ...,2,  1, 0, 1, 2,  2.1.2.1 Operations on the set of integers i) Addition (+) 45 If two integers a & b are added using the operation “+”, then the sum a+b is also an integer. If the sum of the two integers a & b is denoted by c, then we can write the operation as: c = a+b, where c is called the sum and a & b are called terms. Example 2.20: 4+9 = 13, here 13 is the sum whereas 4 & 9 are terms. ii) Subtraction (  ) For any two integers a & b, the operation of subtracting b from a, denoted by a  b is defined by a  b  a  (b). This means that subtracting b from a is equivalent to adding the additive inverse of b to a. Example 2.21: 7  5  7  (5)  2 iii) Multiplication (  ) If two integers a & b are multiplied using the operation “  ”, then the product a  b is also an integer. If the product of the two integers a & b is denoted by c, then we can write the operation as: c = a  b, where c is called the product and a & b are called factors. Example 2.22: 4  7 = 28, here 28 is the product whereas 4 & 7 are factors. Properties of addition and multiplic