BCA124 CU- BCA-Sem 2 -Discrete Mathematical Structures(Draft 3)-converted

BACHELOR OF COMPUTER APPLICATIONS SEMESTER-II DISCRETE MATHEMATICAL STRUCTURES BCA124

CHANDIGARH UNIVERSITY Institute of Distance and Online Learning Course Development Committee Prof. (Dr.) R.S.Bawa Pro Chancellor, Chandigarh University, Gharuan, Punjab Advisors Prof. (Dr.) Bharat Bhushan, Director – IGNOU Prof. (Dr.) Majulika Srivastava, Director – CIQA, IGNOU Programme Coordinators & Editing Team Master of Business Administration (MBA) Bachelor of Business Administration (BBA) Coordinator – Dr. Rupali Arora Coordinator – Dr. Simran Jewandah Master of Computer Applications (MCA) Bachelor of Computer Applications (BCA) Coordinator – Dr. Raju Kumar Coordinator – Dr. Manisha Malhotra Master of Commerce (M.Com.) Bachelor of Commerce (B.Com.) Coordinator – Dr. Aman Jindal Coordinator – Dr. Minakshi Garg Master of Arts (Psychology) Bachelor of Science (Travel &Tourism Management) Coordinator – Dr. Samerjeet Kaur Coordinator – Dr. Shikha Sharma Master of Arts (English) Bachelor of Arts (General) Coordinator – Dr. Ashita Chadha Coordinator – Ms. Neeraj Gohlan Academic and Administrative Management Prof. (Dr.) R. M. Bhagat Prof. (Dr.) S.S. Sehgal Executive Director – Sciences Registrar Prof. (Dr.) Manaswini Acharya Prof. (Dr.) Gurpreet Singh Executive Director – Liberal Arts Director – IDOL © No part of this publication should be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording and/or otherwise without the prior written permission of the authors and the publisher. SLM SPECIALLY PREPARED FOR CU IDOL STUDENTS Printed and Published by: TeamLease Edtech Limited www.teamleaseedtech.com CONTACT NO:- 01133002345 For: CHANDIGARH UNIVERSITY Institute of Distance and Online Learning

First Published in 2020 All rights reserved. No Part of this book may be reproduced or transmitted, in any form or by any means, without permission inwriting from Chandigarh University. Any person who does any unauthorized act in relation to this book may be liable to criminal prosecution and civil claims for damages. This book is meant for educational and learning purpose. The authors of the book has/have taken all reasonable care to ensure that the contents of the book do not violate any existing copyright or other intellectual property rights of any person in any manner whatsoever. In the even the Authors has/ have been unable to track any source and if any copyright has been inadvertently infringed, please notify the publisher in writing for corrective action.

CONTENT Unit 1- Set Theory 1..............................................................................................................................5 Unit 2- Set Theory 2............................................................................................................................30 Unit 3- Relation...................................................................................................................................51 Unit 4 - Functions ...............................................................................................................................75 Unit 5- Combinatorics 1 .....................................................................................................................90 Unit 6- Combinatorics 2 ...................................................................................................................113 Unit 7- Recurrence Relations...........................................................................................................135 Unit 8- Generating Function 1.........................................................................................................155 Unit 9- Generating Function 2.........................................................................................................168 Unit 10- Trees....................................................................................................................................183 Unit 11- Graphs ................................................................................................................................208 4 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 1- SET THEORY 1 Structure 1.0. Learning Objectives 1.1. Introduction 1.2. Definition of sets, 1.3. Operation on Sets: Complements, Union, Intersection, Symmetrical Difference and Disjoint Sets 1.4. Venn Diagrams, 1.5. Cartesian products, 1.6. Power sets. 1.7. Summary 1.8. Keywords 1.9. Learning activity 1.10.Unit End Questions 1.11.References 1.0 LEARNING OBJECTIVESS After studying this unit, you will be able to: • Explain the basic concept of Sets • Enumerate the use of Venn Diagram • State the concept of Cardinality and power sets Set theory is the mathematical theory of well-determined collections, called sets, of objects that are called members, or elements, of the set. Set theory is important because it is a theory of integers, models of axiom systems, infinite ordinals, and real numbers, all in one unified structure. This allows it to serve as a foundation for all of mathematics. So, there are four ways in which we can define sets: • Extension or enumeration: its elements are enclosed in brackets and separated by commas. Each set describes a list of all its elements. • Understanding: its elements are determined by a condition that is established between brackets. • Venn diagrams: closed regions that allow us to visualize the relationships between the sets. • Verbal description: This is a statement that describes a feature common to all elements of the set. 5 CU IDOL SELF LEARNING MATERIAL (SLM)

1.1 INTRODUCTION Set theory, as a separate mathematical discipline, begins in the work of Georg Cantor. One might say that set theory was born in late 1873, when he made the amazing discovery that the linear continuum, that is, the real line, is not countable, meaning that its points cannot be counted using the natural numbers. Set theory is the mathematical theory of well-determined collections, called sets, of objects that are called members, or elements, of the set. Pure set theory deals exclusively with sets, so the only sets under consideration are those whose members are also sets. The theory of the hereditarily-finite sets, namely those finite sets whose elements are also finite sets, the elements of which are also finite, and so on, is formally equivalent to arithmetic. So, the essence of set theory is the study of infinite sets, and therefore it can be defined as the mathematical theory of the actual—as opposed to potential— infinite. 1.2 DEFINITION OF A SET? SET: It is a collection of things. Things like what we carry in our school/college bag as books, pen, and geometry set, Tiffin, Water bottle, napkin, etc. When we write these things in curly bracket like below, it represents the Set&Set is always denoted by Capital Letters like A, B, C, etc. S = {Books, pen, geometry set, tiffin, water bottle, napkin} Example: Set of Whole numbers: - W = {0, 1, 2, 3…} Set of Alphabets: - A = {a, b, c… z} Each member like in above example i.e., 0,1, 2 or a, b c, are known as elements of the Set& is represented with lowercase letters it is denoted by ‘∈’. So, a ∈A – a is an element of A a∉W - a is not an element of W Five ways to describe set: 1. Describing the properties of the members of the set 2. Describing by listing its elements 3. Describing by its characteristics function a. µA(x) = 1 if x∈ A b. µA(x) = 0 if x∉ A 4. Describing by recursive formula 5. Describe by an operation (such as union, intersection, complement, etc.) 6 CU IDOL SELF LEARNING MATERIAL (SLM)

