Discrete Math Assignment 3

={0, +- 5+-10,+-15,+-20,+-25} = So A ={0, +- 5+-10,+-15,+-20,+-25} Now, the set B is explicitly expressed as follows, B = { m E Z , n =20 s for some integer s} =20{0,+-1,+-2,+-3,…} = {0,+-20,+-40,+-60,+-80,+-100,…} So B= {0,+-20,+-40,+-60,+-80,+-100,…} From A = {0,+-5,+-10,+-15,+-20,+-25…..} B = { 0 +-20,+-40,+-60,+- 80,+- 100….} This implies that set B is contained in A. That is B C A. But set A is not entirely contained in B so A not in B. A is false and B is true. A. The union of two sets, denoted by A ∪ B, is the set of all elements that are in set A, or in set B, or in both. B. The intersection of two sets, denoted by A∩B, is the set of all elements that are common to both set A and set B. C. (c) A ∪ C={1,2,3,4,5,6,7,8,9} D. (d) A∩C={}or ∅ (Empty set) E. (e) A−B={1,5,7} The set difference, denoted as A−B, represents the set of elements that are in set A but not in set B. F. (f) B−A={6} G. (g) B ∪ C={2,3,4,6,8,9}

By the definition of the set R-, the set does not contain the element 0. Thus, R – NOT ZERO By the definition of mutually disjoint, the set {R+,R-,{0}} is mutually disjoint set. So, As the real number set contains negative numbers, zero and positive numbers so the real numbers set can be written as union of sets R -,{0}, and R +. Therefore, R =R U {0} U R+ The set {R+, R -, {0}} satisfies all the conditions of the partition of the set. Hence, the set {R+, R -, {0}} is a partition of the set. Partition of the set: Let the set {A1,A2,……An} be the subsets of A . The set {A1,A2,……An} is said to be partition of A, if each the elements are mutually disjoint and A1 U A2 U ….U An= A Now we are going to check that whether the set{A1,A2,A3……An} is mutually disjoint set or not. By the definition of the sets A0 and A1, there are no common elements in both the sets A0 and A1. Thus, A0 (∩) A1 = ( ∅ ). By the definition of the sets A0 and A1, there are no common elements in both the setsA0 and A1. Thus, A0 (∩) A1 = ( ∅ ). By the definition of the sets A0 and A3, there are no common elements in both the sets A3 and A3.

The proof doesn't talk about where the items from B go, but it doesn't need to. We just need to focus on the fact that our item is definitely from one of the bags. 7) So, no matter which bag the item came from, it is definitely in C. Whether the item was from A (which we know fits in C) or B (which could also have items that fit in C), it will be in C. 8) Since this is true for any item you pick, it means all items from the combined A and B bags are in the big C bag. 9) Every single item, no matter which one we choose, will end up in C. So, the combined collection of items from A and B will all fit into C. All the items from both A and B, when put together, are still part of C. A ⊆ C means every element in set A is also in set C. A ∪ C represents the union of sets A and C, which means it includes all the elements that are in A, in C, or in both. B ∪ C is the union of sets B and C, including all elements that are in B, in C, or in both. The statement A ∪ C ⊆ B ∪ C is saying that if you take all the elements from both A and C, this combined set will not have any elements that aren't already in the combined set of B and C. Since A is already a subset of C, adding C to A doesn't bring any new elements to the table that aren't already in C. Therefore, when you add C to B to make B ∪ C, you're guaranteed to have all the elements from A ∪ C because A didn't add anything new that wasn't in C. Hence, A ∪ C is a subset of B ∪ C.

(a) set of positive divisors of 1 = {1} this set contain one element. (b) T (15) = the set of positive divisors of 15 = [1,3,5,15} this set contain four elements. (c) T (17) = the set of positive divisors of 17

