Showing a bijection between a set of functions and a set of relations

[Aaron7]

Homework Statement

With X and Y being sets, I need to show that there is a bijection between the set of functions (X->P(Y)) and the set of relations P(X x Y) where P(..) is the power set symbol.

Homework Equations

P(Y) = {Z | Z subset of Y}

The Attempt at a Solution

I know a bijection is injective and surjective. The set of functions is {f ε P(X x P(Y)) | f is a function}. I also know that a function is bijective if it has an inverse. I am not too sure where to start or whether I am missing something. I have been trying to find a function and then show it has an inverse but I am stuck.

Thanks for the help.

 

[mighty2000]

Thank you for your inquiry. I will provide a step-by-step solution to help you understand the concept and approach to proving this bijection.

First, let's define the sets involved. We have X, which is a set, and Y, which is also a set. We also have the power set of Y, denoted as P(Y), which is the set of all subsets of Y. Similarly, we have the power set of X x Y, denoted as P(X x Y), which is the set of all subsets of X x Y.

To prove that there is a bijection between the set of functions (X->P(Y)) and the set of relations P(X x Y), we need to show that there exists a function that maps each element in one set to a unique element in the other set, and vice versa.

Let's start with the set of functions (X->P(Y)). A function, f, in this set can be represented as f:X->P(Y), where f(x) is a subset of Y for every x in X. In other words, for each element x in X, there exists a unique subset of Y, denoted as f(x), that is the output of the function.

Now, let's consider the set of relations P(X x Y). A relation, R, in this set can be represented as R subset of X x Y, where R is a subset of the Cartesian product of X and Y. In other words, R is a set of ordered pairs (x,y) where x is an element of X and y is an element of Y.

To show that there is a bijection between these two sets, we need to find a function that maps each element in one set to a unique element in the other set, and vice versa. Let's define a function, g, that maps each function in (X->P(Y)) to a relation in P(X x Y) as follows:

g:(X->P(Y))->P(X x Y)
g(f) = {(x,y) | x in X, y in f(x)}

In other words, for a given function f in (X->P(Y)), g(f) is a relation in P(X x Y) that consists of all possible ordered pairs (x,y) where x is an element of X and y is an element of f(x). It is easy to see that g(f) is a subset of