Example: Describe the set containing natural numbers up to 5 Let N denote the set then we can describe N in following ways 1. N= {x | x is natural number less than or equal to 5} 2. N = {1,2,3,4,5} 3. μN(x) = {10 for x = 1,2, … ,5 otherwise 4. N = {xi+1 = xi + 1, i = 0,1, … ,4 where x0 = 0} 5. This type will be discussed ahead in the section ‘Operation on Set’. CONCEPTS RELATED TO SETS: 1. Subset: Let A and B be two sets such that A is a subset of B and it is represented as ‘A ⊆ B’ if every element of A is an element of B A is a proper subset of B and it is represented as ‘A ⊂ B’ if A is a subset of B &at least one element of B which is not there in A. Properties related to Subset: 1. A⊆A 2. If A⊆ B & B⊆ C, then A⊆ C 3. If A⊂B & B⊂C then A⊂ C 4. If A⊆ B&A⊈C, then B⊈ C where⊈ means is not contained in. 2. Equal Sets: Two sets are equal when A⊆ B & B ⊆A that is A=B 3. Empty Set or Null Set: A set containing no element & denoted by∅. The empty set is a subset of every set. 4. Singleton: A set containing one element 5. Universal Set: A set that contains everything 1.3 OPERATION OF SET 1. Complement: Suppose U is the universal set & A be any subset of U, so A (absolute complement of A) is {x | x ∉ A} or {x| x∉U and x ∈ A} A & B are two sets then relative complement of A with respect to B is B – A = {x | x ∈B and x ∉A} From above explanation we can drive the following a. The complement of Universal Set U is U = ∅ b. The complement of Empty Set ∅ is ∅ = U 7 CU IDOL SELF LEARNING MATERIAL (SLM)

2. Union of Sets: It is denoted by ������implies that it contains all the elements of respective set considered in Union. Let A& B be two sets then their union is represented as A ������ B = {x | x ∈ A or x ∈ B or both} 3. Intersection of two sets: -It is denoted by ∩implies that it contains all the common elements of respective set considered in intersection. Let A& B be two sets then their union is represented as A ∩ B = {x | x ∈ A or x ∈ B} Properties related to Union & Intersection of two sets: UNION INTERSECTION A∩B Idempotent A������ A = A Commutative A ������ B = B ������ A A∩B=B∩A Associative A ������ (B ������ C) = (A ������ B) ������ C A ∩ (B ∩C) = (A ∩ B) ∩ C 4. Symmetrical Difference: When the elements of the set belong to either one set or other set but not both which are considered for the operation. It is denoted by ∆. Let A& B be the two sets so the symmetrical difference of both sets is A ∆ B = {x | x ∈ A or x ∈ B, but not both} 5. Disjoint Set: They does not have common elements & represented as A ∩ B = ∅ Let us explore few theorems on the basis of above operations Theorem 1: Distributive Law Let A, B & C be three sets then, C ∩ (A������B) = (C ∩ A) ������ (C ∩ A) 8 CU IDOL SELF LEARNING MATERIAL (SLM)

C ������ (A∩B) = (C ������ A) ������ (C������A) Theorem 2:DeMorgan’s Law Let A& B be the two sets then A ������ B = A ∩ B A ∩ B = A ������ B Example 1: Let A = {x: x is a natural number and a factor of 18} and B= {x: x is a natural number and less than 6}. Find A ������ B. Solution: A = {1, 2, 3, 6, 9, 18} B= {1, 2, 3, 4, 5} Therefore, A ������ B = {1, 2, 3, 4, 5, 6, 9, 18} Example 2: Let A = {0, 1, 2, 3, 4, 5}, B = {2, 4, 6, 8} and C = {1, 3, 5, 7} Verify (A ������ B) ������ C = A ������ (B ������ C) Solution: (A ������ B) ������ C = A ������ (B ������ C) L.H.S. = (A ������ B) ������ C A ������ B = {0, 1, 2, 3, 4, 5, 6, 8} (A ������ B) ������ C = {0, 1, 2, 3, 4, 5, 6, 7, 8} .............................. (1) R.H.S. = A ������ (B ������ C) B ������ C = {1, 2, 3, 4, 5, 6, 7, 8} 9 CU IDOL SELF LEARNING MATERIAL (SLM)

A ������ (B ������ C) = {0, 1, 2, 3, 4, 5, 6, 7, 8} ................................ (2) Therefore, from (1) and (2), we conclude that; (A ������ B) ������ C = A ������ (B ������ C) Example 3: If P = {multiples of 3 between 1 and 20} and Q = {even natural numbers up to 15}. Find the intersection of the two given set P and set Q. Solution: P = {multiples of 3 between 1 and 20} So, P = {3, 6, 9, 12, 15, 18} Q = {even natural numbers up to 15} So, Q = {2, 4, 6, 8, 10, 12, 14} Therefore, intersection of P and Q is the largest set containing only those elements which are common to both the given sets P and Q Hence, P ∩ Q = {6, 12}. Example 4: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9}, A = {1, 2, 3, 4} and B = {2, 4, 6, 8}. (i) Find A' (ii) Find B' Solution: (i) A' = U - A = {1, 2, 3, 4, 5, 6, 7, 8, 9} - {1, 2, 3, 4} = {5, 6, 7, 8, 9} (ii) B' = U - B = {1, 2, 3, 4, 5, 6, 7, 8, 9} - {2, 4, 6, 8} = {1, 3, 5, 7, 9} 10 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 5: Let A = {3, 5, 7}, B = {2, 3, 4, 6} and C = {2, 3, 4, 5, 6, 7, 8} 11 (i) Verify (A ∩ B)' = A' ������ B' (ii) Verify (A ������ B)' = A' ∩ B' Solution: (i) (A ∩ B)' = A' ������ B' L.H.S. = (A ∩ B)' A ∩ B = {3} (A ∩ B)' = {2, 4, 5, 6, 7, 8} ..............................(1) R.H.S. = A' ������ B' A’ = {5, 7, 8} B’ = {2, 4, 6} A’������B’ = {2, 4, 5, 6, 7, 8} ..............................(2) From (1) and (2), we conclude that; (A ∩ B)' = (A' ������ B') (ii) (A ������ B)' = A' ∩ B' L.H.S. = (A ������ B)' A������B = {2, 3, 4, 5, 6, 7} (A ������ B)' = {8}...............................(1) R.H.S. = A' ∩ B' CU IDOL SELF LEARNING MATERIAL (SLM)

A' = {2, 4, 6, 8} 12 B' = {5, 7, 8} A' ∩ B' = {8} ..............................(2) From (1) and (2), we conclude that; (A ������ B)' = A' ∩ B' Example 6: Given three sets P, Q and R such that: P = {x: x is a natural number between 10 and 16}, Q = {y: y is an even number between 8 and 20} and R = {7, 9, 11, 14, 18, 20} (i) Find the difference of two sets P and Q (ii) Find Q - R (iii) Find R - P (iv) Find Q – P Solution: According to the given statements: P = {11, 12, 13, 14, 15} Q = {10, 12, 14, 16, 18} R = {7, 9, 11, 14, 18, 20} (i) P – Q = {Those elements of set P which are not in set Q} = {11, 13, 15} (ii) Q – R = {Those elements of set Q not belonging to set R} = {10, 12, 16} CU IDOL SELF LEARNING MATERIAL (SLM)

(iii) R – P = {Those elements of set R which are not in set P} = {7, 9, 18, 20} (iv) Q – P = {Those elements of set Q not belonging to set P} = {10, 16, 18} Example 7: Let A = {1, 3, 5, 6}, B = {0, 5, 6, 7}, find A Δ B. Solution: A \\ B = {1, 3, 5, 6} \\ {0, 5, 6, 7} = {1, 3} B \\ A = {0, 5, 6, 7} \\ {1, 3, 5, 6} = {0, 7} A Δ B = (A \\ B) u (B \\ A) A Δ B = {1, 3} u {0, 7} A Δ B = {1, 3, 0, 7} Example 8: Let A = {1, 3, 5, 6}, B = {0, 7}, find A ∩ B. Solution: A ∩ B = {1, 3, 5, 6} u {0, 7} A ������B = {} or Empty set Hence, A and B are disjoint sets. Example 9:If U = {j, k, l, m, n}, X = {j, k, m} and Y = {k, m, n}. Proof of De Morgan's law: (X ∩ Y)' = X' U Y'. 13 CU IDOL SELF LEARNING MATERIAL (SLM)

Solution: We know, U = {j, k, l, m, n} X = {j, k, m} Y = {k, m, n} (X ∩ Y) = {j, k, m} ∩ {k, m, n} = {k, m} Therefore, (X ∩ Y)' = {j, l, n} .......................... (i) Again, X = {j, k, m} so, X' = {l, n} and Y = {k, m, n} so, Y' = {j, l} X' ������ Y' = {l, n} ������ {j, l} Therefore, X' ������ Y' = {j, l, n} ..........................(ii) Combining (i)and (ii) we get; (X ∩ Y)' = X' U Y'. Example 10: Let U = {1, 2, 3, 4, 5, 6, 7, 8}, P = {4, 5, 6} and Q = {5, 6, 8}. Show that (P ������ Q)' = P' ∩ Q'. Solution: We know, U = {1, 2, 3, 4, 5, 6, 7, 8} P = {4, 5, 6} Q = {5, 6, 8} P ������ Q = {4, 5, 6} ������ {5, 6, 8} = {4, 5, 6, 8} 14 CU IDOL SELF LEARNING MATERIAL (SLM)

