0
$\begingroup$

I was put into a position recently where I could describe a set verbally, but not using set notation. The question posed was:

Describe a bijection from $\mathcal{P}(X \times Y) \rightarrow (X \rightarrow \mathcal{P}(Y))$, where $(A \rightarrow B)$ denotes the set of all functions from $A$ to $B$.

I can explain it in English - given all pairs $(x,y)$ in the set passed to the bijection to a pair, transform them to pairs with distinct $x$ values and the set containing all $y$ values which have that $x$ as the first element in the pair in which they appear. Eg:

Call the bijection $\beta$, then $\beta(\{(0,0), (0,1), (1,0)\})=\{(0,\{0,1\}), (1,\{0\})\}$.

I believe this to be a correct bijection, but I can't formulate it in set notation. My attempts looked like the following:

$\beta(X)=\{(a,B) \mid \forall (x,y) \in X, a=x \wedge y \in B\}$

But this feels too "weak"? It doesn't really state what should go where. My background is in computing so it's difficult to stray away from my imperative roots! It doesn't help that in the official answer to the question, the notation used was a weird mashup of lambda notation and set notation.

I would appreciate any advice or hints.

$\endgroup$
2
  • $\begingroup$ You can use the notation $B^A$, which means the set of all functions $f: A \to B$ $\endgroup$
    – AsafHaas
    Apr 18, 2017 at 9:51
  • $\begingroup$ I hadn't seen that notation before, thank you - this is the notation shown to us in lectures so for now I'll stick to using it for the purposes of passing exams! $\endgroup$
    – hnefatl
    Apr 18, 2017 at 9:55

2 Answers 2

0
$\begingroup$

The idea is correct, but you can simplify it, conceptually and notationally, by thinking of the elements of $X\to\mathcal P(Y)$ as actual functions, rather than sets of ordered pairs. Then you can define the obvious function from left to right as $$R\mapsto \lambda x.\{y:xRy\},$$ and the obvious function in the other direction as $$f\mapsto \{\langle x,y\rangle:y\in f(x)\}.$$

If, for some reason, you need to use set builder notation, then your $\beta(R)$ is almost right, but you'll want to use the existential quantifier, not the universal; otherwise, if $R$ contains any pairs $\langle x, y\rangle,\langle z,w\rangle$ such that $x\neq z$, $\beta(R)$ will be empty. You also don't want merely that $y\in B$, but rather the stronger condition that $B=\{y:\langle a,y\rangle \in R\}$. But it's ultimately more succinct to write $$B(R):=\left\{\langle a,\{y:\langle a,y\rangle \in R\}\rangle:a\in X\right\},$$ which is easy to check is a function $X\to \mathcal P(Y)$.

$\endgroup$
2
  • $\begingroup$ Thank you, the set builder notation you described is exactly what I was looking for - I'm not familiar with the $\lambda$ notation, but I can see what the intent is and that is a nicer way of expressing it. $\endgroup$
    – hnefatl
    Apr 18, 2017 at 11:36
  • $\begingroup$ It's kind of an old-school notation, but $\lambda x.\xi$ is really just a synonym of $x\mapsto \xi$. $\endgroup$ Apr 18, 2017 at 11:39
0
$\begingroup$

In this answer I use the notation $B^A$ for the set of functions $A\to B$.


Prescribe $\beta:\wp(X\times Y)\to\wp(Y)^X$ by: $$B\mapsto\beta_B$$where function $\beta_B:X\to\wp(Y)$ on its turn is prescribed by:$$x\mapsto\{y\mid\langle x,y\rangle\in B\}$$

Prescribe $\alpha:\wp(Y)^X\to\wp(X\times Y)$ by: $$g\mapsto\{\langle x,y\rangle\mid y\in g(x)\}$$

Then: $$(\alpha\circ\beta)(B)=\alpha(\beta(B))=\alpha(\beta_B)=\{\langle x,y\rangle\mid y\in\beta_B(x)\}=\{\langle x,y\rangle\mid \langle x,y\rangle\in B\}=B$$

and:$$(\beta\circ\alpha)(g)=\beta(\alpha(g))=\beta(\{\langle x,y\rangle\mid y\in g(x)\})=\beta_{\{\langle x,y\rangle\mid y\in g(x)\}}=g$$

Proved is now that $\alpha$ and $\beta$ are inverses of eachother hence are bijections.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .