Question 1
a) Given sets A, B, and C, express each of the following sets in terms of A, B, and C, using the symbols [, \, and .
(i) D = fx j x 2 A ^ (x 2 B _ x 2 C)g
(ii) E = fx j (x 2 A ^ x 2 B) _ x 2 Cg
(iii) F = fx j x 2 A ^ (x 2 B ! x 2 C)g
b) Prove or disprove the following
(i) (A B) C=A (B C)
(ii) (A\B)\C =A\(B\C)
(iii) (A B) C=A (B C)
Note that A B denotes the symmetric di erence which is de ned as the set containing those elements either in A or B but not in both A and B.
To prove A = B, show that A B and B A, to disprove give a counterexample and/or explanation. You can use the laws given in the Table 1 (page 130) of the textbook with reference. You should give proofs for other set identities (if any) that you use.
Question 2
Let f : A ! B be a function, A0 A, B0 B and f 1 denote the preimage of B0 under f de ned by
◦ 1(B0) = fa j f(a) 2 B0g
a) Show that A0 f 1(f(A0)) and that equality holds if f is injective.
b) Show that f(f 1(B0)) B0 and that equality holds if f is surjective.
1
Question 3
Let A be a nonempty set. Show that the following are equivalent
(i) A is countable
(ii) There is a surjective function f : Z+ ! A
(iii) There is an injective function f : A ! Z+
Note: It is su cient to show that (i) ! (ii), (ii) ! (iii), and (iii) ! (i).
Question 4
A binary string is a sequence of 0s and 1s. A binary string is called nite if it is a nite sequence, and in nite if it is an in nite sequence of 0s and 1s.
a) Show that the set of nite binary strings is countable.
b) Show that the set of in nite binary strings is uncountable.
Question 5
a) Determine whether log n! is (n log n).
b) Which function grows faster, n! or 2n? Justify your answer algebraically.
Regulations
1. You have to write your answers to the provided sections of the template answer le given.
2. Late Submission: Not allowed.
3. Cheating: We have zero tolerance policy for cheating. People involved in cheating will be punished according to the university regulations.
4. Updates & Announces: Possible updates will be announced via Odtuclass (odtuclass.metu.edu.tr).
5. Evaluation:Your latex le will be converted to pdf and evaluated by course assistants. The .tex le will be checked for plagiarism automatically using \black-box" technique and manually by assistants, so make sure to obey the speci cations.
Submission
Submission will be done via Odtuclass. Download the given template answer le the2.tex. When you nish your exam upload the .tex le with the same name to Odtuclass.
Note: You cannot submit any other les. Make sure that your .tex le successfully compiles in Inek machines using the command below.
$ pdflatex the2.tex
2