Therefore, (P ������ Q)' = {1, 2, 3, 7} ............................ (i) Now P = {4, 5, 6} so, P' = {1, 2, 3, 7, 8} and Q = {5, 6, 8} so, Q' = {1, 2, 3, 4, 7} P' ∩ Q' = {1, 2, 3, 7, 8} ∩ {1, 2, 3, 4, 7} Therefore, P' ∩ Q' = {1, 2, 3, 7} ............................ (ii) Combining (i)and (ii) we get; (P ������ Q)' = P' ∩ Q'. Hence, Proved. 1.4 VENN DIAGRAM Venn diagram: Represents information that is easy in understanding 1. Set B is a proper subset of A A B 2. The absolute complement of set A Fig 1.1: Venn Diagram to represent Subset A Fig 1.2: Venn Diagram to represent Absolute Complement 15 CU IDOL SELF LEARNING MATERIAL (SLM)

3. The relative complement of set B with respect to set A A B Fig 1.3: Venn Diagram to represent Relative Complement 4. The Union of sets A and B AB 5. The intersection of sets A and B Fig 1.4: Venn Diagram to represent Union of Sets AB Fig 1.5: Venn Diagram to represent Intersection of Sets 6. The symmetrical difference of sets A and B AB Fig 1.6: Venn Diagram to represent 16 CU IDOL SELF LEARNING MATERIAL (SLM)

Symmetrical Difference of Sets Example 1: If A = {2, 3, 4, 5, 6, 7} and B = {3, 5, 7, 9, 11, 13}, then find (i) A – B and (ii) B – A. Solution: According to the given statement; A = {2, 3, 4, 5, 6, 7} and B = {3, 5, 7, 9, 11, 13} (i) A – B Fig 1.7: Difference of A and B = {2, 4, 6} (ii) B – A Fig 1.8: Difference of B and A = {9, 11, 13}. adjoining figure find A union Example 2: From the B. 17 CU IDOL SELF LEARNING MATERIAL (SLM)

Fig 1.9: Union of A and B Solution: According to the adjoining figure we get; Set A = {0, 1, 3, 5, 8} Set B = {2, 5, 8, 9} Therefore, A union B is the set of elements which in set A or in set B or in both. Thus, A U B = {0, 1, 2, 3, 5, 8, 9} Example 3. If A = {1, 2, 3, 4, 5} and B = {1, 3, 9, 12}. Find A ∩ B using Venn diagram. Solution: According to the given question we know, A = {1, 2, 3, 4, 5} and B = {1, 3, 9, 12} Now let’s draw the Venn diagram to find A intersection B. 18 CU IDOL SELF LEARNING MATERIAL (SLM)

Fig 1.10: Intersection of A and B Therefore, from the Venn diagram we get A ∩ B = {1, 3} Example 4: By definition of A – B A – (A – B) = A – (A ∩B) =A ∩A∩B By definition of A– B = A ∩ (A ������ B) By DeMorgan = (A ∩ A) ������(A∩B) By Distributive Law = ϕ ������ (A ∩B) By (A ∩ A= ∅) = (A ∩B) By ∅ ������A = A 1.5 CARTESIAN PRODUCTS • Cartesian product of two non-empty sets A and B is denoted by A×B and defined as the “collection of all the ordered pairs (a, b) such that a∈A and b∈B “. It is also called the cross product, set direct product or the product set of A and B. One very important thing to note here is that it is the collection of ordered pairs. By ordered pair, it is meant that two elements taken from each set are written in particular order. So, if a ≠ b, ordered pairs (a, b) and (b, a) are distinct. Number of Ordered Pairs For two non-empty sets, A and B. If the number of elements of A is h i.e., n(A) = h & that of B is k i.e., n(B) = k, then the number of ordered pairs in Cartesian product will be n (A × B) = n(A) × n(B) = hk. 19 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 1: Let P & Q be two sets such that n(P) = 4 and n(Q) = 2. If in the Cartesian product we have (m,1), (n-1), (x,1), (y, -1). Find P and Q, where m, n, x, and y are all distinct. Answer: P = set of first elements = {m, n, x, y} and Q = set of second elements = {1, -1} Remark: • Two ordered pairs are equal, if and only if the corresponding first elements are equal and the second elements are also equal. • A × A × A = {(a, b, c): a, b, c ∈ A}. Here (a, b, c) is called an ordered triplet. • A x {infinite set} = {infinite set} where A is non-empty set. • n (A x B) = n(A) * n(B) • n (A x B x C) = n(A) * n(B) * n(C) • AxB ≠ BxA Example 2: If X = {x, y, z} and P = {p}, form the sets X × P and P × X. Solution: X × P = {(x, p), (y, p), (z, p)} P X X = {(p, x), (p, y), (p, z)} Example 3: If A × B = {(p, x); (p, y); (q, x); (q, y)}, find A and B. Solution: A is a set of all first entries in ordered pairs in A × B. B is a set of all second entries in ordered pairs in A × B. Thus A = {p, q} and B = {x, y} Example 4: If A and B are two sets, and A × B consists of 6 elements: If three elements of A × B are (2, 5) (3, 7) (4, 7) find A × B. Solution: Since, (2, 5) (3, 7) and (4, 7) are elements of A × B. 20 CU IDOL SELF LEARNING MATERIAL (SLM)

So, we can say that 2, 3, 4 are the elements of A and 5, 7 are the elements of B. So, A = {2, 3, 4} and B = {5, 7} Now, A × B = {(2, 5); (2, 7); (3, 5); (3, 7); (4, 5); (4, 7)} Thus, A × B contain six ordered pairs. Example 5: If A = {1, 3, 5} and B = {2, 3}, then Find: (i) A × B (ii) B × A (iii) A × A (iv) (B × B) Solution: A ×B={1, 3, 5} × {2,3} = [{1, 2},{1, 3},{3, 2},{3, 3},{5, 2},{5, 3}] B × A = {2, 3} × {1, 3, 5} = [{2, 1},{2, 3},{2, 5},{3, 1},{3, 3},{3, 5}] A × A = {1, 3, 5} × {1, 3, 5}= [{1, 1},{1, 3},{1, 5},{3, 1},{3, 3},{3, 5},{5, 1},{5, 3},{5, 5}] B × B = {2, 3} × {2, 3} = [{2, 2},{2, 3},{3, 2},{3, 3}] Note: If either A or B are null sets, then A ×B will also be an empty set, i.e., if A = ∅ or B = ∅, then A × B = ∅ 1.6 POWER SETS We have defined a set as a collection of its elements so, if S is a set then the collection or family of all subsets of S is called the power set of S and it is denoted by P(S). Thus, if S = a, b then the power set of S is given by P(S) = {{a}, {b}, {a, b}, ∅} We have defined a set as a collection of its elements if the element be sets themselves, then we have a family of set or set of sets. Thus, A = {{1}, {1, 2, 3}, {2}, {1, 2}} is a family of sets. The null set or empty set having no element of its own is an element of the power set; since, it is a subset of all sets. The set being a subset of itself is also as an element of the power set. 21 CU IDOL SELF LEARNING MATERIAL (SLM)

