Problem One: Graphs and Logic, Problem Two: Relations and Functions and Problem Three: Functions

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.