5
$\begingroup$

I am looking for the name of the class of functions $f:\mathcal P(A)→\mathcal P(A)$ that are monotone and that are characterised by their image on finite subsets, i.e. the functions $f$ satisfying the following property:

$$ f(S) = \bigcup_{X\in \mathcal P_{fin}(S)} f(X)$$

where $\mathcal P_{fin}(S)$ is the set of finite subsets of $S$.

  1. Does it corresponds to Scott continuity with the subset order?

    ($D=\mathcal P_{fin}(S)$ is indeed directed and $\sup D = S$, but not all directed $D$ are of the form $\mathcal P_{fin}(S)$, so I have not been able to conclude.)

  2. Regardless of 1., is there a name/reference for this class?

    It might have some interest to be restricted to the subset order, as this class seems to be closed under usual operations on sets (intersection, composition and arbitrary union).

I am interested by the fact that if $f$ in in the class then $f^\omega$ is idempotent. I am also interested in relations ($A = B\times B$), for which the class is also closed under pointwise relational composition (it seems, in fact, to be closed under a lot of operations).

$\endgroup$
  • 1
    $\begingroup$ What is $f^\omega$? $ \bigcup_{n\in \omega} f^n$ ? $\endgroup$ – MphLee Dec 28 '14 at 14:52
  • 2
    $\begingroup$ @MphLee: yes, sorry. It is idempotent iff $f∘f^\omega ⊆ f^\omega$ (which is implied by my condition above. This becomes clearer if you write it as $f^\omega = \bigcup_{n∈ℕ} f^{n\downarrow}$ with $f^{n\downarrow} = \bigcup_{i\leq n} f^i$.) $\endgroup$ – jmad Dec 28 '14 at 15:56
2
$\begingroup$

Regarding 1.

These are precisely the Scott-continuous functions. If a function is Scott-continuous then it obviously satisfies the condition since the set of finite subsets of a given set is directed.

To see the converse let $D$ be a directed set of sets. Then $$ f\left(\bigcup_{d\in D} d\right) = \bigcup_{x \subseteq^{fin}\bigcup_{d\in D}}f(x).$$

Now finite sets are compact elements of the powerset lattice. So because $x \subseteq^{fin}\bigcup_{d\in D}$ then there is a $x_d \in D$ such that $x \subseteq x_d$. Because $f$ is order-preserving this gives $$ f\left(\bigcup_{d\in D} d\right) \subseteq \bigcup_{x_d \in D}f(x_d).$$

On the other hand, because $f$ is order-preserving, we have for every $x_d \in D$ $$f(x_d) \subseteq f\left(\bigcup_{d\in D} d\right)$$ and so $$ \bigcup_{x_d \in D}f(x_d) \subseteq f\left(\bigcup_{d\in D} d\right).$$

So $f$ preserves directed suprema, so is Scott-continuous.

A direct generalization of this situation are algebraic lattices. These are complete lattices such that every element is a directed supremum of compact elements below it. Then to check continuity it suffices to check the condition analogous to the one you stated.

Regarding 2.

Perhaps somebody knows a better reference, but Dana Scott in (1) calls these just continuous set mappings (page 229). He also has several other equivalent characterizations and some properties.

  1. Dana S. Scott: "Lambda Calculus: Some Models, Some Philosophy", Studies in Logic and the Foundations of Mathematics, Volume 101, 1980, Pages 223-265, The Kleene Symposium
$\endgroup$
  • $\begingroup$ Got it, thank you! And $x_d$ can be an upper bound of the finite set $x$ by definition of directed set (not sure why you talked about compact elements). I'll accept the answer in a while if nobody answers 2. $\endgroup$ – jmad Dec 28 '14 at 15:46
  • $\begingroup$ @jmad I now added a reference where functions satisfying precisely your conditions are studied (among other things). But they are just called continuous set mappings there. $\endgroup$ – Aleš Bizjak Dec 28 '14 at 17:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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