Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 3800 Spring 2024
Homework 2
(due Friday, January 26)
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?