1. The collection of all subsets of a non-empty set S is a set of sets. Thus, the power set of as given set is always non-empty. This set is said to be the power set of S and is denoted by P(S). If S contains N elements, then P(S) contains 2^n subsets, because a subset of P(S) is either ∅ or a subset containing r elements of S, r = 1, 2, 3, ……... Let S = {1, 2, 3} then the power set of S is given by P(S) = {{1}, {2}, {3}, {1, 2}, {2, 3}, {1, 3}, ∅, S}. 2. If S = (a), then P(S) = {(a), ∅}; if again S = ∅, then P(S) = {∅}. It should be notated that ∅ ≠ {∅}. If S = {1, 2, 3} then the subset of S {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, ∅. Hence, P(S) = {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, ∅}. 3. We know, since a set formed of all the subset of a set M as its elements is called a power set of M and is symbolically denoted by P(M). So, if M is a void set ∅, then P(M) has just one element ∅ then the power set of M is given by P(M) = {∅} Example 1: 1. Let A and B be two finite sets such that n(A) = 20, n(B) = 28 and n (A ������ B) = 36, find n (A ∩ B). Solution: Using the formula n (A ������ B) = n(A) + n(B) - n (A ∩ B). then n (A ∩ B) = n(A) + n(B) - n (A ������ B) = 20 + 28 - 36 = 48 - 36 = 12 Example 2:There are 35 students in art class and 57 students in dance class. Find the number of students who are either in art class or in dance class. • When two classes meet at different hours and 12 students are enrolled in both activities. • When two classes meet at the same hour. Solution: n(A) = 35, n(B) = 57, n (A ∩ B) = 12 (Let A be the set of students in art class. B be the set of students in dance class.) (i) When 2 classes meet at different hours n(A ������ B) = n(A) + n(B) - n(A ∩ B) = 35 + 57 - 12 = 92 - 12 = 80 (ii) When two classes meet at the same hour, A∩B = ∅ n (A ������ B) = n(A) + n(B) - n(A ∩ B) 22 CU IDOL SELF LEARNING MATERIAL (SLM)

= n(A) + n(B) = 35 + 57 = 92 Example 3: From the adjoining Venn diagram, find the following sets. i)A ii) B iii) ξ iv)C' v) C – A vi) (A ∩ B)' Fig 1.11: Venn Diagram for example 3 Solution: (i) A= {1, 3, 4, 5} (ii) B= {4, 5, 6, 2} (iii)Ξ= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} iv) To Find C' all elements of universal set leaving the elements of set C. C = {1, 5, 6, 7, 10} Therefore, C' = {2, 3, 4, 8, 9} v) C - A Here C = {1, 5, 6, 7, 10} A = {1, 3, 4, 5} then C – A = {6, 7, 10} excluding all elements of A from C. vi) (A ∩ B)' A = {1, 3, 4, 5} B = {4, 5, 6, 2} (A ∩ B) = {4, 5} (A ∩ B)' = {1, 2, 3, 6, 7, 8, 9, 10} 1.7 SUMMARY The essence of set theory is the study of infinite sets, and therefore it can be defined as the mathematical theory of the actual—as opposed to potential—infinite. 23 CU IDOL SELF LEARNING MATERIAL (SLM)

The axioms of set theory imply the existence of a set-theoretic universe so rich that all mathematical objects can be construed as sets. Also, the formal language of pure set theory allows one to formalize all mathematical notions and arguments. Thus, set theory has become the standard foundation for mathematics, as every mathematical object can be viewed as a set, and every theorem of mathematics can be logically deduced in the Predicate Calculus from the axioms of set theory. Both aspects of set theory, namely, as the mathematical science of the infinite, and as the foundation of mathematics, are of philosophical importance. Set: A set is a collection of things (numbers, pencils, cows, etc.). Sets are denoted by capital letters and braces. Element: An element of a set is one of the things that belong to the set (3 is an element of the set of all odd numbers). Elements are denoted by lower case letters. Universal Set: The universal set is the set of all elements being considered (the universal set of classes at Regent University is every course in the course catalogue). The universal set is denoted by “������”. Empty Set: The empty set contains no elements (the intersection of the set of men and women is the empty set). Cardinal Number: The cardinal number of a set is the number of elements in a set (The set of primary colors has a cardinal number of 3). The cardinality of a set is denoted by “������”. Set Equality: Two sets are equal if every element of one set is in the other set and the other set has no additional elements (The set of the letters in the word “god” is equal to the set of the letters in the work “dog”). Subset: A subset is a set that only contains elements found in a larger set (The set of odd numbers from 1 to 10 is a subset of the set of numbers from 1 to 10). Mutually Exclusive: Sets are mutually exclusive if they do not share any of the same elements (the set of animals that are dogs and the set of animals that are cats are mutually exclusive). Set Theory Rules In mathematics, we follow some rules for the representation of sets. The rules are: • The name of the set is denoted by upper case alphabet letters. • The elements or members or objects of the set are denoted by lower case alphabet letters. • If ′a′ belongs to A, this is represented as a∈A. Here, ∈ is a Greek symbol, called epsilon. ∈ denotes “belongs to”. If ′c′ doesn’t belong to set A, we write it as c∉A. Types of Sets 24 CU IDOL SELF LEARNING MATERIAL (SLM)

The different types of sets in set theory are: • Finite set • Infinite set • Empty set • Singleton set • Equal set • Equivalent set • Power set • Universal set • Subset The four important set operations that are widely used are: • Union of sets • Intersection of sets • Complement of sets • Cartesian product of sets → Theorem 1: Distributive Law Let A, B & C be three sets then, C ∩ (A������B) = (C ∩ A) ������ (C ∩ A) C ������ (A∩B) = (C ������ A) ������ (C������A) Theorem 2:DE Morgan’s Law Let A & B be the two sets then A ������ B = A ∩ B A ∩ B = A ������ B Venn Diagram - a diagram representing mathematical or logical sets pictorially as circles or closed curves within an enclosing rectangle (the universal set), common elements of the sets being represented by intersections of the circles. 25 CU IDOL SELF LEARNING MATERIAL (SLM)

Circles: Each circle in a Venn Diagram represents a set. Overlap of Circles: The overlap between circles is the intersection between those sets. The Box: The box represents the universal set. Everything inside the box that is not in a circle is the complement of all of the sets that are represented by circles. 1.8 KEY WORDS/ABBREVIATIONS • SET: A set is a collection of objects. • Element: An element or member of a set is an object that belongs to the set • Universe of Discourse – the set containing all elements under discussion for a particular problem • Intersection: The intersection of two sets, A ∩ B, is the set of elements common to both. • Disjoint sets: two sets which have no elements in common. 1.9 LEARNING ACTIVITY 1. Using Venn diagram, create sets of scores of different subjects for all students. Verify Demorgan’s law 2. Out of forty students, 14 are taking English Composition and 29 are taking Chemistry. a. If five students are in both classes, how many students are in neither class? b. How many are in either class? c. What is the probability that a randomly-chosen student from this group is taking only the Chemistry class? 1.10 UNIT END QUESTIONS (MCQ AND DESCRIPTIVE) A. Descriptive Types Questions 1. In a group of 100 persons, 72 people can speak English and 43 can speak French. How many can speak English only? How many can speak French only and how many can speak both English and French? 2. Let A = {1, 2, 3}, B = {3, 4} and C = {4, 5, 6}. Find A × (B ∩ C) 3. Explain Complement of Set 26 CU IDOL SELF LEARNING MATERIAL (SLM)

4. Discuss Cartesian product of two sets 5. Solve Using Venn diagram: In a survey of university students, 64 had taken mathematics course, 94 had taken chemistry course, 58 had taken physics course, 28 had taken mathematics and physics, 26 had taken mathematics and chemistry, 22 had taken chemistry and physics course, and 14 had taken all the three courses. Find how many had taken one course only. B. Multiple Choice Questions 1. If A and B are sets and A������ B= A ∩ B, then a) A = Φ b) B = Φ c) A = B d) None of these 2. A is an ordered collection of objects. a) Relation b) Function c) Set d) Proposition 3. The set O of odd positive integers less than 10 can be expressed by a) {1, 2, 3} b) {1, 3, 5, 7, 9} c) {1, 2, 5, 9} d) {1, 5, 7, 9, 11} 4. What is the cardinality of the set of odd positive integers less than 10? a) 10 b) 5 c) 3 d) 20 5. The set of positive integers is a) Infinite b) Finite c) Subset d) Empty 27 CU IDOL SELF LEARNING MATERIAL (SLM)

