Homework #1 1. Prove the following: A - (B ^ C) = (A - B) v (A - C) Solution: let L = A - (B ^ C) and R = (A - B) v (A - C) To show that L = R we will show that 1) L is a subset of R and 2) R is a subset of L. 1) Let x be any element of L; then x is in A, but x is not in both B and C (which also means that either x is not in B or x is not in C). If x is in A but not in B, then x is an element of (A - B). If x is in A but not in C, then x is an element of (A - C). Because x is in A but either not in B or not in C, then x is an element of either (A - B) or (A - C), and is thus an element of R. Therefore L is a subset of R. 2) Let x be any element of R; then x is either an element of A but not an element of B, or x is an element of A but not an element of C. In either case we know that x is an element of A. We also know that x is either not an element of B or not an element of C, which means that x cannot be an element of both B and C (x is not an element of B^C). As a result, x is an element of L. Therefore R is a subset of L. Q.E.D. 2. Give functions f: N->N that satisfy a) f is one-to-one but not onto b) f is onto but not one-to-one c) f is a bijection Solution: a) f(x) = x * 2 Every distinct element of x has a different value of (x*2), thus the function is one-to-one. On the other hand, some values in the range of the function (namely the odd numbers) are not under the image under f of any element in N. Thus the function is not onto. b) f(x) = floor(x / 2) Every distinct element y of x is an image under f of some element in N (in particular, the element y*2 and y*2 + 1), thus the function is onto. However, two distinct elements of x can map to the same value under the function f. In particular, x=2 and x=3 both map to the natural number 1. Thus the function is not one-to-one. c) f(x) = x This is a simple example. Because every distinct element x will be mapped onto a distinct natural number, the function is onto. Every element of N is an image under f of some element in N (namely itself), so the function is onto. Because the function is one-to-one and onto, by definition the function is a bijection. 3. Prove that the union of two countable sets is countable. Solution: To show a bijection f:N->(AvB), where A and B are countable sets, we can use the dovetailing technique described in the textbook. In particular, we will visit the first element of set A followed by the first element of set B, then the second element of set A then set B, and so on. The union can be listed as AvB = {a0, b0, a1, b2, ...}. For each element we have to consider the case that the same element may exist in the other set (the union does not include duplicates). Thus for each element, before we visit the element we first check each element already visited (because a finite number of elements have been visited, this requires finite time). If no equivalent element has been visited, we visit the element. If a duplicate is found, we do not visit (add to the list) the element. Similarly, it is sufficient to show that AvB is a subset of a countably infinite set. We know that AvB is a subset of the set created by concatenating the two sets A and B. The only difference between the concatenation of A and B and their union is that duplicate elements are not included in the union. We can use the "dovetailing" described on page 22 of the textbook to show that the concatenation of the sets is countably infinite. Because AvB is a subset of this concatenation, AvB is countably infinite. 4. Let R1 and R2 be any two partial orders on the same set A. Show that R1 ^ R2 is a partial order. Solution: To show that R=R1^R2 is a partial order we need to show that R is reflexive, transitive, and has no nontrivial cycles. Note that (x,y) is in R if it is in R1 and in R2. Reflexive ((x,x) in R). For any element x, (x,x) is in R1 and (x,x) is in R2 (since R1 and R2 are partial orders they are reflexive), thus (x,x) is in R. Transitive (if (x,y) and (y,z) are in R, then (x,z) is in R). If (x,y) and (y,z) are in R then they are both in R1 and R2. Because R1 and R2 are partial orders they are transitive, so (x,z) is in both R1 and R2. Thus (x,z) is in R. No nontrivial cycles (prove by contradiction). Let (a1, ..., an) be a nontrivial cycle in R, n > 1. We know that each for sequence pair (ai, ai+1) to be in R, it is in both R1 and R2. If each such pair exists in both R1 and R2, then the entire chain exists in both R1 and R2. This is a contradiction, because R1 and R2 are partial orders and cannot contain nontrivial cycles. Thus R does not contain nontrivial cycles. 5. Let R be b binary relation on the set A = the set of all English words; (a,b) in R if and only if a is longer than b. Is R a partial order? Is R a total order? Justify your answer. What are the minimal element(s)? Solution: R is not a partial order because R is not reflexive (a word cannot be longer than itself). I will also construct a solution for relation R that is {(a,b}: word a is longer than or equal in length to b}. In this case, R is a partial order but not a total order (words of equal length are not elements of R). The minimal elements are words consisting of one character such as "a" and "I". 6. Consider the set of elements S = {1,2,3} and a relation R defined on these elements R = {(1,2), (2,1), (2,2), (2,3), (3,2)}. Show R2 (R2 is R.R, or R composed with itself) and the transition closure of R (R*). Solution: R2 = R.R = {(1,2), (2,1), (2,2), (2,3), (3,2)} v {(1,1), (1,3), (3,1), (3,3)} We cannot add any new relations in the transitive closure, so R* = R2. 7. Are the following sets closed under the following operations? If not, name a set of which the property is a closure property. a) The even integers under division b) The positive integers under multiplication. Solution: a) No. 18 divided by 6 is not an even integer. Real numbers are closed under division. b) Yes.