Show that if , then .
My attempt at the question is as follows:
Since , .
Since , there exist 2 injective functions and .
The problem here is what I should do to prove that .
Thank you in advance.
Hey,
We can think of functions from Y to {0, 1} as determining subsets of Y. For instance, a function f from Y to {0, 1} determines the set {x in Y: f(x) = 1} -- it basically `says' of every member of Y whether or not it's in this set, `yes' if f(x) = 1, and `no' if f(x) = 0. Conversely, for any subset A of Y, we can define such a function for A by f(x) = 1 if x is in A, and f(x) = 0 if not. We can call such a function a characteristic function for A.
Now, any function g from X to N is a subset of X x N -- it consists solely of pairs whose first element is in X and whose second element is in N. So consider its characteristic function f(<x, n>) = 1 if <x, n> is in g, and f(<x, n>) = 0 if not. This will be a function from X x N to {0, 1}. Mapping each function from X to N to its characteristic function in this way, we get an injective mapping from the functions from X to N, to some functions from X x N to {0, 1}.
Then your result follows easily.
Hope this helps
Sam