Question

1. What is ∅^(∅^(∅^∅))?           ∅ is empty set and ^ means raised to

2. ∀X∀Y∀f ∈ Y X((f is an injection ∧ X ̸= ∅) =⇒ ∃g ∈ X^Y∀x ∈X (g(f(x)) = x)) (Hint: try to construct one such g)

3. ∃f ∈N^N(f(0) = 1∧∀n ∈N(n > 0 ⇒ f(n) =∑︀_{i=0to n-1} f(i)^2)) (Hint: Using the definition of summation symbol, we see that f(n) = f(n−1)+f(n−1)2, hence we can define f as f = {(n,y) ∈N×N : (n = 0∧y = 1)∨(n > 0∧∃y′ ∈ N((n−1,y′) ∈ f∧y = y′+y′2))}, and show that this is a function by induction.)

Answer 1

Nap)