CS 3800
Instructions: This homework is to be submitted on GradeScope as a single pdf (not in parts) by 11:59 pm on the due date. You may either type your solutions in a word processor and print to a pdf, or write them by hand and submit a scanned copy. Do write and submit your answers as if they were a professional report. There will be point deductions if the submission isn’t neat (is disordered, difficult to read, scanned upside down, etc....).
Begin by reviewing your class notes, the slides, and the textbook. Then do the exercises below.
Show your work. An unjustified answer may receive little or no credit.
Read: 1.1 through Example 1.21 (for Friday)
1. [6 Points] Let L(x,y) mean “x loves y”and consider the symbolic forms ∃x∃y L(x,y), ∃x∀y L(x,y), ∀x∃y L(x,y), ∀x∀y L(x,y), ∃y ∀x L(x,y), ∀y ∃x L(x,y). Next to each of the following English statements, write the one symbolic form that expresses it.
(a) everybody loves somebody
(b) everybody is loved by somebody
(c) everybody loves everybody
(d) somebody loves everybody
(e) somebody is loved by everybody
(f) somebody loves somebody
2. [6 Points] Let S = {3, 5, 8, 9, 12, 16, 17, 21}. Use the listing method to describe the follow- ing sets. Make sure to use correct notation, including braces and commas.
(a) {x ∈ S | x is odd}
(b) {x ∈ S | x + 4 ∈ S}
(c) {x + 3 | x ∈ S}
3. [5 Points] For each of the following set operations, specify the result by listing its elements inside curly braces. Be sure to use proper notation.
(a) {1, 2, 3} ∪ {2, 4}
(b) {1, 2, 3} ∩ {2, 4}
(c) {1, 2, 3} × {2, 4}
(d) {1, 2, 3} − {2, 4}
(e) {1, 2, 3} − {1, 2}
4. [6 Points] For each positive integer i define set Si to be the interval
Determine each of the following sets (giving as simple a description as possible).
5. [5 Points] Use the listing method to write the set
Make sure to use proper notation.
6. [6 Points] For each of the following arrow diagrams, state whether it represents a function from X to Y and explain your answer.
7. [12 Points] Let A = {1, 2, 3, 4}, B = {a,b,c}, C = {a,b,c,d}, D = {1, 2, 3} and consider the functions
f : A → B f = {(1, a),(2, c),(3, a),(4, c)}
g : A → C g = {(1, b),(2, c),(3, a),(4, c)}
h : C → A h = {(a, 3),(b, 4),(c, 1),(d, 2)}
j : A → B j = {(1, b),(2, c),(3, a),(4, c)}
m : D → C m = {(1, b),(2, d),(3, b)}
In the questions below, you are asked to select some of these functions. For each of the functions f,g,h,j,m, carefully explain why you reject/accept that function.
(a) Which, if any, of the functions are injective?
(b) Which, if any, of the functions are surjective?
(c) Which, if any, of the functions are bijective?