A) For the function f = { (1,1) , (2,2) , (3,3) } there is no element in the domain X that maps to 4 in the codomain Y. Therefore, f is a one-to-one (injective) function but not onto (surjective). (b) In the function g = { (1,1) , (2,2) , (3,2) } both elements 2 and 3 from the domain X are mapped to the same element 2 in the codomain Y. This indicates that g is onto (surjective) since every element in Y has a preimage in X, but it is not one-to-one (injective) because two different elements in X map to the same element in Y. (c) Looking at the function h = { (1,1) , (2,2) , (3,1) } the elements 1 and 3 in the domain X both map to 1 in the codomain Y. This makes h not one-to-one (injective). Additionally, there is no element in X that maps to 3 in Y, making h also not onto (surjective). (D) The function k = { (1,2) , (2,3) , (3,1) } shows that each element in the domain X maps to a unique element in the codomain Y, making it one-to-one (injective). Moreover, every element in Y is mapped from an element in X, so k is also onto (surjective). However, since there is no element x in X for which f(x)=x, k does not qualify as an identity function. a) Suppose s1= aaabb and abaab are in s such that n(s1)=n(s2) By definition of n, N(s1)=3=n(s3) But s1 not equal to s2. Therefore, this relationship does not hold, indicating that different elements in the domain do not necessarily produce unique outputs in the codomain. Consequently, the function fails to be injective (one-to-one). b) The codomain of n is z and it includes negative integers. By definition n, cannot have negative number of a’s. Thus n(s)=-1 is not satisfied.

(a) No, because {a} ∩{b}= ∅ (b) {a,b} J {b,c} = {a,b} ∩ {b,c} ={b} ∅ So, yes, {a,b} J {b,c} (c) {a,b} J {a,b,c} = {a,b} ∩ {a,b,c} = {a,b} ∅ So, yes {a,b} J {a,b,c} Let A= {3,4,5} and B={4,5,6} be two sets. Let s be the “divides” relation. That is, for all (X,Y) e A*B , X S Y  X|Y As A = {3,4,5} and B = {4,5,6}, then A x B = {(3,4),(3,5),(3,6),(4,4),(4,5),(4,6),(5,4),(5,5),(5,6)} Observe that, S= {(3,6),(4,4),(5,5)}. Here 3 divides 6, 4 divides 4 and 5 divides 5. These 3 are true. Here is the relation x|y, so 3|6,4|4,5|5. The inverse relation R^-1={(y,x) ∈ BxA | (x,y) ∈ AxB} Also, observe that S^-1= {(6,3)(4,4)(5,5)} because, .S^-1 = {(y,x) ∈ BxA| (x,y) ∈ S, i.e.,x|y}

(A) (b). For all X in a set A, (X,X) ∈ R then is called reflexive. Here (0,0) NOT ∈ R7, (1,1) ∈ R7, (2,2) NOT ∈ R7 and (3,3) NOT ∈ R7 Hence, R7 is not reflexive. (c) For all x and y in a set A, if (X, Y) ∈ then (Y,X) ∈ then is called symmetric. In this relation R7, (0,3) ∈ R7 But (3,0) not ∈ R7. Hence, R7is not symmetric. (D) The transitive condition is vacuously true for R7. If R7 were not transitive, That is, there would have to be elements X, Y, Z in a set A such that (x,y) ∈ R7, (Y,Z) ∈ R7 and (X,Z) Not ∈ R7. So, it is clear by hypothesis no such elements exist in R7. It follows that it is impossible for R7 not to be transitive.

Thus, R7is transitive. In 9–33, determine whether the given relation is reflexive, symmetric, transitive, or none of these. Justify your answers . Reflexive: For X=1, 1 1, as 1^2 +1^2 =2 ≠1 Thus, C is not reflexive. Symmetric: Suppose x C y, then x^2+y^2 =1 As sum of real numbers obeys commutative property, so y^2+x^2=1 So, y C x. Thus, C is symmetric. Transitive: For x=1, y=0,z=1 consider 1C0 and 0C1 But 1 1. Thus, C is not transitive. Reflexivity We know that R is reflexive For all lines l in A, 1R1. By the definition of R, for a line in A.IRI=>1 is parallel to l. This is true since every line is parallel to itself.

