Homework Set 2 Solution

Complete each of the following problems to the best of your ability. Remember, you can’t be graded on what you don’t write down so (unless you are just making stu up) something is better than nothing. Discussing problems between each other is ne, but your nal writeup and work must be your own.







Sets




(Ch. 2 Supplementary Exercises, 1) Let A be the set of English words that contain the letter x, and let B be the set of English words that contain the letter q. Express each of these as a combination of A and B:



The set of English words that do not contain the letter x.



The set of english words that contain both an x and a q.



The set of English words that contain an x but not a q.



The set of English words that do not contain either an x or a q.



The set of English words that contain an x or a q, but not both.



(Ch. 2 Supplementary Exercises, 2) Show that if A is a subset of B, then the power set of A is a subset of the power set of B.



(Ch. 2 Supplementary Exercises, 4) Let E denote the set of even integers, let O denote the set of odd integers. As usual, let Z denote the set of all integers. Determine each of these sets:



E [ O



E \ O



Z E



Z O



Show that the even and odd integers (E and O) form a partition of the integers Z.



(Ch. 2 Supplementary Exercises, 6) Let A and B be sets. Show that A B if and only if A \ B = A.



6) (Ch. 2 Supplementary Exercises, 8) Suppose that A; B; and C are sets. Prove or disprove that (A B) C=(A C) B.







Functions For these problems, let SN be the set of numbers f1; 2; 3; : : : ; Ng.




How many functions are there that map SN to SN ?



Argue that if a map f : SN 7!SN is surjective, then f is a bijection.



Argue that if a map f : SN 7!SN is injective, then f is a bijection.



How many bijections are there that map SN to SN ?



Suppose f is a map from a set S to itself, f : S 7!S.



If S is a nite set, argue that jf(S)j = jSj if and only if f is a bijection. Give an example of an in nite S and an f such that




f is not a bijection, but jf(S)j = jSj.




f is a bijection, but f(S) is a proper subset of S. Cardinality




1
Computer Science Department - Rutgers University
 
1) (Ch. 2 Supplementary Exercises, 12) Let A and B be subsets of the nite universal set U. Show that
jAc \Bcj = jUj j Aj j Bj + jA \Bj:
(1)
(Ch. 2 Supplementary Exercises, 14) Suppose that f is a function from A to B where A and B are nite sets. Explain why jf(S)j jSj for all subsets S of A.



Argue that the set of irrational numbers is uncountable. Computability



Argue that the set of computer programs in any language must be at most countably in nite. What do we know about computer programs?



Argue that for a given programming language, most real numbers cannot be computed as the (potentially in nite) output of any program.



Di erent programming languages have di erent abilities. Is it possible that between ProgrammingLan-guage 1 and ProgrammingLanguage 2, they could, taken together, compute all real numbers? Why or why not.



Is it possible that the set of programming languages is uncountably in nite? Why or why not. Would it help us compute more things if it were?



Argue that there are functions from the natural numbers to the natural numbers that are uncomputable by any computer program. What do you need to show in order to prove this?















































































































2