6. Power set of empty set has exactly subset. a) One b) Two c) Zero d) Three 7. What is the Cartesian product of A = {1, 2} and B = {a, b}? a) {(1, a), (1, b), (2, a), (b, b)} b) {(1, 1), (2, 2), (a, a), (b, b)} c) {(1, a), (2, a), (1, b), (2, b)} d) {(1, 1), (a, a), (2, a), (1, b)} 8. Which of the following two sets are equal? a) A = {1, 2} and B = {1} b) A = {1, 2} and B = {1, 2, 3} c) A = {1, 2, 3} and B = {2, 1, 3} d) A = {1, 2, 4} and B = {1, 2, 3} 9. The intersection of the sets {1, 2, 5} and {1, 2, 6} is the set a) {1, 2} b) {5, 6} c) {2, 5} d) {1, 6} 10. Two sets are called disjoint if there is the empty set. a) Union b) Difference c) Intersection d) Complement Answers: 1 –c; 2 – c ;3 – b; 4 – b; 5 – a; 6 -a; 7 – c; 8 -c; 9 – a; 10 – c; 1.11 REFERENCES • Kenneth Rosen, Discrete Mathematics and Its Applications with Combinatorics and Graph Theory (SIE) | 7th Edition, McGraw Hill Education; 7 editions • Jean-Paul Tremblay, R Manohar, Discrete Mathematical Structures with Applications to Computer Science,McGraw Hill Education; 1st edition 28 CU IDOL SELF LEARNING MATERIAL (SLM)

• Susanna S. Epp, Discrete Mathematics with Applications, Cengage Learning. • C Liu, D. Mohapatra, Elements of Discrete Mathematics: A Computer Oriented Approach | 4th Edition, McGraw Hill Education • Jiri Matousek , Jaroslav Nesetril, Invitation to Discrete Mathematics,OUP Oxford • V.K. Balakrishnan, Introductory Discrete Mathematics (Dover Books on Computer Science),Dover Publications Inc • László Lovász, József Pelikán, Katalin Vesztergombi, Discrete Mathematics: Elementary and Beyond (Undergraduate Texts in Mathematics), Springer • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin 29 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT 2- SET THEORY Structure 2.0. Learning Objectives 2.1. Introduction 2.2. Counting principle, 2.3. Cardinality and count ability (Countable and Uncountable sets), 2.3.1 Sets with Equal Cardinalities 2.3.2 Countable and Uncountable Sets 2.4. Proofs of some general identities on sets 2.5. Summary 2.6. Key Words/Abbreviations 2.7. Learning Activity 2.8. Unit End Questions (MCQ and Descriptive) 2.9.References 2.0 LEARNING OBJECTIVES After studying this unit, you will be able to: • State the Counting principle, • Comprehend the Cardinality and count ability (Countable and Uncountable sets), • Enumerate Proofs of some general identities on sets 2.1 INTRODUCTION Two finite sets are considered to be of the same size if they have equal numbers of elements. To formulate this notion of size without reference to the natural numbers, one might declare two finite sets A and B to have the same cardinality if and only if there exists a bijection A→B. For finite sets, these two definitions are equivalent. A bijection will exist between A and B only when elements of A can be paired in one-to-one correspondence with elements of B, which necessarily requires A and B have the same number of elements The cardinality of a set is a measure of a set's size, meaning the number of elements in the set. For instance, the set A= {1,2,4} has a cardinality of 3 for the three elements that are in it. In the sense of cardinality, countably infinite sets are \"smaller\" than uncountably infinite sets. Of course, finite sets are \"smaller\" than any infinite sets, but the distinction between countable and uncountable gives a way of comparing sizes of infinite sets as well. 30 CU IDOL SELF LEARNING MATERIAL (SLM)

Cardinality places an equivalence relation on sets, which declares two sets A andB areequivalent when there exists a bijection A→B. The equivalence classes thus obtained are called cardinal numbers. 2.2 COUNTING PRINCIPLE: The Fundamental Counting Principle gives us a quicker way to count up the number of ways to complete the task. If a task requires a sequence of choices, then the number of ways to complete the task is to multiply together the number of options for each choice. The cardinality of a set is a measure of the \"number of elements\" of the set Counting mainly encompasses fundamental counting rule, the permutation rule, and the combination rule. The Rules of Sum and Product The Rule of Sum and Rule of Product are used to decompose difficult counting problems into simple problems. • The Rule of Sum − If a sequence of tasks T1,T2,…,Tm can be done in w1,w2,…wmways respectively (the condition is that no tasks can be performed simultaneously), then the number of ways to do one of these tasks is w1+ w2 +⋯+ wm. If we consider two tasks A and B which are disjoint (i.e. A∩B = ∅), then mathematically |A������B| = |A| + |B| |A������B| = |A| + |B| General Representation: Let E1 and E2 be mutually exclusive events (i.e., there are no common outcomes). Let event E describe the situation where either event E1 or event E2 will occur. The number of times event E will occur can be given by the expression: n(E) = n(E1) + n(E2) where n(E) = Number of outcomes of event E n(E1) = Number of outcomes of event E1 n(E2) = Number of outcomes of event E2 Example 1: Consider a set of numbers S= {−4, −2,1,3,5,6,7,8,9,10} Let the events E1, E2 and E3 be defined as: 31 CU IDOL SELF LEARNING MATERIAL (SLM)

E = choosing a negative or an odd number from S; 32 E1= choosing a negative number from S; E2 = choosing an odd number from S. Find n(E). Solution:E1 and E2 are mutually exclusive events (i.e., no common outcomes). n(E) = n(E1) + n(E2) =2+5 =7 Example 2 In how many ways can a number be chosen from 1 to 22 such that (a) it is a multiple of 3 or 8? (b) it is a multiple of 2 or 3? Solution: Part (a) Here, E1 = multiples of 3: E1 = {3, 6, 9,12, 15, 18, 21} n(E1) = 7 E2 = multiples of 8: E2 = {8, 16} n(E2) = 2 Events E1 and E2 are mutually exclusive. n(E) = n(E1) + n(E2) = 7 + 2 = 9 Part (b) Here, E1 = multiples of 2: E1 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22} n(E1) = 11 CU IDOL SELF LEARNING MATERIAL (SLM)

E2 = multiples of 3: E2 = {3, 6, 9,12, 15, 18, 21} n(E2) = 7 Events E1 and E2 are not mutually exclusive. We could proceed as follows: n(E) = n(E1) + n(E2) − n (E1 ∩ E2) = 11 + 7 − 3 = 15 where E1 ∩ E2 means \"the intersection of the sets E1 and E2\". • The Rule of Product − If a sequence of tasks T1,T2,…,Tm can be done in w1,w2,…wmw1,w2,…wm ways respectively and every task arrives after the occurrence of the previous task, then there are w1×w2×⋯×wmw1×w2×⋯×wm ways to perform the tasks. Mathematically, if a task B arrives after a task A, then |A×B| = |A| × |B| |A×B| = |A|×|B| General Representation: Suppose that event E1 can result in any one of n(E1) possible outcomes; and for each outcome of the event E1, there are n(E2) possible outcomes of event E2. Together there will be n(E1) × n(E2) possible outcomes of the two events. That is, if event E is the event that both E1 and E2 must occur, then n(E) = n(E1) × n(E2) Example 3− A boy lives at X and wants to go to School at Z. From his home X he has to first reach Y and then Y to Z. He may go X to Y by either 3 bus routes or 2 train routes. From there, he can either choose 4 bus routes or 5 train routes to reach Z. How many ways are there to go from X to Z? Solution − From X to Y, he can go in 3+2=5 ways (Rule of Sum). Thereafter, he can go Y to Z in 4+5=9 ways (Rule of Sum). Hence from X to Z he can go in 5×9=45 ways (Rule of Product). Example 4: What is the total number of possible outcomes when a pair of coins is tossed? 33 Solution: The events are described as: E1 = toss first coin (2 outcomes, so n(E1) = 2.) E2 = toss second coin (2 outcomes, so n(E2) = 2.) CU IDOL SELF LEARNING MATERIAL (SLM)

