What other statements of this general form can we prove about the direct image function?

53 Views Asked by At

Given a relation $R : X \rightarrow Y,$ write $R_* : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ for the direct image function defined by asserting that $$b \in R_*(A) \Leftrightarrow \exists a \in A : (a,b) \in R$$ holds for all $b \in Y$ and all $A \in \mathcal{P}(X)$.

Its clear that $R_*$ is order-preserving, and more generally that $R_*$ interacts nicely with arbitrary unions. A consequence is that $R_*(\emptyset_X) = \emptyset_Y$. Its also clear that $R \neq R'$ implies $R_* \neq R'_*$ whenever $R,R'$ are relations $X \rightarrow Y$.

Furthermore, every function $f : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ that interacts nicely with arbitrary unions is equal to $R_*$ for some relation $R : X \rightarrow Y$, and by the previous observation, this $R$ is unique. Indeed, we can define the unique such $R$ explicitly by writing $$(a,b) \in R \Leftrightarrow b \in f(\{a\})$$

and this gives us our proof.

In summary, we have a result of the form: a function $f : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ has [Property 1] (namely, the property of interacting nicely with arbitrary unions) iff there exists a [kind of entity] (namely, a relation) $R : X \rightarrow Y$ such that $R_* = f$.

What other results of this general form can we prove?


Proof. Let $f : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ interact nicely with arbitrary unions, and suppose $R : X \rightarrow Y$ satisfies $$(a,b) \in R \Leftrightarrow b \in f(\{a\}).$$ Then following are equivalent.

$b \in R_*(A)$

$\exists a \in A : (a,b) \in R$

$\exists a \in A : b \in f(\{a\})$

$b \in \bigcup_{a \in A}f(\{a\})$

$b \in f\left(\bigcup_{a \in A}\{a\}\right)$

$b \in f(A)$

1

There are 1 best solutions below

2
On

I think the following fact would be an example of what you are looking for. A function $f: \mathcal{P}(Y) \to \mathcal{P}(X)$ respects complementation and arbitrary unions (and therefore all other infinitary Boolean operations as well) if and only if there is a function $g: X \to Y$ such that for every subset $B \subset Y$ we have $$f(B) = \{x \in X : g(x) \in B\}.$$ (Hint to prove the forward direction: first show that the images of singletons under such a function $f$ form a partition of $X$.)