For a partial function $p:X\to Y$, we have

  • $p^{-1}(A\cap B)=p^{-1}(A)\cap p^{-1}(B)$
  • $p^{-1}(A\cup B)=p^{-1}(A)\cup p^{-1}(B)$
  • $p^{-1}(A \setminus B)=p^{-1}(A) \setminus p^{-1}(B)$
  • $p^{-1}(A \operatorname{\Delta} B)=p^{-1}(A) \operatorname{\Delta} p^{-1}(B)$ where $A \operatorname{\Delta} B := (A \setminus B) \cup (B \setminus A)$

But $p^{-1}(Y)=X$ is only true if $p$ is a total function. Especially $p^{-1}(A^c)=p^{-1}(A)^c$ is only true (even for specific $A$) if $p$ is total, since otherwise $$p^{-1}(Y)=p^{-1}(A\cup A^c)=p^{-1}(A)\cup p^{-1}(A^c) \quad = \quad p^{-1}(A)\cup p^{-1}(A)^c=X$$

We also have

  • $A \subseteq B \Rightarrow p^{-1}(A) \subseteq p^{-1}(B)$
  • $A' \subseteq B' \Rightarrow p(A') \subseteq p(B')$
  • $p(p^{-1}(B)) \subseteq B$

But $A' \subseteq p^{-1}(p(A'))$ is only true (for $A'=X$) if $p$ is a total function.

And then it gets hard to find any further properties absent for partial functions

  • $p(A'\cap B') \subseteq p(A')\cap p(B')$ and $p(A'\cap B')=p(A')\cap p(B')$ for injective $p$
  • $p(A'\cup B')=p(A')\cup p(B')$
  • $p(A' \setminus B') \supseteq p(A') \setminus p(B')$ and $p(A' \setminus B')=p(A') \setminus p(B')$ for injective $p$
  • $p(A' \operatorname{\Delta} B') \supseteq p(A') \operatorname{\Delta} p(B')$ and $p(A' \operatorname{\Delta} B')=p(A') \operatorname{\Delta} p(B')$ for injective $p$
  • $p(A'^c) \subseteq p(A')^c$ for injective $p$
  • $p(A'^c) \supseteq p(A')^c$ for surjective $p$

In a certain sense, the above considerations only identified two properties ($p^{-1}(A^c)=p^{-1}(A)^c$ and $A' \subseteq p^{-1}(p(A'))$) of total functions absent for partial functions, since $p^{-1}(Y)=X$ is just a restatement of the property for being total. Another absent property is suggested at the and of this answer, which is related to operators $\operatorname{op}:\mathcal{P}(Y)\to\mathcal{P}(Y)$ satisfying $A \subseteq B \Rightarrow \operatorname{op}(A) \subseteq \operatorname{op}(B)$. My question is which other properties of this type (i.e. properties which don't explicitly mention elements) are absent for partial functions.

This answer works out the absent property suggested at the the and of this answer.

Let $f: X \to Y$ be a total function. Let $\operatorname{op}_x:\mathcal{P}(X) \to \mathcal{P}(X)$ and $\operatorname{op}_y:\mathcal{P}(Y) \to \mathcal{P}(Y)$ be increasing operators, i.e. satisfying $A \subseteq B \Rightarrow \operatorname{op}_x(A) \subseteq \operatorname{op}_x(B)$ for all $A,B\subseteq X$ and the analogous condition for $\operatorname{op}_y$. Then the following two conditions are equivalent:

  1. $f(\operatorname{op}_x(A)) \subseteq \operatorname{op}_y(f(A))$ for all $A \subseteq X$
  2. $\operatorname{op}_x(f^{-1}(B)) \subseteq f^{-1}(\operatorname{op}_y(B))$ for all $B \subseteq Y$

The proof uses $A \subseteq f^{-1}(f(A))$ and $f(f^{-1}(B)) \subseteq B$ for both directions.
1. -> 2.: $\operatorname{op}_x(f^{-1}(B)) \subseteq f^{-1}(f(\operatorname{op}_x(f^{-1}(B)))) \subseteq f^{-1}(\operatorname{op}_y(f(f^{-1}(B)))) \subseteq f^{-1}(\operatorname{op}_y(B))$
2. -> 1.: $f(\operatorname{op}_x(A)) \subseteq f(\operatorname{op}_x(f^{-1}(f(A)))) \subseteq f(f^{-1}(\operatorname{op}_y(f(A)))) \subseteq \operatorname{op}_y(f(A))$

For a partial function $p:X\to Y$, we only have $A\cap p^{-1}(Y) \subseteq p^{-1}(p(A))$ and $p(p^{-1}(B)) \subseteq B$. Hence the same proof only yields something weaker for partial functions.
1. -> 2.: $\operatorname{op}_x(p^{-1}(B))\cap p^{-1}(Y) \subseteq p^{-1}(p(\operatorname{op}_x(p^{-1}(B)))) \subseteq p^{-1}(\operatorname{op}_y(p(p^{-1}(B)))) \subseteq p^{-1}(\operatorname{op}_y(B))$
2. -> 1.: $p(\operatorname{op}_x(A\cap p^{-1}(Y))) \subseteq p(\operatorname{op}_x(p^{-1}(p(A)))) \subseteq p(p^{-1}(\operatorname{op}_y(p(A)))) \subseteq \operatorname{op}_y(p(A))$
So we only have that the following two conditions are equivalent:

  1. $p(\operatorname{op}_x(A\cap p^{-1}(Y))) \subseteq \operatorname{op}_y(p(A))$ for all $A \subseteq X$
  2. $\operatorname{op}_x(p^{-1}(B))\cap p^{-1}(Y) \subseteq p^{-1}(\operatorname{op}_y(B))$ for all $B \subseteq Y$

Finally, we need two counter examples to show that the unmodified conditions don't imply each other in either direction. Let $X=Y=\{1,2\}$ and let $\operatorname{op}_x=\operatorname{op}_y$ map $\{2\}$ to $\{1,2\}$ and map any other subset to itself. If $p$ is undefined at $1$ and maps $2$ to $2$ then condition 1. is satisfied and condition 2. is violated. If $p$ maps $1$ to $1$ and is undefined at $2$, then condition 2. is satisfied and condition 1. is violated.

  • A partial function is an epimorphism if and only if it is surjective, no need to be total.

But a partial function is a monomorphism (in the category of sets and partial functions) if and only if it is an injective total function. Here, a partial function $i:X\to Y$ is a monomorphism if it has the following cancelation property with respect to composition $$\forall W \forall h_1,h_2:W\to X\ [(\forall w\in W:i(h_1(w))=i(h_2(w)))\ \Rightarrow\ h_1=h_2]$$

up vote 0 down vote accepted

For a partial function $p:X\to Y$, we have $p^{-1}(A_{1}\cap\ldots\cap A_{r})=p^{-1}(A_{1})\cap\ldots\cap p^{-1}(A_{r})$ if $r\geq 1$. But for $r=0$, this is only true of $p$ is total. Hence $$\begin{array}{c}A_{1}\cap\ldots\cap A_{r}\ \subseteq\ B_{1}\cup\ldots\cup B_{s} \\ \Downarrow\\ p^{-1}(A_{1})\cap\ldots\cap p^{-1}(A_{r})\ \subseteq\ p^{-1}(B_{1})\cup\ldots\cup p^{-1}(B_{s})\end{array}$$ can fail if $p$ is not total and $r=0$.

I missed this initially, especially in the post which triggered the question.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.