10
$\begingroup$

Suppose $X,Y$ are sets, and $f:X\to Y$ and $g: Y \to X$. Then there are disjoint subsets $X_1,X_2 \subseteq X$ with $X_1\cup X_2= X$ and disjoint subsets $Y_1,Y_2 \subseteq Y$ with $Y_1\cup Y_2= Y$ such that

  • $f(X_1) = Y_1$, and
  • $g(Y_2) = X_2$.

(This curious result is a consequence of the Knaster-Tarski fixed point theorem.)

Can this statement be generalized to partial functions, or even binary relations $R_1, R_2 \subseteq X\times Y$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Yes, I think the exact same proof goes through for binary relations $R: X \nrightarrow Y$ and $S: Y \nrightarrow X$ (which of course includes the partial function case). Each induces a monotone operation between power sets, e.g. $\exists R: PX \to PY$ takes $A \subseteq X$ to $\{y: \exists_{x \in A} R(x, y)\}$. Letting $\neg_X$ denote complementation on subsets $A \subseteq X$, we obtain a covariant (i.e. monotone) operation

$$\neg_X \circ \exists S \circ \neg_Y \circ \exists R: PX \to PX$$

which by the Knaster-Tarski theorem has a fixed point $X_1 \in PX$. Put $Y_1 = (\exists R)(X_1)$ and $Y_2 = \neg_Y Y_1$ and $X_2 = (\exists S)(Y_2)$. Then $X_2 = \neg_X X_1$ by the fixed point equation.

Improve this answer
$\endgroup$
12
  • 2
    $\begingroup$ This answer is a gem (to my mind). @Todd Trimble. Existing methods are here efficiently brought to bear to answer the question in the OP. Some of the aspects of the answer will probably not be appreciated by some readers not experienced in category theory. Since there seems to be a discipline of 'art appreciation' to try save aspects of a work of art being lost on some, there should also be something like 'mathematics appreciation', so here I try to do this for some of the unexplained aspects of this answer. Firstly, $R\colon X \nrightarrow Y$ is [...] $\endgroup$
    – Peter Heinig
    Commented Aug 14, 2017 at 20:24
  • 1
    $\begingroup$ [...] currently apparently only treats functions, not binary relations, so is not yet quite compatible with the above answer. It might improve the above answer to write $\exists_R$ instead of $\exists R$, which to some may read 'there exists $R$', while '$\exists_R$' also notationally suggests that something like 'exists-via-$R$' is meant. (Incidentally, knowing that that $\exists_f$ is firmly entrenched, if I were to choose I would write $\exists_f$ in the form $(f)\exists(-)$, making it even more look like '$f$-wise exists'.) Incidentally, [...] $\endgroup$
    – Peter Heinig
    Commented Aug 14, 2017 at 20:30
  • $\begingroup$ [...] changing to this subscript notation would spare you a parenthesis-pair in '$(\exists R)(X_1)$' later on. Another small thing, in a solution as good as the above, where form is so important, the notation $\{y\colon\exists_{x\in A} R(x,y)\}$ in the current version seems not quite good enough for the answer, in particular if the suggestion to write $\exists_R$ in analogy with $\exists_f$ is adopted. At least according to how I learned set-theory (correct me if there is something essentially wrong here), [...] $\endgroup$
    – Peter Heinig
    Commented Aug 14, 2017 at 20:32
  • $\begingroup$ [...] the notation $\{x\colon \varphi (x,y_0,\dotsc,y_{n-1})\}$, where $\varphi(x,y_0,\dotsc,y_{n-1})$ is a first-order formula over the signature of ZF set-theory, denotes a class, and may or may not denote a set, and in order to make formally sure that one defines a set, one has to use the axiom schema of separation and in particular use a set in before the colon. So in particular, currently $\{x\colon \varphi (x,y_0,\dotsc,y_{n-1})\}$ seems (to me) improvable, for the benefit of future readers, [...] $\endgroup$
    – Peter Heinig
    Commented Aug 14, 2017 at 20:33
  • 1
    $\begingroup$ Thanks for your comments, @PeterHeinig! Maybe you could put them in a separate answer for better readability and appreciation? $\endgroup$
    – Dominic van der Zypen
    Commented Aug 15, 2017 at 4:44

You must log in to answer this question.

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