They are independent, since neither toss affects the outcome of the other toss. So n(E) = n(E1) × n(E2) = 2 × 2 = 4 [We could list the outcomes: HH HT TH TT]. Example 5: The life insurance policies of an insurance company are classified by: • age of the insured: ▪ under 25 years, ▪ between 25 years and 50 years, ▪ over 50 years old; • sex; • marital status: ▪ single or ▪ married. What is the total number of classifications? Solution: The events are described as: E1 = age of the insured: 3 age divisions, so n(E1) = 3. E2 = sex: 2 possibilities, so n(E2) = 2. E3 = marital status: 2 possibilities, so n(E3) = 2. Each event is independent, so n(E) = n(E1) × n(E2) × n(E3) = 3 × 2 × 2 = 12 2.3 CARDINALITY AND COUNTABILITY OF A SET: Definition 2.2.1: Let‘S’ be a set. If there are exactly n distinct elements in S, where n is a nonnegative integer, we say S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by | S |. Examples: 1. V = {1,2,3,4,5} |V| = 5 2. A = {1,2, 3,…, 20} 34 CU IDOL SELF LEARNING MATERIAL (SLM)

|A| = 20 3. |∅| = 0 2.3.1 Sets with Equal Cardinalities We begin with a discussion of what it means for two sets to have the same cardinality. Up until this point we’ve said |A| = |B| if A and B have the same number of elements: Count the elements of A, then count the elements of B. If you get the same number, then |A| = |B|. Although this is a fine strategy if the sets are finite (and not too big!), it doesn’t apply to infinite sets because we’d never be done counting their elements. We need a new approach that applies to both finite and infinite sets. Here it is: Definition 2.2.2:Two sets A and B have the same cardinality, written |A| = |B|, if there exists a bijective function f: A → B. If no such bijective function exists, then the sets have unequal cardinalities, that is, |A| ≠ |B|. Fig 2.1: Same Cardinality of A and B The above picture illustrates our definition. There is a bijective function f: A → B, so |A| = |B|. The function f matches up A with B. Think of f as describing how to overlay A onto B so that they fit together perfectly. Fig 2.2 (a) and (b): Unequal Cardinalities of A and B 35 CU IDOL SELF LEARNING MATERIAL (SLM)