Symmetry We know that R is symmetric <=> for all lines , in A, if , then . By the definition of R, for in A, => is parallel to , which is implied from is parallel to , which is true from the symmetric property of parallel lines. So by the definition of R, . Transitive We know that R is transitive  for all lines i1,i2,i3 in A, if and , then . By the definition for i1,i2,i3 in A and means that, is parallel to , and is parallel to i3, which implies that is parallel to i3. This is true by the transitive property of parallel lines. So, by definition, 3 Reflexivity R is not reflexive Symmetry R is symmetric R is symmetric for all in A, if . Then, by the definition of R1,I1,I2 in A means is perpendicular to , which implies that is perpendicular to . Transitive R is not transitive

Exercise Set 8.3 (p. 520+): Exercises 4, 6, 14 Let A be set and R be an equivalence class on A , then for some element a ∈ A an equivalence class is defined as, [a] = {x ∈ A| x R a}. Write the equivalence classes for each element in the set A using the above definition. [a]= {x ∈ A| x Ra } ={a} [b]= {x ∈ A| x Rb} = {b,d} [c]= {x ∈ A| x R c} = {c} [d]= {x ∈ A| x R d} = {b,d} Here, observe that, [b] = [d] = {b,d} Therefore, {a},{b,d} and {c} For integer a: [a] = {x ∈ A | x Ra} = {x ∈ A | 3| x-a} = x ∈ A| x= 3k +a, for some integer K A=1 => 3|-2,-1,3|1-1, and 3|4-1 follows {-2,1,4}

Similarly, [2] = {x ∈ A: x R2} = {x ∈ A: 3| x-2} = {x ∈ A: x-2 = 3k, for some integer k} = {x ∈ A: x =3k+2, for some int K} Following equivalence class => {-4, -1,2,5} And finally [3] = {x ∈ A: x R3} = {x ∈ A: 3| x-3} = {x ∈ A: x-3 = 3k, for some integer k} = {x ∈ A: x =3k+3, for some int K} Same process as above we get {-3,0,3} Now combining the distinct equivalences {-2,1,4}, {-4, -1,2,5},{-3,0,3} To solve this problem, we must first determine all strings of length 4 that consist of 0's, 1's, and 2's such that the sum of the characters is less than or equal to 2. Then, we can determine the equivalence classes under relation R. An equivalence relation partitions a set into disjoint subsets where each element belongs to exactly one subset. In the context of the problem, two strings are equivalent if they have the same sum of characters (as this is what we can infer from the given information, although the exact nature of R is not specified). Let's find the valid strings first and then determine the equivalence classes.

The distinct equivalence classes of R for the set A, based on the sum of the characters in the strings, are as follows: 1. Equivalence class for sum 0= {‘0000’} 2. Equivalence class for sum 1= {‘0001’,’0010’,’0100’,’1000”} 3. Equivalence class for sum 2 = {‘0002’,”00011’,’0020’,’0101’,’0110’,’0200’,1001’,’1010’,’1100’,’2000’} These classes group the strings where the sum of the digits is the same, hence they are in the same equivalence class under the relation R. Exercise Set 9.1 (p. 571+): Exercises 1, 4, 6, 8, 14 Numbers Outcomes Number of heads s.num Outcomes Number of heads 1 TT 0 16 HH 2 2 TH 1 17 TT 0 3 HT 1 18 TH 1 4 HH 2 19 HT 1 5 TT 0 20 HH 2 6 TH 1 21 TT 0 7 HT 1 22 TH 1 8 HH 2 23 HT 1 9 TT 0 24 HH 2 10 TH 1 25 TT 0 11 HT 1 26 TH 1 12 HH 2 27 HT 1 13 TT 0 28 HH 2 14 TH 1 29 TT 0 15 HT 1 30 TH 1 Relative frequency: Relative frequency of the occurrence of heads, 0, 1, and 2. Event Tally Frequency Relative frequency 2 heads obtained 7 23% 1 head obtained 15 50%

