1. Consider a graph G = (V, E), where V = {A, B, C, D, E}. The edge set, E, is to be decided by you, according to criteria given below. The criteria are given in first-order logic, using the following functions and predicates:
• Degree(v): a function giving the degree of vertex v.
• Even(x): a predicate that is true if and only if the number x is even.
• > : a predicate with the usual mathematical greater-than meaning.
i. (2pts) Give a value for the edge set E that minimizes |E| and satisfies this criteria:
ii. (2pts) Give a value for the edge set E that minimizes |E| and satisfies this criteria:
2. Given a function f : A → A (where A is some set), we define a relation Rf over A as
x Rf y if f(x) = y.
i. (2pts) Define a function f : ℕ → ℕ that makes Rf reflexive.
ii. (2pts) Define a function f : ℕ → ℕ that makes Rf symmetric, but neither reflexive nor transitive.
iii. Define a function f : ℕ → ℕ that makes Rf transitive, but neither reflexive nor symmetric.
3. Given a function f : A → B (where A and B are sets), we define a new function popf : ℘(A) → ℘(B) as follows:
Popf (S) = { y ∈ B | ∃x ∈ S. f(x) = y }
Notice that each input to popf is a set S, because the domain of popf is ℘(A) (so each S is some subset of A). Given some subset of A as input, popf produces as output an element of ℘(B) (so each output is some subset of B), formed by applying f to each element of S.
i. (3pts) Let A = {0, 1} and B = {2, 3}. Define a function f : A → B such that its resulting popf
function is not surjective.
f(x) = 2 if x is 0 2 if x is 1
ii. Let A and B be sets. Prove that if f : A → B has a left inverse, then popf has a left inverse.
