MAT1830 Textbook: Discrete Mathematics PDF

Contents Lecture 1: What is MAT1830 about? Lecture 2: Divisors and primes Lecture 3: Congruences Lecture 4: Logic Lecture 5: Tautologies and logical equivalence Lecture 6: Rules of inference Lecture 7: Predicates and quantifiers Lecture 8: Predicate logic Lecture 9: Mathematical i...

Contents Lecture 1: What is MAT1830 about? Lecture 2: Divisors and primes Lecture 3: Congruences Lecture 4: Logic Lecture 5: Tautologies and logical equivalence Lecture 6: Rules of inference Lecture 7: Predicates and quantifiers Lecture 8: Predicate logic Lecture 9: Mathematical induction Lecture 10: Induction and well-ordering Lecture 11: Sets Lecture 12: Operations on sets Lecture 13: Functions Lecture 14: Examples of functions Lecture 15: Composition and inversion Lecture 16: Relations Lecture 17: Equivalence relations Lecture 18: Order relations Lecture 19: Selections and arrangements Lecture 20: Pascal’s triangle Lecture 21: Probability Lecture 22: Conditional probability and Bayes’ theorem Lecture 23: Random variables Lecture 24: Expectation and variance Lecture 25: Discrete distributions Lecture 26: Recursion Lecture 27: Recursive algorithms Lecture 28: Recursion, lists and sequences Lecture 29: Graphs Lecture 30: Walks, paths and trails Lecture 31: Degree Lecture 32: Trees Lecture 33: Trees, queues and stacks  Lecture 1: What is MAT1830 about? Discrete mathematics studies objects which we’ll see, even if you are pretty sure that some- have distinct separated values (e.g. integers), as thing is true, it can be really useful to have a opposed to objects which vary smoothly (e.g. proof of it, for a number of reasons. real numbers). You can think of it as being “digital” mathematics rather than “analogue” 1.3 Maths in computer science mathematics. Discrete mathematics is particularly impor- As we mentioned above, maths and computer tant in computer science and the two fields are science are very closely related. The topics in very closely linked. this course all have many applications to com- This course covers a wide range of topics in puter science. For example: discrete mathematics including the following: Number theory is used in cryptography Numbers to enable secure communication, identity verification, online banking and shopping Logic etc. Induction and recursion Logic is used in digital circuit design and in program control flow. Sets, functions and relations Induction and recursion are used to study Probability algorithms and their effectiveness. Graph theory Functions are important in the theory of programming and relations are vital in 1.1 What to expect database theory and design. What we do here might be a bit different to a lot Probability is vital for understanding ran- of the maths you’ve done in the past. We’ll be domised algorithms and for creating sys- concentrating on really understanding the con- tems to deal with uncertain situations. cepts, rather than simply learning how to solve certain types of questions. Graph theory is used in software which For a lot of the questions we ask, there won’t solves allocation and scheduling problems. be a single fixed procedure you can apply to get the answer. Instead, you’ll have to think care- Questions fully about what the question is asking and try 1.1 What maths that you’ve done in the past to work out what is really going on. Don’t be would count as discrete? What would afraid to try different things, play around, and count as continuous instead? Are there look at examples. grey areas? We’ll also be emphasising the importance of proving results. 1.2 Why might proofs be important to math- ematicians and computer scientists? 1.2 Proofs 1.3 Can you think of other links between A proof is essentially just a water-tight argu- maths and computer science? ment that a certain statement must be true. As  Lecture 2: Divisors and primes Thus to test whether 10001 is prime, say, we We say that integer a divides integer b if only have to see whether any of the√numbers b = qa for some integer q. 2, 3, 4,... 6 100 divide 10001, since 10001 < 101. (The least divisor found is in fact 73, be- Example. 2 divides 6 because 6 = 3 × 2. cause 10001 = 73 × 137.) This is the same as saying that division with This explains a common algorithm for recog- remainder gives remainder 0. Thus a does not nising whether n is prime: try dividing n by √ divide b when the remainder is 6= 0. a = 2, 3,... while a 6 n. The algorithm is written with a boolean vari- Example. 3 does not divide 14 because it leaves able prime, and n is prime if prime = T (true) remainder 2: 14 = 4 × 3 + 2. when the algorithm terminates. When a divides b we also say: a is a divisor of b, assign a the value 2. a is a factor of b, assign prime the value T. √ b is divisible by a, while a 6 n and prime= T b is a multiple of a. if a divides n give prime the value F 2.1 Primes else increase the value of a by 1. A positive integer p > 1 is a prime if its only positive integer divisors are 1 and p. Thus the first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,... 2.3 Finding divisors The number 1 is not counted as a prime, as this would spoil the This algorithm also finds a prime divisor of n. Either Fundamental Theorem of Arithmetic. √ the least a 6 n which divides n, Each integer > 1 can be expressed in exactly or, one way, up to order, as a product of primes. √ if we do not find a divisor among the a 6 n, n itself is prime. Example. 210 = 2 × 3 × 5 × 7, and this is the only product of primes which equals 210. This would not be true if 1 was counted as 2.4 The greatest common divisor of a prime, because many factorisations involve 1. two numbers E.g. It is remarkable that we can find the greatest 210 = 1 × 2 × 3 × 5 × 7 = 12 × 2 × 3 × 5 × 7 =... common divisor of positive integers m and n, gcd(m, n), without finding their prime divisors. 2.2 Recognising primes This is done by the famous Euclidean al- If an integer n > 1 has a divisor, it has a divisor gorithm, which repeatedly divides the greater √ √ 6 n, because for any divisor a > n we also number by the smaller, keeping the smaller num- √ have the divisor n/a, which is < n. ber and the remainder.  2.6 Extended Euclidean algorithm Euclidean Algorithm. Input: positive integers m and n with m > n If we have used the Euclidean algorithm to find Output: gcd(m, n) that gcd(m, n) = d, we can “work backwards” a := m, b := n through its steps to find integers a and b such r := remainder when a is divided by b that am + bn = d. while r 6= 0 do Example. For our m = 237, n = 105 example a := b above: b := r r := remainder when a is divided by b end 3= 27 − 1×24 return b 3= 27 − 1(105 − 3×27) = −105 + 4×27 3 = −105 + 4(237 − 2×105) = 4×237 − 9×105 Example. m = 237, n = 105 So we see that a = 4 and b = −9 is a solution in The first values are a = 237, b = 105, this case. so r = 237 − 2 × 105 = 27. Our first line above was a rearrangement of The next values are a = 105, b = 27, the second last line of our original Euclidean al- so r = 105 − 3 × 27 = 24. gorithm working. In the second line we made a The next values are a = 27, b = 24, substitution for 24 based on the second line of so r = 27 − 1 × 24 = 3. our original Euclidean algorithm working. In The next values are a = 24, b = 3, the third line we made a substitution for 27 so r = 24 − 8 × 3 = 0. based on the first line of our original Euclidean Thus the final value of b is 3, which is algorithm working. gcd(237, 105). This can be set out more neatly: Questions 237 = 2 × 105 + 27 2.1 Write down multiples of 13, and multiples 105 = 3 × 27 + 24 of 21, until you find a multiple of 13 and 27 = 1 × 24 + 3 a multiple of 21 which differ by 1. 24 = 8 × 3 + 0 2.2 Can a multiple of 15 and a multiple of 21 differ by 1? If not, what is the small- 2.5 The Euclidean algorithm works! est positive difference between such mul- We start with the precondition m > n > 0. tiples? Then the division theorem tells us there is a re- 2.3 Find gcd(13, 21) and gcd(15, 21), and sug- mainder r < b when a = m is divided by b = n. gest how they are related to the results in Repeating the process gives successively smaller Questions 2.1 and 2.2. remainders, and hence the algorithm eventually returns a value. 2.4 Work out the prime factorisations of 999 That the value returned value is actually and 1000. gcd(m, n) relies on the following fact. 2.5 You should find no common prime factor Fact. If a, b and k are integers, then of 999 and 1000. How could you see this without factorising the numbers? (Hint: a gcd(a − kb, b) = gcd(a, b). common divisor of 1000 and 999 is also a common divisor of... what?) By using this fact repeatedly, we can show that after each execution of the while loop in the al- gorithm gcd(b, r) = gcd(m, n). When the algo- rithm terminates, this means b = gcd(b, 0) = gcd(m, n). (Equivalently, in the neat set out given above, the gcd of the numbers in the last two columns is always gcd(m, n).)  Lecture 3: Congruences We’re used to classifying the integers as ei- Example. ther even or odd. The even integers are those 19 ≡ 13 (mod 6) because 6 divides 19-13 that can be written as 2k for some integer k. The odd integers are those that can be written 12 ≡ 20 (mod 4) because 4 divides 20-12 as 2k + 1 for some integer k. 22 ≡ 13 (mod 3) because 3 divides 22-13 even... , −6, −4, −2, 0, 2, 4, 6,... odd... , −5, −3, −1, 1, 3, 5,... 3.2 Working with congruences When working with congruences modulo some fixed integer n, we can “substitute in” just like This classification is useful because even and we can with equalities. odd integers have particular properties. For ex- ample, the sum of any two odd integers is even. Similarly we can split the integers into three If a ≡ b (mod n) and b ≡ c (mod n), then classes: those that are 3k for some integer k, a ≡ c (mod n). those that are 3k + 1 for some integer k, and those that are 3k + 2 for some integer k. Example. Suppose x ≡ 13 (mod 7). Then x ≡ 6 (mod 7) because 13 ≡ 6 (mod 7). 3k... , −9, −6, −3, 0, 3, 6, 9,... 3k + 1... , −8, −5, −2, 1, 4, 7, 10,... We can add, subtract and multiply congru- 3k + 2... , −7, −4, −1, 2, 5, 8, 11,... ences just like we can with equations. If a1 ≡ b1 (mod n) and a2 ≡ b2 (mod n), then These classes also have particular properties. For example, the sum of an integer in the sec- a1 + a2 ≡ b1 + b2 (mod n) ond class and an integer in the third class will always be in the first class. a1 − a2 ≡ b1 − b2 (mod n) We don’t have to stop with 3. We could di- a1 a2 ≡ b1 b2 (mod n). vide integers into 4 different classes according to their remainders when divided by 4, and so on. Example. If x ≡ 3 (mod 8) and y ≡ 2 (mod 8), then 3.1 Congruences x + y ≡ 5 (mod 8) x − y ≡ 1 (mod 8) Let n > 2 be an integer. We say integers a and b are congruent modulo n and write xy ≡ 6 (mod 8). a ≡ b (mod n) We can also deduce that x + 4 ≡ 7 (mod 8), when n divides a − b. that 4x ≡ 12 (mod 8) and so on, because obvi- ously 4 ≡ 4 (mod 8). Note as well that 4x ≡ 12 (mod 8) can be simplified to 4x ≡ 4 (mod 8).  In some situations we can also “divide 3.4 Modular inverses through” a congruence by an integer. A modular multiplicative inverse of an inte- If a ≡ b (mod n) and d divides a, b and n, ger a modulo n is an integer x such that then a b n ax ≡ 1 (mod n). d ≡ d (mod d ). From the last section we know that such an in- verse will exist if and only if gcd(a, n) = 1. If 3.3 Solving linear congruences inverses do exist then we can find them using the extended Euclidean algorithm (there will Think of a congruence like 7x ≡ 5 (mod 9). This be lots of inverses, but they will all be in one will hold if 9 divides 7x − 5 or in other words if congruence class modulo n). These inverses there is an integer y such that 7x − 5 = 9y. So have important applications to cryptography to solve our original congruence we can find an and random number generation. integer solution to 7x − 9y = 5. Some congruences don’t have solutions. Example. 8 should have a multiplicative in- For example, there is no solution to 10x ≡ verse modulo 45 because gcd(8, 45) = 1. Using 6 (mod 20) because there are no integers x and the extended Euclidean algorithm we see that y such that 10x − 20y = 6. −3 × 45 + 17 × 8 = 1. So 8 × 17 ≡ 1 (mod 45). To find an expression for all the integers x This means that 17 is a multiplicative inverse of that satisfy a congruence like ax ≡ b (mod n), 8 modulo 45. first find d = gcd(a, n) and then act as follows. If d = 1: Find integers x0 and y 0 such that Questions ax − ny 0 = b. The integers x that satisfy the 0 original congruence are exactly those for which 3.1 Are the following true or false? x ≡ x0 (mod n). 6 ≡ 3 (mod 3) If d > 1 and d divides b: The method above will still work but it will only give some 9 ≡ 18 (mod 8) of the solutions. To find all of the solutions, 5x + 6 ≡ 2x (mod 3) first divide through the congruence by d to get 3.2 Prove all of the facts about congruences the equivalent congruence ad x ≡ db (mod nd ) and that were stated in this lecture (use the then use the method above on the new congru- definition of congruence modulo n and the ence. definition of divides). If d doesn’t divide b: The congruence has no solutions. 3.3 Find an expression for all the integers x Example. Find all integers x such that that satisfy 9x ≡ 12 (mod 60). 36x ≡ 10 (mod 114). Using the Euclidean algorithm we find gcd(36, 114) = 6. So 6 divides 36x − 114y for any integers x and y, and consequently 36x − 114y 6= 10. This means that there are no integers x such that 36x ≡ 10 (mod 114). Example. Find all integers x such that 24x ≡ 8 (mod 44). Using the Euclidean algorithm we find gcd(24, 44) = 4. So we divide through by 4 to get the equivalent congruence 6x ≡ 2 (mod 11). Using the extended Euclidean algorithm we see that 2×6−1×11 = 1, and hence 4×6−2×11 = 2. Thus the integers x such that 24x ≡ 8 (mod 44) are exactly the integers x ≡ 4 (mod 11).  Lecture 4: Logic The simplest and most commonly used part Similarly, p ∨ q is true when p is true or q is of logic is the logic of “and”, “or” and “not”, true, but now we have to be more precise, be- which is known as propositional logic. cause “or” has at least two meanings in ordinary A proposition is any sentence which has a speech. definite truth value (true= T or false= F), such as We define ∨ by the truth table 1 + 1 = 2, or p q p∨q 10 is a prime number. T T T but not T F T What is your name? or F T T This sentence is false. F F F Propositions are denoted by letters such as This is the inclusive sense of “p or q” (often writ- p, q, r,... , and they are combined into com- ten “p and/or q” and meaning at least one of p, pound propositions by connectives such as ∧ q is true). (and), ∨ (or) and ¬ (not). Finally, “not” ¬ (also called negation) is de- fined as follows. We define ¬ by the truth table p ¬p 4.1 Connectives ∧, ∨ and ¬ T F ∧, ∨ and ¬ are called “connectives” because they F T can be used to connect two sentences p and q into one. These particular connectives are de- The connectives ∧, ∨ and ¬, are functions of the fined so that they agree with the most com- propositional variables p and q, which can take mon interpretations of the words “and”, “or” the two values T and F. For this reason, ∧, ∨ and “not”. and ¬ are also called truth functions. To define p ∧ q, for example, we only have to say that p ∧ q is true only when p is true and q 4.2 Implication is true. Another important truth function is p → q, We define ∧ by the following truth table: which corresponds to “if p then q” or “p implies q” in ordinary speech. p q p∧q In ordinary speech the value of p → q de- T T T pends only on what happens when p is true. For T F F example to decide whether F T F MCG flooded → the cricket is off F F F it is enough to see what happens when the MCG is flooded. Thus we agree that p → q is true when p is false.  3. If we write 0 for F and 1 for T then ∨ becomes We define → by the truth table the function p q p→q p q p∨q T T T 1 1 0 T F F 1 0 1 F T T 0 1 1 F F T 0 0 0 This is also known as the “mod 2 sum”, because 1 + 1 = 2 ≡ 0 (mod 2). (It could also be called 4.3 Other connectives the “mod 2 difference” because a + b is the same a − b, mod 2). Two other important connectives are ↔ (“if and only if”) and ∨ (“exclusive or”). 4. The mod 2 sum occurs in many homes where The sentence p ↔ q is true exactly when the two switches p, q control the same light. The truth values of p and q agree. truth value of p ∨ q tells whether the light is on or not, and the light can be switched to the op- We define ↔ by the truth table posite state by switching the value of either p or p q p↔q q. T T T Questions T F F F T F 4.1 Which of the following are propositions? F F T 1 + 1 = 3, 1 + 1, 3 divides 7, 3÷7 We could also write p ↔ q as (p → q) ∧ (q → p). 4.2 Let f be the proposition “foo” and let b be We’ll see how to prove this in the next lecture. the proposition “bar”. Write the following The sentence p ∨ q is true exactly when the propositions in symbols, using f, b, → and truth values of p and q disagree. ¬. if foo, then bar. We define ∨ by the truth table bar if foo. p q p∨q bar only if foo. T T F foo implies not bar. T F T foo is sufficient for bar. F T T foo is necessary for bar. F F F 4.3 In the following examples, is the “or” in- tended to be inclusive or exclusive? 4.4 Remarks Would you like coffee or tea? 1. The symbols ∧ and ∨ are intentionally sim- Oranges or lemons are a good source ilar to the symbols ∩ and ∪ for set intersection of vitamin C. and union because He will arrive in a minute or two. x ∈ A ∩ B ⇔ (x ∈ A) ∧ (x ∈ B) x ∈ A ∪ B ⇔ (x ∈ A) ∨ (x ∈ B) (We study sets later.) 2. The “exclusive or” function ∨ is written XOR in some programming languages.  Lecture 5: Tautologies and logical equivalence A major problem in logic is to recognise 5.2 Logical equivalence statements that are “always true” or “always false”. Sentences φ and ψ are logically equivalent if they are the same truth function, which also means 5.1 Tautologies and contradictions φ ↔ ψ is a tautology. This relation between sentences is written φ ⇔ ψ or φ ≡ ψ. A sentence φ in propositional logic is a formula with variables p, q, r,... which can take the val- ues T and F. The possible interpretations of φ are all possible assignments of values to its vari- ables. A sentence in propositional logic is Example. p → q ≡ (¬p) ∨ q We know p → q has the truth table a tautology if it has value T under all interpretations; p q p→q a contradiction if it has value F under T T T all interpretations. T F F F T T We can check whether φ is a tautology, a F F T contradiction, or neither by computing its value for all possible values of its variables. Now (¬p) ∨ q has the truth table p q ¬p (¬p) ∨ q Example. (¬p) ∨ p is a tautology. T T F T The truth table for (¬p) ∨ p is T F F F p ¬p (¬p) ∨ p F T T T T F T F F T T F T T So p → q and (¬p) ∨ q have the same truth So (¬p)∨p has value T under all interpretations, table (looking just at their columns). It follows and thus is a tautology. (It is sometimes known from this that p → q can always be rewritten as the law of the excluded middle). as (¬p) ∨ q. In fact, all truth functions can be expressed in terms of ∧, ∨, and ¬. We can similarly compute the values of any truth function φ, so this is an algorithm for recognising tautologies. However, if φ has n variables, they have 2n sets of values, so the amount of computation grows rapidly with n. One of the biggest unsolved problems of logic This is like finding identities in algebra – one and computer science is to find an efficient algo- uses known equivalences to rearrange, expand rithm for recognising tautologies. and simplify. 5.3 Useful equivalences brackets. Since p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r, we can write either side as p ∨ q ∨ r. This is like The following equivalences are the most fre- p + (q + r) = (p + q) + r = p + q + r in ordinary quently used in this “algebra of logic”. algebra. Equivalence law 3. The distributive laws are used to “expand” p ↔ q ≡ (p → q) ∧ (q → p) combinations of ∧ and ∨. Implication law p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p → q ≡ (¬p) ∨ q is like Double Negation law p(q + r) = pq + pr. ¬¬p ≡ p The other distributive law is not like anything Idempotent laws in ordinary algebra. p∧p≡p 4. Some of these laws are redundant, in the sense p∨p≡p that other laws imply them. For example, the Commutative laws absorption law p∧q ≡q∧p p ∧ (p ∨ q) ≡ p p∨q ≡q∨p follows from the distributive, idempotent, iden- Associative laws tity and annihilation laws: p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r p ∧ (p ∨ q) ≡ (p ∧ p) ∨ (p ∧ q) p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r by distributive law Distributive laws ≡ p ∨ (p ∧ q) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) by idempotent law p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) ≡ (p ∧ T) ∨ (p ∧ q) De Morgan’s laws by identity law ¬(p ∧ q) ≡ (¬p) ∨ (¬q) ≡ p ∧ (T ∨ q) ¬(p ∨ q) ≡ (¬p) ∧ (¬q) by distributive law Identity laws ≡ p∧T p∧T≡p by annihilation law p∨F≡p ≡ p by identity law Annihilation laws p∧F≡F Questions p∨T≡T Inverse laws 5.1 Explain why there are 8 ways to assign truth values to variables p, q, r; 16 ways p ∧ (¬p) ≡ F to assign truth values to variables p, q, r, s; p ∨ (¬p) ≡ T and in general 2n ways to assign truth val- Absorption laws ues to n variables. p ∧ (p ∨ q) ≡ p 5.2 Use truth tables to verify the de Morgan’s p ∨ (p ∧ q) ≡ p laws and absorption laws. 5.3 If p ∨ q is the “exclusive or” discussed last Remarks lecture, see whether it satisfies the dis- 1. The commutative laws are used to rear- tributive laws range terms, as in ordinary algebra. The law p ∨ q ≡ q ∨ p is like p + q = q + p in ordinary p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) algebra, and p ∧ q ≡ q ∧ p is like pq = qp. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) 2. The associative laws are used to remove  Lecture 6: Rules of inference Last time we saw how to recognise tautolo- Example. The contrapositive of gies and logically equivalent sentences by com- “If it’s a bird then it has feathers.” puting their truth tables. Another way is to in- fer new sentences from old by rules of inference. is “If it doesn’t have feathers, then it’s not a bird.” 6.1 Replacement The contrapositive has the same meaning as the Any sentence may be replaced by a logically original statement. equivalent sentence. Any series of such replace- ments therefore leads to a sentence equivalent to Example. On the other hand, the negation of the one we started with. the statement Using replacement is like the usual method of proving identities in algebra – make a series “If it’s a bird then it has feathers.” of replacements until the left hand side is found is equal to the right hand side. “It’s a bird and it doesn’t have feathers.” This is (roughly speaking) the opposite of the Example. Prove that x → y ≡ (¬y) → (¬x). original statement. Note that the negation of an “implies” statement is an “and” statement, x → y ≡ (¬x) ∨ y not another “implies” statement. by implication law ≡ y ∨ (¬x) by commutative law 6.3 Using logic laws ≡ (¬¬y) ∨ (¬x) Example. Prove that p → (q → p) is a tautol- by law of double negation ogy. ≡ (¬y) → (¬x) by implication law p → (q → p) ≡ (¬p) ∨ (q → p) 6.2 Contrapositives by implication law ≡ (¬p) ∨ ((¬q) ∨ p) x → y ≡ (¬y) → (¬x) by implication law (¬y) → (¬x) is the contrapositive of x → y. ≡ (¬p) ∨ (p ∨ (¬q)) by commutative law Example. The contrapositive of ≡ ((¬p) ∨ p) ∨ (¬q) MCG flooded → cricket is off by associative law is ≡ (p ∨ (¬p)) ∨ (¬q) Cricket is on → MCG not flooded. by commutatve law An implication and its contrapositive are ≡ T ∨ (¬q) by inverse law equivalent: they mean the same thing! ≡ T by annihilation law Example. Prove that ((p → q) ∧ p) → q is a Questions tautology. 6.1 The slogan “no pain, no gain” stands for an implication. What is it? ((p → q) ∧ p) → q 6.2 What is the contrapositive of “no pain, no ≡ ¬((p → q) ∧ p) ∨ q gain”? by implication law ≡ (¬(p → q) ∨ (¬p)) ∨ q 6.3 Write the following sentences as implica- by de Morgan’s law tions, and then write their contrapositives. ≡ ¬(p → q) ∨ ((¬p) ∨ q) You can’t make an omelette without by associative law breaking eggs. ≡ ¬(p → q) ∨ (p → q) If n is even, so is n2 by implication law Haste makes waste. ≡ (p → q) ∨ ¬(p → q) 6.4 Show that p → (q → (r → p)) is a tautol- by commutative law ogy using the laws of logic. ≡ T by inverse law 6.5 Find a tautology with n variables which This tautology says that “if p implies q and p is is p → (q → p) for n = 2 and p → true then q is true”. (q → (r → p)) for n = 3. 6.4 Logical consequence A sentence ψ is a logical consequence of a sen- tence φ, if ψ = T whenever φ = T. We write this as φ ⇒ ψ. It is the same to say that φ → ψ is a tautol- ogy, but φ ⇒ ψ makes it clearer that we are dis- cussing a relation between the sentences φ and ψ. Any sentence ψ logically equivalent to φ is a logical consequence of φ, but not all conse- quences of ψ are equivalent to it. Example. p ∧ q ⇒ p p is a logical consequence of p ∧ q, because p = T whenever p ∧ q = T. However, we can have p ∧ q = F when p = T (namely, when q = F). Hence p ∧ q and p are not equivalent. This example shows that ⇒ is not symmet- ric: (p ∧ q) ⇒ p but p ; (p ∧ q) This is where ⇒ differs from ≡, because if φ ≡ ψ then ψ ≡ φ. In fact, we build the relation ≡ from ⇒ the same way ↔ is built from →: φ ≡ ψ means (φ ⇒ ψ) and (ψ ⇒ φ).  Lecture 7: Predicates and quantifiers We get a more expressive language than Another way is to use quantifiers: propositional logic by admitting predicates like ∀ (meaning “for all”) and ∃ (meaning “there exists” or “there is”). P (n), Q(x, y), R(a, b, c) These stand for properties or relations such as Example. ∃nP (n) is the (true) sentence P (n) : n is prime Q(x, y) : x 6 y there exists an n such that n is prime. R(a, b, c) : a + b = c. ∀nP (n) is the (false) sentence Those with one variable, such as “n is prime,” for all n, n is prime. are usually called properties, while those with two or more variables, such as “x 6 y,” are usu- ally called relations. Note that when ∃n is read “there exists an n” we also add a “such that.” 7.1 Predicates A predicate such as “n is prime” is not a proposi- 7.3 Quantifiers and connectives tion because it is neither true nor false. Rather, it is a function P (n) of n with the Boolean val- We can also combine quantifiers with connec- ues T (true) or F (false). In this case, P (n) is a tives from propositional logic. function of natural numbers defined by ( T if n is prime Example. Let Sq(n) be the predicate “n is a P (n) = F otherwise. square,” and let P os(n) be the predicate “n is Similarly, the “x 6 y” predicate is a function of positive” as above. Then we can symbolise the pairs of real numbers, defined by following sentences: ( There is a positive square: T if x 6 y R(x, y) = ∃n(P os(n) ∧ Sq(n)). F otherwise. Since most of mathematics involves properties There is a positive integer which is not a and relations such as these, only a language with square: predicates is adequate for mathematics (and ∃n(P os(n) ∧ ¬Sq(n)) computer science). All squares are positive: ∀n(Sq(n) → P os(n)) 7.2 Building sentences from predi- cates Notice that the “All... are” combination in One way to create a sentence from a predicate English actually involves an implication. This is to replace its variables by constants. For ex- is needed because we are making a claim only ample, when P (n) is the predicate “n is prime,” about squares and the implication serves to P (3) is the sentence “3 is prime.” “narrow down” the set we are examining. 7.4 Alternating quantifiers Remark. Another way to say “you can’t fool all of the people all of the time” is Combinations of quantifiers like ∀x∃y... , “for all x there is a y...” are common in mathe- ∃p∃t¬F (p, t). matics, and can be confusing. It helps to have some examples in mind to recall the difference Questions between ∀x∃y... and ∃y∀x... 7.1 Write “roses are red” in the language of The relation x < y is convenient to illustrate predicate logic, using such combinations; we write x < y as the pred- icate L(x, y) rose(x) for “x is a rose” Then red(x) for “x is red.” ∀x∃yL(x, y) 7.2 If P (n) stands for “n is prime” and E(n) is the (true) sentence stands for “n is even,” what does P (n) ∧ (¬E(n)) say about n? for all x there is a y such that x < y, which says that there is no greatest number. 7.3 Using the predicates But with the opposite combination of quan- pol(x) for “x is a politician” tifiers we have liar(x) for “x is a liar” ∃y∀xL(x, y) represent the following statements in logic. is the false sentence all politicians are liars there is a y such that for all x, x < y, some politicians are liars which says there is a number greater than all no politicians are liars numbers. Even though these statements are usually some politicians are not liars. written without brackets they are effectively Are any of these sentences logically equiv- bracketed “from the centre”. So ∀x∃yL(x, y) alent? means ∀x(∃yL(x, y)) and ∃y∀xL(x, y) means ∃y(∀xL(x, y)). 7.5 An example from Abraham Lin- coln You can fool all of the people some of the time and you can fool some of the people all of the time but you can’t fool all of the people all of the time. Let F (p, t) be the predicate: person p can be fooled at time t. Then ∀p∃tF (p, t) says you can fool all of the people some of the time, ∃p∀tF (p, t) says you can fool some of the people all of the time, ¬∀p∀tF (p, t) says you can’t fool all of the people all of the time. Hence Lincoln’s sentence in symbols is: ∀p∃tF (p, t) ∧ ∃p∀tF (p, t) ∧ ¬∀p∀tF (p, t)  Lecture 8: Predicate logic 8.1 Valid sentences Example. The sentence The language of predicate logic is based on ∀x∃yQ(x, y) → ∃x∀yQ(x, y) predicate symbols, variables, constants, brack- is false if we interpret Q(x, y) as x 6 y on the ets, ∀, ∃ and connectives. The examples from real numbers. With this interpretation last lecture illustrate how these ingredients are used to form sentences. ∀x∃yQ(x, y) is true (for any number there is a larger number), but A sentence in predicate logic is valid if it has value T under all interpretations. ∃x∀yQ(x, y) is false (there is no number 6 all numbers). Hence the This is similar to the definition of a tautology implication is false. in propositional logic. But now “all interpreta- tions” means all interpretations of the predicate symbols, which is more complicated. The inter- 8.4 Consequence and equivalence pretation of a symbol P (n), say, must include both the range of the variable n, as well as say- As in propositional logic, a sentence ψ is a logi- ing those n for which P (n) is true. cal consequence of a sentence φ if any interpre- tation which makes φ true makes ψ true. Again 8.2 Interpretations we write φ ⇒ ψ if ψ is a consequence of φ, and this is the same as saying φ → ψ is valid. For example, one interpretation of P (n) is “n is positive,” where n ranges over the real numbers. Under this interpretation, ∀nP (n) is false. Example. Any interpretation which makes A different interpretation of P (n) is “n is ∀x∀yP (x, y) true makes ∀y∀xP (x, y) true, and positive,” where n ranges over the numbers > 2. so ∀x∀yP (x, y) ⇒ ∀y∀xP (x, y). Under this interpretation, ∀nP (n) is true. Unlike in propositional logic, there are in- Similarly, sentences ψ and φ are equivalent, finitely many different interpretations of each written ψ ≡ φ, if each is a consequence of the formula. Thus there is no truth table method other. Some sentences are equivalent for “propo- for predicate logic. We cannot decide whether a sitional logic reasons.” formula is valid by testing all interpretations. 8.3 Recognising valid sentences Example. We have Nevertheless, in some cases, we can see that a ∀x(P (x) ∧ Q(x)) ≡ ∀x(Q(x) ∧ P (x)) sentence is true for all interpretations. simply because Example. ∀x∀yP (x, y) → ∀y∀xP (x, y) is true P (x) ∧ Q(x) ≡ Q(x) ∧ P (x) for all properties P , and hence is valid. for any x. Likewise, we can sometimes see that a sen- tence is not valid by finding an interpretation However there are also equivalences that which makes it false. genuinely involve quantifiers. 8.5 Useful equivalences 8.7* Completeness and undecidabil- ity Two important equivalences involving quanti- In 1930, Gödel proved that there is a complete fiers are set of rules of inference for predicate logic. This means, in particular, that there is an algorithm ¬∀xP (x) ≡ ∃x¬P (x) to list the valid sentences. However, in 1936, Church and Turing proved ¬∃xP (x) ≡ ∀x¬P (x) that there is no algorithm to list the logically false sentences. This means, in particular, that These make sense intuitively. For example, predicate logic is undecidable: there is no algo- ¬∀xP (x) means P (x) is not true for all x, hence rithm which, for any sentence φ, decides whether there is an x for which P (x) is false, that is, φ is valid or not. ∃x¬P (x). This negative result is due to the power of They can also be viewed as “infinite De Mor- predicate logic: it can express all mathemati- gan’s laws.” If x ranges over {1, 2, 3,...} for ex- cal or computational problems, and it is known ample, then that some of these problems cannot be solved by algorithm. ∀xP (x) ≡ P (1) ∧ P (2) ∧ P (3) ∧ · · · and Questions ∃xP (x) ≡ P (1) ∨ P (2) ∨ P (3) ∨ · · · 8.1 Give interpretations which make the fol- Hence lowing sentences false. ¬∀xP (x) ≡ ¬ (P (1) ∧ P (2) ∧ P (3) ∧ · · · ) ∃nP (n) → ∀nP (n) ≡ (¬P (1)) ∨ (¬P (2)) ∨ (¬P (3)) ∨ · · · ∀x∀y (R(x, y) → R(y, x)) by de Morgan’s law ∀m∃nS(m, n) ≡ ∃x¬P (x). 8.2 Give interpretations which show that the And similarly sentences ¬∃xP (x) ≡ ¬ (P (1) ∨ P (2) ∨ P (3) ∨ · · · ) ∃x (P (x) ∧ L(x)) ≡ (¬P (1)) ∧ (¬P (2)) ∧ (¬P (3)) ∧ · · · and by de Morgan’s law ∃x (P (x) ∧ ¬L(x)) ≡ ∀x¬P (x). are not equivalent. 8.3 Is ∃y∀xR(x, y) a logical consequence of ∀x∃yR(x, y)? 8.6 Simplification If so, explain why. If not, give an interpre- tation which makes ∀x∃yR(x, y) true and The infinite de Morgan’s laws allow a certain ∃y∀xR(x, y) false. simplification of predicate formulas by “pushing 8.4 Is ∀x∃yR(x, y) a logical consequence of ¬ inside quantifiers.” ∃y∀xR(x, y)? If so, explain why. If not, give an interpre- tation which makes ∃y∀xR(x, y) true and Example. ∀x∃yR(x, y) false. ¬∀x∃yQ(x, y) ≡ ∃x¬∃yQ(x, y) ≡ ∃x∀y¬Q(x, y). 8.5 Explain why ¬∀p∀tF (p, t) ≡ ∃p∃t¬F (p, t). It is in fact possible to transform any quanti- fied statement in predicate logic to an equivalent with all quantifiers at the front.  Lecture 9: Mathematical induction Since the natural numbers 0, 1, 2, 3,... are Example 2. Prove there are 2n n-bit binary generated by a process which begins with 0 and strings. repeatedly adds 1, we have the following. Let P (n) be “there are 2n n-bit binary strings”. Property P is true for all natural numbers if Base step. There is 20 = 1 0-bit binary string 1. P (0) is true. (the empty string) so P (0) is true. 2. P (k) ⇒ P (k + 1) for all k ∈ N. Induction step. We want to prove that This is called the principle of mathematical induction. there are 2k k-bit binary strings It is used in a style of proof called proof by ⇒ there are 2k+1 (k + 1)-bit binary strings induction, which consists of two steps. Well, a (k + 1)-bit binary string is either W 0 or Base step: Proof that the required property P W 1, where W is any k-bit binary string. Thus is true for 0. if there are 2k k-bit binary strings W , there are Induction step: Proof that if P (k) is true 2 × 2k = 2k+1 (k + 1)-bit binary strings. then P (k + 1) is true, for each k ∈ N. This completes the induction step, and hence completes the proof. 9.1 Examples Example 1. Prove that 3 divides n3 + 2n for all n ∈ N 9.2 Starting the base step higher Let P (n) be “3 divides n3 + 2n”. It is not always appropriate to start the induc- Base step. 3 divides 03 + 2 × 0 = 0, so P (0) is tion at 0. Some properties are true only from a true. certain positive integer upwards, in which case Induction step. We want to prove the induction starts at that integer. 3 divides k 3 + 2k Example 3. Prove n! > 2n for all integers ⇒ 3 divides (k + 1)3 + 2(k + 1). n>4 Well, Let P (n) be “n! > 2n ”. (k + 1)3 + 2(k + 1) Base step. 4! = 4 × 3 × 2 = 24 > 16 = 24 , so = k 3 + 3k 2 + 3k + 1 + 2k + 2 P (4) is true. = k 3 + 2k + 3k 2 + 3k + 3 Induction step. We want to prove k! > 2k ⇒ = k 3 + 2k + 3(k 2 + k + 1). (k + 1)! > 2k+1 for all integers k > 4. Now, for k > 4, if k! > 2k , Therefore, (k+1)! = (k+1)×k! > (k+1)×2k > 2×2k = 2k+1. 3 divides k 3 + 2k (The first > holds because we are assuming ⇒ 3 divides k 3 + 2k + 3(k 2 + k + 1) k! > 2k and the second holds because k > 4.) ⇒ 3 divides (k + 1)3 + 2(k + 1) Thus k! > 2k ⇒ (k + 1)! > 2k+1 , as required to as required. This completes the induction step, complete the induction. and hence completes the proof. So n! > 2n for all n > 4. Example 4. Prove any integer value n > 8 (in Remark. Another proof is to write down cents) is obtainable with 3c and 5c stamps. 1 + 2 + 3 + · · · + (n − 1) + n Let P (n) be “n cents is obtainable with 3c and n + (n − 1) + · · · + 3 + 2 + 1 5c stamps”. and observe that each of the n columns sums Base step. 8c can be obtained by a 3c plus a 5c to n + 1. Thus the sum of twice the series is stamp. So P (8) is true. n(n + 1), and hence the sum of the series itself Induction step. We have to show that if k cents is n(n + 1)/2. One could argue that this proof is obtainable, so is (k + 1) cents, when k > 8. uses induction stealthily, to prove that the sum Case 1. The k cents is obtained using a 5c of each column is the same. stamp (among others). Replace the 5c stamp by two 3c stamps, thus obtaining k + 1 cents. Questions Case 2. If the k cents is obtained using only In most induction problems set for students we 3c stamps, there are at least three of them (since skip the experimental part, which is finding what k > 8). In this case, replace three 3c stamps by to prove. Before trying to prove that 3 divides two 5c stamps, again obtaining k + 1 cents. n3 + 2n, for example, someone needs to guess Thus in either case, when k > 8, P (k) ⇒ that it is true, perhaps by trying n = 1, 2, 3, 4. P (k + 1). This completes the induction proof that n cents are obtainable from 3c and 5c 9.1 In this question, try to guess what ? stands stamps, for all integers n > 8. for, by trying a few values of n. ? divides n2 + n The sum of the first n odd numbers is ? 1 1 1 1 1×2 + 2×3 + 3×4 +... + n(n+1) = 1−? 9.3 Sums of series 9.2 If you correctly guessed the sum 1 1 1 1 Induction is often used to prove that sum for- 1×2 + 2×3 + 3×4 +... + n(n+1) , mulas are correct. you might wonder why it is so simple. Here is a clue: Example 5. Prove 1+2+3+· · ·+n = n(n+1)/2 1 = 1 − 12. 1×2 1 for all integers n > 1. 1 1 Let P (n) be “1 + 2 + 3 + · · · + n = n(n + 1)/2”. What is 2×3 ? 3×4 ? How does this lead to a simple formula for Base step. When n = 1, the left hand side is 1, 1 1 1 1 and the right hand side is 1(1 + 1)/2 = 2/2 = 1, 1×2 + 2×3 + 3×4 +... + n(n+1) ? so P (1) is true. OK, if we can guess formulas correctly, Induction step. We have to prove that why bother proving them by induction? 1 + 2 + ··· + k = k(k+1) The reason is that a statement which fits 2 (k+1)(k+2) many values of n can still be wrong. ⇒ 1 + 2 + · · · + k + (k + 1) = 2. Now, if P (k) is true, 9.3 Show that n2 + n + 41 is a prime number for n = 1, 2, 3, 4 (and go further, if you 1 + 2 + · · · + k + (k + 1) like). Do you think n2 + n + 41 is prime = (1 + 2 + · · · + k) + (k + 1) for all natural numbers n? k(k+1) = 2 + (k + 1) using P (k) = (k + 1)( k2 + 1) (k+1)(k+2) = 2 as required. This completes the induction proof.  Lecture 10: Induction and well-ordering In the previous lecture we were able to prove Example 2. Prove that every positive integer a property P holds for 0, 1, 2,... as follows: is a sum of distinct powers of 2. (Just a power Base step. Prove P (0) of two by itself counts as a “sum”.) Induction step. Prove P (k) ⇒ P (k + 1) for The idea behind this proof is to repeatedly sub- each natural number k. tract the largest possible power of 2. We illus- This is sufficient to prove that P (n) holds for trate with the number 27. all natural numbers n, but it may be difficult to prove that P (k + 1) follows from P (k). It may 27 − largest power of 2 less than 27 in fact be easier to prove the induction step = 27 − 16 = 11 11 − largest power of 2 less than 11 = 11 − 8 = 3 P (0) ∧ P (1) ∧ · · · ∧ P (k) ⇒ P (k + 1). 3 − largest power of 2 less than 3 =3−2=1 That is, it may help to assume P holds for Hence 27 = 16 + 8 + 2 + 1 = 24 + 23 + 21 + 20. all numbers before k + 1. Induction with this (It is only interesting to find distinct powers style of induction step is sometimes called the of 2, because of course each integer > 1 is a sum strong form of mathematical induction. of 1s, and 1 = 20.) The strong induction proof goes as follows. Let P (n) be “n is a sum of distinct powers of 2”. Base step. 1 = 20 , so 1 is a sum of (one) power 10.1 Examples of strong induction of 2. Thus P (1) is true. Induction step. Suppose each of the numbers Example 1. Prove that every integer > 2 is a 1, 2, 3,... , k is a sum of distinct powers of 2. We product of primes. (Just a prime by itself counts wish to prove that k +1 is a sum of distinct pow- as a “product”.) ers of 2. Let P (n) be “n is a product of primes”. This is certainly true if k + 1 is a power of 2. If not, let 2j be the greatest power of 2 less than Base step. 2 is a prime, hence a product of (one) k + 1. Then prime. So P (2) is true. i = k + 1 − 2j Induction step. Suppose 2, 3,... , k are products is one of the numbers 1, 2, 3,..., k, and hence it of primes. We wish to prove that k +1 is a prod- is a sum of distinct powers of 2. uct of primes. Also, the powers of 2 that sum to i are all This is certainly true if k + 1 is a prime. If not less than 2j , otherwise 2j is less than half k + 1, k + 1 = i × j, contrary to the choice of 2j as the largest power for some natural numbers i and j less than k +1. of 2 less than k + 1. But then i and j are products of primes by our Hence k + 1 = 2j + powers of 2 that sum to assumption, hence so is i × j = k + 1. i is a sum of distinct powers of 2. This completes the induction proof. This completes the induction proof.  √ 10.2 Well-ordering and descent But then 2 = m1 /n1 , and we can repeat the argument to show that m1 and n1 are both Induction expresses the fact that each natural even, so m1 = 2m2 and n1 = 2n2 , and so on. number n can be reached by starting at 0 and Since the argument can be repeated indefi- going upwards (e.g. adding 1) a finite number nitely, we get an infinite descending sequence of of times. natural numbers Equivalent facts are that it is only a finite number of steps downwards from any natural m > m1 > m2 > · · · number to 0, that any descending sequence of which is impossible. natural numbers is finite, and that any set of Hence √ there are no natural numbers m and natural numbers has a least element. n with 2 = m/n. This property is called well-ordering of the natural numbers. It is often convenient to ar- Questions range a proof to “work downwards” and appeal to well-ordering by saying that the process of 10.1 For each of the following statements, say working downwards must eventually stop. which is likely to require strong induction Such proofs are equivalent to induction, for its proof. though they are sometimes called “infinite de- an+1 −1 1 + a + a2 + · · · + an = a−1 scent” or similar. ¬ (p1 ∨ p2 ∨ p3 ∨ · · · ∨ pn ) ≡ (¬p1 ) ∧ (¬p2 ) ∧ (¬p3 ) ∧ · · · ∧ (¬pn ) 10.3 Proofs by descent n Each fraction m < 1 is a sum of Example 1. Prove that any integer > 2 has a distinct fractions with numerator 1 prime divisor. for example, 11 1 1 1
12 = 2 + 3 + 12. If n is prime, then it is a prime divisor of itself. 10.2 There is something else which tells you ev- If not, let n1 < n be a divisor of n. ery integer > 1 is a sum of distinct powers If n1 is prime, it is a prime divisor of n. If of 2. What is it? not, let n2 < n1 be a divisor of n1 (and hence of n). 10.3 Is every integer > 1 a sum of distinct pow- If n2 is prime, it is a prime divisor of n. If ers of 3? not, let n3 < n2 be a divisor of n2 , etc. The sequence n > n1 > n2 > n3 > · · · must eventually terminate, and this means we find a prime divisor of n. √ Example 2. Prove 2 is irrational. √ Suppose that 2 = m/n for natural numbers m and n. We will show this is impossible. Since the square of an odd number is odd, we can argue as follows √ 2 = m/n ⇒ 2 = m2 /n2 squaring both sides ⇒ m2 = 2n2 ⇒ m2 is even ⇒ m is even since the square of an odd number is odd ⇒ m = 2m1 say ⇒ 2n2 = m2 = 4m21 ⇒ n2 = 2m21 ⇒ n is even, = 2n1 say  Lecture 11: Sets Sets are vital in expressing mathematics for- working within a local “universal set” which in- mally and are also very important data struc- cludes only those objects under consideration. tures in computer science. For example, when discussing arithmetic it A set is basically just an unordered collection might be sufficient to work just with the num- of distinct objects, which we call its elements or bers 0, 1, 2, 3,.... Our universal set could then members. Note that there is no notion of order be taken as for a set, even though we often write down its N = {0, 1, 2, 3,...}, elements in some order for convenience. Also, there is no notion of multiplicity: an object is and other sets of interest, e.g. {x : x is prime}, either in a set or not – it cannot be in the set are parts of N. multiple times. 11.3 Subsets Sets A and B are equal when every element of A is an element of B and vice-versa. We say that A is a subset of B and write A ⊆ B when each element of A is an element 11.1 Set notation of B. x ∈ S means x is an element of set S. Example. The set of primes forms a subset of N, that is {x : x is prime} ⊆ N. {x1 , x2 , x3 ,...} is the set with elements x1 , x2 , x3 ,.... 11.4 Characteristic functions {x : P (x)} is the set of all x with property P. A subset A of B can be specified by its charac- teristic function χA , which tells which elements Example. of B are in A and which are not. 17 ∈ {x : x is prime} = {2, 3, 5, 7, 11, 13,...} ( 1 if x ∈ A {1, 2, 3} = {3, 1, 2} χA (x) = {1, 1, 1} = {1} 0 if x ∈ /A Sometimes it is more convenient to use a slight variation on the colon notation given Example. The subset A = {a, c} of B = above. For a set S and a property P , we {a, b, c} has the characteristic function χA with sometimes write {x ∈ S : P (x)} instead of χA (a) = 1, χA (b) = 0, χA (c) = 1. {x : x ∈ S and P (x)}. We also write this function more simply as For a finite set S, we write |S| for the number of elements of S. a b c 1 0 1 11.2 Universal set In fact we can list all characteristic functions The idea of a “set of all sets” leads to logical on {a, b, c}, and hence all subsets of {a, b, c}, by difficulties. Difficulties are avoided by always listing all sequences of three binary digits:  characteristic function subset corresponds to the property of being even. a b c Similarly, the set 0 0 0 {} {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,...} 0 0 1 {c} corresponds to the property of being prime. The 0 1 0 {b} power set P(N) corresponds to all possible prop- 0 1 1 {b, c} erties of natural numbers. 1 0 0 {a} 11.7* What are numbers? 1 0 1 {a, c} 1 1 0 {a, b} The most common approach to building mathe- matics up from logical foundations considers all 1 1 1 {a, b, c} mathematical objects to be fundamentally made of sets. One simple way to define numbers using We could similarly list all the subsets of a sets (due to von Neumann) is the following. four-element set, and there would be 24 = 16 of 0 = {} them, corresponding to the 24 sequences of 0s and ls. 1 = {0} In the same way, we find that an n-element 2 = {0, 1} set has 2n subsets, because there are 2n binary... sequences of length n. (Each of the n places in the sequence can be filled in two ways.) n + 1 = {0, 1, 2,... , n} We are not going to use this definition in this course. Still, it is interesting that numbers can 11.5 Power set be defined in such a simple way. The set of all subsets of a set U is called the Questions power set P(U ) of U. 11.1 Suppose E(x) stands for “x is even” and F (x) stands for “5 divides x.” Example. We see from the previous table that P({a, b, c}) is the set What is the set {x : E(x) ∧ F (x)}?  Write a formula using E(x) and {}, {c}, {b}, {b, c}, {a}, {a, c}, {a, b}, {a, b, c}. F (x) which describes the set {5, 15, 25, 35,...}. If U has n elements, then P(U ) has 2n ele- ments. 11.2 How many subsets does the set {2, 5, 10, 20} have? (The reason P(U ) is called the “power” set 11.3 Consider the infinitely many sets is probably that the number of its elements is this power of 2. In fact, the power set of U is {x : 0 < x < 1} sometimes written 2U.) {x : 0 < x < 12 } {x : 0 < x < 13 } 11.6 Sets and properties {x : 0 < x < 14 }.. We mentioned at the beginning that {x : P (x)}. stands for the set of objects x with property P. Do they have any element in common? Thus sets correspond to properties. Properties of the natural numbers 0, 1, 2, 3,... , for example, correspond to sub- sets of the set N = {0, 1, 2, 3,...}. Thus the subset {0, 2, 4, 6,...} = {n ∈ N : n is even}  Lecture 12: Operations on sets There is an “arithmetic” of sets similar to or- 12.4 Difference A − B dinary arithmetic. There are operations similar The difference A − B of sets A and B consists of to addition, subtraction and multiplication. the elements in A and not in B, indicated by the shaded region in the following Venn diagram. 12.1 Venn diagrams The simple operations on sets can be visualised U with the help of Venn diagrams, which show sets A B A, B, C,... as disks within a rectangle represent- ing the universal set U. U A B The difference U − B relative to the univer- sal set U is called the complement B of B. Here is the Venn diagram of B. U A B 12.2 Union A ∪ B The union A ∪ B of sets A and B consists of the elements in A or B, and is indicated by the shaded region in the following Venn diagram. U 12.5 Symmetric difference A4B A B The union of A − B and B − A is called the symmetric difference A4B of A and B. U A B 12.3 Intersection A ∩ B The intersection A ∩ B of sets A and B consists of the elements in A and B, indicated by the shaded region in the following Venn diagram. A4B consists of the elements of one of A, B but not the other. U It is clear from the diagram that we have not A B only A4B = (A − B) ∪ (B − A), but also A4B = (A ∪ B) − (A ∩ B). 12.6 Ordered Pairs area l × w. In fact, we call it an “l × w rectan- gle.” This is probably the reason for using the Sometimes we do want order to be important. × sign, and for calling A × B a “product.” In computer science arrays are ubiquitous ex- amples of ordered data structures. In maths, Questions ordered pairs are frequently used. An ordered pair (a, b) consists simply of a first object a and 12.1 Draw a Venn diagram for A ∩ B. What is a second object b. The objects a and b are some- another name for this set? times called the entries or coordinates of the or- dered pair. 12.2 Check the de Morgan laws by drawing Venn diagrams for A ∪ B, A ∩ B, A ∩ B Two ordered pairs (a, b) and (c, d) are equal and A ∪ B if and only if a = c and b = d. 12.3 Find which of the following is true by drawing suitable Venn diagrams. Example. {0, 1} = {1, 0} but (0, 1) 6= (1, 0). A ∩ (B4C) = (A ∩ B)4(A ∩ C)? There’s no reason we need to stop with pairs. A4(B ∩ C) = (A4B) ∩ (A4C)? We can similarly define ordered triples, quadru- 12.4 If plane = line × line, what do you think ples, and so on. When there are k coordinates, line × circle is? What about circle × cir- we call the object an ordered k-tuple. Two or- cle? dered k-tuples are equal if and only if their ith coordinates are equal for i = 1, 2,... , k. 12.7 Cartesian product A × B The set of ordered pairs A × B = {(a, b) : a ∈ A and b ∈ B} is the cartesian product of sets A and B. The commonest example is where A = B = R (the set of real numbers, or the number line). Then the pairs (a, b) are points in the plane, so R × R is the plane. (a, b) b O a Because Descartes used this idea in geome- try, the cartesian product is named after him. 12.8 A × B and multiplication If A has |A| elements and B has |B| elements, then A × B has |A| × |B| elements. Similarly, if L is a line of length l, and W is a line of length w, then L × W is a rectangle of  Lecture 13: Functions √ A function can be thought of as a “black 2. The square root function sqrt(x) = x with box” which accepts inputs and, for each input, domain R>0 , codomain R, and pairs produces a single output. √ {(x, x) : x ∈ R and x > 0}. 13.1 Defining functions via sets 2 Formally we represent a function f as a set X 1 of possible inputs, a set Y so that every out- put of f is guaranteed to be in Y , and a set of (input,output) pairs from X × Y. The vital 0 property of a function is that each input gives exactly one output. -1 A function f consists of a domain X, a -1 0 1 2 3 codomain Y , and a set of ordered pairs from The image of this function (the set of y values) X × Y which has exactly one ordered pair is the set R>0. (x, y) for each x ∈ X. 3. The cubing function cube(x) = x3 with do- When (a, b) is in this set we write f (a) = b. main R, codomain R, and pairs The set of y values occurring in these pairs is {(x, x3 ) : x ∈ R}, the image of f. Note that the image of a function is always a subset of its codomain but they may or may not be equal. If the image of a function is equal to its 1 codomain, we say the function is onto. Examples. 0 1. The squaring function square(x)= x2 with -1 domain R, codomain R, and pairs -1 0 1 2 {(x, x ) : x ∈ R}, which form what we usually call the plot of the squaring function. 1 The image of this function is the whole of the 0 codomain R, so it is onto. -1 0 1 The image of this function (the set of y val- ues) is the set R>0 of real numbers > 0. 13.2 Arrow notation functions are or are not one-to-one. Example. The function f : R → R given by If f is a function with domain A and f (x) = 6x + 2 is one-to-one because codomain B we write f (x1 ) = f (x2 ) f : A → B, ⇒ 6x1 + 2 = 6x2 + 2 and we say that f is from A to B. ⇒ 6x1 = 6x2 For example, we could define ⇒ x1 = x2. square : R → R. Example. The function f : R → R given We could also define by f (x) = x2 + 1 is not one-to-one because f (−1) = 2 and f (1) = 2 and so square : R → R>0. f (−1) = f (1). Likewise, we could define cube : R → R. Questions However we could not define 13.1 Some of the following “rules” do not define >0 genuine functions. Which are they? cube : R → R , because for some x ∈ R, cube(x) is negative. For each set S of natural numbers, let For example, cube(−1) = −1. f (S) be the least element of S. For each set X of real numbers be- 13.3 One-to-one functions tween 0 and 1, let g(X) be the least element of X. A function f : X → Y is one-to-one if for For each circle C in the (x, y) plane, each y in the image of f there is only one let h(C) be the minimum distance x ∈ X such that f (x) = y. from C to the x-axis. For example, the function cube(x) is one-to- For each pair A, B of sets of real num- one because each real number y is the cube of bers, let s(A, B) be the smallest set exactly one real number x. such that both A and B are subsets The function square: R → R is not one-to- of s(A, B). one because the real number 1 is the square of For each pair A, B of sets of real num- two different real numbers, 1 and −1. (In fact bers, let t(A, B) be the largest set each real y > 0 is the square of two different real that is a subset of both A and B. √ √ numbers, y and − y) On the other hand, square : R>0 → R is one- 13.2 For each of the following, say which can be to-one because each real number y in R>0 is the defined with domain R and codomain R. square of only one real number in R>0 , namely √ √ √ x2 , 1/x, log x, x, 3 x y. The last example shows that the domain of a function is an important part of its descrip- tion, because changing the domain can change the properties of the function. 13.4 Proving a function is one-to-one There is an equivalent way of phrasing the def- inition of one-to-one: a function f : X → Y is one-to-one when, for all x1 , x2 ∈ X, f (x1 ) = f (x2 ) ⇒ x1 = x2. This can be useful for proving that some  Lecture 14: Examples of functions The functions discussed in the last lecture 14.3 Characteristic functions were familiar functions of real numbers. Many A subset of N = {0, 1, 2, 3,...} can be repre- other examples occur elsewhere, however. sented by its characteristic function. For exam- ple, the set of squares is represented by the func- tion χ : N → {0, 1} defined by ( 14.1 Functions of several variables 1 if n is a square χ(n) = 0 if n is not a square We might define a function which has the following sequence of values sum : R × R → R by sum(x, y) = x + y. 110010000100000010000000010000000000100... Because the domain of this function is R×R, the (with 1s at the positions of the squares inputs to this function are ordered pairs (x, y) 0, 1, 4, 9, 16, 25, 36,...). of real numbers. Because its codomain is R, we Any property of natural numbers can like- are guaranteed that each output will be a real wise be represented by a characteristic function. number. This function can be thought of as a For example, the function χ above represents function of two variables x and y. the property of being a square. Similarly we might define a function Thus any set or property of natural numbers is represented by a function binomial : R × R × N → R χ : N → {0, 1}. by Characteristic functions of two or more vari- binomial(a, b, n) = (a + b)n. ables represent relations between two or more Here the inputs are ordered triples (x, y, n) such objects. For example, the relation x 6 y be- that x and y are real numbers and n is a natural tween real numbers x and y has the character- number. We can think of this as a function of istic function χ : R × R → {0, 1} defined by three variables. ( 1 if x 6 y χ(x, y) = 0 otherwise. 14.2 Sequences 14.4 Boolean functions The connectives ∧, ∨ and ¬ are functions of vari- An infinite sequence of numbers, such as ables whose values come from the set B = {T, F} 1, 21 , 14 , 18 , 16 1 ,..., of Boolean values (named after George Boole). ¬ is a function of one variable, so can be viewed as the function f : N → R de- fined by f (n) = 2−n. In this case, the inputs to ¬:B→B f are natural numbers, and its outputs are real and it is completely defined by giving its values numbers. on T and F, namely Any infinite sequence a0 , a1 , a2 , a3 ,... can be viewed as a function g(n) = an from N to some ¬T = F and ¬F = T. set containing the values an. This is what we previously did by giving the truth table of ¬. The construction of f is sometimes called a “di- ∧ and ∨ are functions of two variables, so agonalisation argument”, because we get its val- ues by switching values along the diagonal in the ∧:B×B→B table of values of f0 , f1 , f2 , f3 ,.... and ∨:B×B→B They are completely defined by giving their val- ues on the pairs (T, T), (T, F), (F, T), (F, F) in B × B, which is what their truth tables do. Questions 14.1 Suggest domains and codomains for the 14.5* Characteristic functions and following functions, writing the domain as subsets of N a cartesian product where applicable. Mathematicians say that two (possibly infinite) gcd, reciprocal, remainder ∩, ∪ sets A and B have the same cardinality (size) if there is a one-to-one and onto function from A 14.2 If A and B are subsets of N with charac- to B. This function associates each element of A teristic functions χA and χB respectively, with a unique element of B and vice-versa. With what set does the function χA (n)χB (n) this definition, it is not too hard to show that, represent? for example, N and Z have the same cardinality 14.3 How many Boolean functions of n vari- (they are both “countably infinite”). ables are there? It turns out, though, that P(N) has a strictly greater cardinality than N. We can prove this by showing: no sequence f0 , f1 , f2 , f3 ,... in- cludes all characteristic functions for subsets of N. (This shows that there are more characteris- tic functions than natural numbers.) In fact, for any infinite list f0 , f1 , f2 , f3 ,... of characteristic functions, we can define a char- acteristic function f which is not on the list. Imagine each function given as the infinite se- quence of its values, so the list might look like this: f0 values 0101010101... f1 values 0000011101... f2 values 1111111111... f3 values 0000000000... f4 values 1001001001...... Now if we switch each of the underlined values to its opposite, we get a characteristic function ( 1 if fn (n) = 0 f (n) = 0 if fn (n) = 1 which is different from each function on the list. In fact, it has a different value from fn on the number n. For the given example, f has values 11011...  Lecture 15: Composition and inversion Complicated functions are often built from 15.2 Conditions for composition simple parts. For example, the function f : R → Composite functions do not always exist. R defined by f (x) = (x2 + 1)3 is computed by doing the following steps in succession: Example. If reciprocal : R − {0} → R is de- fined by reciprocal(x) = x1 and predecessor : square, R → R is defined by predecessor(x) = x − 1, then reciprocal ◦ predecessor does not exist, be- add 1, cause predecessor(1) = 0 is not a legal input for reciprocal. cube. To avoid this problem, we demand that the We say that f (x) = (x2 + 1)3 is the composite codomain of h be equal to the domain of g for of the functions (from R to R) g ◦ h to exist. This ensures that each output of h will be a legal input for g. square(x)=x2 , Let h : A → B and g : C → D be func- successor(x)=x + 1, tions. Then g ◦ h : A → D exists if and only if B = C. cube(x)=x3. 15.1 Notation for composite func-