0 heads obtained 8 27% Lets BE be the event that denomination of the chosen card be black and even. Theres 26 cards back cards and there 10 out of them that are even, which are the 2,4,6,8,10 cards of clubs and spades. Then P(B/E) = 10/52 = 5/26 Lets m4 be the event that denomination of the chosen card is at most four. There are 3 cards of each suit which have denomination at most 4, thus there are 4*3 =12 cards with a denomination of at most 4. Then =12/52 = 3/13 Let   S   be the sample space containing all the outcomes when two dices are rolled. Then, N(36) Lets E be the event that sum of the numbers showing face up are the same Then, E { 11,22,33,44,55,66} > N ( e) =6 The prob that the sum of the numbers show the same number is 6/36 or 1/6

(a) The probability that exactly one of the people becomes ill can be calculated by considering all the possible combinations where one person is ill and the other two are not. The probability is 3/8. (b) The probability that exactly two people become ill is P2 = 3/8; the probability that exactly three people become ill is P3 = 1/8. Therefore, the probability that at least two people become ill is P2 + P3 = 3/8 + 1/8 = 1/2. (c) The probability that none of the three people becomes ill is the probability that all three do not become ill. Since each person has a 50% chance of not becoming ill, the calculation is 0.5×0.5×0.5=1/8.The probability is 1/8. Exercise Set 9.2 (p. 585+) Exercises 5, 15, 17 In a match where the victory condition is either securing three consecutive wins or achieving four wins overall, player X secures the initial game, while player Y is victorious in both the second and third games. Commencing with the initial match, player X emerges victorious. Subsequently, player Y claims victory in the second match. Continuing the streak, player Y also triumphs in the third match. With this succession, Y has accumulated three consecutive wins, thereby concluding the match in their favor.

The various scenarios in which the matches could unfold, given that player one clinches the initial game while player two takes the subsequent two matches, are enumerated as such: 1. XYYY 2. XYYXXX 3. XYYXXYX 4. XYYXXYY 5. XYYXYY 6. XYYXYXX 7. XYYXYXY There are a total of 7 possible ways in which the game can be played. A. USING counting principle to solve: The first position of the combination can be filled in 30 ways. The number of ways the second position of the lock can be filled in 29 ways. The last position can be filled in 29 ways. Because the number used in the first position can be used again. The total number of combinations is 30*29*29 By simplifying the above value: Multiply 30 by 29 = 870

Multiply 870 *29 = 25,230 The conclusion is there is 25,230 combinations. b) since the locks are constructed in such a way that no number can be used twice. For the first number there are 30 choices. The second number can’t be the first number so we have 29 other possibilities. For the third choice there are 28 Total different combinations possible are: 30*29*28=24,360 a. with inclusive counting: 9999-1000+1 =10000-1000 =9000 b) Its known that the even and odd number are alternate: so the number s of the odd integers are: 9000/2=4500 and the number of even integers: 9000/2 = 4500 c) to construct a 4−digit number having distinct digits we have several choices is 9 since the first digit, we cannot pick 0 so 9 ways to pick the second digit and 8 and 7 ways for other digits. so, we have the numbers that have a distinct digit 9*9*8*7=4536 d) We will construct a 4-digit odd number we have 5 choices for the last digit. we get 8 choices for the first digit (not zero or the same as the last digit), 8 and 7 choices for the second and third. So, we have 8×8×7×5=2,240 odd numbers with distinct digits. e) The prob that a randomly chosen four-digit integer has a distinct digit is: 4536 / 9000 = 63/125 and 2240/9000 = 56/225