Let $\Lambda$ be any partial combinatory algebra. For each set $X$, define a binary relation on $\mathscr{P} (\Lambda)^X$ as follows:
- Given $P, Q : X \to \mathscr{P} (\Lambda)$, $P \le_X Q$ iff there is some $e \in \Lambda$ such that, for all $x \in X$ and all $p \in P (x)$, $e p$ is defined and $e p \in Q (x)$.
By considering the $\mathsf{I}$ and $\mathsf{B}$ combinators, we see that $\le_X$ is reflexive and transitive. Thus $\mathscr{P} (\Lambda)^X$ is a preordered set. Moreover, by considering the $\mathsf{K}$ combinator, it is clear that the poset quotient of $\mathscr{P} (\Lambda)^1$ is isomorphic to $\{ 0 < 1 \}$.
Now suppose $\Lambda$ is the Kleene partial combinatory algebra, i.e. $\mathbb{N}$ with the partial binary operation $(n, m) \mapsto f_n (m)$, where $f_n : \mathbb{N} \rightharpoonup \mathbb{N}$ is the $n$-th computable partial function (with respect to some reasonable coding).
Question. What is the poset quotient of $\mathscr{P} (\Lambda)^X$?
This seems to be difficult, even for $X = 2 = \{ 0, 1 \}$. For instance, suppose $Q (x) = \{ x \}$. Then $P \le_2 Q$ if and only if $P (0) \cap P (1) = \emptyset$ and there is a partial computable function $f : P (0) \cup P (1) \to \{ 0, 1 \}$ such that $f (x) = 0$ for all $x \in P (0)$ and $f (x) = 1$ for all $x \in P (1)$. Thus $P \le_X Q$ is related to the recursive separability of $P (0)$ and $P (1)$.
I would be happy to know even just some basic facts – for instance, is the poset quotient of $\mathscr{P} (\Lambda)^X$ finite, countably infinite, or uncountable? Does it have infinite chains? What about antichains?
Update. A friend suggested focusing on those $P$ where $P (0) \cap P (1) = \emptyset$ and $P (0) \cup P (1) = \mathbb{N}$. For each $X \subseteq \mathbb{N}$, let $S_X (0) = X$ and $S_X (1) = \mathbb{N} \setminus X$. Then $S_X \le_2 S_Y$ if and only if $X$ is many-one reducible to $Y$. In particular:
The many-one reducibility preorder (on $\mathscr{P} (\mathbb{N})$) embeds into $\mathscr{P} (\Lambda)^2$.
It follows that the poset quotient of $\mathscr{P} (\Lambda)^2$ contains an antichain of continuum cardinality.