Example 1: The sets A = {n ∈Z: 0 ≤ n ≤ 5}and B = {n ∈Z:−5 ≤ n ≤ 0} have the same cardinality because there is a bijective function f:A → Bgiven by the rule f (n) = −n. Several comments are in order. First, if |A| = |B|, there can be lots ofbijective functions from A to B. We only need to find one of them in order to conclude|A| = |B|. Second, as bijective functions play such a big role here, we use the word bijection to mean bijective function. Thus, the function f (n) = −n from Example 1 is a bijection. Also, an injective function is called an injection and a surjective function is called a surjection. We emphasize and reiterate thatabove Definition applies to finite as well as infinite sets. If A and B are infinite, then |A| = |B| provided thereexists a bijection f: A → B. If no such bijection exists, then |A| ≠ |B|. Example 2 This example shows that |N| = |Z|. To see why this is true,notice that the following table describes a bijection f: N → Z. Notice that f is described in such a way that it is both injective andsurjective. Every integer appears exactly once on the infinitely long secondrow. Thus, according to the table, given any b ∈Z there is some naturalnumber n with f (n) = b, so f is surjective. It is injective because the way the table is constructed forces f (m) ≠ f (n) whenever m 6= n. Because of thisbijection f: N → Z, we must conclude from Definition 2.2.2 that |N| = |Z|. Example 3:It may seem slightly unsettling. On one hand it makessense that |N| = |Z| because N and Z are both infinite, so their cardinalitiesare both “infinity.” On the other hand, Z may seem twice as large as N because Z has all the negative integers as well as the positive ones. Definition settles the issue. Because the bijection f: N → Z matchesup N with Z, it follows that |N| = |Z|. We summarize this with a theorem. Theorem 1 There exists a bijection f: N → Z. Therefore |N| = |Z|.The fact that N and Z have the same cardinality might prompt us compare the cardinalities of other infinite sets. How, for example, do Nand R compare? Let’s turn our attention to this. In fact, |N| ≠ |R|. This was first recognized by Georg Cantor (1845–1918), who devised an ingenious argument to show that there are no surjectivefunctions f: N → R. (This in turn implies that there can be no bijectionsf: N → R, so |N| ≠|R| by Definition. 36 CU IDOL SELF LEARNING MATERIAL (SLM)

We now describe Cantor’s argument for why there are no surjectionsf: N → R. Let’s see reason informally, rather than writing out an exact proof. Take any arbitrary function f: N → R. Here’s why f can’t be surjective: Imagine making a table for f, where values of n in N are in the left-hand column and the corresponding values f (n) are on the right. Thefirst few entries might look something as follows. In this table, the realnumbers f (n) is written with all their decimal places trailing off to the right. Thus, even though f (1) happens to be the real number 0.4, we writeit as 0.40000000... , etc Table 2.1: Arbitrary function There is a diagonal shaded band in the table. For each n ∈N, this band covers the nth decimal place of f (n): The 1st decimal place of f (1) is the 1st entry on the diagonal. The 2nd decimal place of f (2) is the 2nd entry on the diagonal. The 3rd decimal place of f (3) is the 3rd entry on the diagonal. The 4th decimal place of f (4) is the 4th entry on the diagonal, etc. The diagonal helps us construct a number b ∈R that is unequal to any f (n).Just let the nth decimal place of b differ from the nth entry of the diagonal.Then the nth decimal place of b differs from the 37 CU IDOL SELF LEARNING MATERIAL (SLM)

nth decimal place of f (n). In order to be definite, define b to be the positive number less than 1 whose nth decimal place is 0 if the nth decimal place of f (n) is not 0, and whosenth decimal place is 1 if the nth decimal place of f (n) equals 0. Thus, for the function f illustrated in the above table, we have b = 0.01010001001000...andb has been defined so that, for any n ∈N, its nth decimal place is unequal to the nth decimal place of f (n). Therefore f (n) ≠ b for everynatural number n, meaning f is not surjective. Since this argument applies to any function f: N → R (not just the onein the above example) we conclude that there exist no bijections f: N → R,so |N| ≠ |R| by Definition. We summarize this as a theorem. Theorem2 There exists no bijection f: N → R. Therefore |N| ≠ |R|.This is our first indication of how there are different kinds of infinities. Both N and Rare infinite sets, yet |N| ≠ |R|. The next example shows that theintervals (0, ∞) and (0,1) on R have the same cardinality. Fig 2.3: A bijection f:(0, ∞) → (0,1) Example 4: Show that | (0, ∞) | = | (0,1) |. To accomplish this, we need to show that there is a bijection f: (0, ∞) → (0,1). We describe this function geometrically. Consider the interval (0, ∞) as the positive x-axis of R2. Let the interval (0,1) be on the y-axis as illustrated in Figure 2.1, so that (0, ∞) and (0,1) are perpendicular to each other. The figure also shows a point P = (−1,1). Define f (x) to be the point on (0,1) where the line from P to x ∈ (0, ∞) intersects the y-axis. By similartriangles, we have 38 CU IDOL SELF LEARNING MATERIAL (SLM)

It is important to note that equality of cardinalities is an equivalence relation on sets: it is reflexive, symmetric and transitive. Let us confirm this. Given a set A, the identity function A → A is a bijection, so |A| = |A|. (This is the reflexive property.) For the symmetric property, if |A| = |B|,then there is a bijection f :A → B, and its inverse is a bijection f −1 : B → A,so |B| = |A|. For transitivity, suppose |A| = |B| and |B| = |C|. Then there are bijections f: A → B and g:B → C. The composition g ◦ f: A → C is a bijection,so |A| = |C|. The transitive property can be useful. If, in trying to show two sets Aand C have the same cardinality, we can produce a third set B for which|A| = |B| and |B| = |C|, then transitivity assures us that indeed |A| = |C|. The next example uses this idea. Example 5:Show that |R| = | (0,1) |. Because of the bijection g: R → (0, ∞) where g(x) = 2x, we have |R| = | (0, ∞) |. Also, Example 3 shows that | (0, ∞) | = | (0,1) |. Therefore |R| = | (0,1) |. So far in this chapter we have declared that two sets have “the same cardinality” if there is a bijection between them. They have “different cardinalities” if there exists no bijection between them. Using this idea, we showed that |Z| = |N| ≠ |R| = | (0, ∞) | = | (0,1) |. So, we have a means of determining when two sets have the same or different cardinalities. 2.3.2 Countable and Uncountable Sets let’s summarize the main points from the previous section. 1. |A| = |B| if and only if there exists a bijection A → B. 2. |ℕ| = |Z| because there exists a bijection ℕ→ ℤ. 3. |ℕ| ≠ |R| because there exists no bijection ℕ→ ℝ. Thus, even though ℕ, ℤ and ℝ are all infinite sets, their cardinalitiesare not all the same. The sets ℕ andℤ have the same cardinality, butℝ’s cardinality is different from that of both the other sets. This meansinfinite sets can have different sizes. We now make some definitions toput words and symbols to this phenomenon. In a certain sense you can count the elements of ℕ; you can count itselements off as 1,2,3, 4... but you’d have to continue this process foreverto count the whole set. Thus, we will call ℕ a countable infinite set, and the same term is used for any set whose cardinality equals that of ℕ. 39 CU IDOL SELF LEARNING MATERIAL (SLM)

Definition 1 SupposeA is a set. Then A is countably infinite if| ℕ| = |A|, that is, if there exists a bijection N → A. The set A is uncountableif A is infinite and | ℕ| ≠ |A|, that is, if A is infinite and there exists no bijection ℕ→ A. Thus ℤ is countably infinite but ℝ is uncountable. This section dealsmainly with countably infinite sets. Uncountable sets are treated later. If A is countably infinite, then | ℕ| = |A|, so there is a bijection f: ℕ→ A.You can think of f as “counting” the elements of A. The first element of Ais f (1), followed by f (2), then f (3) and so on. It makes sense to think of acountably infinite set as the smallest type of infinite set, because if the counting process stopped, the set would be finite, not infinite; a countablyinfinite set has the fewest elements that a set can have and still be infinite. It is common to reserve the special symbol ℵ0 to stand for the cardinalityof countably infinite sets. Definition 2 The cardinality of the natural numbers is denoted as ℵ0. That is, |ℕ| = ℵ0. Thus, any countably infinite set has cardinality ℵ0. (The symbol ℵis the first letter in the Hebrew alphabet, and is pronounced “aleph.” The symbol ℵ0 is pronounced “aleph naught.”) The summary of facts at the beginning of this section shows |ℤ| = ℵ0 and |ℝ| ≠ ℵ0. Example 6: Let E = {2k: k∈ℤ} be the set of even integers. The function f: Z → E defined as f (n) = 2n is easily seen to be a bijection, so we have|Z| = |E|. Thus, as |N| = |Z| = |E|, the set E is countably infinite and |E| = ℵ0 Here is a significant fact: The elements of any countably infinite set A can be written in an infinitely long list a1, a2, a3, a4... that begins with someelement a1 ∈ A and includes every element of A. For example, the set E inthe above example can be written in list form as 0,2, −2,4, −4,6, −6,8, −8... The reason that this can be done is as follows. Since A is countably infinite, Definition 2.4.2 says there is a bijection f: N → A. This allows us to list out the set A as an infinite list f (1), f (2), f (3), f (4), ... Conversely, if theelements of A can be written in list form as a1, a2, a3, then the functionf: N → A defined as f (n) = an is a bijection, so A is countably infinite. We summarize this as follows. Example 7: Prove or disprove that the following sets are countable: 40 (a) A = {log n: n ∈ N}. CU IDOL SELF LEARNING MATERIAL (SLM)

(b) A = {(m, n) ∈ N × N: m ≤ n}. (c) A = Q100. (d) The set of irrational numbers. Solution: (a) Let f: N → A be defined as f(n) = log n. f is one-to-one because log x = log y implies x = y. f is onto because the image of f is exactly the set A. Therefore, f is a bijection. Therefore, A is countable. (b) A ⊆ N × N. Therefore |A| ≤ |N|. But since A is also infinite (indeed, n is unbounded in the set), then |A| = N. Therefore, A is countable. (c) Q100 = Q × Q × · · · × Q is a cross product of countable sets. Since the finite cross product of countable sets is countable. The set is countable. (d) Let A be the set of irrationals. Since every real number is either rational or irrational, then A ������ℚ = ℝ. Suppose for the sake of contradiction that A is countable. Then since ℚ is countable, A ������ℚ is also countable. Therefore, ℝ is countable. This contradicts the fact that the set of real numbers is uncountable. Therefore, A is uncountable. 2.4 PROOFS OF SOME GENERAL IDENTITIES ON SETS Theorem 3 A set A is countably infinite if and only if its elementscan be arranged in an infinite list a1, a2, a3, a4...As an example of how this theorem might be used, let P denote the setof all prime numbers. Since we can list its elements as 2,3,5,7,11, 13 ...... it follows that the set P is countably infinite. As another consequence of Theorem, note that we can interpret thefact that the setℝis not countably infinite as meaning that it is impossibleto write out all the elements of ℝ in an infinite list. This raises a question. Is it also impossible to write out all the elementsof ℚ in an infinite list? In other words, is the set ℚ of rational numberscountably infinite or uncountable? If you start plotting the rational numbers on the number line, they seem to mostly fill up ℝ. Sure, some numbers such as p2, π and e will not be plotted, but the dots representing rationalnumbers seem to predominate. We might thus expect ℚ to be uncountable. However, it is a surprising fact that ℚ is countable. The proof presentedbelow arranges all the rational numbers in an infinitely long list. Theorem 4 The set ℚ of rational numbers is countably infinite. Proof. To prove this, we just need to show how to write the set ℚ in list form. Begin by arranging all rational numbers in an infinite array. This is done by making the following chart. The top row has a 41 CU IDOL SELF LEARNING MATERIAL (SLM)

list of all integers, beginning with 0, then alternating signs as they increase. Each column headed by an integer k contains all the fractions (in reduced form) with numeratork. For example, the column headed by 2 contains the fractions2 , 2 , 2 , 2 … and so on. It does not contain 2 , 2 , 2 etc., because those 1357 24 6 arenot reduced, and in fact their reduced forms appear in the column headedby 1. You should examine this table and convince yourself that it containsall rational numbers in Q. Table 2.2: All rational numbers in Q Next, draw an infinite path in this array, beginning at 0and snakingback 1 indicated rational and forth as path below. Every number is on this 42 CU IDOL SELF LEARNING MATERIAL (SLM)

Table 2.3: Path drawn Beginning at 0 1 and following the path, we get an infinite list of all rational numbers: By Theorem 3, it follows that ℚ is countably infinite, that is, |ℚ| = |ℕ|. ■ It is also true that the Cartesian product of two countably infinite sets is itself countably infinite, as our next theorem states. Theorem 5 If A andB are both countably infinite, then so is A × B. Proof.Suppose A andB are both countably infinite. By Theorem 13.3, we know we can write A and B in list form as A = {a1, a2, a3, a4...}, B = {b1, b2, b3, b4...}. 43 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 2.4 shows how to form an infinite path winding through all of A×B. Therefore A × B can be written in list form, so it is countably infinite. Fig 2.4.A product of two countably infinite sets is countably infinite As an example of a consequence of this theorem, notice that since ℚ iscountably infinite, the set ℚ×ℚ is also countably infinite. We have the following corollary of Theorem 5. Corollary1 Given n countably infinite sets A1, A2, A3..., An, within ≥ 2, the Cartesian product A1× A2× A3×···× Anis also countably infinite. Proof.The proof is by induction on n. For the basis step, notice that whenn = 2 the statement asserts that for countably infinite sets A1 and A2, the productA1× A2 is countably infinite, and this is true by Theorem 5. Assume that for k ≥ 2, any product A1× A2× A3×··· ×Akof countablyinfinite sets is countably infinite. 44 CU IDOL SELF LEARNING MATERIAL (SLM)

Consider a product A1×A2×A3×···×Ak+1of k +1 countably infinite sets. It is easily confirmed that the function f : A1× A2× A3×···× Ak × Ak+1−→ (A1× A2× A3×···× Ak)× Ak+1 f (x1,x2,...,xk,xk+1) = ¡(x1,x2,...,xk), xk+1¢is bijective, so |A1 × A2 × A3 ×···× Ak × Ak+1| = |(A1 × A2 × A3 ×···× Ak)× Ak+1|. By the induction hypothesis, (A1× A2× A3×···× Ak)× Ak+1 is a product oftwo countably infinite sets, so it is countably infinite by Theorem 5. Asnoted above, A1× A2× A3×···× Ak × Ak+1 has the same cardinality, so it toois countably infinite. Theorem 6: If A andB are both countably infinite, then A ������ B iscountably infinite. Proof.Suppose A andB are both countably infinite. By Theorem 3, weknow we can write A and B in list form as A = {a1,a2, a3, a4...}, B = {b1, b2, b3, b4...}. We can “shuffle” A and B into one infinite list for A ������B as follows. A ������B = {a1, b1, a2, b2, a3, b3, a4, b4...}. (We agree not to list an element twice if it belongs to both A and B.) Therefore, by Theorem 3, it follows that A ������B is countably infinite. 2.5 SUMMARY An efficient way of counting is necessary to handle large masses of statistical data (e.g., the level of inventory at the end of a given month, or the number of productions runs on a given machine in a 24- hour period, etc.), and for an understanding of probability. The total number of possible outcomes of a scenario where multiple decisions are made in no particular order is found by multiplying the total number of options for each decision. • Note: It is usually wise to draw a blank for each decision category and put a multiplication sign between each. Then, fill each blank in with the number of options for that decision and multiply them. Rule of Sum: - The rule of sum is a basic counting approach in combinatorics. A basic statement of the rule is that if there are n choices for one action and m choices for another action, and the two actions cannot be done at the same time, then there are n+m ways to choose one of these actions. Rule of Product:The rule of product states that if there are n ways of doing something, and mm ways of doing another thing after that, then there are n×m ways to perform both of these 45 CU IDOL SELF LEARNING MATERIAL (SLM)

actions. In other words, when choosing an option for n and an option for m, there are n×m different ways to do both actions. The cardinality provides a window to all possible subsets that exist within a given set. Which quite literally translates to everyday decision allocation problems such as budgeting a grocery trip or balancing a portfolio. CARDINALITY The number of elements in a set is the cardinality of that set. The cardinality of the set A is often notated as |A| or n(A) Cardinal Number of a set: The number of distinct elements or members in a finite set is known as the cardinal number of a set. Finite sets: A set is called finite if it is empty or has the same cardinality as the set {1, 2, . . ., n} for some n ∈ N; it is called infinite otherwise. Countable sets: A set A is called countable (or countably infinite) if it has the same cardinality as N, i.e., if there exists a bijection between A and N. Uncountable sets: A set is called uncountable if it is infinite and not countable 2.6 KEY WORDS/ABBREVIATIONS • Injective Function - A function that always maps the distinct element of its domain to the distinct element of its codomain. • Surjective Function - A function that maps one or more elements of A to the same element of B. • Bijective Function - A function that is both injective and surjective • Same Cardinality: Two sets A and B have the same cardinality, written |A| = |B|, if there exists a bijective function f:A → B • CARDINALITY: TheNumber of Elements in A Set Is the Cardinality of That Set. 2.7 LEARNING ACTIVITIES 1. Neela has twelve different skirts, ten different tops, eight different pairs of shoes, three different necklaces and five different bracelets. In how many ways can Neela dress up? State the principle applied to solve the problem and state its answers. 46 CU IDOL SELF LEARNING MATERIAL (SLM)

2. There are 35 students in art class and 57 students in dance class. Find the number of students who are either in art class or in dance class. • When two classes meet at different hours and 12 students are enrolled in both activities. • When two classes meet at the same hour. 2.8 UNIT END QUESTIONS A. Descriptive Type Questions 1. Show that the two given sets have equal cardinality by describing a bijection from one to the other. Describe your bijection with a formula i. R and (0, ∞) ii. R and (0,1) 2. Prove that the set A = ln(n): n ∈Nª ⊆R is countably infinite. 3. Prove that the set A = (m,n) ∈N×N: m ≤ nª is countably infinite. 4. Show that the function f(x) = 3x – 5 is a bijective function from R to R. 5. A survey asks: Which online services have you used in the last month: • Twitter • Facebook • Have used both The results show 40% of those surveyed have used Twitter, 70% have used Facebook, and 20% have used both. How many people have used neither Twitter or Facebook? B. Multiple Choice Questions: 1. How many five-digit numbers can be made from the digits 1 to 7 if repetition is allowed? a) 16807 b) 54629 c) 23467 d) 32354 47 CU IDOL SELF LEARNING MATERIAL (SLM)

2. How many even 4-digit whole numbers are there? a) 1358 b) 7250 c) 4500 d) 3600 3. Let set A = {1, 2} and C be {3, 4} then A X B (Cartesian product of set A and B) is? a) {1, 2, 3, 4} b) {(1, 3), (2, 4)} c) {(1, 3), (2, 4), (1, 4), (2, 3)} d) {(3, 1), (4, 1)} 4. If set A has 3 elements then number of elements in A X A X A are a) 9 b) 27 c) 6 d) 19 5. If set A and B have 3 and 4 elements respectively then the number of subsets of set (A X B) is? a) 1024 b) 2048 c) 512 d) 4096 6. If set A has 4 elements and B has 3 elements then set n (A X B) is? a) 12 b) 14 c) 24 d) 7 7. If set A has 3 elements then number of elements in A X A X A are a) 9 b) 27 c) 6 d) 19 48 CU IDOL SELF LEARNING MATERIAL (SLM)

8. Which of the following statements regarding sets is false? a) A X B = B X A b) A X B ≠ B X A c) n (A X B) = n(A) * n(B) d) All of the mentioned 9. If n (A X B) = n (B X A) = 36 then which of the following may hold true? a) n(A)=2, n(B)=18 b) n(A)=9, n(B)=4 c) n(A)=6, n(b)=6 d) None of the mentioned 10. Let the sets be A, B, C, D then (A ∩ B) X (C ∩ D) is equivalent to a) (A X C) ∩ (B X D) b) (A X D) U (B X C) c) (A X C) U (B X D) d) None of the mentioned Answers: 1- a; 2- c; 3- c; 4- b; 5 – d; 6 – a; 7 – b; 8 – a; 9 -c; 10 - a; 2.9 REFERENCES • Kenneth Rosen, Discrete Mathematics and Its Applications with Combinatorics and Graph Theory (SIE) | 7th Edition, McGraw Hill Education; 7 editions • Jean-Paul Tremblay, R Manohar, DISCRETE MATHEMATICAL STRUCTURES WITH APPLICATIONS TO COMPUTER SCIENCE, McGraw Hill Education; 1st edition • Seymour Lipschutz, Marc LaraLipson, Varsha H. Patil, Discrete Mathematics (Schaum's Outlines) | Revised 3rd Edition, McGraw Hill Education; Revised Third edition • C Liu, D. Mohapatra, Elements of Discrete Mathematics: A Computer Oriented Approach | 4th Edition, McGraw Hill Education • Jiri Matousek , Jaroslav Nesetril, Invitation to Discrete Mathematics,OUP Oxford • Harry Lewis, Rachel Zax, Essential Discrete Mathematics for Computer Science, Princeton University Press • Oscar Levin, University of Northern Colorado, Discrete Mathematics: An Open Introduction - 3rd Edition, Oscar Levin 49 CU IDOL SELF LEARNING MATERIAL (SLM)